Method to find community structures based on information centrality

Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Nov;70(5 Pt 2):056104. doi: 10.1103/PhysRevE.70.056104. Epub 2004 Nov 15.

Abstract

Community structures are an important feature of many social, biological, and technological networks. Here we study a variation on the method for detecting such communities proposed by Girvan and Newman and based on the idea of using centrality measures to define the community boundaries [M. Girvan and M. E. J. Newman, Proc. Natl. Acad. Sci. U.S.A. 99, 7821 (2002)]. We develop an algorithm of hierarchical clustering that consists in finding and removing iteratively the edge with the highest information centrality. We test the algorithm on computer generated and real-world networks whose community structure is already known or has been studied by means of other methods. We show that our algorithm, although it runs to completion in a time O(n4) , is very effective especially when the communities are very mixed and hardly detectable by the other methods.

Publication types

  • Evaluation Study

MeSH terms

  • Algorithms*
  • Computer Simulation
  • Information Storage and Retrieval
  • Interpersonal Relations
  • Models, Biological*
  • Population Dynamics*
  • Residence Characteristics*
  • Social Behavior*
  • Social Change*
  • Social Support*