Finding community structure in very large networks
| dc.creator | Clauset, Aaron | |
| dc.creator | Newman, M. E. J. | |
| dc.creator | Moore, Cristopher | |
| dc.date | 2004-08-09 | |
| dc.date | 2004-08-30 | |
| dc.date.accessioned | 2026-07-07T09:31:43Z | |
| dc.date.available | 2026-07-07T09:31:43Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cond-mat/0408187 | |
| dc.identifier | http://arxiv.org/abs/cond-mat/0408187 | |
| dc.identifier | Phys. Rev. E 70, 066111 (2004) | |
| dc.identifier | doi:10.1103/PhysRevE.70.066111 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/158556 | |
| dc.subject | Statistical Mechanics | |
| dc.subject | Disordered Systems and Neural Networks | |
| dc.title | Finding community structure in very large networks | |
| dc.type | text |