Method to find community structures based on information centrality.
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.
Fortunato
Santo
S
Fakultät für Physik, Universität Bielefeld, D-33501 Bielefeld, Germany.
Latora
Vito
V
Marchiori
Massimo
M
D000465:Algorithms; D003198:Computer Simulation; D016247:Information Storage and Retrieval; D007398:Interpersonal Relations; D008954:Models, Biological; D011157:Population Dynamics; D012111:Residence Characteristics; D012919:Social Behavior; D012922:Social Change; D012944:Social Support