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 Osn 4 d, is very effective especially when the communities are very mixed and hardly detectable by the other methods. DOI: 10.1103/PhysRevE.70.056104 PACS number(s): 89.75.Hc I. INTRODUCTION Network analysis has revealed as a powerful approach to understand complex phenomena and organization in social, biological and technological systems [1–5]. In the frame- work of network analysis a given system is modeled as a graph in which the nodes are the elements of the system, for instance the individuals in a social system, the neurons in a brain and the routers in the Internet, and the edges represent the interactions, social links, synapses and electric wirings respectively, between couples of elements. A lot of interest has been focused on the characterization of various structural and locational properties of the network [1–5]. Among the others, an important property common to many networks is the presence of subgroups or communities. For instance, in social networks some individuals can be part of a tightly connected group or of a closed social elite, others can be completely isolated, while some others may act as bridges between groups. The differences in the way that individuals are embedded in the structure of groups within the network can have important consequences on the behav- ior they are likely to practice. The division of the individuals of a social network into communities is a fundamental aspect of a social system. In fact, subgroups in social systems often have their own norms, orientations and subcultures, some- times running counter to the official culture, and are the most important source of a person’s identity [2]. For this reason one of the main concerns, since the very beginning of social network analysis, has been the definition and the identifica- tion of subgroups of individuals within a network. And the first algorithms to find community structures have been pro- posed in social network analysis. Subgroups are also important to other networks. The pres- ence of subgrouping in biological...

Website: www.ct.infn.it | Filesize: -
No of Page(s): 13
Download Method to find community structures based on information centrality.pdf