What Do Large Networks Look Like?

Abstract

What do large networks look like? Can we visually tell the topological di erence between networks such as the Web graph and Facebook network? Due to the huge size of the network, the overall structure will not be discernible if all the nodes and edges are plotted regardless of the graph layout. We reduce the number of nodes and edges by producing a representative subgraph. The nodes are sampled with probability proportional to their degrees, so that large nodes with more connections have a higher probability of being sampled. The edges are reduced further using uniform random spanning tree. The efficacy of the method is demonstrated to preserve the community structure that is characterized by the Network Community Pro le (NCP). The result is supported by six real-world large networks, and demonstrated on Twitter user network which contains 4x10^7 nodes.

Weibo Structure

Visualization

Category: Flower-like

Twitter WikiTalk EmaiEu

Category: Dumbbell-like

Stanford BerkStan Flickr
NotreDame Huge Community NotreDame Common Community NotreDame Macro View

Category: Evenly-distributed

Gowalla Slashdot Skitter
Google Facebook Amazon