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
- Santo Fortunato
- Jure Leskovec
- Binghui Wang
- Neil Zhenqiang Gong
- Mark Newman
- Tiago P. Peixoto
- Jaewon Yang
- Ludo Waltman
In Statistical and Nonlinear Physics
- Santo Fortunato
- Jure Leskovec
- Mark Newman
- Olaf Sporns
- Darko Hric
- M. A. Porter
- Jaewon Yang
- Tiago P. Peixoto
Citations in the corpus
- Comparative metabolomics and transcriptomics of plant response to Tomato yellow leaf curl virus infection in resistant and susceptible tomato cultivars (2014, methodology): “In order to identify such communities, we used a fast greedy algorithm (Clauset et al. 2004) implemented in the igraph R package (Csárdi and Nepusz 2006).”
- An event-based framework for characterizing the evolutionary behavior of interaction graphs (2007, background): “The problem of identifying these clusters or communities from static graphs has been extensively studied [13, 7, 25, 11] over the past decade.”
- Polarization of the Vaccination Debate on Facebook (2018, methodology): “To do this we apply five well known community detection algorithms: FastGreedy1[23], WalkTrap2[24], MultiLevel3[25] and LabelPropagation4[26].”
- Why we twitter: understanding microblogging usage and communities (2007, background): “In social network area, Newman and Girvan [13, 7] proposed a metric called modularity to measure the strength of the community structure.”
- Event Detection in Social Streams (2012, neutral): “, 11, 25], these methods are typically designed for static networks.”
- NetCoMi: network construction and comparison for microbiome data in R (2020, neutral): “Similarity Fast greedy modularity optimization [86] Modularity clustering via a fast greedy algorithm,which is suitable for very large networks.”
- Scientific Paper Summarization Using Citation Summary Networks (2008, methodology): “To find the communities in the citation summary network we use (Clauset et al., 2004), a hierarchical agglomeration algorithm which works by greedily optimizing the modularity in a linear running time for sparse graphs.”
- Social big data: Recent achievements and new challenges (2015, methodology): “[51], who used the matrix f modularity variations to arrange for the algorithm to perform more fficiently.”
- Phylogenetic Molecular Ecological Network of Soil Microbial Communities in Response to Elevated CO2 (2011, methodology): “In this study, modules were detected by fast greedy modularity optimization (32).”
- Vision‐Based Automated Crack Detection for Bridge Inspection (2015, positive): “The technical details are provided in Clauset et al. (2004).”
- Detect overlapping and hierarchical community structure in networks (2008, methodology): “The extended modularity is de-4 fined as Note that EQ reduces to Q in [9] when each vertex belongs to only one community (Readers can refer to [14] for details), and EQ is equal to 0 when all nodes belong to the same community.”
- Clustering and Community Detection in Directed Networks: A Survey (2013, methodology): “ularity value. Thus, the algorithm can be considered as an agglomerative hierarchical clustering method (e.g., see Ref. [9]) and the whole procedure can be represented by a dendrogram. Clauset et al. [44] 14 presented a faster greedy algorithm (almost linear time in sparse graphs), based again on an”
- Mapping Change in Large Networks (2008, methodology): “a reference, the new algorithm is as fast as the previous high-speed algorithms (the greedy search presented in the supporting appendix of ref. (1)), which were based on the method introduced in ref. (7) and rened in ref. (8). At the same time, it is also more accurate than our previous high-accurac”
- Towards real-time community detection in large networks. (2008, methodology): “These networks are respectively the Amazon Purchasing Network analysed in [5] and the actor collaboration network [2].”
- On the permanence of vertices in network communities (2014, methodology): “A huge volume of work has been devoted to finding communities in large networks, including diverse methods such as modularity optimization [3, 6], spectral graph-partitioning [23], random-walk [24], information-theoretic [25, 26], consensus clustering [17] and many others (see [8] for the review).”
- An Efficient Framework for Generating Storyline Visualizations from Streaming Data (2015, methodology): “All tests for these studies were conducted on a MacBook Pro with an Intel Core i7 (2.6 GHz ) CPU and 16 GB memory.”
- UserRec: A User Recommendation Framework in Social Tagging Systems (2010, methodology): “In the second stage, we adopt a fast greedy algorithm for community discovery in networks (Clauset, Newman, and Moore 2004), which optimizes the modularity, Q, of a network by connecting the two vertices at each step, leading to the largest increase of modularity.”