A classification for community discovery methods in complex networks. (English) Zbl 07260300
Summary: Many real-world networks are intimately organized according to a community structure. Much research effort has been devoted to develop methods and algorithms that can efficiently highlight this hidden structure of a network, yielding a vast literature on what is called today community detection. Since network representation can be very complex and can contain different variants in the traditional graph model, each algorithm in the literature focuses on some of these properties and establishes, explicitly or implicitly, its own definition of community. According to this definition, each proposed algorithm then extracts the communities, which typically reflect only part of the features of real communities. The aim of this survey is to provide a ‘user manual’ for the community discovery problem. Given a meta definition of what a community in a social network is, our aim is to organize the main categories of community discovery methods based on the definition of community they adopt. Given a desired definition of community and the features of a problem (size of network, direction of edges, multidimensionality, and so on) this review paper is designed to provide a set of approaches that researchers could focus on. The proposed classification of community discovery methods is also useful for putting into perspective the many open directions for further research.
Keywords:
community discovery; social network; groups; complex network; graph partitioning; graph clustering; graph mining; information propagationReferences:
| [1] | G. W. Flake, S. Lawrence, C. L. Giles, and F. M. Coetzee, Self-organization and identification of web communities, IEEE Comput 35 (2002), 66-71. |
| [2] | R. Guimera and L. A. N. Amaral, Functional cartography of complex metabolic networks, Nature 433(7028) (2005), 895-900. |
| [3] | G. Palla, I. Derenyi, I. Farkas, and T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society, Nature 435 (2005), 814-818. |
| [4] | M. Girvan and M. E. J. Newman, Community structure in social and biological networks, Proc Natl Acad Sci U S A 99 (2002), 7821. · Zbl 1032.91716 |
| [5] | X. Yan and J. Han, gspan: Graph-based substructure pattern mining, In IEEE International Conference on Data Mining, 2002. |
| [6] | S. Fortunato, Community detection in graphs, Phys Rep 486(3-5) (2010), 175-174. |
| [7] | M. E. J. Newman and E. A. Leicht, Mixture models and exploratory analysis in networks, Proc Natl Acad Sci 104 (2007), 9564-9569. · Zbl 1155.91026 |
| [8] | L. Tang, H. Liu, J. Zhang, and Z. Nazeri, Community evolution in dynamic multi-mode networks, KDD ’08: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, New York, NY, ACM, 2008, 677-685. |
| [9] | A. Goyal, F. Bonchi, and L. V. Lakshmanan, Discovering leaders from community actions, CIKM ’08: Proceeding of |
| [10] | D. Chakrabarti, R. Kumar, and A. Tomkins, Evolutionary clustering, KDD ’06: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2006, 554-560. |
| [11] | B. Long, X. Wu, Z. M. Zhang, and P. S. Yu, Unsupervised learning on k-partite graphs, KDD ’06: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2006, 317-326. |
| [12] | L. Tang and H. Liu, Relational learning via latent social dimensions, KDD ’09: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2009, 817-826. |
| [13] | L. Tang, X. Wang, and H. Liu, Uncovering groups via heterogeneous interaction analysis, Miami, Florida, ICDM, IEEE, 2009. |
| [14] | A. Banerjee, S. Basu, and S. Merugu, Multi-way clustering on relation graphs, Minneapolis, Minnesota, SDM, SIAM, 2007. |
| [15] | C. Kemp, J. B. Tenenbaum, T. L. Griffiths, T. Yamada, and N. Ueda, Learning systems of concepts with an infinite relational model, AAA I’06: Proceedings of the 21st National Conference on Artificial Intelligence, Boston, MA, AAAI Press, 2006, 381-388. |
| [16] | L. Friedland and D. Jensen, Finding tribes: identifying close-knit individuals from employment patterns, KDD ’07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2007, 290-299. |
| [17] | D. Chakrabarti, Autopart: parameter-free graph partitioning and outlier detection, PKDD ’04: Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, New York, NY, Springer-Verlag New York, Inc., 2004, 112-124. |
| [18] | J. Ferlez, C. Faloutsos, J. Leskovec, D. Mladenic, and M. Grobelnik, Monitoring network evolution using MDL, Int Conf Data Eng 0 (2008), 1328-1330. |
| [19] | S. Papadimitriou, J. Sun, C. Faloutsos, and P. S. Yu, Hierarchical, parameter-free community discovery, ECML PKDD ’08: Proceedings of the European conference on Machine Learning and Knowledge Discovery in Databases—Part II, Berlin, Heidelberg, Springer-Verlag, 2008, 170-187. |
| [20] | A. Clauset, M. E. J. Newman, and C. Moore, Finding community structure in very large networks, Phys Rev E 70 (2004), 066111. |
| [21] | Y.-R. Lin, J. Sun, P. Castro, R. Konuru, H. Sundaram, and A. Kelliher, Metafac: community discovery via relational hypergraph factorization, KDD ’09: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2009, 527-536. |
| [22] | J. M. Hofman, and C. H. Wiggins, A bayesian approach to network modularity, Phys Rev Lett 100 (2008), 258-701. |
| [23] | J. Baumes, M. Goldberg, and M. Magdon-ismail, Efficient identification of overlapping communities, In IEEE International Conference on Intelligence and Security Informatics (ISI), 2005, 27-36. |
| [24] | S. E. Schaeffer, Stochastic local clustering for massive graphs, Proceedings of the Ninth Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD-05), |
| [25] | S. Gregory, A fast algorithm to find overlapping communities in networks, ECML PKDD ’08: Proceedings of the 2008 European Conference on Machine Learning and Knowledge Discovery in Databases-Part I, Berlin, Heidelberg, Springer-Verlag, 2008, 408-423. |
| [26] | J. Bagrow and E. Bollt, A local method for detecting communities, Phys Rev E 72 (2005), 46-108. |
| [27] | A. Lancichinetti, S. Fortunato, and J. Kertesz, Detecting the overlapping and hierarchical community structure of complex networks, New J Phys 11 (2009), 033015. |
| [28] | U. N. Raghavan, R. Albert, and S. Kumara, Near linear time algorithm to detect community structures in largescale networks, Phys Rev E 76 (2007), 036106. |
| [29] | C. Tantipathananandh, T. Berger-Wolf, and D. Kempe, A framework for community identification in dynamic social networks, KDD ’07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2007, 717-726. |
| [30] | F. Wu and B. A. Huberman, Finding communities in linear time: a physics approach, Eur Phys J B 38(2) (2004), 331-338. |
| [31] | M. Goldberg, S. Kelley, M. Magdon-Ismail, K. Mertsalov, and W. A. Wallace, Communication dynamics of blog networks, In The 2nd SNA-KDD Workshop ’08 (SNAKDD’08), August 2008. |
| [32] | E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing, Mixed membership stochastic blockmodels, J Mach Learn Res 9 (2007), 1981. · Zbl 1225.68143 |
| [33] | D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393(6684) (1998), 440-442. · Zbl 1368.05139 |
| [34] | P. Pons, and M. Latapy, Computing communities in large networks using random walks, J Graph Algor Appl 3733 (2006), 284-293. · Zbl 1161.68694 |
| [35] | F. Wei, W. Qian, C. Wang, and A. Zhou, Detecting overlapping community structures in networks, World Wide Web 12(2) (2009), 235-261. |
| [36] | S. Lehmann, M. Schwartz, and L. K. Hansen, Bi-clique communities, Phys Rev 78 (2008), 016108. |
| [37] | M. Kuramochi and G. Karypis, Finding frequent patterns in a large sparse graph, Data Min Knowl Discov 11(3) (2005), 243-271. |
| [38] | C. Komusiewicz, F. H¨uffner, H. Moser, and R. Niedermeier, Isolation concepts for efficiently enumerating dense subgraphs, Theor Comput Sci 410(38-40) (2009), 3640-3654. · Zbl 1171.68030 |
| [39] | C. Bron and J. Kerbosch, Algorithm 457: finding all cliques of an undirected graph, Commun ACM 16(9) (1973), 575-577. · Zbl 0261.68018 |
| [40] | T. S. Evans and R. Lambiotte, Line graphs, link partitions and overlapping communities, Phys Rev E 80 (2009), 016105. |
| [41] | Y.-Y. Ahn, J. P. Bagrow, and S. Lehmann, Link communities reveal multi-scale complexity in networks, Nature 466 (2010), 761-764. |
| [42] | S. Fortunato and M. Barthelemy, Resolution limit in community detection, Proc Natl Acad Sci 104 (2007), 36-41. |
| [43] | T. Eliassi-Rad, K. Henderson, S. Papadimitriou, and C. Faloutsos, A hybrid community discovery framework for |
| [44] | D. Cai, Z. Shao, X. He, X. Yan, and J. Han, Community mining from multi-relational networks, In Proceedings of the 2005 European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD’05), (Porto, Portugal), 2005. |
| [45] | M. Szell, R. Lambiotte, and S. Thurner, Trade, conflict and sentiments: multi-relational organization of large-scale social networks, arXiv.org, 1003.5137, 2010. |
| [46] | J. Leskovec, D. Huttenlocher, and J. Kleinberg, Predicting positive and negative links in online social networks, WWW, ACM, 2010, 641-650. |
| [47] | M. Berlingerio, M. Coscia, F. Giannotti, A. Monreale, and D. Pedreschi, Foundations of multidimensional network analysis, In ASONAM, IEEE, 2011, in press. |
| [48] | J. Rissanen, Modelling by the shortest data description, Automatica 14 (1978), 465-471. · Zbl 0418.93079 |
| [49] | P. D. Gr¨unwald, The Minimum Description Length Principle, vol. 1, MIT Press Books, Boston, MA, The MIT Press, 2007. |
| [50] | J. Kleinberg, An impossibility theorem for clustering, In Advances in Neural Information Processing Systems, S. Becker, S. Thrun, and K. Obermayer, eds. MIT Press, 2002, 446-453. |
| [51] | B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, Bell Syst Tech J 49(1) (1970), 291-307. · Zbl 0333.05001 |
| [52] | A. Pothen, H. D. Simon, and K.-P. Liou, Partitioning sparse matrices with eigenvectors of graphs, SIAM J Matrix Anal Appl 11(3) (1990), 430-452. · Zbl 0711.65034 |
| [53] | S. P. Borgatti and M. G. Everett, Graph colorings and power in experimental exchange networks, Social Netw 14(3-4) (1992), 287-308. |
| [54] | M. G. Everett and S. P. Borgatti, Exact colorations of graphs and digraphs, Social Netw 18(4) (1996), 319-331. |
| [55] | P. Doreian, V. Batagelj, and A. Ferligoj, Generalized Blockmodeling (Structural Analysis in the Social Sciences), Cambridge, UK, Cambridge University Press, 2004. · Zbl 1181.68106 |
| [56] | R. Lambiotte, J. Delvenne, and M. Barahona, Laplacian dynamics and multiscale modular structure in networks, ArXiv e-prints, 2008. |
| [57] | J. Reichardt and S. Bornholdt, Statistical mechanics of community detection, Phys Rev E 74 (2006), 016110. · Zbl 1459.91116 |
| [58] | L. Kaufman and P. J. Rousseeuw, Finding groups in data: an introduction to cluster analysis, Hoboken, NJ, John Wiley, 1990. · Zbl 1345.62009 |
| [59] | I. S. Dhillon, S. Mallela, and D. S. Modha, Informationtheoretic co-clustering, KDD ’03: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2003, 89-98. |
| [60] | D. Chakrabarti, S. Papadimitriou, D. S. Modha, and C. Faloutsos, Fully automatic cross-associations, KDD ’04: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2004, 79-88. |
| [61] | B. Long, Z. M. Zhang, X. W´u, and P. S. Yu, Spectral clustering for multi-type relational data, ICML ’06: Proceedings of the 23rd International Conference on Machine Learning, New York, NY, ACM, 2006, 585-592. |
| [62] | S. C. Madeira and A. L. Oliveira, Biclustering algorithms for biological data analysis: a survey, IEEE/ACM Trans Comput Biol Bioinform 1(1) (2004), 24-45. |
| [63] | P. Hoff, A. Raftery, and M. Handcock, Latent space approaches to social network analysis, J Am Stat Assoc 97 (2002), 1090-1098. · Zbl 1041.62098 |
| [64] | T. M. Cover and J. A. Thomas, Elements of Information Theory, Hoboken, NJ, Wiley-Interscience, 1991. · Zbl 0762.94001 |
| [65] | P. Grunwald, A tutorial introduction to the minimum description length principle, 2004. |
| [66] | D. H. Fisher, Knowledge acquisition via incremental conceptual clustering, Mach Learn 2 (1987), 139-172. |
| [67] | C. C. Aggarwal, J. Han, J. Wang, and P. S. Yu, A framework for clustering evolving data streams,, VLDB ’2003: Proceedings of the 29th International Conference on Very Large Data Bases, VLDB Endowment, 2003, 81-92. |
| [68] | H. Koga, T. Ishibashi, and T. Watanabe, Fast agglomerative hierarchical clustering algorithm using locality-sensitive hashing, Knowl Inf Syst 12(1) (2007), 25-53. · Zbl 1110.68452 |
| [69] | Y.-R. Lin, Y. Chi, S. Zhu, H. Sundaram, and B. L. Tseng, Facetnet: a framework for analyzing communities and their evolutions in dynamic networks, WWW ’08: Proceeding of the 17th International Conference on World Wide Web, New York, NY, ACM, 2008, 685-694. |
| [70] | M.-S. Kim and J. Han, A particle-and-density based evolutionary clustering method for dynamic networks, Proc VLDB Endow 2(1) (2009), 622-633. |
| [71] | B. Gao, T.-Y. Liu, X. Zheng, Q.-S. Cheng, and W.-Y. Ma, Consistent bipartite graph co-partitioning for star-structured high-order heterogeneous data co-clustering, KDD ’05: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, New York, NY, ACM, 2005, 41-50. |
| [72] | A. Banerjee, S. Merugu, I. Dhillon, and J. Ghosh, Clustering with Bregman Divergences, J Mach Learn Res 6 (2004), 234-245. · Zbl 1190.62117 |
| [73] | H. Cho, I. Dhillon, Y. Guan, and S. Sra, Minimum sum squared residue co-clustering of gene expression data, SDM, Orlando, Florida, USA, SIAM, 2004. |
| [74] | A. Banerjee, I. Dhillon, J. Ghosh, S. Merugu, and D. S. Modha, A generalized maximum entropy approach to bregman co-clustering and matrix approximation, In KDD, 2004, 509-514. · Zbl 1222.68139 |
| [75] | M. Mcpherson, L. S. Lovin, and J. M. Cook, Birds of a feather: Homophily in social networks, Annu Rev Sociol 27(1) (2001), 415-444. |
| [76] | L. Tang, S. Rajan, and V. K. Narayanan, Large scale multi-label classification via metalabeler, WWW ’09: Proceedings of the 18th International Conference on World Wide Web, New York, NY, ACM, 2009, 211-220. |
| [77] | I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun, Support vector machine learning for interdependent and structured output spaces, ICML, Banff, Alberta, Canada, ACM, 2004. · Zbl 1222.68321 |
| [78] | L. Tang and H. Liu, Scalable learning of collective behavior based on sparse social dimensions, In CIKM, 2009. |
| [79] | L. Tang and H. Liu, Uncovering cross-dimension group structures in multi-dimensional networks, In SDM workshop on Analysis of Dynamic Networks, 2009. |
| [80] | G. H. Golub and C. F. V. Loan, Matrix Computations, Baltimore, MD, Johns Hopkins Studies in Mathematical Sciences, 1989. · Zbl 0733.65016 |
| [81] | J. Kettenring, Canonical analysis of several sets of variables, Biometrika 58(3) (1971), 433-451. · Zbl 0225.62072 |
| [82] | J. Pitman, Combinatorial stochastic processes, Berlin, Springer-Verlag, 2006. · Zbl 1103.60004 |
| [83] | S. Papadimitriou, A. Gionis, P. Tsaparas, R. A. V¨ais¨anen, H. Mannila, and C. Faloutsos, Parameter-free spatial data mining using mdl, IEEE Int Conf Data Mining 0 (2005), 346-353. |
| [84] | C. C. Aggarwal, J. Han, J. Wang, P. S. Yu, T. J. Watson, and R. Ctr, A framework for projected clustering of high dimensional data streams, In Proceedings of VLDB, 2004, 852-863. |
| [85] | J. Sun, C. Faloutsos, S. Papadimitriou, and P. S. Yu, Graphscope: parameter-free mining of large time-evolving graphs, KDD ’07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2007, 687-696. |
| [86] | M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks, Phys Rev E 69 (2004), 026113. |
| [87] | B. H. Good, Y.-A. de Montjoye, and A. Clauset, The performance of modularity maximization in practical contexts, Physical Review E 4 (2010), 046106. |
| [88] | M. E. J. Newman, Finding community structure in networks using the eigenvectors of matrices, Phys Rev E 74 (2006), 036104. |
| [89] | P. J. Mucha, T. Richardson, K. Macon, M. A. Porter, and J. Onnela, Community Structure in Time-Dependent, Multiscale, and Multiplex Networks, Science 328 (2010), 876-878. · Zbl 1226.91056 |
| [90] | M. Berlingerio, M. Coscia, and F. Giannotti, Finding and characterizing communities in multidimensional networks, ASONAM, Kaohsiung, Taiwan, IEEE, 2011. |
| [91] | M. Berlingerio, M. Coscia, and F. Giannotti, Finding redundant and complementary communities in multidimensional networks, CIKM, Glasgow, Scotland, ACM, 2011, in press. |
| [92] | M. E. J. Newman, Fast algorithm for detecting community structure in networks, Phys Rev E 69 (2004), 066133. |
| [93] | E. A. Leicht, and M. E. J. Newman, Community structure in directed networks, Phy Rev Lett 100 (2008), 118703. |
| [94] | M. E. J. Newman, Modularity and community structure in networks, Proc Natl Acad Sci U S A 103 (2006), 8577. |
| [95] | V. Nicosia, G. Mangioni, V. Carchiolo, and M. Malgeri, Extending the definition of modularity to directed graphs with overlapping communities, J Stat Mech 3 (2009), P03024. |
| [96] | G. Agarwal and D. Kempe, Modularity-maximizing graph communities via mathematical programming, Eur Phys J B 66(2008), (3) 409-418. · Zbl 1188.90262 |
| [97] | J. Duch and A. Arenas, Community detection in complex networks using extremal optimization, Phys Rev E 72 (2005), 027104. |
| [98] | P. Bak and K. Sneppen, Punctuated equilibrium and criticality in a simple model of evolution, Phys Rev Lett 71 (1993), 4083-4086. |
| [99] | S. Boettcher and A. G. Percus, Optimization with extremal dynamics, Phys Rev Lett 86 (2001), 5211-5214. |
| [100] | A. Arenas, J. Duch, A. Fernandez, and S. Gomez, Size reduction of complex networks preserving modularity, New J Phys 9 (2007), 176. |
| [101] | R. Guimera and L. A. Amaral, Cartography of complex networks: modules and universal roles, J Stat Mech: Theory Exper 2005 (2005), 1-13. |
| [102] | V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, Fast unfolding of communities in large networks, J Stat Mech 10 (2008), P10008. · Zbl 1459.91130 |
| [103] | K. Wakita and T. Tsurumi, Finding community structure in mega-scale social networks: [extended abstract], |
| [104] | P. Boldi, M. Santini, and S. Vigna, A large time-aware web graph, SIGIR Forum 42(2) (2008), 33-38. |
| [105] | M. L. Wallace, Y. Gingras, and R. Duhon, A new approach for detecting scientific specialties from raw cocitation networks, J Am Soc Inf Sci Technol 60(2) (2009), 240-246. |
| [106] | S. Gomez, P. Jensen, and A. Arenas, Analysis of community structure in networks of correlated data,ArXiv e-prints, 2008. |
| [107] | M. J. Barber, Modularity and community detection in bipartite networks, arXiv 76 (2007), 066102. |
| [108] | V. A. Traag and J. Bruggeman, Community detection in networks with positive and negative links, arXiv 80 (2009), 036115. |
| [109] | M. N. L. Narasimhan, Principles of Continuum Mechanics, New York, John Wiley and Sons, 1993. · Zbl 0779.73002 |
| [110] | T. G. Kolda and B. W. Bader, Tensor decompositions and applications, SIAM Rev 51 (2009), 455-500. · Zbl 1173.65029 |
| [111] | L. D. Lathauwer and A. de Baynast, Blind deconvolution of ds-cdma signals by means of decomposition in rank(1, l, l) terms, IEEE Trans Signal Process 56(4) (2008), 1562-1571. · Zbl 1390.94147 |
| [112] | A. N. Langville and W. J. Stewart, A kronecker product approximate preconditioner for sans, Numerical Linear Algebra with Applications 11(8-9) (2004), 723-752. · Zbl 1164.65396 |
| [113] | J. Sun, S. Papadimitriou, and P. Yu, Window-based tensor analysis on high-dimensional and multi-aspect streams, ICDM06, Hong Kong, China, IEEE, 2006, 1076-1080. |
| [114] | J. Sun, D. Tao, and C. Faloutsos, Beyond streams and graphs: dynamic tensor analysis, KDD ’06: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2006, 374-383. |
| [115] | B. Bader, R. Harshman, and T. Kolda, Temporal analysis of semantic graphs using asalsan, ICDM07, Omaha, Nebraska, USA, IEEE, 2007, 33-42. |
| [116] | E. Acar, D. M. Dunlavy, and T. G. Kolda, Link prediction on evolving data using matrix and tensor factorizations, LDMTA ’09: Proceeding of the ICDM ’09 Workshop on Large Scale Data Mining Theory and Applications, Miami, Florida, IEEE Computer Society Press, 2009, 262-269. |
| [117] | Y. Chi, S. Zhu, Y. Gong, and Y. Zhang, Probabilistic polyadic factorization and its application to personalized recommendation, CIKM ’08: Proceeding of the 17th ACM conference on Information and Knowledge Management, New York, NY, ACM, 2008, 941-950. |
| [118] | T. G. Kolda, and J. Sun, Scalable tensor decompositions for multi-aspect data mining, ICDM ’08: Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, Washington, DC, IEEE Computer Society, 2008, 363-372. |
| [119] | M. B. Hastings, Community detection as an inference problem, Phys Rev E 74(3) (2006), 035102. |
| [120] | M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul, An introduction to variational methods for graphical models, Journal Machine Learning 37(2) (1999), 105-161. · Zbl 0910.68175 |
| [121] | P. W. Holland, K. B. Laskey, and S. Leinhardt, Stochastic blockmodels: some first steps, Social Netw 5 (1983), 109-137. |
| [122] | Y. J. Wang and G. Y. Wong, Stochastic blockmodels for directed graphs, J Am Stat Assoc 82 (1987), 8-19. · Zbl 0613.62146 |
| [123] | J. Baumes, M. K. Goldberg, M. Magdon-Ismail, and W. A. Wallace, Discovering hidden groups in communication networks, In ISI, 2004, 378-389. |
| [124] | J. Baumes, M. K. Goldberg, M. S. Krishnamoorthy, M. Magdon-Ismail, and N. Preston, Finding communities by clustering a graph into overlapping subgraphs, In IADIS AC, 2005, 97-104. |
| [125] | L. Page, S. Brin, R. Motwani, and T. Winograd, The pagerank citation ranking: bringing order to the web, Stanford, CA, 1998. |
| [126] | S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing, Science 220(4598) (1983), 671-680. · Zbl 1225.90162 |
| [127] | R. A. Hanneman, and M. Riddle, Introduction to social network methods, Berkeley, CA, University of California; University of California Press, 2005. |
| [128] | G. T. Heineman, G. Pollice, and S. Selkow, Algorithms in a nutshell (chapter 6), In O’Reilly Media, 2008. |
| [129] | L. C. Freeman, A set of measures of centrality based on betweenness, Sociometry 40 (1977), 35-41. |
| [130] | D. R. White, F. Harary, M. Sobel, and M. Becker, The cohesiveness of blocks in social networks: node connectivity and conditional density, 2001. |
| [131] | F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, Defining and identifying communities in networks, Proc Natl Acad Sci U S A 101 (2004), 2658-2663. |
| [132] | I. Vragovi´c and E. Louis, Network community structure and loop coefficient method, Phys Rev E 74 (2006), 016105-. |
| [133] | S. Gregory, An algorithm to find overlapping community structure in networks, Proceedings of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD 2007), Warsaw, Poland, Springer-Verlag, 2007, 91-102. |
| [134] | S. Gregory, Finding overlapping communities using disjoint community detection algorithms, Complex Networks: CompleNet 2009, Berlin, Heidelberg, Springer-Verlag, 2009, 47-61. |
| [135] | M. E. J. Newman, The structure and function of complex networks, SIAM Rev 45 (2003), 167. · Zbl 1029.68010 |
| [136] | J. Leskovec, L. A. Adamic, and B. A. Huberman, The dynamics of viral marketing, ACM Trans Web 1(1) (2007), 5. |
| [137] | S. Fortunato, V. Latora, and M. Marchiori, A method to find community structures based on information centrality, Phys Rev E 70 (2004), 056104. |
| [138] | E. Ziv, M. Middendorf, and C. H. Wiggins, Informationtheoretic approach to network modularity, Phys Rev E 71 (2005), 046117. |
| [139] | L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan, Group formation in large social networks: membership, growth, and evolution, KDD ’06: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2006, 44-54. |
| [140] | W. Chen, Y. Wang, and S. Yang, Efficient influence maximization in social networks, KDD ’09: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2009, 199-208. |
| [141] | S. Gregory, Finding overlapping communities in networks by label propagation, New Journal of Physics 12(10) (2009), 103018. · Zbl 1448.90094 |
| [142] | T. Y. Berger-Wolf and J. Saia, A framework for analysis of dynamic social networks, KDD ’06: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2006, 523-528. |
| [143] | C. Tantipathananandh and T. Berger-Wolf, Constant-factor approximation algorithms for identifying dynamic communities, KDD ’09: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2009, 827-836. |
| [144] | N. A. Alves, Unveiling community structures in weighted networks, Phys Rev E 76 (2007), 036101. |
| [145] | N. Agarwal, H. Liu, L. Tang, and P. S. Yu, Identifying the influential bloggers in a community, WSDM ’08: Proceedings of the International Conference on Web Search and Web Data Mining, New York, NY, ACM, 2008, 207-218. |
| [146] | J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, Cost-effective outbreak detection in networks, KDD ’07: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2007, 420-429. |
| [147] | D. Kempe, J. Kleinberg, and E. Tardos, Maximizing the spread of influence through a social network, KDD ’03: Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2003, 137-146. · Zbl 1337.91069 |
| [148] | F. Bonchi, F. Giannotti, A. Mazzanti, and D. Pedreschi, Examiner: Optimized level-wise frequent pattern mining with monotone constraints, IEEE Int Conf Data Mining 0 (2003), 11. |
| [149] | A. Goyal, B.-W. On, F. Bonchi, and L. V. S. Lakshmanan, Gurumine: A pattern mining system for discovering leaders and tribes, Int Conf Data Eng 0 (2009), 1471-1474. |
| [150] | Y. W. Teh, D. Newman, and M. Welling, A collapsed variational Bayesian inference algorithm for latent Dirichlet allocation, Advances in Neural Information Processing Systems, vol. 19, 2007. |
| [151] | T. Minka and J. Lafferty, Expectation-propagation for the generative aspect model, Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence, Edmonton, Alberta, Canada, Morgan Kaufmann, 2002, 352-359. |
| [152] | E. A. Erosheva and S. E. Fienberg, Bayesian mixed membership models for soft clustering and classification, Classification-The Ubiquitous Challenge, Berlin, Heidelberg, Springer, 2005. |
| [153] | M. Mørup and L. K. Hansen, Learning latent structure in complex networks, In Workshop on Analyzing Networks and Learning with Graphs, 2009. |
| [154] | A. Decelle, F. Krzakala, C. Moore, and L. Zdeborov´a, Phase transition in the detection of modules in sparse networks, ArXiv e-prints, 2011. |
| [155] | M. Rosvall, and C. T. Bergstrom, Maps of random walks on complex networks reveal community structure, Proc Natl Acad Sci 105 (2008), 1118-1123. |
| [156] | S. M. van Dongen, Graph Clustering by Flow Simulation, PhD thesis, University of Utrecht, The Netherlands, 2000. |
| [157] | F. Fouss, A. Pirotte, J. M. Renders, and M. Saerens, A novel way of computing dissimilarities between nodes of a graph, with application to collaborative filtering, International Conference on Web Intelligence, Compiegne, France, IEEE Computer Society, 2004. |
| [158] | H. Zhou and R. Lipowsky, Network brownian motion: a new method to measure vertex-vertex proximity and to |
| [159] | F. Wei, C. Wang, L. Ma, and A. Zhou, Detecting overlapping community structures in networks with global partition and local expansion, In Progress in WWW Research and Development, 2008. |
| [160] | A. Lancichinetti and S. Fortunato, Community detection algorithms: a comparative analysis, Phys Rev E 80 (2009), 056117. |
| [161] | M. Berlingerio, F. Bonchi, B. Bringmann, and A. Gionis, Mining graph evolution rules, In ECML/PKDD (1), 2009, 115-130. |
| [162] | S. Nijssen and J. N. Kok, A quickstart in frequent structure mining can make a difference, KDD ’04: Proceedings of the tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, ACM, 2004, 647-652. |
| [163] | H. Shen, X. Cheng, K. Cai, and M.-B. Hu, Detect overlapping and hierarchical community structure in networks, Physica A 388 (2009), 1706. |
| [164] | K. Saito, and T. Yamada, Extracting communities from complex networks by the k-dense method, ICDMW ’06: Proceedings of the Sixth IEEE International Conference on Data Mining-Workshops, Washington, DC, IEEE Computer Society, 2006, 300-304. |
| [165] | H. Ito, K. Iwama, and T. Osumi, Linear-time enumeration of isolated cliques, In ESA, 2005, 119-130. · Zbl 1162.68497 |
| [166] | H. Ito and K. Iwama, Enumeration of isolated cliques and pseudo-cliques, In ACM Transactions on Algorithms, 2008. · Zbl 1298.05250 |
| [167] | B. Balasundaram, S. Butenko, I. Hicks, and S. Sachdeva, Clique relaxations in social network analysis: the maximum k-plex problem, Operations Research, 2009, 59 (1), Linthicum, Maryland, USA, INFORMS Institute for Operations Research and the Management Sciences (INFORMS), (2011). · Zbl 1218.90228 |
| [168] | N. Nishimura, P. Ragde, and D. M. Thilikos, Fast fixedparameter tractable algorithms for nontrivial generalizations of vertex cover, Disc Appl Math 152(1-3) (2005), 229-245. · Zbl 1080.05093 |
| [169] | T. Uno, M. Kiyomi, and H. Arimura, Lcm ver.3: collaboration of array, bitmap and prefix tree for frequent itemset mining, OSDM ’05: Proceedings of the 1st International Workshop on Open Source Data Mining, New York, NY, ACM, 2005, 77-86. |
| [170] | B. Ball, B. Karrer, and M. E. J. Newman, An efficient and principled method for detecting communities in networks, ArXiv e-prints, 2011. |
| [171] | A. Clauset, C. Moore, and M. E. Newman, Hierarchical structure and the prediction of missing links in networks., Nature 453(7191) (2008), 98-101. |
| [172] | K. Henderson, and T. Eliassi-Rad, Applying latent dirichlet allocation to group discovery in large graphs, SAC ’09: Proceedings of the 2009 ACM Symposium on Applied Computing, New York, NY, ACM, 2009, 1456-1461. |
| [173] | D. M. Blei, A. Y. Ng, and M. I. Jordan, Latent dirichlet allocation, J Mach Learn Res 3 (2003), 993-1022. · Zbl 1112.68379 |
| [174] | T. Griffiths, Gibbs sampling in the generative model of latent dirichlet allocation, Tech. Rep., Stanford University, 2002. |
| [175] | A. Bjorck, Numerical methods for least squares problems, Philadelphia, SIAM, 1996. · Zbl 0847.65023 |
| [176] | T. Hastie, R. Tibshirani, and J. H. Friedman, The elements of statistical learning, Berlin, Heidelberg, Springer, 2003. · Zbl 0973.62007 |
| [177] | J. Leskovec, K. J. Lang, and M. Mahoney, Empirical comparison of algorithms for network community detection, Proceedings of the 19th International Conference on WORLD WIDE WEB, WWW ’10, New York, NY, ACM, 2010, 631-640. |
| [178] | M. Newman, Detecting community structure in networks, Eur Phys J B 38 (2004), 321-330. |
| [179] | D. Chakrabarti and C. Faloutsos, Graph mining: laws, generators, and algorithms, ACM Comput Surv 38(1) (2006), 2. |
| [180] | L. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas, Comparing community structure identification, Journal of Statistical Mechanics: Theory and Experiment 9 (2005), 09008. |
| [181] | S. Fortunato and C. Castellano, Community structure in graphs, 2007, Encyclopedia of Complexity and Systems Science, Berlin, Germany, Springer (2009), 1141-1163. |
| [182] | M. A. Porter, J.-P. Onnela, and P. J. Mucha, Communities in networks, Notices Am Math Soc 56 (2009), 1082. · Zbl 1188.05142 |
| [183] | S. E. Schaeffer, Graph clustering, Comput Sci Rev 1(1) (2007), 27-64. · Zbl 1302.68237 |
| [184] | J. P. Scott, Social Network Analysis: A Handbook, Thousand Oaks, California, SAGE Publications, 2000. |
| [185] | A. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
