Finding community structure in very large networks.

By Aaron Clauset, Mark Newman, Cristopher Moore. Physical review. E, Statistical, nonlinear, and soft matter physics, 2004

7,384 citations recorded by the source corpus.

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 (md log n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with m approximately n and d approximately 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 on-line 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 x 10(6) edges. We show that our algorithm can extract meaningful communities from this network, revealing large-scale patterns present in the purchasing habits of customers.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/d4d88b070a222286952e4aef0a31afbed35b46d7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

  1. Santo Fortunato
  2. Jure Leskovec
  3. Binghui Wang
  4. Neil Zhenqiang Gong
  5. Mark Newman
  6. Tiago P. Peixoto
  7. Jaewon Yang
  8. Ludo Waltman

In Statistical and Nonlinear Physics

  1. Santo Fortunato
  2. Jure Leskovec
  3. Mark Newman
  4. Olaf Sporns
  5. Darko Hric
  6. M. A. Porter
  7. Jaewon Yang
  8. Tiago P. Peixoto

Citations in the corpus