Community detection in graphs

Euler, 1736, Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Petropolitanae, 8, 128 Bollobas, 1998 Wasserman, 1994 Scott, 2000 Albert, 2002, Statistical mechanics of complex networks, Rev. Mod. Phys., 74, 47, 10.1103/RevModPhys.74.47 Mendes, 2003 Newman, 2003, The structure and function of complex networks, SIAM Rev., 45, 167, 10.1137/S003614450342480 Pastor-Satorras, 2004 Boccaletti, 2006, Complex networks: Structure and dynamics, Phys. Rep., 424, 175, 10.1016/j.physrep.2005.10.009 Barrat, 2008 Erdös, 1959, On random graphs. I., Publ. Math. Debrecen, 6, 290, 10.5486/PMD.1959.6.3-4.12 Girvan, 2002, Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA, 99, 7821, 10.1073/pnas.122653799 Newman, 2004, Detecting community structure in networks, Eur. Phys. J. B, 38, 321, 10.1140/epjb/e2004-00124-y Danon, 2007, 93 Schaeffer, 2007, Graph clustering, Comput. Sci. Rev., 1, 27, 10.1016/j.cosrev.2007.05.001 Fortunato, 2009, Community structure in graphs Porter, 2009, Communities in networks, Notices of the American Mathematical Society, 56, 1082 Coleman, 1964 Freeman, 2004 Kottak, 2004 Moody, 2003, Structural cohesion and embeddedness: A hierarchical concept of social groups, Am. Sociol. Rev., 68, 103, 10.2307/3088904 Rives, 2003, Modular organization of cellular networks, Proc. Natl. Acad. Sci. USA, 100, 1128, 10.1073/pnas.0237338100 Spirin, 2003, Protein complexes and functional modules in molecular networks, Proc. Natl. Acad. Sci. USA, 100, 12123, 10.1073/pnas.2032324100 Chen, 2006, Detecting functional modules in the yeast protein–protein interaction network, Bioinformatics, 22, 2283, 10.1093/bioinformatics/btl370 Flake, 2002, Self-organization and identification of web communities, IEEE Computer, 35, 66, 10.1109/2.989932 Dourisboure, 2007, Extraction and classification of dense communities in the web, 461 Guimerà, 2005, Functional cartography of complex metabolic networks, Nature, 433, 895, 10.1038/nature03288 Palla, 2005, Uncovering the overlapping community structure of complex networks in nature and society, Nature, 435, 814, 10.1038/nature03607 Pimm, 1979, The structure of food webs, Theoret. Popul. Biol., 16, 144, 10.1016/0040-5809(79)90010-8 Krause, 2003, Compartments revealed in food-web structure, Nature, 426, 282, 10.1038/nature02115 Krishnamurthy, 2000, On network-aware clustering of web clients, SIGCOMM Comput. Commun. Rev., 30, 97, 10.1145/347057.347412 Reddy, 2002, A graph based approach to extract a neighborhood customer community for collaborative filtering, 188 Agrawal, 1994, Algorithms for searching massive graphs, Knowl. Data Eng., 6, 225, 10.1109/69.277767 Wu, 2004, Mining scale-free networks using geodesic clustering, 719 Perkins, 2001 Steenstrup, 2001 Csermely, 2008, Creative elements: Network-based predictions of active centres in proteins and cellular and social networks, Trends Biochem. Sci., 33, 569, 10.1016/j.tibs.2008.09.006 Granovetter, 1973, The strength of weak ties, Am. J. Sociol., 78, 1360, 10.1086/225469 Burt, 1976, Positions in networks, Soc. Forces, 55, 93, 10.2307/2577097 Freeman, 1977, A set of measures of centrality based on betweenness, Sociometry, 40, 35, 10.2307/3033543 Gfeller, 2007, Spectral coarse graining of complex networks, Phys. Rev. Lett., 99, 038701, 10.1103/PhysRevLett.99.038701 Gfeller, 2008, Spectral coarse graining and synchronization in oscillator networks, Phys. Rev. Lett., 100, 174104, 10.1103/PhysRevLett.100.174104 Pollner, 2006, Preferential attachment of communities: The same principle, but a higher level, Europhys. Lett., 73, 478, 10.1209/epl/i2005-10414-6 Simon, 1962, The architecture of complexity, Proc. Am. Phil. Soc., 106, 467 Weiss, 1955, A method for the analysis of the structure of complex organizations, Am. Sociol. Rev., 20, 661, 10.2307/2088670 Rice, 1927, The identification of blocs in small political bodies, Am. Polit. Sci. Rev., 21, 619, 10.2307/1945514 Homans, 1950 Donetti, 2004, Detecting network communities: a new systematic and efficient algorithm, J. Stat. Mech., P10012 Arenas, 2008, Analysis of the structure of complex networks at different resolution levels, New J. Phys., 10, 053039, 10.1088/1367-2630/10/5/053039 Zachary, 1977, An information flow model for conflict and fission in small groups, J. Anthropol. Res., 33, 452, 10.1086/jar.33.4.3629752 Lusseau, 2003, The emergent properties of a dolphin social network, Proc. R. Soc. London B, 270, S186, 10.1098/rsbl.2003.0057 Zhang, 2009 Jonsson, 2006, Cluster analysis of networks generated through homology: Automatic identification of important protein communities involved in cancer metastasis, BMC Bioinf., 7, 2, 10.1186/1471-2105-7-2 Newman, 2004, Finding and evaluating community structure in networks, Phys. Rev. E, 69, 026113, 10.1103/PhysRevE.69.026113 Albert, 1999, Internet: Diameter of the world-wide web, Nature, 401, 130, 10.1038/43601 Brin, 1998, The anatomy of a large-scale hypertextual web search engine, Comput. Netw. ISDN, 30, 107, 10.1016/S0169-7552(98)00110-X Leicht, 2008, Community structure in directed networks, Phys. Rev. Lett., 100, 118703, 10.1103/PhysRevLett.100.118703 Rosvall, 2008, Maps of random walks on complex networks reveal community structure, Proc. Natl. Acad. Sci. USA, 105, 1118, 10.1073/pnas.0706851105 D.L. Nelson, C.L. McEvoy, T.A. Schreiber, The university of south florida word association, rhyme, and word fragment norms (1998) Barber, 2007, Modularity and community detection in bipartite networks, Phys. Rev. E, 76, 066102, 10.1103/PhysRevE.76.066102 Adomavicius, 2005, Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions, IEEE Trans. Knowl. Data Eng., 17, 734, 10.1109/TKDE.2005.99 Davis, 1941 Gan, 2007 Garey, 1990 Papadimitriou, 1994 Mancoridis, 1998, Using automatic clustering to produce high-level system organizations of source code Luce, 1949, A method of matrix analysis of group structure, Psychometrika, 14, 95, 10.1007/BF02289146 Bomze, 1999, The maximum clique problem, 1 Bron, 1973, Finding all cliques on an undirected graph, Commun. ACM, 16, 575, 10.1145/362342.362367 Luce, 1950, Connectivity and generalized cliques in sociometric group structure, Psychometrika, 15, 169, 10.1007/BF02289199 Alba, 1973, A graph-theoretic definition of a sociometric clique, J. Math. Sociol., 3, 113, 10.1080/0022250X.1973.9989826 Mokken, 1979, Cliques, clubs and clans, Qual. Quant., 13, 161, 10.1007/BF00139635 Seidman, 1978, A graph theoretic generalization of the clique concept, J. Math. Sociol., 6, 139, 10.1080/0022250X.1978.9989883 Seidman, 1983, Network structure and minimum degree, Soc. Netw., 5, 269, 10.1016/0378-8733(83)90028-X V. Batagelj, M. Zaversnik, An o(m) algorithm for cores decomposition of networks. arXiv:cs.DS/0310049 Matsuda, 1999, Classifying molecular sequences using a linkage graph with their pairwise similarities, Theoret. Comput. Sci., 210, 305, 10.1016/S0304-3975(98)00091-7 Luccio, 1969, IEEE Trans. Circuit Th. CT, 16, 184, 10.1109/TCT.1969.1082924 Radicchi, 2004, Defining and identifying communities in networks, Proc. Natl. Acad. Sci. USA, 101, 2658, 10.1073/pnas.0400054101 Hu, 2008, Comparative definition of community and corresponding identifying algorithm, Phys. Rev. E, 78, 026121, 10.1103/PhysRevE.78.026121 Borgatti, 1990, LS sets, lambda sets, and other cohesive subsets, Soc. Netw., 12, 337, 10.1016/0378-8733(90)90014-Z Feige, 2001, The dense k-subgraph problem, Algorithmica, 29, 410, 10.1007/s004530010050 Asahiro, 2002, Complexity of finding dense subgraphs, Discrete Appl. Math., 121, 15, 10.1016/S0166-218X(01)00243-8 Holzapfel, 2003, The complexity of detecting fixed-density clusters, vol. 2653, 201 Šíma, 2006, On the NP-completeness of some graph cluster measures, vol. 3831, 530 Reichardt, 2006, Statistical mechanics of community detection, Phys. Rev. E, 74, 016110, 10.1103/PhysRevE.74.016110 Lorrain, 1971, Structural equivalence of individuals in social networks, J. Math. Sociol., 1, 49, 10.1080/0022250X.1971.9989788 Elias, 1956, Note on maximum flow through a network, IRE Trans. Inf. Theory IT-, 2, 117, 10.1109/TIT.1956.1056816 Ahuja, 1993 Estrada, 2008, Communicability in complex networks, Phys. Rev. E, 77, 036111, 10.1103/PhysRevE.77.036111 Estrada, 2009, Communicability graph and community structures in complex networks, Appl. Math. Comput., 214, 500, 10.1016/j.amc.2009.04.024 M. Saerens, F. Fouss, L. Yen, P. Dupont, The principal component analysis of a graph and its relationships to spectral clustering, in: Proc. Eur. Conf. on Machine Learning, 2004. URL citeseer.ist.psu.edu/saerens04principal.html Fouss, 2007, Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation, IEEE Trans. Knowl. Data Eng., 19, 355, 10.1109/TKDE.2007.46 Yen, 2009, Graph nodes clustering with the sigmoid commute-time kernel: A comparative study, Data Knowl. Eng., 68, 338, 10.1016/j.datak.2008.10.006 L. Yen, F. Fouss, C. Decaestecker, P. Francq, M. Saerens, Graph nodes clustering based on the commute-time kernel, in: PAKDD, 2007, pp. 1037–1045 Chandra, 1989, The electrical resistance of a graph captures its commute and cover times, 574 Klein, 1993, Resistance distance, J. Math. Chem., 12, 81, 10.1007/BF01164627 White, 2003, Algorithms for estimating relative importance in networks, 266 Zhou, 2003, Distance, dissimilarity index, and network community structure, Phys. Rev. E, 67, 061901, 10.1103/PhysRevE.67.061901 Harel, 2001, On clustering using random walks, 18 Latapy, 2005, Lect. Notes Comput. Sci., 3733, 284, 10.1007/11569596_31 Nadler, 2006, Diffusion maps, spectral clustering and reaction coordinates of dynamical systems, Appl. Comput. Harmon. Anal., 21, 113, 10.1016/j.acha.2005.07.004 C.R. Palmer, C. Faloutsos, Electricity based external similarity of categorical attributes, in: Proceedings of PAKDD 2003, 2003, pp. 486–500 Tong, 2008, Random walk with restart: Fast solutions and applications, Knowl. Inf. Syst., 14, 327, 10.1007/s10115-007-0094-2 Gori, 2007, Itemrank: A random-walk based scoring algorithm for recommender engines, 2766 Andrews, 1976 Lovász, 1993 Pólya, 1998 Ravasz, 2002, Hierarchical organization of modularity in metabolic networks, Science, 297, 1551, 10.1126/science.1073374 Ravasz, 2003, Hierarchical organization in complex networks, Phys. Rev. E, 67, 026112, 10.1103/PhysRevE.67.026112 Lancichinetti, 2009, Detecting the overlapping and hierarchical community structure in complex networks, New J. Phys., 11, 033015, 10.1088/1367-2630/11/3/033015 Kleinberg, 2002, An impossibility theorem for clustering, 446 M. Tumminello, F. Lillo, R.N. Mantegna, Correlation, hierarchies, and networks in financial markets, eprint arXiv:0809.4615 Dorogovtsev, 2002, Evolution of networks, Adv. Phys., 51, 1079, 10.1080/00018730110112519 Łuczak, 1992, Sparse random graphs with a given degree sequence, 165 Molloy, 1995, A critical point for random graphs with a given degree sequence, Random Struct. Algor., 6, 161, 10.1002/rsa.3240060204 Djidjev, 2007, A scalable multilevel algorithm for graph clustering and community structure detection, vol. 4936, 117 B.H. Good, Y. de Montjoye, A. Clauset, The performance of modularity maximization in practical contexts, eprint arXiv:0910.0165 Newman, 2006, Finding community structure in networks using the eigenvectors of matrices, Phys. Rev. E, 74, 036104, 10.1103/PhysRevE.74.036104 Holmström, 2009, Modularity density of network community divisions, Physica D, 238, 1161, 10.1016/j.physd.2009.03.015 C.P. Massen, J.P.K. Doye, Thermodynamics of Community Structure, eprint arXiv:cond-mat/0610077 Noack, 2009, Modularity clustering is force-directed layout, Phys. Rev. E, 79, 026102, 10.1103/PhysRevE.79.026102 Arenas, 2007, Size reduction of complex networks preserving modularity, New J. Phys., 9, 176, 10.1088/1367-2630/9/6/176 A. Pothen, Graph partitioning algorithms with applications to scientific computing, Tech. rep., Norfolk, VA, USA, 1997 Kernighan, 1970, An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J., 49, 291, 10.1002/j.1538-7305.1970.tb01770.x Suaris, 1988, An algorithm for quadrisection and its application to standard cellplacement, IEEE Trans. Circuits Syst., 35, 294, 10.1109/31.1742 Barnes, 1982, An algorithm for partitioning the nodes of a graph, SIAM J. Algebr. Discrete Methods, 3, 541, 10.1137/0603056 Fiedler, 1973, Algebraic connectivity of graphs, Czech. Math. J., 23, 298, 10.21136/CMJ.1973.101168 Lanczos, 1950, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Natl. Bur. Stand., 45, 255, 10.6028/jres.045.026 Golub, 1989 Ford, 1956, Maximal flow through a network, Canad. J. Math., 8, 399, 10.4153/CJM-1956-045-5 Goldberg, 1988, A new approach to the maximum flow problem, J. ACM, 35, 921, 10.1145/48014.61051 Flake, 2000, Efficient identification of web communities, 150 Wei, 1989, Towards efficient hierarchical designs by ratio cut partitioning, 298 Shi, 1997, Normalized cuts and image segmentation, 731 Shi, 2000, Normalized cuts and image segmentation, IEEE Trans. Pattern Anal. Mach. Intell., 22, 888, 10.1109/34.868688 Matula, 1990, Sparsest cuts and bottlenecks in graphs, Discrete Appl. Math., 27, 113, 10.1016/0166-218X(90)90133-W Blake, 1987 Hagen, 1992, New spectral methods for ratio cut partitioning and clustering, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 11, 1074, 10.1109/43.159993 Chan, 1993, Spectral k-way ratio-cut partitioning and clustering, 749 Hastie, 2001 MacQueen, 1967, Some methods for classification and analysis of multivariate observations, 281 Lloyd, 1982, Least squares quantization in PCM, IEEE Trans. Inform. Theory, 28, 129, 10.1109/TIT.1982.1056489 Schenker, 2003, Graph representations for web document clustering, vol. 2652, 935 Hlaoui, 2004, A direct approach to graph clustering, Neural Networks Computational Intelligence, 158 Rattigan, 2007, Graph clustering with network structure indices, 783 Dunn, 1974, A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters, J. Cybernet., 3, 32, 10.1080/01969727308546046 Bezdek, 1981 Donath, 1973, Lower bounds for the partitioning of graphs, IBM J. Res. Dev., 17, 420, 10.1147/rd.175.0420 D.A. Spielman, S.-H. Teng, Spectral partitioning works: Planar graphs and finite element meshes, in: IEEE Symposium on Foundations of Computer Science, 1996, pp. 96–105 U. von Luxburg, A tutorial on spectral clustering, Tech. Rep. 149, Max Planck Institute for Biological Cybernetics, August 2006 Stewart, 1990 Bhatia, 1997 Ng, 2001, On spectral clustering: Analysis and an algorithm M. Meilă, J. Shi, A random walks view of spectral segmentation, in: AI and STATISTICS (AISTATS) 2001 J.M. Anthonisse, The rush in a directed graph, Tech. rep., Stichting Mathematisch Centrum, 2e Boerhaavestraat 49 Amsterdam, The Netherlands, 1971 Brandes, 2001, A faster algorithm for betweenness centrality, J. Math. Sociol., 25, 163, 10.1080/0022250X.2001.9990249 Zhou, 2006, Notes on the calculation of node betweenness, Chin. Phys. Lett., 23, 2327, 10.1088/0256-307X/23/8/099 Newman, 2005, A measure of betweenness centrality based on random walks, Soc. Netw., 27, 39, 10.1016/j.socnet.2004.11.009 Newman, 2004, Analysis of weighted networks, Phys. Rev. E, 70, 056131, 10.1103/PhysRevE.70.056131 Tyler, 2003, Email as spectroscopy: Automated discovery of community structure within organizations, 81 Wilkinson, 2004, A method for finding communities of related genes, Proc. Natl. Acad. Sci. U.S.A., 101, 5241, 10.1073/pnas.0307740100 Rattigan, 2006, Using structure indices for efficient approximation of network properties, 357 Brandes, 2003, Experiments on graph clustering algorithms, 568 Holme, 2003, Subnetwork hierarchies of biochemical pathways, Bioinformatics, 19, 532, 10.1093/bioinformatics/btg033 Pinney, 2006, Betweenness-based decomposition methods for social and biological networks, 87 Gregory, 2007, An algorithm to find overlapping community structure in networks, 91 Watts, 1998, Collective dynamics of ‘small-world’ networks, Nature, 393, 440, 10.1038/30918 Castellano, 2004, Self-contained algorithms to detect communities in networks, Eur. Phys. J. B, 38, 311, 10.1140/epjb/e2004-00123-0 P. Zhang, J. Wang, X. Li, Z. Di, Y. Fan, The clustering coefficient and community structure of bipartite networks, eprint arXiv:0710.0117 Latora, 2001, Efficient behavior of small-world networks, Phys. Rev. Lett., 87, 198701, 10.1103/PhysRevLett.87.198701 Fortunato, 2004, Method to find community structures based on information centrality, Phys. Rev. E, 70, 056104, 10.1103/PhysRevE.70.056104 Vragović, 2006, Network community structure and loop coefficient method, Phys. Rev. E, 74, 016105, 10.1103/PhysRevE.74.016105 Newman, 2004, Fast algorithm for detecting community structure in networks, Phys. Rev. E, 69, 066133, 10.1103/PhysRevE.69.066133 Clauset, 2004, Finding community structure in very large networks, Phys. Rev. E, 70, 066111, 10.1103/PhysRevE.70.066111 Danon, 2006, The effect of size heterogeneity on community identification in complex networks, J. Stat. Mech., 11, 10 Pujol, 2006, Clustering algorithm for determining community structure in large networks, Phys. Rev. E, 74, 016107, 10.1103/PhysRevE.74.016107 Du, 2007, An algorithm for detecting community structure of social networks based on prior knowledge and modularity, Complexity, 12, 53, 10.1002/cplx.20166 K. Wakita, T. Tsurumi, Finding community structure in mega-scale social networks, eprint arXiv:cs/0702048 Blondel, 2008, Fast unfolding of communities in large networks, J. Stat. Mech., P10008 Schuetz, 2008, Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement, Phys. Rev. E, 77, 046112, 10.1103/PhysRevE.77.046112 Schuetz, 2008, Multistep greedy algorithm identifies community structure in real-world and computer-generated networks, Phys. Rev. E, 78, 026112, 10.1103/PhysRevE.78.026112 Noack, 2009, Multi-level algorithms for modularity clustering, 257 Xiang, 2009, Finding community structure based on subgraph similarity, vol. 207, 73 Mei, 2009, Revealing network communities through modularity maximization by a contraction-dilation method, New J. Phys., 11, 043025, 10.1088/1367-2630/11/4/043025 Guimerà, 2004, Modularity from fluctuations in random graphs and complex networks, Phys. Rev. E, 70, 025101 (R), 10.1103/PhysRevE.70.025101 Massen, 2005, Identifying communities within energy landscapes, Phys. Rev. E, 71, 046101, 10.1103/PhysRevE.71.046101 Medus, 2005, Detection of community structures in networks via global optimization, Physica A, 358, 593, 10.1016/j.physa.2005.04.022 Duch, 2005, Community detection in complex networks using extremal optimization, Phys. Rev. E, 72, 027104, 10.1103/PhysRevE.72.027104 S. White, P. Smyth, A spectral clustering approach to finding communities in graphs, in: Proceedings of SIAM International Conference on Data Mining, 2005, pp. 76–84 Newman, 2006, From the cover: Modularity and community structure in networks, Proc. Natl. Acad. Sci. USA, 103, 8577, 10.1073/pnas.0601602103 Lehmann, 2007, Deterministic modularity optimization, Eur. Phys. J. B, 60, 83, 10.1140/epjb/e2007-00313-2 Ruan, 2007, An efficient spectral algorithm for network community discovery and its applications to biological and social networks, 643 U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikolski, D. Wagner, On modularity — np-completeness and beyond. URL http://digbib.ubka.uni-karlsruhe.de/volltexte/documents/3255 Ye, 2008, Adaptive clustering algorithm for community detection in complex networks, Phys. Rev. E, 78, 046115, 10.1103/PhysRevE.78.046115 Kirkpatrick, 1983, Optimization by simulated annealing, Science, 220, 671, 10.1126/science.220.4598.671 Boettcher, 2001, Optimization with extremal dynamics, Phys. Rev. Lett., 86, 5211, 10.1103/PhysRevLett.86.5211 Richardson, 2009, Spectral tripartitioning of networks, Phys. Rev. E, 80, 036111, 10.1103/PhysRevE.80.036111 Sun, 2009, Improved community structure detection using a modified fine-tuning strategy, Europhys. Lett., 86, 28004, 10.1209/0295-5075/86/28004 Wang, 2008, A vector partitioning approach to detecting community structure in complex networks, Comput. Math. Appl., 55, 2746, 10.1016/j.camwa.2007.10.028 Demmel, 2000 Gleiser, 2003, Community structure in jazz, Adv. Complex Syst., 6, 565, 10.1142/S0219525903001067 Newman, 2001, The structure of scientific collaboration networks, Proc. Natl. Acad. Sci. USA, 98, 404, 10.1073/pnas.021544898 Agarwal, 2008, Modularity-maximizing network communities via mathematical programming, Eur. Phys. J. B, 66, 409, 10.1140/epjb/e2008-00425-1 Karloff, 1991 Xu, 2007, Finding community structures in complex networks using mixed integer optimisation, Eur. Phys. J. B, 60, 231, 10.1140/epjb/e2007-00331-0 Chen, 2008, Community structures of networks, Math. Comput. Sci., 1, 441, 10.1007/s11786-007-0035-1 Hillier, 2004 J.W. Berry, B. Hendrickson, R.A. LaViolette, V.J. Leung, C.A. Phillips, Community detection via facility location, eprint arXiv:0710.3800 Peterson, 1987, A mean field theory learning algorithm for neural networks, Complex Systems, 1, 995 Holland, 1992 M. Tasgin, A. Herdagdelen, H. Bingol, Community detection in complex networks using genetic algorithms, eprint arXiv:0711.0491 Liu, 2007, Effective algorithm for detecting community structure in complex networks based on GA and clustering, 657 Feng, 2007, A novel similarity-based modularity function for graph partitioning, Lect. Notes Comp. Sci., 4654, 385, 10.1007/978-3-540-74553-2_36 R. Ghosh, K. Lerman, Community detection using a measure of global influence, eprint arXiv:0805.4606 Y. Kim, S.-W. Son, H. Jeong, Link rank: Finding communities in directed networks, eprint arXiv:0902.3728 Shen, 2009, Detect overlapping and hierarchical community structure in networks, Physica A, 388, 1706, 10.1016/j.physa.2008.12.021 Nicosia, 2009, Extending the definition of modularity to directed graphs with overlapping communities, J. Stat. Mech., P03024 Shen, 2009, Quantifying and identifying the overlapping community structure in networks, J. Stat. Mech., P07042 Gaertler, 2007, Significance-driven graph clustering, vol. 4508, 11 Muff, 2005, Local modularity measure for network clusterizations, Phys. Rev. E, 72, 056107, 10.1103/PhysRevE.72.056107 Mezard, 1987 Arenas, 2008, Motif-based communities in complex networks, J. Phys. A, 41, 224001, 10.1088/1751-8113/41/22/224001 Milo, 2002, Network motifs: Simple building blocks of complex networks, Science, 298, 824, 10.1126/science.298.5594.824 Mantegna, 2000 Bansal, 2004, Correlation clustering, Mach. Learn., 56, 89, 10.1023/B:MACH.0000033116.57574.95 Gómez, 2009, Analysis of community structure in networks of correlated data, Phys. Rev. E, 80, 016114, 10.1103/PhysRevE.80.016114 T.D. Kaplan, S. Forrest, A dual assortative measure of community structure, eprint arXiv:0801.3290 Traag, 2009, Community detection in networks with positive and negative links, Phys. Rev. E, 80, 036115, 10.1103/PhysRevE.80.036115 Williams, 2000, Simple rules yield complex food webs, Nature, 404, 180, 10.1038/35004572 Guimerà, 2007, Module identification in bipartite and directed networks, Phys. Rev. E, 76, 036102, 10.1103/PhysRevE.76.036102 Barber, 2008, Searching for communities in bipartite networks, vol. 1021, 171 Reichardt, 2006, When are networks truly modular?, Physica D, 224, 20, 10.1016/j.physd.2006.09.009 Reichardt, 2007, Partitioning and modularity of graphs with arbitrary degree distribution, Phys. Rev. E, 76, 015102 (R), 10.1103/PhysRevE.76.015102 Fu, 1986, Application of statistical mechanics to NP-complete problems in combinatorial optimisation, J. Phys. A, 19, 1605, 10.1088/0305-4470/19/9/033 Sherrington, 1975, Solvable model of a spin-glass, Phys. Rev. Lett., 35, 1792, 10.1103/PhysRevLett.35.1792 Fortunato, 2007, Resolution limit in community detection, Proc. Natl. Acad. Sci. USA, 104, 36, 10.1073/pnas.0605965104 Guimerà, 2003, Self-similar community structure in a network of human interactions, Phys. Rev. E, 68, 065103 (R), 10.1103/PhysRevE.68.065103 Danon, 2005, Comparing community structure identification, J. Stat. Mech., P09008 Fortunato, 2007, Quality functions in community detection, vol. 6601, 660108 Li, 2008, Quantitative function for community detection, Phys. Rev. E, 77, 036109, 10.1103/PhysRevE.77.036109 Ruan, 2008, Identifying network communities with a high resolution, Phys. Rev. E, 77, 016104, 10.1103/PhysRevE.77.016104 Kumpula, 2007, Limited resolution in complex network community detection with Potts model approach, Eur. Phys. J. B, 56, 41, 10.1140/epjb/e2007-00088-4 J.W. Berry, B. Hendrickson, R.A. LaViolette, C.A. Phillips, Tolerating the community detection resolution limit with edge weighting, eprint arXiv:0903.1072 Eriksen, 2003, Modularity and extreme edges of the internet, Phys. Rev. Lett., 90, 148701, 10.1103/PhysRevLett.90.148701 Simonsen, 2004, Diffusion on complex networks: A way to probe their large-scale topological structures, Physica A, 336, 163, 10.1016/j.physa.2004.01.021 Slanina, 2005, Referee networks and their spectral properties, Acta Phys. Polon. B, 36, 2797 Mitrović, 2009, Spectral and dynamical properties in classes of sparse networks with mesoscopic inhomogeneities, Phys. Rev. E, 80, 026123, 10.1103/PhysRevE.80.026123 Simonsen, 2005, Diffusion and networks: A powerful combination!, Physica A, 357, 317, 10.1016/j.physa.2005.06.032 Alves, 2007, Unveiling community structures in weighted networks, Phys. Rev. E, 76, 036101, 10.1103/PhysRevE.76.036101 Capocci, 2005, Detecting communities in large networks, Physica A, 352, 669, 10.1016/j.physa.2004.12.050 Yang, 2008, Discovering global network communities based on local centralities, ACM Trans. Web, 2, 1, 10.1145/1326561.1326570 Bonacich, 1972, Factoring and weighting approaches to status scores and clique identification, J. Math. Sociol., 2, 113, 10.1080/0022250X.1972.9989806 Bonacich, 1987, Power and centrality: A family of measures, Amer. J. Sociol., 92, 1170, 10.1086/228631 Wu, 1982, The Potts model, Rev. Mod. Phys., 54, 235, 10.1103/RevModPhys.54.235 Blatt, 1996, Superparamagnetic clustering of data, Phys. Rev. Lett., 76, 3251, 10.1103/PhysRevLett.76.3251 Reichardt, 2004, Detecting Fuzzy community structures in complex networks with a Potts model, Phys. Rev. Lett., 93, 218701, 10.1103/PhysRevLett.93.218701 Ispolatov, 2006, Finding mesoscopic communities in sparse networks, J. Stat. Mech., P09014 Son, 2006, Random field Ising model and community structure in complex networks, Eur. Phys. J. B, 50, 431, 10.1140/epjb/e2006-00155-4 Middleton, 2002, Three-dimensional random-field Ising magnet: Interfaces, scaling, and the nature of states, Phys. Rev. B, 65, 134411, 10.1103/PhysRevB.65.134411 Noh, 2001, Disorder-driven critical behavior of periodic elastic media in a crystal potential, Phys. Rev. Lett., 87, 176102, 10.1103/PhysRevLett.87.176102 Noh, 2002, Numerical study of the disorder-driven roughening transition in an elastic manifold in a periodic potential, Phys. Rev. E, 66, 036117, 10.1103/PhysRevE.66.036117 Hughes, 1995 Zhou, 2003, Network landscape from a brownian particle’s perspective, Phys. Rev. E, 67, 041908, 10.1103/PhysRevE.67.041908 Zhou, 2004, Network brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities, Lect. Notes Comput. Sci., 3038, 1062, 10.1007/978-3-540-24688-6_137 Ward, 1963, Hierarchical grouping to optimize an objective function, J. Am. Assoc., 58, 236, 10.2307/2282967 Hu, 2008, Community detection by signaling on complex networks, Phys. Rev. E, 78, 016115, 10.1103/PhysRevE.78.016115 J.C. Delvenne, S.N. Yaliraki, M. Barahona, Stability of graph communities across time scales, eprint arXiv:0812.1811 Fiedler, 1975, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czechoslovak Math. J., 25, 619, 10.21136/CMJ.1975.101357 R. Lambiotte, J. Delvenne, M. Barahona, Laplacian dynamics and multiscale modular structure in networks, eprint arXiv:0812.1770 Weinan, 2008, Optimal partition and effective dynamics of complex networks, Proc. Natl. Acad. Sci. USA, 105, 7907, 10.1073/pnas.0707563105 S. van Dongen, Graph clustering by flow simulation, Ph.D. Thesis, Dutch National Research Institute for Mathematics and Computer Science, University of Utrecht, Netherlands, 2000 Pikovsky, 2001 Arenas, 2006, Synchronization reveals topological scales in complex networks, Phys. Rev. Lett., 96, 114102, 10.1103/PhysRevLett.96.114102 Kuramoto, 1984 Arenas, 2007, Synchronization and modularity in complex networks, Eur. Phys. J. Special Topics, 143, 19, 10.1140/epjst/e2007-00066-2 Boccaletti, 2007, Detecting complex network modularity by dynamical clustering, Phys. Rev. E, 75, 045102, 10.1103/PhysRevE.75.045102 Pluchino, 2005, Changing opinions in a changing world, Int. J. Mod. Phys. C, 16, 515, 10.1142/S0129183105007261 Li, 2008, Synchronization interfaces and overlapping communities in complex networks, Phys. Rev. Lett., 101, 168701, 10.1103/PhysRevLett.101.168701 Mackay, 2003 Winkler, 2003 Doreian, 2005 Burnham, 2002 Handcock, 2007, Model based clustering for social networks, J. Roy. Statist. Soc. A, 170, 1 Koskinen, 2007, Bayesian inference for dynamic social network data, J. Stat. Plan. Infer., 137, 3930, 10.1016/j.jspi.2007.04.011 Rhodes, 2007, Social network topology: A bayesian approach, J. Oper. Res. Soc., 58, 1605, 10.1057/palgrave.jors.2602352 Rowicka, 2004, Bayesian modeling of protein interaction networks, 283 Berg, 2006, Cross-species analysis of biological networks by bayesian alignment, Proc. Natl. Acad. Sci. USA, 103, 10967, 10.1073/pnas.0602294103 Hastings, 2006, Community detection as an inference problem, Phys. Rev. E, 74, 035102, 10.1103/PhysRevE.74.035102 Gallager, 1963 Newman, 2007, Mixture models and exploratory analysis in networks, Proc. Natl. Acad. Sci. USA, 104, 9564, 10.1073/pnas.0610537104 Dempster, 1977, Maximum likelihood from incomplete data via the EM algorithm, J. Roy. Stat. Soc. B, 39, 1 Snijders, 1997, Estimation and prediction for stochastic blockmodels for graphs with latent block structure, J. Classification, 14, 75, 10.1007/s003579900004 K. Nowicki, T.A.B. Snijders, Estimation and prediction for stochastic blockstructures, J. Am. Assoc. 96 (455) M. Mungan, J.J. Ramasco, Who is keeping you in that community? eprint arXiv:0809.1398 Vazquez, 2008, Population stratification using a statistical model on hypergraphs, Phys. Rev. E, 77, 066106, 10.1103/PhysRevE.77.066106 A. Vazquez, Bayesian approach to clustering real value, categorical and network data: Solution via variational methods, eprint arXiv:0805.2689 Jordan, 1999, An introduction to variational methods for graphical models, Mach. Learn., 37, 183, 10.1023/A:1007665907178 M.J. Beal, Variational algorithms for approximate bayesian inference, Ph.D. Thesis, Gatsby Computational Neuroscience Unit, University College London, 2003 Ramasco, 2008, Inversion method for content-based networks, Phys. Rev. E, 77, 036122, 10.1103/PhysRevE.77.036122 Ren, 2009, Simple probabilistic algorithm for detecting community structure, Phys. Rev. E, 79, 036111, 10.1103/PhysRevE.79.036111 J. Čopič, M.O. Jackson, A. Kirman, Identifying community structures from network data. URL http://www.hss.caltech.edu/~jernej/netcommunity.pdf Zanghi, 2008, Fast online graph clustering via Erdös-Rényi mixture, Pattern Recognit., 41, 3592, 10.1016/j.patcog.2008.06.019 Biernacki, 2000, Assessing a mixture model for clustering with the integrated completed likelihood, IEEE Trans. Pattern Anal. Mach. Intell., 22, 719, 10.1109/34.865189 Hofman, 2008, Bayesian Approach to Network Modularity, Phys. Rev. Lett., 100, 258701, 10.1103/PhysRevLett.100.258701 White, 1983, Graph and semigroup homomorphisms on networks and relations, Soc. Netw., 5, 193, 10.1016/0378-8733(83)90025-4 Everett, 1994, Regular equivalence: General theory, J. Math. Soc., 19, 29, 10.1080/0022250X.1994.9990134 Fienberg, 1981, Categorical data analysis of single sociometric relations, Sociol. Methodol., 12, 156, 10.2307/270741 Holland, 1983, Stochastic blockmodels: Some first steps, Soc. Netw., 5, 109, 10.1016/0378-8733(83)90021-7 Reichardt, 2007, Role models for complex networks, Eur. Phys. J. B, 60, 217, 10.1140/epjb/e2007-00340-y Akaike, 1974, A new look at the statistical model identification, IEEE Trans. Automat. Control, 19, 716, 10.1109/TAC.1974.1100705 Schwarz, 1978, Estimating the dimension of a model, Ann. Stat., 6, 461, 10.1214/aos/1176344136 Rissanen, 1978, Modelling by shortest data descriptions, Automatica, 14, 465, 10.1016/0005-1098(78)90005-5 Grünwald, 2005 Wallace, 1968, An information measure for classification, Comput. J., 11, 185, 10.1093/comjnl/11.2.185 Rosvall, 2007, An information-theoretic framework for resolving community structure in complex networks, Proc. Natl. Acad. Sci. USA, 104, 7327, 10.1073/pnas.0611034104 Sun, 2007, Graphscope: Parameter-free mining of large time-evolving graphs, 687 Huffman, 1952, A method for the construction of minimum-redundancy codes, Proc. IRE, 40, 1098, 10.1109/JRPROC.1952.273898 M. Rosvall, D. Axelsson, C.T. Bergstrom, The map equation, eprint arXiv:0906.1405 Chakrabarti, 2004, Autopart: Parameter-free graph partitioning and outlier detection, vol. 3202, 112 Ziv, 2005, Information-theoretic approach to network modularity, Phys. Rev. E, 71, 046117, 10.1103/PhysRevE.71.046117 N. Tishby, F. Pereira, W. Bialek, The information bottleneck method, in: Proceedings of the 37-th Annual Allerton Conference on Communication, Control and Computing, 1999, pp. 368–377 Raghavan, 2007, Near linear time algorithm to detect community structures in large-scale networks, Phys. Rev. E, 76, 036106, 10.1103/PhysRevE.76.036106 Tibély, 2008, On the equivalence of the label propagation method of community detection and a Potts model approach, Physica A, 387, 4982, 10.1016/j.physa.2008.04.024 Barber, 2009, Detecting network communities by propagating labels under constraints, Phys. Rev. E, 80, 026129, 10.1103/PhysRevE.80.026129 Leung, 2009, Towards real-time community detection in large networks, Phys. Rev. E, 79, 066107, 10.1103/PhysRevE.79.066107 Lancichinetti, 2008, Benchmark graphs for testing community detection algorithms, Phys. Rev. E, 78, 046110, 10.1103/PhysRevE.78.046110 Bagrow, 2005, Local method for detecting communities, Phys. Rev. E, 72, 046108, 10.1103/PhysRevE.72.046108 L. da Fontoura Costa, Hub-based community finding, eprint arXiv:cond-mat/0405022 Porter, 2007, Community structure in the United States House of Representatives, Physica A, 386, 414, 10.1016/j.physa.2007.07.039 Rodrigues, 2007, Fast community identification by hierarchical growth, Int. J. Mod. Phys. C, 18, 937, 10.1142/S0129183107011042 S. Papadopoulos, A. Skusa, A. Vakali, Y. Kompatsiaris, N. Wagner, Bridge bounding: A local approach for efficient community discovery in complex networks, eprint arXiv:0902.0871 Clauset, 2005, Finding local community structure in networks, Phys. Rev. E, 72, 026132, 10.1103/PhysRevE.72.026132 P. Hui, E. Yoneki, S.-Y. Chan, J. Crowcroft, Distributed community detection in delay tolerant networks, in: Proc. MobiArch, 2007 Eckmann, 2002, Curvature of co-links uncovers hidden thematic layers in the World Wide Web, Proc. Natl. Acad. Sci. USA, 99, 5825, 10.1073/pnas.032093399 Long, 2007, Community learning by graph approximation, 232 Wu, 2004, Finding communities in linear time: A physics approach, Eur. Phys. J. B, 38, 331, 10.1140/epjb/e2004-00125-x Orponen, 2005, Local clustering of large graphs by approximate Fiedler vectors, vol. 3503, 524 Ohkubo, 2006, Nonadditive volume and community detection problem in complex networks, J. Phys. Soc. Japan, 75, 115001-1, 10.1143/JPSJ.75.115001 Zarei, 2009, Eigenvectors of network complement reveal community structure more accurately, Physica A, 388, 1721, 10.1016/j.physa.2009.01.007 Condon, 2001, Algorithms for graph partitioning on the planted partition model, Random Struct. Algor., 18, 116, 10.1002/1098-2418(200103)18:2<116::AID-RSA1001>3.0.CO;2-2 Gudkov, 2008, Community detection in complex networks by dynamical simplex evolution, Phys. Rev. E, 78, 016113, 10.1103/PhysRevE.78.016113 M.J. Krawczyk, K. Kulakowski, Communities in networks — A continuous approach, eprint arXiv:0709.0923 Krawczyk, 2008, Differential equations as a tool for community identification, Phys. Rev. E, 77, 065701, 10.1103/PhysRevE.77.065701 A. Narasimhamurthy, D. Greene, N. Hurley, P. Cunningham, Community finding in large social networks through problem decomposition, in: Proc. 19th Irish Conference on Artificial Intelligence and Cognitive Science, AICS’08, 2008 Dhillon, 2007, Weighted graph cuts without eigenvectors: A multilevel approach, IEEE Trans. Pattern Anal. Mach. Intell., 29, 1944, 10.1109/TPAMI.2007.1115 Everett, 1998, Analyzing clique overlap, Connections, 21, 49 Derényi, 2005, Clique percolation in random networks, Phys. Rev. Lett., 94, 160202, 10.1103/PhysRevLett.94.160202 Adamcsek, 2006, Cfinder: Locating cliques and overlapping modules in biological networks, Bioinformatics, 22, 1021, 10.1093/bioinformatics/btl039 Farkas, 2007, Weighted network modules, New J. Phys., 9, 180, 10.1088/1367-2630/9/6/180 Lehmann, 2008, Biclique communities, Phys. Rev. E, 78, 016108, 10.1103/PhysRevE.78.016108 Peeters, 2003, The maximum edge biclique problem is NP-complete, Discrete Appl. Math., 131, 651, 10.1016/S0166-218X(03)00333-0 Du, 2008, Overlapping community detection in bipartite networks, 176 Kumpula, 2008, Sequential algorithm for fast clique percolation, Phys. Rev. E, 78, 026109, 10.1103/PhysRevE.78.026109 Baumes, 2005, Finding communities by clustering a graph into overlapping subgraphs, 97 J. Baumes, M. Goldberg, M. Magdon-Ismail, Efficient identification of overlapping communities, in: IEEE International Conference on Intelligence and Security Informatics, ISI, 2005, pp. 27–36 Zhang, 2007, Identification of overlapping community structure in complex networks using fuzzy c-means clustering, Physica A, 374, 483, 10.1016/j.physa.2006.07.023 Nepusz, 2008, Fuzzy communities and the concept of bridgeness in complex networks, Phys. Rev. E, 77, 016107, 10.1103/PhysRevE.77.016107 Evans, 2009, Line graphs, link partitions, and overlapping communities, Phys. Rev. E, 80, 016105, 10.1103/PhysRevE.80.016105 Y.-Y. Ahn, J.P. Bagrow, S. Lehmann, Communities and hierarchical organization of links in complex networks, eprint arXiv:0903.3178 Balakrishnan, 1997 Gregory, 2009, Finding overlapping communities using disjoint community detection algorithms, vol. 207, 47 Heimo, 2008, Detecting modules in dense weighted networks with the Potts method, J. Stat. Mech., P08007, 10.1088/1742-5468/2008/08/P08007 P. Pons, Post-processing hierarchical community structures: Quality improvements and multi-scale view, eprint arXiv:cs/0608050 Glover, 1986, Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res., 13, 533, 10.1016/0305-0548(86)90048-1 Kumpula, 2007, Limited resolution and multiresolution methods in complex network community detection, vol. 6601, 660116 P. Ronhovde, Z. Nussinov, A highly accurate and resolution-limit-free Potts model for community detection, eprint arXiv:0803.2548 Ronhovde, 2009, Multiresolution community detection for megascale networks by information-based replica correlations, Phys. Rev. E, 80, 016109, 10.1103/PhysRevE.80.016109 Sales-Pardo, 2007, Extracting the hierarchical organization of complex systems, Proc. Natl. Acad. Sci. USA, 104, 15224, 10.1073/pnas.0703740104 Barrat, 2004, The architecture of complex weighted networks, Proc. Natl. Acad. Sci. USA, 101, 3747, 10.1073/pnas.0400087101 Itzkovitz, 2005, Coarse-graining and self-dissimilarity of complex networks, Phys. Rev. E, 71, 016127, 10.1103/PhysRevE.71.016127 Guimerà, 2007, A network-based method for target selection in metabolic networks, Bioinformatics, 23, 1616, 10.1093/bioinformatics/btm150 Clauset, 2007, Structural inference of hierarchies in networks, vol. 4503, 1 Clauset, 2008, Hierarchical structure and the prediction of missing links in networks, Nature, 453, 98, 10.1038/nature06830 Newman, 1999 Liben-Nowell, 2003, The link prediction problem for social networks, 556 Kumar, 2003, On the bursty evolution of blogspace, 568 Kumar, 2006, Structure and evolution of online social networks, 611 Leskovec, 2005, Graphs over time: Densification laws, shrinking diameters and possible explanations, 177 Leskovec, 2008, Microscopic evolution of social networks, 462 Palla, 2007, Quantifying social group evolution, Nature, 446, 664, 10.1038/nature05670 Hopcroft, 2004, Tracking evolving communities in large linked networks, Proc. Natl. Acad. Sci. USA, 101, 5249, 10.1073/pnas.0307750100 Giles, 1998, CiteSeer: An automatic citation indexing system, 89 Baeza-Yates, 1999 Asur, 2007, An event-based framework for characterizing the evolutionary behavior of interaction graphs, 913 Fenn, 2009, Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007–2008 credit crisis, Chaos, 19, 033119, 10.1063/1.3184538 Chakrabarti, 2006, Evolutionary clustering, 554 Chi, 2007, Evolutionary spectral clustering by incorporating temporal smoothness, 153 Lin, 2008, Facetnet: a framework for analyzing communities and their evolutions in dynamic networks, 685 Kullback, 1951, On information and sufficiency, Ann. Math. Statist., 22, 49, 10.1214/aoms/1177729694 M.-S. Kim, J. Han, A particle-and-density based evolutionary clustering method for dynamic networks, in: Proceedings of 2009 Int. Conf. on Very Large Data Bases, Lyon, France, 2009 Backstrom, 2006, Group formation in large social networks: membership, growth, and evolution, 44 Gfeller, 2005, Finding instabilities in the community structure of complex networks, Phys. Rev. E, 72, 056135, 10.1103/PhysRevE.72.056135 Karrer, 2008, Robustness of community structure in networks, Phys. Rev. E, 77, 046119, 10.1103/PhysRevE.77.046119 M. Rosvall, C.T. Bergstrom, Mapping change in large networks, eprint arXiv:0812.1242 Efron, 1993 Earl, 2005, Parallel tempering: Theory, applications, and new perspectives, Phys. Chem. Chem. Phys., 7, 3910, 10.1039/b509983h Bianconi, 2009, Assessing the relevance of node features for network structure, Proc. Natl. Acad. Sci. USA, 106, 11433, 10.1073/pnas.0811511106 Bianconi, 2008, The entropy of randomized network ensembles, Europhys. Lett., 81, 28005, 10.1209/0295-5075/81/28005 Bianconi, 2008, Entropies of complex networks with hierarchically constrained topologies, Phys. Rev. E, 78, 016114, 10.1103/PhysRevE.78.016114 A. Lancichinetti, F. Radicchi, J.J. Ramasco, Statistical significance of communities in networks, eprint arXiv:0907.3708 David, 2003 Beirlant, 2004 Lancichinetti, 2009, Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities, Phys. Rev. E, 80, 016118, 10.1103/PhysRevE.80.016118 Reichardt, 2008, (Un)detectable cluster structure in sparse networks, Phys. Rev. Lett., 101, 078701, 10.1103/PhysRevLett.101.078701 Mézard, 2003, The cavity method at zero temperature, J. Stat. Phys., 111, 1, 10.1023/A:1022221005097 Fan, 2007, Accuracy and precision of methods for community identification in weighted networks, Physica A, 377, 363, 10.1016/j.physa.2006.11.036 J.P. Bagrow, Evaluating local community methods in networks, J. Stat. Mech. P05001 Barabási, 1999, Emergence of scaling in random networks, Science, 286, 509, 10.1126/science.286.5439.509 Watts, 2003 Sawardecker, 2009, Detection of node group membership in networks with group overlap, Eur. Phys. J. B, 67, 277, 10.1140/epjb/e2008-00418-0 Meilă, 2007, Comparing clusterings — An information based distance, J. Multivariate Anal., 98, 873, 10.1016/j.jmva.2006.11.013 Wallace, 1983, A method for comparing two hierarchical clusterings: Comment, J. Am. Assoc., 78, 569, 10.2307/2288118 Fowlkes, 1983, A method for comparing two hierarchical clusterings, J. Am. Assoc., 78, 553, 10.2307/2288117 Rand, 1971, Objective criteria for the evaluation of clustering methods, J. Am. Assoc., 66, 846, 10.2307/2284239 Mirkin, 1996 Meilă, 2001, An experimental comparison of model-based clustering methods, Mach. Learn., 42, 9, 10.1023/A:1007648401407 S. van Dongen, Performance criteria for graph clustering and Markov cluster experiments, Tech. rep., National Research Institute for Mathematics and Computer Science in the Netherlands, Amsterdam, The Netherlands, 2000 Gustafsson, 2006, Comparison and validation of community structures in complex networks, Physica A, 367, 559, 10.1016/j.physa.2005.12.017 Gusfield, 2002, Partition-distance: A problem and class of perfect graphs arising in clustering, Inform. Process. Lett., 82, 159, 10.1016/S0020-0190(01)00263-0 Stanley, 1997 Zhang, 2006, The analysis and dissimilarity comparison of community structure, Physica A, 367, 577, 10.1016/j.physa.2005.11.018 A.L. Traud, E.D. Kelsic, P.J. Mucha, M.A. Porter, Community structure in online collegiate social networks, eprint arXiv:0809.0690 Donetti, 2005, Improved spectral algorithm for the detection of network communities, vol. 779, 104 A. Lancichinetti, S. Fortunato, Community detection algorithms: A comparative analysis, eprint arXiv:0908.1062 D. Delling, M. Gaertler, R. Görke, Z. Nikoloski, D. Wagner, How to evaluate clustering techniques., Tech. rep., Universität Karlsruhe, Germany, 2007 J. Leskovec, K.J. Lang, A. Dasgupta, M.W. Mahoney, Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters, eprint arXiv:0810.1355 Dunbar, 1998 Guimerà, 2005, Cartography of complex networks: Modules and universal roles, J. Stat. Mech., P02001 Junker, 2008 Dunn, 2005, The use of edge-betweenness clustering to investigate biological function in protein interaction networks, BMC Bioinf., 6, 39, 10.1186/1471-2105-6-39 Farutin, 2006, Edge-count probabilities for the identification of local protein communities and their organization, Proteins, 62, 800, 10.1002/prot.20799 Sen, 2006, Functional clustering of yeast proteins from the protein–protein interaction network, BMC Bioinf., 7, 355, 10.1186/1471-2105-7-355 A.C.F. Lewis, N.S. Jones, M.A. Porter, C.M. Deane, The function of communities in protein interaction networks, eprint arXiv:0904.0989 Ashburner, 2000, Gene ontology: Tool for the unification of biology, Nature Genetics, 25, 25, 10.1038/75556 K. Yuta, N. Ono, Y. Fujiwara, A gap in the community-size distribution of a large-scale social networking site, eprint arXiv:physics/0701168 de Solla Price, 1965, Networks of scientific papers, Science, 169, 510, 10.1126/science.149.3683.510 Reichardt, 2007, Clustering of sparse data via network communities—a prototype study of a large online market, J. Stat. Mech., 2007, P06016, 10.1088/1742-5468/2007/06/P06016 R.K.-X. Jin, D.C. Parkes, P.J. Wolfe, Analysis of bidding networks in ebay: Aggregate preference identification through community detection, in: Proc. AAAI Workshop on Plan, Activity and Intent Recognition, PAIR, 2007, pp. 66–73 Porter, 2005, A network analysis of committees in the US House of Representatives, Proc. Natl. Acad. Sci. USA, 102, 7057, 10.1073/pnas.0500191102 Zhang, 2008, Community structure in congressional cosponsorship networks, Physica A, 387, 1705, 10.1016/j.physa.2007.11.004 Mantegna, 1999, Hierarchical structure in financial markets, Eur. Phys. J. B, 11, 193, 10.1007/s100510050929 Bonanno, 2000, Taxonomy of stock market indices, Phys. Rev. E, 62, R7615, 10.1103/PhysRevE.62.R7615 Bonanno, 2003, Topology of correlation-based minimal spanning trees in real and model markets, Phys. Rev. E, 68, 046130, 10.1103/PhysRevE.68.046130 Onnela, 2002, Dynamic asset trees and portfolio analysis, Eur. Phys. J. B, 30, 285, 10.1140/epjb/e2002-00380-9 Onnela, 2003, Dynamics of market correlations: Taxonomy and portfolio analysis, Phys. Rev. E, 68, 056110, 10.1103/PhysRevE.68.056110 A.E. Allahverdyan, A. Galstyan, Community detection with and without prior information, eprint arXiv:0907.4803 Chung, 1997 Barahona, 2002, Synchronization in small-world systems, Phys. Rev. Lett., 89, 054101, 10.1103/PhysRevLett.89.054101 Nishikawa, 2003, Heterogeneity in oscillator networks: Are smaller worlds easier to synchronize?, Phys. Rev. Lett., 91, 014101, 10.1103/PhysRevLett.91.014101 Solomonoff, 1951, Connectivity of random nets, Bull. Math. Biophys., 13, 107, 10.1007/BF02478357 Milgram, 1967, The small world problem, Psychol. Today, 2, 60 Travers, 1969, An experimental study of the small world problem, Sociometry, 32, 425, 10.2307/2786545 Albert, 2000, Error and attack tolerance of complex networks, Nature, 406, 378, 10.1038/35019019 Cohen, 2000, Resilience of the internet to random breakdowns, Phys. Rev. Lett., 85, 4626, 10.1103/PhysRevLett.85.4626 Pastor-Satorras, 2001, Epidemic spreading in scale-free networks, Phys. Rev. Lett., 86, 3200, 10.1103/PhysRevLett.86.3200 de Solla Price, 1976, A general theory of bibliometric and other cumulative advantage processes, J. Am. Soc. Inform. Sci., 27, 292, 10.1002/asi.4630270505 Simon, 1955, On a class of skew distribution functions, Biometrika, 42, 425, 10.1093/biomet/42.3-4.425