Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
2006-06-08
Physica D, 224 (1-2), pp. 20-26, 2006
Physics
Condensed Matter
Disordered Systems and Neural Networks
Scientific paper
10.1016/j.physd.2006.09.009
Study of the cluster- or community structure of complex networks makes an important contribution to the understanding of networks at a functional level. Despite the many efforts, no definition of community has been agreed on and important aspects such as the statistical significance and theoretical limits of community detection are not well understood. We show how the problem of community detection can be mapped onto finding the ground state of an infinite range spin glass. The ground state energy then corresponds directly to the quality of the partition. The network modularity Q previously defined by Girvan and Newman [Phys. Rev. E, 69, 026113 (2004)] turns out to be a special case of this spin glass energy. Through this spin glass analogy, we are able to give expectation values for the modularity of random graphs that can be used in the assessment of the statistical significance of real network clusterings. Further, it allows for assessing the theoretical limits of community detection.
Bornholdt Stefan
Reichardt Joerg
No associations
LandOfFree
When are networks truly modular? 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 When are networks truly modular?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and When are networks truly modular? will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-506851