Communities in Complex Networks

Communities in Complex Networks: Identification at Different Levels - Alex Arenas, Jordi Duch, Sergi Gómez, Leon Danon, Albert Díaz-Guilera ©Encyclopedia of Life Support Systems (EOLSS) COMMUNITIES IN COMPLEX NETWORKS: IDENTIFICATION AT DIFFERENT LEVELS Alex Arenas, Jordi Duch and Sergi Gómez Departament Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Spain Leon Danon Mathematics Institute, University of Warwick, Great Britain Albert Díaz-Guilera Departament Física Fonamental, Universitat de Barcelona, Spain Keywords: Communities, hierarchies, overlap, dynamics Contents 1. Introduction 2. Definition of communities 3. Evaluating community identification 4. Link removal methods 4.1. Shortest Path Centrality 4.2. Extensions of the Shortest Path Centrality 4.3. Information Centrality 4.4. Link Clustering 5. Agglomerative methods 5.1. Hierarchical Clustering 5.2.

L-Shell Method 5.3. K-Clique Method 6. Maximizing modularity methods 6.1. Greedy Algorithm 6.2. Extremal Optimization 6.3. Simulated Annealing Methods 6.4. Information Theoretic Approach 7. Spectral Analysis methods 7.1. Spectral Bisection 7.2. Multi Dimensional Spectral Analysis 7.3. Constrained Optimization 7.4. Approximate Resistance Networks 8. Other methods 8.1. Clustering and Curvature 8.2. Random Walk Based Methods 8.3. Q-Potts Model 9. Further structural complexity 9.1. Hierarchical Organization 9.2. Overlap 10. Applications: Search and congestion 11. Conclusions UNESCO – EOLSS SAMPLE CHAPTERS COMPLEX NETWORKS - Communities in Complex Networks: Identification at Different Levels - Alex Arenas, Jordi Duch, Sergi Gómez, Leon Danon, Albert Díaz-Guilera ©Encyclopedia of Life Support Systems (EOLSS) Acknowledgements Glossary Bibliography Biographical Sketches Summary We present here and compare the most common approaches to community structure identification in terms of sensitivity and computational cost. The work is intended as an introduction as well as a proposal for a standard benchmark test of community detection methods. 1. Introduction The analysis of complex networks has received a vast amount of attention from the scientific community during the last decade. Statistical physicists in particular have become interested in the study of networks describing the topologies of a wide variety of systems, from biological technological or social networks. Although several questions have been addressed (see the review paper by Costa et al. for a complete set of measurements), many important ones still resist complete resolution. One such problem is the analysis of modular structure found in many networks. Distinct modules or communities within networks can loosely be defined as subsets of nodes which are more densely linked, when compared to the rest of the network. Such communities, as usually called in social sciences, have been observed, using some of the methods we shall go on to describe, in many different contexts, including biological networks, economic networks and most notably social networks. As a result, the problem of identification of communities has been the focus of many recent efforts. As a concrete example we show in Figure 1 the network representing the Spanish research community of Statistical and Nonlinear Physicists (FISES, http://www.fises.es). We consider two scientists linked if they have co-authored a panel contribution to any of the conferences. To be able to consider the historical structure of this network we ''accumulate'' the network over all the conferences, that is, once a link is created, it remains, even if the authors never collaborated again. The final network...

Website: www.eolss.net | Filesize: -
No of Page(s): 11
Download Communities in Complex Networks: Identification at ... - EOLSS.pdf