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
at hoc introduced quality function from ReichardtPRL and the
modularity $Q$ as defined by Newman and Girvan 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 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.
Описание
[cond-mat/0603718] Statistical Mechanics of Community Detection
%0 Generic
%1 reichardt2006statistical
%A Reichardt, Joerg
%A Bornholdt, Stefan
%D 2006
%K community detection model modularity physics
%T Statistical Mechanics of Community Detection
%U http://arxiv.org/abs/cond-mat/0603718
%X 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
at hoc introduced quality function from ReichardtPRL and the
modularity $Q$ as defined by Newman and Girvan 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 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.
@misc{reichardt2006statistical,
abstract = { 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.
},
added-at = {2011-08-02T17:54:33.000+0200},
author = {Reichardt, Joerg and Bornholdt, Stefan},
biburl = {https://www.bibsonomy.org/bibtex/2d6af16d67e04371e9769aaf4b7e88beb/folke},
description = {[cond-mat/0603718] Statistical Mechanics of Community Detection},
interhash = {968ba40de011d4560e3d1279bee169ac},
intrahash = {d6af16d67e04371e9769aaf4b7e88beb},
keywords = {community detection model modularity physics},
note = {cite arxiv:cond-mat/0603718},
timestamp = {2011-08-02T17:54:33.000+0200},
title = {Statistical Mechanics of Community Detection},
url = {http://arxiv.org/abs/cond-mat/0603718},
year = 2006
}