2012
Report  Open Access

A classification for community discovery methods in complex networks

Coscia M., Giannotti F., Pedreschi D.

Computer Science - Data Structures and Algorithms  Social and Information Networks (cs.SI)  complex network  Information Systems  Social network  Data Mining  FOS: Physical sciences  05C82 Small world graphs  Graph partitioning  Computer Science - Social and Information Networks  G.2.2 Graph Theory  FOS: Computer and information sciences  Computer Science Applications  Groups  Analysis  Physics - Physics and Society  Complex networks  Community discovery  Physics and Society (physics.soc-ph)  Data Structures and Algorithms (cs.DS) 

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.

Source: ISTI Technical reports, pp.512–546, 2012


[1] G. W. Flake, S. Lawrence, C. L. Giles, and F. M. Coetzee, “Self-organization and identification of web communities,” IEEE Computer, vol. 35, pp. 66-71, 2002.
[2] R. Guimera and L. A. N. Amaral, “Functional cartography of complex metabolic networks,” Nature, vol. 433, no. 7028, pp. 895-900, 2005.
[3] G. Palla, I. Derenyi, I. Farkas, and T. Vicsek, “Uncovering the overlapping community structure of complex networks in nature and society,” Nature, vol. 435, pp. 814-818, June 2005.
[4] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” PROC.NATL.ACAD.SCI.USA, vol. 99, p. 7821, 2002.
[5] X. Yan and J. Han, “gspan: Graph-based substructure pattern mining,” 2002.
[6] S. Fortunato, “Community detection in graphs,” Physics Reports, vol. 486, no. 3-5, pp. 75 - 174, 2010.
[7] M. E. J. Newman and E. A. Leicht, “Mixture models and exploratory analysis in networks,” Proceedings of the National Academy of Science, vol. 104, pp. 9564-9569, June 2007.
[8] L. Tang, H. Liu, J. Zhang, and Z. Nazeri, “Community evolution in dynamic multi-mode networks,” in KDD '08: Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 677-685, ACM, 2008.
[9] A. Goyal, F. Bonchi, and L. V. Lakshmanan, “Discovering leaders from community actions,” in CIKM '08: Proceeding of the 17th ACM conference on Information and knowledge management, (New York, NY, USA), pp. 499-508, ACM, 2008.
[10] M. Szell, R. Lambiotte, and S. Thurner, “Trade, conflict and sentiments: Multi-relational organization of large-scale social networks,” arXiv.org, 1003.5137, 2010.
[11] J. Leskovec, D. Huttenlocher, and J. Kleinberg, “Predicting positive and negative links in online social networks,” in WWW, pp. 641-650, ACM, 2010.
[12] M. Berlingerio, M. Coscia, F. Giannotti, A. Monreale, and D. Pedreschi, “Foundations of multidimensional network analysis,” in ASONAM, IEEE, 2011 (to appear).
[13] J. Rissanen, “Modelling by the shortest data description,” Automatica, vol. 14, pp. 465-471, 1978.
[14] P. D. Grnwald, The Minimum Description Length Principle, vol. 1 of MIT Press Books. The MIT Press, 2007.
[15] J. Kleinberg, “An impossibility theorem for clustering,” in Advances in Neural Information Processing Systems (S. Becker, S. Thrun, and K. Obermayer, eds.), pp. 446-453, MIT Press, 2002.
[16] B. W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,” The Bell system technical journal, vol. 49, no. 1, pp. 291-307, 1970.
[17] A. Pothen, H. D. Simon, and K.-P. Liou, “Partitioning sparse matrices with eigenvectors of graphs,” SIAM J. Matrix Anal. Appl., vol. 11, no. 3, pp. 430-452, 1990.
[18] A. Clauset, M. E. J. Newman, and C. Moore, “Finding community structure in very large networks,” Physical Review E, vol. 70, p. 066111, 2004.
[19] R. Lambiotte, J. Delvenne, and M. Barahona, “Laplacian Dynamics and Multiscale Modular Structure in Networks,” ArXiv e-prints, Dec. 2008.
[20] J. Reichardt and S. Bornholdt, “Statistical mechanics of community detection,” vol. 74, pp. 016110-+, July 2006.
[21] D. Chakrabarti, R. Kumar, and A. Tomkins, “Evolutionary clustering,” in KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 554-560, ACM, 2006.
[22] B. Long, X. Wu, Z. M. Zhang, and P. S. Yu, “Unsupervised learning on k-partite graphs,” in KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 317- 326, ACM, 2006.
[23] L. Tang and H. Liu, “Relational learning via latent social dimensions,” in KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 817-826, ACM, 2009.
[24] L. Tang, X. Wang, and H. Liu, “Uncovering groups via heterogeneous interaction analysis,” in ICDM, IEEE, 2009.
[25] A. Banerjee, S. Basu, and S. Merugu, “Multi-way clustering on relation graphs.,” in SDM, SIAM, 2007.
[26] C. Kemp, J. B. Tenenbaum, T. L. Griffiths, T. Yamada, and N. Ueda, “Learning systems of concepts with an infinite relational model,” in AAAI'06: Proceedings of the 21st national conference on Artificial intelligence, pp. 381-388, AAAI Press, 2006.
[27] L. Friedland and D. Jensen, “Finding tribes: identifying closeknit individuals from employment patterns,” in KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 290-299, ACM, 2007.
[28] D. Chakrabarti, “Autopart: parameter-free graph partitioning and outlier detection,” in PKDD '04: Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, (New York, NY, USA), pp. 112-124, Springer-Verlag New York, Inc., 2004.
[29] J. Ferlez, C. Faloutsos, J. Leskovec, D. Mladenic, and M. Grobelnik, “Monitoring network evolution using mdl,” Data Engineering, International Conference on, vol. 0, pp. 1328-1330, 2008.
[30] S. Papadimitriou, J. Sun, C. Faloutsos, and P. S. Yu, “Hierarchical, parameter-free community discovery,” in ECML PKDD '08: Proceedings of the European conference on Machine Learning and Knowledge Discovery in Databases - Part II, (Berlin, Heidelberg), pp. 170-187, Springer-Verlag, 2008.
[31] Y.-R. Lin, J. Sun, P. Castro, R. Konuru, H. Sundaram, and A. Kelliher, “Metafac: community discovery via relational hypergraph factorization,” in KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 527-536, ACM, 2009.
[32] J. M. Hofman and C. H. Wiggins, “A bayesian approach to network modularity,” Physical Review Letters, vol. 100, p. 258701, 2008.
[33] J. Baumes, M. Goldberg, and M. Magdon-ismail, “Efficient identification of overlapping communities,” in In IEEE International Conference on Intelligence and Security Informatics (ISI, pp. 27-36, 2005.
[34] S. E. Schaeffer, “Stochastic local clustering for massive graphs,” in Proceedings of the Ninth Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD-05), vol. 3518 of Lecture Notes in Computer Science, pp. 354-360, Springer-Verlag GmbH, 2005.
[35] S. Gregory, “A fast algorithm to find overlapping communities in networks,” in ECML PKDD '08: Proceedings of the 2008 European Conference on Machine Learning and Knowledge Discovery in Databases - Part I, (Berlin, Heidelberg), pp. 408- 423, Springer-Verlag, 2008.
[36] J. Bagrow and E. Bollt, “A local method for detecting communities,” Physical Review E, vol. 72, p. 046108, 2005.
[37] A. Lancichinetti, S. Fortunato, and J. Kertesz, “Detecting the overlapping and hierarchical community structure of complex networks,” New Journal of Physics, vol. 11, p. 033015, 2009.
[38] U. N. Raghavan, R. Albert, and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Physical Review E, vol. 76, p. 036106, 2007.
[39] C. Tantipathananandh, T. Berger-Wolf, and D. Kempe, “A framework for community identification in dynamic social networks,” in KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 717-726, ACM, 2007.
[40] F. Wu and B. A. Huberman, “Finding communities in linear time: a physics approach,” The European Physical Journal B - Condensed Matter and Complex Systems, vol. 38, no. 2, pp. 331-338, 2004.
[41] 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 (SNA-KDD'08), August 2008.
[42] W. Chen, Y. Wang, and S. Yang, “Efficient influence maximization in social networks,” in KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 199- 208, ACM, 2009.
[43] E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing, “Mixed membership stochastic blockmodels,” JOURNAL OF MACHINE LEARNING RESEARCH, vol. 9, p. 1981, 2007.
[44] P. Pons and M. Latapy, “Computing communities in large networks using random walks,” Journal of Graph Algorithms and Applications, 2006.
[45] F. Wei, W. Qian, C. Wang, and A. Zhou, “Detecting overlapping community structures in networks,” World Wide Web, vol. 12, no. 2, pp. 235-261, 2009.
[46] M. Rosvall and C. T. Bergstrom, “Maps of random walks on complex networks reveal community structure,” Proceedings of the National Academy of Science, vol. 105, pp. 1118-1123, Jan. 2008.
[47] C. Komusiewicz, F. Hu¨ffner, H. Moser, and R. Niedermeier, “Isolation concepts for efficiently enumerating dense subgraphs,” Theor. Comput. Sci., vol. 410, no. 38-40, pp. 3640- 3654, 2009.
[48] S. Lehmann, M. Schwartz, and L. K. Hansen, “Bi-clique communities,” PHYS.REV., vol. 78, p. 016108, 2008.
[49] H. Shen, X. Cheng, K. Cai, and M.-B. Hu, “Detect overlapping and hierarchical community structure in networks,” PHYSICA A, vol. 388, p. 1706, 2009.
[50] T. S. Evans and R. Lambiotte, “Line graphs, link partitions and overlapping communities,” Physical Review E, vol. 80, p. 016105, 2009.
[51] Y.-Y. Ahn, J. P. Bagrow, and S. Lehmann, “Link communities reveal multi-scale complexity in networks,” Nature, 2010.
[52] B. Ball, B. Karrer, and M. E. J. Newman, “An efficient and principled method for detecting communities in networks,” ArXiv e-prints, Apr. 2011.
[53] T. Eliassi-Rad, K. Henderson, S. Papadimitriou, and C. Faloutsos, “A hybrid community discovery framework for complex networks,” in SIAM Conference on Data Mining, 2010.
[54] 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.
[55] A. Clauset, C. Moore, and M. E. Newman, “Hierarchical structure and the prediction of missing links in networks.,” Nature, vol. 453, no. 7191, pp. 98-101, 2008.
[56] L. Kaufman and P. J. Rousseeuw, “Finding groups in data: An introduction to cluster analysis,” John Wiley, 1990.
[57] I. S. Dhillon, S. Mallela, and D. S. Modha, “Informationtheoretic co-clustering,” in KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 89-98, ACM, 2003.
[58] D. Chakrabarti, S. Papadimitriou, D. S. Modha, and C. Faloutsos, “Fully automatic cross-associations,” in KDD '04: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 79-88, ACM, 2004.
[59] B. Long, Z. M. Zhang, X. Wu´, and P. S. Yu, “Spectral clustering for multi-type relational data,” in ICML '06: Proceedings of the 23rd international conference on Machine learning, (New York, NY, USA), pp. 585-592, ACM, 2006.
[60] S. C. Madeira and A. L. Oliveira, “Biclustering algorithms for biological data analysis: A survey,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 1, no. 1, pp. 24-45, 2004.
[61] T. M. Cover and J. A. Thomas, Elements of Information Theory. Wiley-Interscience, August 1991.
[62] P. Grunwald, “A tutorial introduction to the minimum description length principle,” 2004.
[63] D. H. Fisher, “Knowledge acquisition via incremental conceptual clustering,” Mach. Learn., vol. 2, pp. 139-172, September 1987.
[64] C. C. Aggarwal, J. Han, J. Wang, and P. S. Yu, “A framework for clustering evolving data streams,” in VLDB '2003: Proceedings of the 29th international conference on Very large data bases, pp. 81-92, VLDB Endowment, 2003.
[65] H. Koga, T. Ishibashi, and T. Watanabe, “Fast agglomerative hierarchical clustering algorithm using locality-sensitive hashing,” Knowl. Inf. Syst., vol. 12, no. 1, pp. 25-53, 2007.
[66] 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,” in WWW '08: Proceeding of the 17th international conference on World Wide Web, (New York, NY, USA), pp. 685-694, ACM, 2008.
[67] M.-S. Kim and J. Han, “A particle-and-density based evolutionary clustering method for dynamic networks,” Proc. VLDB Endow., vol. 2, no. 1, pp. 622-633, 2009.
[68] 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,” in KDD '05: Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, (New York, NY, USA), pp. 41-50, ACM, 2005.
[69] A. Banerjee, S. Merugu, I. Dhillon, and J. Ghosh, “Clustering with bregman divergences,” in Journal of Machine Learning Research, pp. 234-245, 2004.
[70] H. Cho, I. Dhillon, Y. Guan, and S. Sra, “Minimum sum squared residue co-clustering of gene expression data,” 2004.
[71] A. Banerjee, I. Dhillon, J. Ghosh, S. Merugu, and D. S. Modha, “A generalized maximum entropy approach to bregman coclustering and matrix approximation,” in In KDD, pp. 509- 514, 2004.
[72] M. Mcpherson, L. S. Lovin, and J. M. Cook, “Birds of a feather: Homophily in social networks,” Annual Review of Sociology, vol. 27, no. 1, pp. 415-444, 2001.
[73] L. Tang, S. Rajan, and V. K. Narayanan, “Large scale multilabel classification via metalabeler,” in WWW '09: Proceedings of the 18th international conference on World wide web, (New York, NY, USA), pp. 211-220, ACM, 2009.
[74] I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun, “Support vector machine learning for interdependent and structured output spaces,” 2004.
[75] L. Tang and H. Liu, “Scalable learning of collective behavior based on sparse social dimensions,” in CIKM, 2009.
[76] L. Tang and H. Liu, “Uncovering cross-dimension group structures in multi-dimensional networks,” in SDM workshop on Analysis of Dynamic Networks, 2009.
[77] G. H. Golub and C. F. V. Loan, “Matrix computations,” (Baltimore, MD, USA), 1989.
[78] J. Kettenring, “Canonical analysis of several sets of variables,” Biometrika, vol. 58, no. 3, pp. 433-451, 1971.
[79] J. Pitman, “Combinatorial stochastic processes,” 2002.
[80] S. Papadimitriou, A. Gionis, P. Tsaparas, R. A. Visnen, H. Mannila, and C. Faloutsos, “Parameter-free spatial data mining using mdl,” Data Mining, IEEE International Conference on, vol. 0, pp. 346-353, 2005.
[81] 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 In Proc. of VLDB, pp. 852-863, 2004.
[82] J. Sun, C. Faloutsos, S. Papadimitriou, and P. S. Yu, “Graphscope: parameter-free mining of large time-evolving graphs,” in KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 687-696, ACM, 2007.
[83] M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Physical Review E, vol. 69, p. 026113, 2004.
[84] B. H. Good, Y.-A. de Montjoye, and A. Clauset, “The performance of modularity maximization in practical contexts,” 2010.
[85] M. E. J. Newman, “Finding community structure in networks using the eigenvectors of matrices,” Physical Review E, vol. 74, p. 036104, 2006.
[86] M. Berlingerio, M. Coscia, and F. Giannotti, “Finding and characterizing communities in multidimensional networks,” in ASONAM, IEEE, 2011 (to appear).
[87] M. E. J. Newman, “Fast algorithm for detecting community structure in networks,” Physical Review E, vol. 69, p. 066133, 2004.
[88] E. A. Leicht and M. E. J. Newman, “Community structure in directed networks,” Physical Review Letters, vol. 100, p. 118703, 2008.
[89] M. E. J. Newman, “Modularity and community structure in networks,” PROC.NATL.ACAD.SCI.USA, vol. 103, p. 8577, 2006.
[90] V. Nicosia, G. Mangioni, V. Carchiolo, and M. Malgeri, “Extending the definition of modularity to directed graphs with overlapping communities,” J.STAT.MECH., p. P03024, 2009.
[91] Agarwal, G. and Kempe, D., “Modularity-maximizing graph communities via mathematical programming,” Eur. Phys. J. B, vol. 66, no. 3, pp. 409-418, 2008.
[92] J. Duch and A. Arenas, “Community detection in complex networks using extremal optimization,” Physical Review E, vol. 72, pp. 027104+, Aug 2005.
[93] P. Bak and K. Sneppen, “Punctuated equilibrium and criticality in a simple model of evolution,” Phys. Rev. Lett., vol. 71, pp. 4083-4086, Dec 1993.
[94] S. Boettcher and A. G. Percus, “Optimization with extremal dynamics,” Phys. Rev. Lett., vol. 86, pp. 5211-5214, Jun 2001.
[95] A. Arenas, J. Duch, A. Fernandez, and S. Gomez, “Size reduction of complex networks preserving modularity,” New Journal of Physics, vol. 9, p. 176, 2007.
[96] R. Guimera and L. A. Amaral, “Cartography of complex networks: modules and universal roles,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2005, February 2005.
[97] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” J.STAT.MECH., p. P10008, 2008.
[98] K. Wakita and T. Tsurumi, “Finding community structure in mega-scale social networks: [extended abstract],” in WWW '07: Proceedings of the 16th international conference on World Wide Web, (New York, NY, USA), pp. 1275-1276, ACM, 2007.
[99] P. Boldi, M. Santini, and S. Vigna, “A large time-aware web graph,” SIGIR Forum, vol. 42, no. 2, pp. 33-38, 2008.
[100] 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., vol. 60, no. 2, pp. 240-246, 2009.
[101] P. J. Mucha, T. Richardson, K. Macon, M. A. Porter, and J. Onnela, “Community Structure in Time-Dependent, Multiscale, and Multiplex Networks,” Science, vol. 328, pp. 876-878, Nov. 2010.
[102] S. Gomez, P. Jensen, and A. Arenas, “Analysis of community structure in networks of correlated data,” ArXiv e-prints, Dec. 2008.
[103] M. J. Barber, “Modularity and community detection in bipartite networks,” arXiv, vol. 76, pp. 066102-+, Dec. 2007.
[104] V. A. Traag and J. Bruggeman, “Community detection in networks with positive and negative links,” arXiv, vol. 80, pp. 036115-+, Sept. 2009.
[105] M. N. L. Narasimhan, “Principles of continuum mechanics,” John Wiley and Sons, New York, 1993.
[106] T. G. Kolda and B. W. Bader, “Tensor decompositions and applications,” SIAM Review, vol. 51, pp. 455-500, September 2009.
[107] L. D. Lathauwer and A. de Baynast, “Blind deconvolution of ds-cdma signals by means of decomposition in rank-(1, l, l) terms,” IEEE Transactions on Signal Processing, vol. 56, no. 4, pp. 1562-1571, 2008.
[108] A. N. Langville and W. J. Stewart, “A kronecker product approximate preconditioner for sans,” 2003.
[109] J. Sun, S. Papadimitriou, and P. Yu, “Window-based tensor analysis on high-dimensional and multi-aspect streams,” pp. 1076 -1080, dec. 2006.
[110] J. Sun, D. Tao, and C. Faloutsos, “Beyond streams and graphs: dynamic tensor analysis,” in KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 374-383, ACM, 2006.
[111] B. Bader, R. Harshman, and T. Kolda, “Temporal analysis of semantic graphs using asalsan,” pp. 33 -42, oct. 2007.
[112] E. Acar, D. M. Dunlavy, and T. G. Kolda, “Link prediction on evolving data using matrix and tensor factorizations,” in LDMTA'09: Proceeding of the ICDM'09 Workshop on Large Scale Data Mining Theory and Applications, pp. 262-269, IEEE Computer Society Press, December 2009.
[113] Y. Chi, S. Zhu, Y. Gong, and Y. Zhang, “Probabilistic polyadic factorization and its application to personalized recommendation,” in CIKM '08: Proceeding of the 17th ACM conference on Information and knowledge management, (New York, NY, USA), pp. 941-950, ACM, 2008.
[114] T. G. Kolda and J. Sun, “Scalable tensor decompositions for multi-aspect data mining,” in ICDM '08: Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, (Washington, DC, USA), pp. 363-372, IEEE Computer Society, 2008.
[115] M. B. Hastings, “Community detection as an inference problem,” Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), vol. 74, no. 3, p. 035102, 2006.
[116] M. I. Jordan, Z. Ghahramani, T. S. Jaakkola, and L. K. Saul, “An introduction to variational methods for graphical models,” pp. 105-161, 1999.
[117] P. W. Holland, K. B. Laskey, and S. Leinhardt, “Stochastic blockmodels: Some first steps,” Social Networks, vol. 5, pp. 109-137, 1983.
[118] Y. J. Wang and G. Y. Wong, “Stochastic blockmodels for directed graphs,” Journal of American Statistical Associ- ation, vol. 82, pp. 8-19, 1987.
[119] J. Baumes, M. K. Goldberg, M. Magdon-Ismail, and W. A. Wallace, “Discovering hidden groups in communication networks,” in ISI, pp. 378-389, 2004.
[120] 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, pp. 97-104, 2005.
[121] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web,” 1998.
[122] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, Number 4598, vol. 220, 4598, pp. 671-680, 1983.
[123] R. A. Hanneman and M. Riddle, “Introduction to social network methods,” 2005.
[124] G. T. Heineman, G. Pollice, and S. Selkow, “Algorithms in a nutshell (chapter 6),” in O'Reilly Media, 2008.
[125] L. C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, vol. 40, pp. 35-41, March 1977.
[126] D. R. White, F. Harary, M. Sobel, and M. Becker, “The cohesiveness of blocks in social networks: Node connectivity and conditional density,” 2001.
[127] F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, “Defining and identifying communities in networks,” Proceedings of the National Academy of Sciences of the United States of America, vol. 101, pp. 2658-2663, March 2004.
[128] I. Vragovi´c and E. Louis, “Network community structure and loop coefficient method,” Phys. Rev. E, vol. 74, p. 016105, Jul 2006.
[129] S. Gregory, “An algorithm to find overlapping community structure in networks,” in Proceedings of the 11th European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD 2007), pp. 91-102, Springer-Verlag, September 2007.
[130] S. Gregory, “Finding overlapping communities using disjoint community detection algorithms,” in Complex Networks: CompleNet 2009, pp. 47-61, Springer-Verlag, May 2009.
[131] M. E. J. Newman, “The structure and function of complex networks,” SIAM Review, vol. 45, p. 167, 2003.
[132] J. Leskovec, L. A. Adamic, and B. A. Huberman, “The dynamics of viral marketing,” ACM Trans. Web, vol. 1, no. 1, p. 5, 2007.
[133] S. Fortunato, V. Latora, and M. Marchiori, “A method to find community structures based on information centrality,” 2004.
[134] E. Ziv, M. Middendorf, and C. H. Wiggins, “Informationtheoretic approach to network modularity,” Phys. Rev. E, vol. 71, p. 046117, Apr 2005.
[135] L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan, “Group formation in large social networks: membership, growth, and evolution,” in KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 44-54, ACM, 2006.
[136] S. Gregory, “Finding overlapping communities in networks by label propagation,” 2009.
[137] T. Y. Berger-Wolf and J. Saia, “A framework for analysis of dynamic social networks,” in KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 523- 528, ACM, 2006.
[138] C. Tantipathananandh and T. Berger-Wolf, “Constant-factor approximation algorithms for identifying dynamic communities,” in KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 827-836, ACM, 2009.
[139] N. A. Alves, “Unveiling community structures in weighted networks,” Physical Review E, vol. 76, p. 036101, 2007.
[140] A.-L. Barabasi and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, p. 509, 1999.
[141] A. L. Barabasi, H. Jeong, Z. Neda, E. Ravasz, A. Schubert, and T. Vicsek, “Evolution of the social network of scientific collaborations,” PHYSICA A, vol. 311, p. 3, 2002.
[142] G. Kossinets and D. J. Watts, “Empirical analysis of an evolving social network,” Science, vol. 311, no. 5757, pp. 88-90, 2006.
[143] N. Agarwal, H. Liu, L. Tang, and P. S. Yu, “Identifying the influential bloggers in a community,” in WSDM '08: Proceedings of the international conference on Web search and web data mining, (New York, NY, USA), pp. 207-218, ACM, 2008.
[144] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, “Cost-effective outbreak detection in networks,” in KDD '07: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 420-429, ACM, 2007.
[145] D. Kempe, J. Kleinberg, and E. Tardos, “Maximizing the spread of influence through a social network,” in KDD '03: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137-146, ACM, 2003.
[146] F. Bonchi, F. Giannotti, A. Mazzanti, and D. Pedreschi, “Examiner: Optimized level-wise frequent pattern mining with monotone constraints,” Data Mining, IEEE International Conference on, vol. 0, p. 11, 2003.
[147] A. Goyal, B.-W. On, F. Bonchi, and L. V. S. Lakshmanan, “Gurumine: A pattern mining system for discovering leaders and tribes,” Data Engineering, International Conference on, vol. 0, pp. 1471-1474, 2009.
[148] Y. W. Teh, D. Newman, and M. Welling, “A collapsed variational Bayesian inference algorithm for latent Dirichlet allocation,” in Advances in Neural Information Processing Systems, vol. 19, 2007.
[149] T. Minka and J. Lafferty, “Expectation-propagation for the generative aspect model,” in In Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence, pp. 352-359, Morgan Kaufmann, 2002.
[150] E. A. Erosheva and S. E. Fienberg, “Bayesian mixed membership models for soft clustering and classification,” in Classification - The ubiquitous challenge, Springer Berlin Heidelberg, 2005.
[151] M. Mørup and L. K. Hansen, “Learning latent structure in complex networks,” Workshop on Analyzing Networks and Learning with Graphs, 2009.
[152] A. Decelle, F. Krzakala, C. Moore, and L. Zdeborova´, “Phase transition in the detection of modules in sparse networks,” ArXiv e-prints, Feb. 2011.
[153] D. J. Watts and S. H. Strogatz, “Collective dynamics of 'smallworld' networks,” Nature, vol. 393, no. 6684, pp. 440-442, 1998.
[154] S. M. van Dongen, Graph Clustering by Flow Simulation. PhD thesis, University of Utrecht, The Netherlands, 2000.
[155] F. Fouss, A. Pirotte, J. michel Renders, and M. Saerens, “A novel way of computing dissimilarities between nodes of a graph, with application to collaborative filtering,” 2004.
[156] H. Zhou and R. Lipowsky, “Network brownian motion: A new method to measure vertex-vertex proximity and to identify communities and subcommunities,” in International Conference on Computational Science, pp. 1062-1069, 2004.
[157] F. Wei, C. Wang, L. Ma, and A. Zhou, “Detecting overlapping community structures in networks with global partition and local expansion,” Progress in WWW Research and Development, 2008.
[158] A. Lancichinetti and S. Fortunato, “Community detection algorithms: A comparative analysis,” Physical Review E, vol. 80, pp. 056117-+, Nov. 2009.
[159] M. Berlingerio, F. Bonchi, B. Bringmann, and A. Gionis, “Mining graph evolution rules,” in ECML/PKDD (1), pp. 115-130, 2009.
[160] S. Nijssen and J. N. Kok, “A quickstart in frequent structure mining can make a difference,” in KDD '04: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, (New York, NY, USA), pp. 647- 652, ACM, 2004.
[161] M. Kuramochi and G. Karypis, “Finding frequent patterns in a large sparse graph*,” Data Min. Knowl. Discov., vol. 11, no. 3, pp. 243-271, 2005.
[162] K. Saito and T. Yamada, “Extracting communities from complex networks by the k-dense method,” in ICDMW '06: Proceedings of the Sixth IEEE International Conference on Data Mining - Workshops, (Washington, DC, USA), pp. 300-304, IEEE Computer Society, 2006.
[163] H. Ito, K. Iwama, and T. Osumi, “Linear-time enumeration of isolated cliques,” in ESA, pp. 119-130, 2005.
[164] H. Ito and K. Iwama, “Enumeration of isolated cliques and pseudo-cliques,” in ACM Transactions on Algorithms, 2008.
[165] B. Balasundaram, S. Butenko, I. Hicks, and S. Sachdeva, “Clique relaxations in social network analysis: The maximum k-plex problem,” in Operations Research, 2009.
[166] N. Nishimura, P. Ragde, and D. M. Thilikos, “Fast fixedparameter tractable algorithms for nontrivial generalizations of vertex cover,” Discrete Appl. Math., vol. 152, no. 1-3, pp. 229- 245, 2005.
[167] T. Uno, M. Kiyomi, and H. Arimura, “Lcm ver.3: collaboration of array, bitmap and prefix tree for frequent itemset mining,” in OSDM '05: Proceedings of the 1st international workshop on open source data mining, (New York, NY, USA), pp. 77-86, ACM, 2005.
[168] C. Bron and J. Kerbosch, “Algorithm 457: finding all cliques of an undirected graph,” Commun. ACM, vol. 16, no. 9, pp. 575- 577, 1973.
[169] S. Fortunato and M. Barthelemy, “Resolution limit in community detection,” Proceedings of the National Academy of Science, vol. 104, pp. 36-41, Jan. 2007.
[170] K. Henderson and T. Eliassi-Rad, “Applying latent dirichlet allocation to group discovery in large graphs,” in SAC '09: Proceedings of the 2009 ACM symposium on Applied Computing, (New York, NY, USA), pp. 1456-1461, ACM, 2009.
[171] D. M. Blei, A. Y. Ng, and M. I. Jordan, “Latent dirichlet allocation,” J. Mach. Learn. Res., vol. 3, pp. 993-1022, 2003.
[172] T. Griffiths, “Gibbs sampling in the generative model of latent dirichlet allocation,” tech. rep., Stanford University, 2002.
[173] A. Bjorck, “Numerical methods for least squares problems,” (Philadelphia), SIAM, 1996.
[174] T. Hastie, R. Tibshirani, and J. H. Friedman, “The elements of statistical learning,” Springer, 2003.
[175] J. Leskovec, K. J. Lang, and M. Mahoney, “Empirical comparison of algorithms for network community detection,” in Proceedings of the 19th international conference on World wide web, WWW '10, (New York, NY, USA), pp. 631-640, ACM, 2010.
[176] M. Newman, “Detecting community structure in networks,” Eur. Phys. J. B, vol. 38, pp. 321-330, mar 2004.
[177] D. Chakrabarti and C. Faloutsos, “Graph mining: Laws, generators, and algorithms,” ACM Comput. Surv., vol. 38, no. 1, p. 2, 2006.
[178] L. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas, “Comparing community structure identification,” 2005.
[179] S. Fortunato and C. Castellano, “Community structure in graphs,” 2007.
[180] M. A. Porter, J.-P. Onnela, and P. J. Mucha, “Communities in networks,” NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, vol. 56, p. 1082, 2009.
[181] S. E. Schaeffer, “Graph clustering,” Computer Science Review, vol. 1, no. 1, pp. 27 - 64, 2007.
[182] J. P. Scott, Social Network Analysis: A Handbook. SAGE Publications, 2000.
[183] A. Lancichinetti, S. Fortunato, and F. Radicchi, “Benchmark graphs for testing community detection algorithms,” Physical Review E, vol. 78, p. 046110, 2008.

Metrics



Back to previous page