Method to find community structures based on information centrality.

By Santo Fortunato, Vito Latora, Massimo Marchiori. Physical review. E, Statistical, nonlinear, and soft matter physics, 2004

327 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/4b27fa9b47a56b450243d65f9d89c9675cd8e91d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Community Structure in Graphs (2007, methodology): “In the algorithm by Fortunato, Latora and Marchiori [43], edges are removed according to decreasing values of information centrality.”
Detecting communities of triangles in complex networks using spectral optimization (2010, methodology): “A lot of effort has been put into proposing reliable techniques to maxim ize odularity [8, 9, 10, 11, 12, 13, 14, 15, 16], see review [17].”
Community detection in Social Media (2012, background): “Several measures of edge betweeness have been devised, for instance, edge, random-walk, and current-flow betweeness (Newman and Grivan 2004), as well as information centrality (Fortunato et al. 2004) and the edge clustering coefficient Radicchi et al. (2004).”
Community detection in graphs (2009, methodology): “Vragoviĉ and Louis defined the loop coefficient of i as the average of 1/djk/i over all pairs of neighbors of i, somewhat reminding of the concept of information centrality used in the method by Fortunato et al. (Fortunato et al., 2004).”
BotGrep: Finding P2P Bots with Structured Graph Analysis (2010, background): “In [22], information centrality has been proposed to measure the edge importance.”
A classification for community discovery methods in complex networks (2011, background): “[137], even if only a novel centrality measure is”
Graph theory and networks in Biology. (2006, background): “In [68, 137, 150, 61] the notions of betweenness and information centrality were first extended to apply to edges rather than nodes.”