Finding community structure in very large networks

Details Finding community structure in very large networks Finding community structure in very large networks

2004-08-09

arxiv.org/abs/cond-mat/0408187v2

Phys. Rev. E 70, 066111 (2004)

Physics

Condensed Matter

Statistical Mechanics

Scientific paper

10.1103/PhysRevE.70.066111

The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O(m d log n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with m ~ n and d ~ log n, in which case our algorithm runs in essentially linear time, O(n log^2 n). As an example of the application of this algorithm we use it to analyze a network of items for sale on the web-site of a large online retailer, items in the network being linked if they are frequently purchased by the same buyer. The network has more than 400,000 vertices and 2 million edges. We show that our algorithm can extract meaningful communities from this network, revealing large-scale patterns present in the purchasing habits of customers.

Affiliated with

Also associated with

No associations

Rating

Finding community structure in very large networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding community structure in very large networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding community structure in very large networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-689136