Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
2006-03-27
Phys. Rev. E 74 (2006) 016110
Physics
Condensed Matter
Disordered Systems and Neural Networks
Scientific paper
10.1103/PhysRevE.74.016110
Starting from a general \textit{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 \textit{at hoc} introduced quality function from \cite{ReichardtPRL} and the modularity $Q$ as defined by Newman and Girvan \cite{Girvan03} 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 effective local update rules for optimization procedures to find the ground state are given. We show how the \textit{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.
Bornholdt Stefan
Reichardt Joerg
No associations
LandOfFree
Statistical Mechanics of Community Detection does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Statistical Mechanics of Community Detection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical Mechanics of Community Detection will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-413242