Fast algorithm for detecting community structure in networks.

By Mark Newman. 2003

5,403 citations recorded by the source corpus.

Many networks display community structure--groups of vertices within which connections are dense but between which they are sparser--and sensitive computer algorithms have in recent years been developed for detecting this structure. These algorithms, however, are computationally demanding, which limits their application to small networks. Here we describe an algorithm which gives excellent results when tested on both computer-generated and real-world networks and is much faster, typically thousands of times faster, than previous algorithms. We give several example applications, including one to a collaboration network of more than 50,000 physicists.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

How researchers see this paper

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

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Towards Better Analysis of Deep Convolutional Neural Networks (2016, methodology): “If the number of neurons in a cluster is too large to be efﬁciently solved via directly running the Held-Karp algorithm, the cluster is divided into several sub-clusters by a widely used graph clustering method developed by Newman Computing the ordering of sub-clusters by running the Held-Karp algor”
Community detection in graphs (2009, methodology): “Modularity can be easily extended to graphs with weighted edges (Newman, 2004).”
Modularity and community structure in networks. (2006, background): “A typical problem in graph partitioning is the division of a set of tasks between the processors of a parallel computer so as to minimize the necessary amount of interprocessor communication.”
A model-based approach to attributed graph clustering (2012, background): “[10] M. E. J. Newman.”
Non-overlapping community detection (2018, methodology): “FastGreedy is an agglomerative hierarchical clustering method developed by Newman et al. (Newman 2004b).”
A Multiobjective Genetic Algorithm to Find Communities in Complex Networks (2012, background): “The idea underlying the edge betweenness comes from the observation that if two communities are joined by a few intercommunity edges, then all the paths from vertices in one community to vertices in the another must pass through these edges.”
Community detection in social networks (2016, background): “Newman 31 has worked to maximize modularity so that the process of aggregating nodes to form communities leads to maximum modularity gain.”
A Spectral Clustering Approach To Finding Communities in Graph (2005, methodology): “Newman [10] and Newman and Girvan [9] showed across a wide variety of simulated and real-world graphs that larger Q values are correlated with better graph clusterings.”
The Statistical Trends of Protein Evolution: A Lesson from AlphaFold Database (2022, background): “It is defined as the fraction of the edges that fall within the given module minus the expected fraction when edges were distributed at random (87, 88).”
Analysis of the structure of complex networks at different resolution levels (2007, background): “‡ Author to whom any correspondence should be addressed”
Network-Based Functional Regions (2011, methodology): “In practice, this problem has been shown to be computationally hard, and therefore some form of heuristic is required to approximate modularity maximisation (Newman, 2004a; 2006b).”
The BioPlex Network: A Systematic Exploration of the Human Interactome (2015, positive): “We have employed a two-stage strategy to map BioPlex community structure, using clique percolation (Palla et al., 2005) to identify 256 communities that were further subdivided via modularity-based clustering (Newman, 2004) (legend continued on next page) subcommunities (Table S3).”
A classification for community discovery methods in complex networks (2011, methodology): “After a pioneering work proposing modularity [87], Newman presented an efficient strategy for modularity maximization, namely repeatedly merging the two communities whose amalgamation produces the largest increase in Q.”
Method to find community structures based on information centrality. (2004, methodology): “At this stage we have four components, two isolated nodes (12 and 27) and two larger groups which are homogeneous except node 10 which is misclassified (curiously enough, this node is also misclassified by the fast algorithm of Newman [23]).”
Robustness of community structure in networks. (2007, methodology): “Perhaps the most widely used technique, however, is the maximization of the benefit function known as modularity [5, 15, 16, 17, 18, 19, 20, 21], which is (to within a multiplicative constant) the difference between the number of edges within communities and the expected number of such edges under a”
Link communities reveal multiscale complexity in networks (2009, methodology): “45 We apply all three frameworks (HLC, CPM and modularity) to the biological networks studied in Fig.”