# Finding community structure in very large networks

**Aaron Clauset****M. E. J. Newman****Cristopher Moore**

CiteWeb id: 20040000139

CiteWeb score: 3548

DOI: 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.

**Finding community structure in very large networks**" is placed in the Top 10000 of the best publications in CiteWeb. Also in the category Physics it is included to the Top 1000. Additionally, the publicaiton "

**Finding community structure in very large networks**" is placed in the Top 1000 among other scientific works published in 2004.

- ece-research.unm.edu/ifis/papers/community-moore.pdf
- tuvalu.santafe.edu/~aaronc/courses/5352/readings/Clauset_Newman_Moore_04_FindingCommunityStructureInVeryLargeNetworks.pdf
- arxiv.org/pdf/cond-mat/0408187
- www.umekkii.jp/college/syllabus/06_report/citation/very_large_networks.pdf
- eece.unm.edu/ifis/papers/community-moore.pdf
- https://www.cs.unm.edu/~treport/tr/04-12/CNM_FastModularity_2004.pdf
- arxiv.org/abs/cond-mat/0408187
- www.ncbi.nlm.nih.gov/pubmed/15697438
- www.ece.unm.edu/ifis/papers/community-moore.pdf
- adsabs.harvard.edu/abs/2004PhRvE..70f6111C
- link.aps.org/doi/10.1103/PhysRevE.70.066111

Aaron Clauset, M. E. J. Newman, Cristopher Moore,

Finding community structure in very large networks(2004)## HTML code:

## Wiki code: