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(n(4)) is very effective especially when the communities are very mixed and hardly detectable by the other methods.