An efficient and principled method for detecting communities in networks

By Brian Ball, Brian Karrer, Mark Newman. 2011

398 citations recorded by the source corpus.

A fundamental problem in the analysis of network data is the detection of network communities, groups of densely interconnected nodes, which may be overlapping or disjoint. Here we describe a method for finding overlapping communities based on a principled statistical approach using generative network models. We show how the method can be implemented using a fast, closed-form expectation-maximization algorithm that allows us to analyze networks of millions of nodes in reasonable running times. We test the method both on real-world networks and on synthetic benchmarks and find that it gives results competitive with previous methods. We also show that the same approach can be used to extract nonoverlapping community divisions via a relaxation method, and demonstrate that the algorithm is competitively fast and accurate for the nonoverlapping problem.

Subfields: Mathematical Physics, 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 Mathematical Physics

In Statistical and Nonlinear Physics

Citations in the corpus

Scalable Recommendation with Poisson Factorization (2013, methodology): “Independently of GaP and user behavior models, Poisson factorization has been studied in the context of signal processing for source separation [5, 12] and for the purpose of detecting community structure in network data [1, 11].”
Scalable Inference of Overlapping Communities (2012, methodology): “Stochastic a-MMSB also beats PM [3], the best scalable probabilistic model of overlapping communities, in predictive accuracy.”
Hierarchical block structures and high-resolution model selection in large networks (2013, methodology): “This type of approach should, in principle, also be applicable to other model classes, such as those based on overlapping [9, 83–85], or link communities [25, 86].”
Overlapping community detection in networks: The state-of-the-art and comparative study (2011, methodology): “Within this framework, one can use Jaccard index as in [Ball et al. 2011] or F-score as a measure of detection accuracy.”
Spectral redemption in clustering sparse networks (2013, neutral): “[31] Ball, B, Karrer, B, and Newman, M E J (2011).”
Bayesian Nonparametric Poisson Factorization for Recommendation Systems (2014, methodology): “Finally, we remark that although we focus on recommendation systems, our BNP model can be used in a broader range of applications requiring matrix factorization, such as topic modeling (Canny, 2004) or community detection (Ball et al., 2011).”
Networks beyond pairwise interactions: structure and dynamics (2020, background): “Yet another variant jointly models the degree sequence and the mesoscopic structure, leading to a so-called degree-corrected bipartite SBM [193] that, unlike the classical degree-corrected SBM, makes explicit the assumptions that there are two node types [188, 189, 194] (Fig.”
A classification for community discovery methods in complex networks (2011, methodology): “We thus have negative cycles and a significant shortest path cannot be computed (since in Bellman-Ford’s algorithm, disallowing edge repetition, it is possible to obtain a shortest path that will always cross all the negative cycles it can, thus destroying the concept of bridge [124]).”
Pseudo-likelihood methods for community detection in large sparse networks (2012, background): “These include the popular stochastic block model [20], its extensions to include varying degree distributions within communities [22] and overlapping communities [2, 4], and various latent variable models [17, 19].”
Detecting cohesive and 2-mode communities indirected and undirected networks (2014, background): “For example, separate me thods have been proposed for detecting communities in undirected networks that are disjoint [4, 13, 21, 38, 40], overlapping [3, 6 , 11, 34, 43], or hierarchically nested [2, 44].”
Community detection in networks: A user guide (2016, methodology): “The link to the stochastic block model based on edge clustering by Ball et al. (Ball et al., 2011) is provided below.”
Core-Periphery Structure in Networks (2012, methodology): “, by using a method that allows overlapping communities) [1, 2].”
Scalable Recommendation with Hierarchical Poisson Factorization (2015, methodology): “Independently of GaP and user behavior models, Poisson factorization has been studied in the context of signal processing for source separation [5, 15] and for detecting community structure in network data [1, 13].”
Blockchain applications in supply chains, transport and logistics: a systematic review of the literature (2019, background): “This type of overlap is a common occurrence in network analysis (Ball, Karrer, and Newman 2011; Palla et al. 2005) and it shows that the aforementioned articles have been commonly referred to in multiple research areas.”