Berlin 2005 – wissenschaftliches Programm

Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe

SYBN: Biological and Social Networks

SYBN 3: Biologische und Soziale Netzwerke, Postersitzung

SYBN 3.13: Poster

Montag, 7. März 2005, 14:00–15:30, Poster TU E

Detecting fuzzy community structures in complex networks — •Jörg Reichardt and Stefan Bornholdt — Institute for Theoretical Physics, University of Bremen

Real world complex networks often show surprising modularity: nodes may be grouped into communities, the members of which are tightly linked among themselves but only loosely connected to the rest of the network. Often, these communities represent a higher organisational order or functional entities and are thus of special interest.

We present a recently developed community detection algorithm [1]. We map the problem of community detection onto finding the minima in the Hamiltonian of a Potts spin glass. By combining a short range ferromagnetic with an infinite range anti-ferromagnetic interaction in the Potts energy function, communities are found to coincide with the domains of equal spin value in these minima. Comparing global and local minima of the Hamiltonian allows for the detection of hierarchies and overlapping (No-dqfuzzyNo-dq) communities and quantifying the association of nodes with multiple communities as well as the robustness of a community. No prior knowledge about the number of communities has to be assumed.

We show an exemplary application in biochemistry by detecting communities in a large protein folding network corresponding to stable and meta-stable conformations.

[1] J. Reichardt, S. Bornholdt, Phys. Rev. Lett. 93, 218701, (2004)