Detecting Fuzzy Community Structures in Complex Networks with a Potts Model

Physical Review LettersPublished 15 November 2004Open access

Jörg Reichardt, Stefan Bornholdt

DOI10.1103/physrevlett.93.218701

Citations599

TL;DR

A fast community detection algorithm based on a q-state Potts model that allows for the detection of overlapping ("fuzzy") communities and quantifying the association of nodes with multiple communities as well as the robustness of a community.

Abstract

A fast community detection algorithm based on a q-state Potts model is presented. Communities (groups of densely interconnected nodes that are only loosely connected to the rest of the network) are found to coincide with the domains of equal spin value in the minima of a modified Potts spin glass Hamiltonian. Comparing global and local minima of the Hamiltonian allows for the detection of overlapping ("fuzzy") communities and quantifying the association of nodes with multiple communities as well as the robustness of a community. No prior knowledge of the number of communities has to be assumed.

Keywords

Social SciencesPhysics and Astronomy

ScienceOptimization by Simulated Annealing

44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more

A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.

Proceedings of the National Academy of SciencesCommunity structure in social and biological networks

15,656 Citations2002Michelle Girvan, M. E. J. Newman

This article proposes a method for detecting communities, built around the idea of using centrality indices to find community boundaries, and tests it on computer-generated and real-world graphs whose community structure is already known and finds that the method detects this known structure with high sensitivity and reliability.

View PDF

Choice Reviews OnlineFinding groups in data: an introduction to cluster analysis

10,614 Citations1991

Physical Review EFast algorithm for detecting community structure in networks

5,491 Citations2004M. E. J. Newman

An algorithm is described which gives excellent results when tested on both computer-generated and real-world networks and is much faster, typically thousands of times faster, than previous algorithms.

View PDF

The European Physical Journal BDetecting community structure in networks

2,022 Citations2004M. E. J. Newman

A number of more recent algorithms that appear to work well with real-world network data, including algorithms based on edge betweenness scores, on counts of short loops in networks and on voltage differences in resistor networks are described.

View PDF

Physical Review LettersSuperparamagnetic Clustering of Data

544 Citations1996Marcelo Blatt, Shai Wiseman +1 more

This work presents a new approach for clustering, based on the physical properties of an inhomogeneous ferromagnetic model, which outperforms other algorithms for toy problems as well as for real data.

Journal of Molecular BiologyThe Protein Folding Network

356 Citations2004Francesco Rao, Amedeo Caflisch

The conformation space of a 20 residue antiparallel beta-sheet peptide, sampled by molecular dynamics simulations, is mapped to a network and provides a basis for understanding the heterogeneity of the TS and denatured state ensemble as well as the existence of multiple pathways.

Journal of Physics A Mathematical and GeneralApplication of statistical mechanics to NP-complete problems in combinatorial optimisation

326 Citations1986Yuchen Fu, Philip W. Anderson

The authors find a spin glass transition in the system, and the low temperature phase space has an ultrametric structure, which sheds light on the nature of hard computation problems.