February 3, 2008 | Jörg Reichardt and Stefan Bornholdt
The paper presents a statistical mechanics approach to community detection in networks, interpreting the problem as finding the ground state of an infinite-range spin glass. The method applies to both weighted and directed networks and includes the modularity $Q$ and an ad hoc quality function as special cases. The community structure is defined as the spin configuration that minimizes the energy of the spin glass, with spins representing community indices. The paper discusses the properties of the ground state configuration, including the definition of communities as cohesive subgroups, and introduces hierarchies and overlap in the community structure. Efficient local update rules for optimization procedures are provided, and the method is extended to find the community around a given node without detecting all communities. The performance of this extension is benchmarked, and expectation values for the modularity of random graphs are given to assess the statistical significance of community structures. The paper also compares the proposed method with other definitions of communities and discusses the stability of community assignments under changes in the parameter $\gamma$. Finally, the method is applied to a real-world example, the co-authorship network of the Los Alamos condensed matter preprint archive, to demonstrate its effectiveness in identifying hierarchical community structures.The paper presents a statistical mechanics approach to community detection in networks, interpreting the problem as finding the ground state of an infinite-range spin glass. The method applies to both weighted and directed networks and includes the modularity $Q$ and an ad hoc quality function as special cases. The community structure is defined as the spin configuration that minimizes the energy of the spin glass, with spins representing community indices. The paper discusses the properties of the ground state configuration, including the definition of communities as cohesive subgroups, and introduces hierarchies and overlap in the community structure. Efficient local update rules for optimization procedures are provided, and the method is extended to find the community around a given node without detecting all communities. The performance of this extension is benchmarked, and expectation values for the modularity of random graphs are given to assess the statistical significance of community structures. The paper also compares the proposed method with other definitions of communities and discusses the stability of community assignments under changes in the parameter $\gamma$. Finally, the method is applied to a real-world example, the co-authorship network of the Los Alamos condensed matter preprint archive, to demonstrate its effectiveness in identifying hierarchical community structures.