Santo Fortunato - arXiv

1 Community detection in graphsSanto Fortunato Complex Networks and Systems Lagrange Laboratory, ISI Foundation, Viale S. Severo 65, 10133, Torino, modern science of networks has brought significant advances to our understanding of complexsystems. One of the most relevant features of graphs representing real systems is communitystructure, or clustering, i. e. the organization of vertices in clusters, with many edges joiningvertices of the same cluster and comparatively few edges joining vertices of different clusters. Suchclusters, or communities, can be considered as fairly independent compartments of a graph , playinga similar role like, e. g.

2 , the tissues or the organs in the human body. Detecting communitiesis of great importance in sociology, biology and computer science, disciplines where systems areoften represented as graphs. This problem is very hard and not yet satisfactorily solved, despitethe huge effort of a large interdisciplinary community of scientists working on it over the past fewyears. We will attempt a thorough exposition of the topic, from the definition of the main elementsof the problem, to the presentation of most methods developed, with a special focus on techniquesdesigned by statistical physicists, from the discussion of crucial issues like the significance ofclustering and how methods should be tested and compared against each other, to the descriptionof applications to real Introduction2II.

3 Communities in real-world networks4 III. Elements of Community Detection8A. Computational complexity9B. Communities91. Basics92. Local definitions103. Global definitions114. Definitions based on vertex similarity12C. Partitions131. Basics132. Quality functions: modularity14IV. Traditional methods16A. graph partitioning16B. Hierarchical clustering19C. Partitional clustering19D. Spectral clustering20V. Divisive algorithms23A. The algorithm of Girvan and Newman23B. Other methods25VI. Modularity-based methods27A. Modularity optimization271. Greedy techniques272. Simulated annealing293. Extremal optimization294. Spectral optimization305. Other optimization strategies33B.

4 Modifications of modularity34C. Limits of modularity38 VII. Spectral Algorithms41 VIII. Dynamic Algorithms43A. Spin models43 Electronic address: Random walk45C. Synchronization47IX. Methods based on statistical inference48A. Generative models49B. Blockmodeling, model selection and informationtheory52X. Alternative methods54XI. Methods to find overlapping communities58A. Clique percolation58B. Other techniques60 XII. Multiresolution methods and cluster hierarchy62A. Multiresolution methods63B. Hierarchical methods65 XIII. Detection of dynamic communities66 XIV. Significance of clustering70XV. Testing Algorithms73A. Benchmarks74B. Comparing partitions: measures77C.

5 Comparing algorithms79 XVI. General properties of real clusters82 XVII. Applications on real-world networks85A. Biological networks85B. Social networks86C. Other networks88 XVIII. Outlook90A. Elements of graph Theory921. Basic Definitions922. graph Matrices943. Model graphs94 References96 [ ] 25 Jan 20102I. INTRODUCTIONThe origin of graph theory dates back to Euler s solu-tion of the puzzle of K onigsberg s bridges in 1736 (Euler,1736). Since then a lot has been learned about graphsand their mathematical properties (Bollobas, 1998). Inthe 20th century they have also become extremely usefulas representation of a wide variety of systems in differentareas. Biological, social, technological, and informationnetworks can be studied as graphs, and graph analysishas become crucial to understand the features of thesesystems.

6 For instance, social network analysis started inthe 1930 s and has become one of the most importanttopics in sociology (Scott, 2000; Wasserman and Faust,1994). In recent times, the computer revolution has pro-vided scholars with a huge amount of data and computa-tional resources to process and analyze these data. Thesize of real networks one can potentially handle has alsogrown considerably, reaching millions or even billions ofvertices. The need to deal with such a large number ofunits has produced a deep change in the way graphs areapproached (Albert and Barab asi, 2002; Barratet al.,2008; Boccalettiet al., 2006; Mendes and Dorogovtsev,2003; Newman, 2003; Pastor-Satorras and Vespignani,2004).

7 Graphs representing real systems are not regular like,e. g., lattices. They are objects where order coexists withdisorder. The paradigm of disordered graph is the ran-dom graph , introduced by P. Erd os and A. R enyi (Erd osand R enyi, 1959). In it, the probability of having anedge between a pair of vertices is equal for all possiblepairs (see Appendix). In a random graph , the distribu-tion of edges among the vertices is highly instance, the distribution of the number of neigh-bours of a vertex, ordegree, is binomial, so most ver-tices have equal or similar degree. Real networks arenot random graphs, as they display big inhomogeneities,revealing a high level of order and organization.

8 The de-gree distribution is broad, with a tail that often followsa power law: therefore, many vertices with low degreecoexist with some vertices with large degree. Further-more, the distribution of edges is not only globally, butalso locally inhomogeneous, with high concentrations ofedges within special groups of vertices, and low concen-trations between these groups. This feature of real net-works is calledcommunity structure(Girvan and New-man, 2002), orclustering, and is the topic of this review(for earlier reviews see Refs. (Danonet al., 2007; Fortu-nato and Castellano, 2009; Newman, 2004a; Porteret al.,2009; Schaeffer, 2007)). Communities, also calledclustersormodules, are groups of vertices which probably sharecommon properties and/or play similar roles within thegraph.

9 In Fig. 1 a schematic example of a graph withcommunities is offers a wide variety of possible group organi-zations: families, working and friendship circles, villages,towns, nations. The diffusion of Internet has also ledto the creation of virtual groups, that live on the Web, FIG. 1A simple graph with three communities, enclosedby the dashed circles. Reprinted figure with permission fromRef. ( Fortunato and Castellano, 2009).c 2009 by online communities. Indeed, social communities havebeen studied for a long time (Coleman, 1964; Freeman,2004; Kottak, 2004; Moody and White, 2003). Communi-ties also occur in many networked systems from biology,computer science, engineering, economics, politics, protein-protein interaction networks, communities arelikely to group proteins having the same specific functionwithin the cell (Chen and Yuan, 2006; Rives and Galitski,2003; Spirin and Mirny, 2003), in the graph of the WorldWide Web they may correspond to groups of pages deal-ing with the same or related topics (Dourisboureet al.)

10 ,2007; Flakeet al., 2002), in metabolic networks they maybe related to functional modules such as cycles and path-ways (Guimer`a and Amaral, 2005; Pallaet al., 2005),in food webs they may identify compartments (Krauseet al., 2003; Pimm, 1979), and so can have concrete applications. Cluster-ing Web clients who have similar interests and are ge-ografically near to each other may improve the perfor-mance of services provided on the World Wide Web, inthat each cluster of clients could be served by a dedi-cated mirror server (Krishnamurthy and Wang, 2000).Identifying clusters of customers with similar interestsin the network of purchase relationships between cus-tomers and products of online retailers (like, , ) enables to set up efficient recommen-dation systems (Reddyet al.