Statistical mechanics of community detection.

By J. Reichardt, Stefan Bornholdt. 2006

2,004 citations recorded by the source corpus.

Starting from a general ansatz, we show how community detection can be interpreted as finding the ground state of an infinite range spin glass. Our approach applies to weighted and directed networks alike. It contains the ad hoc introduced quality function from [J. Reichardt and S. Bornholdt, Phys. Rev. Lett. 93, 218701 (2004)] and the modularity Q as defined by Newman and Girvan [Phys. Rev. E 69, 026113 (2004)] as special cases. The community structure of the network is interpreted as the spin configuration that minimizes the energy of the spin glass with the spin states being the community indices. We elucidate the properties of the ground state configuration to give a concise definition of communities as cohesive subgroups in networks that is adaptive to the specific class of network under study. Further, we show how hierarchies and overlap in the community structure can be detected. Computationally efficient local update rules for optimization procedures to find the ground state are given. We show how the ansatz may be used to discover the community around a given node without detecting all communities in the full network and we give benchmarks for the performance of this extension. Finally, we give expectation values for the modularity of random graphs, which can be used in the assessment of statistical significance of community structure.

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

Community detection in graphs (2009, methodology): “The general spin glass framework by Reichardt and Bornholdt ((Reichardt and Bornholdt, 2006a) and Section VI.”
Critical phenomena in complex networks (2007, methodology): “Reichardt and Bornholdt (2004, 2006) used the configuration model as the null model, i.e., pij = qiqj/2L where qi and qj are degrees of vertices i and j respectively.”
Community detection in networks: A user guide (2016, methodology): “One approach consists in introducing a resolution parameter γ into modularity’s formula (Arenas et al., 2008b; Reichardt and Bornholdt, 2006).”
Social Anxiety Disorder as a Densely Interconnected Network of Fear and Avoidance for Social Situations (2017, methodology): “To examine whether the nodes cohere as a single system or as linked communities (“subnetworks”), we implemented the spin glass algorithm (Reichardt and Bornholdt 2006).”
Communities, modules and large-scale structure in networks (2011, neutral): “Modifications of the method have been proposed that allow one to vary this preferred size 59,60 , but not to eliminate the preference altogether.”
A high-resolution human contact network for infectious disease transmission (2010, methodology): “Reichardt J, Bornholdt S (2006) Statistical mechanics of community detection.”
Community Structure in Time-Dependent, Multiscale, and Multiplex Networks (2009, neutral): “ρi|jp ∗ j = ( k i 2m+ k j kj − k − i 2m− k− j kj ) kj 2m = 1 2m ( k i k + j 2m+ − k− i k − j 2m− ) , (9)”
A classification for community discovery methods in complex networks (2011, background): “Thus, for a historical point of view of the community discovery problem, please refer to other review papers.”
Non-overlapping community detection (2018, methodology): “Spinglass was introduced by Reichardt and Bornholdt (Reichardt and Bornholdt 2006).”
Current best practices in single‐cell RNA‐seq analysis: a tutorial (2019, methodology): “Molecular Systems Biology multi-resolution modularity optimization (Newman & Girvan, 2004; Reichardt & Bornholdt, 2006) as implemented in the Louvain algorithm (Blondel et al , 2008) on single-cell KNN graphs.”
A unified approach to mapping and clustering of bibliometric networks (2010, methodology): “A parameterized variant of the modularity function of Newman and Girvan (2004) was introduced by Reichardt and Bornholdt (2006; see also Heimo, Kumpula, Kaski, & Saramäki, 2008; Kumpula, Saramäki, Kaski, & Kertész, 2007).”
Finding community structure in networks using the eigenvectors of matrices. (2006, methodology): “To get around this we rewrite Eq.”
Mental Disorders as Causal Systems (2015, background): “Advantages of the causal system perspective Network analyses now span fields from physics (e.g., Reichardt & Bornholdt, 2006) to sociology (e.g., Cacioppo, Fowler, & Christakis, 2009), but only recently have empirical studies on psychopathology appeared, featuring the syndromes of major depression…”
Modular Brain Networks (2015, methodology): “To circumvent the resolution limit issue, a number of multiresolution techniques have been proposed (Arenas et al. 2008, Reichardt & Bornholdt 2006).”