Community Discovery in Dynamic Networks: A Survey

Abstract

Several research studies have shown that complex networks modeling real-world phenomena are characterized by striking properties: (i) they are organized according to community structure, and (ii) their structure evolves with time. Many researchers have worked on methods that can efficiently unveil substructures in complex networks, giving birth to the field of community discovery. A novel and fascinating problem started capturing researcher interest recently: the identification of evolving communities. Dynamic networks can be used to model the evolution of a system: nodes and edges are mutable, and their presence, or absence, deeply impacts the community structure that composes them.

This survey aims to present the distinctive features and challenges of dynamic community discovery and propose a classification of published approaches. As a “user manual,” this work organizes state-of-the-art methodologies into a taxonomy, based on their rationale, and their specific instantiation. Given a definition of network dynamics, desired community characteristics, and analytical needs, this survey will support researchers to identify the set of approaches that best fit their needs. The proposed classification could also help researchers choose in which direction to orient their future research.

References

1. Manoj K. Agarwal, Krithi Ramamritham, and Manish Bhide. 2012. Real time discovery of dense clusters in highly dynamic graphs: Identifying real world events in highly dynamic environments. Proceedings of the VLDB Endowment 5, 10, 980--991.
2. Uri Alon. 2007. Network motifs: Theory and experimental approaches. Nature Reviews Genetics 8, 6, 450--461.
3. Hamidreza Alvari, Alireza Hajibagheri, and Gita Sukthankar. 2014. Community detection in dynamic social networks: A game-theoretic approach. In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’14). IEEE, Los Alamitos, CA, 101--107.
4. Sitaram Asur, Srinivasan Parthasarathy, and Duygu Ucar. 2009. An event-based framework for characterizing the evolutionary behavior of interaction graphs. Transactions on Knowledge Discovery From Data 3, 4, 16.
5. Thomas Aynaud, Eric Fleury, Jean-Loup Guillaume, and Qinna Wang. 2013. Communities in evolving networks: Definitions, detection, and analysis techniques. In Dynamics on and of Complex Networks, Volume 2. Springer, 159--200.
6. Thomas Aynaud and Jean-Loup Guillaume. 2010. Static community detection algorithms for evolving networks. In Proceedings of the 8th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt’10). IEEE, Los Alamitos, CA, 513--519.
7. Thomas Aynaud and Jean-Loup Guillaume. 2011. Multi-step community detection and hierarchical time segmentation in evolving networks. In Proceedings of the 5th Social Network Mining and Analysis Workshop, (SNA-KDD Workshop’11).
8. Shweta Bansal, Sanjukta Bhowmick, and Prashant Paymal. 2011. Fast community detection for dynamic complex networks. In Complex Networks. Springer, 196--207.
9. Albert-László Barabási and Réka Albert. 1999. Emergence of scaling in random networks. Science 286, 5439, 509--512.
10. Danielle S. Bassett, Mason A. Porter, Nicholas F. Wymbs, Scott T. Grafton, Jean M. Carlson, and Peter J. Mucha. 2013. Robust detection of dynamic community structure in networks. Chaos 23, 1, 013142.
11. Marya Bazzi, Lucas G. S. Jeub, Alex Arenas, Sam D. Howison, and Mason A. Porter. 2016. Generative benchmark models for mesoscale structure in multilayer networks. arXiv:1608.06196.
12. Fabian Beck, Michael Burch, Stephan Diehl, and Daniel Weiskopf. 2017. A taxonomy and survey of dynamic graph visualization. Computer Graphics Forum 36, 1, 133--159.
13. Mariano G. Beiró, Jorge Rodolfo Busch, and José Ignacio Alvarez-Hamelin. 2010. Visualizing communities in dynamic networks. In Proceedings of the Latin-American Workshop on Dynamic Networks (LAWDN’10). 4.
14. Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment 2008, 10, P10008.
15. András Bóta, László Csizmadia, and András Pluhár. 2010. Community Detection and Its Use in Real Graphs. Available at http://www.academia.edu/17955192/Community_detection_and_its_use_in_Real_Graphs.
16. András Bóta, Miklós Krész, and András Pluhár. 2011. Dynamic communities and their detection. Acta Cybernetica 20, 1, 35--52.
17. Romain Bourqui, Frédéric Gilbert, Paolo Simonetto, Faraz Zaidi, Umang Sharan, and Fabien Jourdan. 2009. Detecting structural changes and command hierarchies in dynamic social networks. In Proceedings of the International Conference on Advances in Social Network Analysis and Mining (ASONAM’08). IEEE, Los Alamitos, CA, 83--88.
18. Kevin Boyack, Katy Börner, and Richard Klavans. 2008. Mapping the structure and evolution of chemistry research. Scientometrics 79, 1, 45--60.
19. Ulrik Brandes, Marco Gaertler, and Dorothea Wagner. 2003. Experiments on graph clustering algorithms. In Algorithms—ESA 2003. Lecture Notes in Computer Science, Vol. 2832. Springer, 568--579.
20. Urs Braun, Axel Schäfer, Henrik Walter, Susanne Erk, Nina Romanczuk-Seiferth, Leila Haddad, Janina I. Schweiger, et al. 2015. Dynamic reconfiguration of frontal brain networks during executive cognition in humans. Proceedings of the National Academy of Sciences 112, 37, 11678--11683.
21. Piotr Bródka, Stanisław Saganowski, and Przemysław Kazienko. 2013. GED: The method for group evolution discovery in social networks. Social Network Analysis and Mining 3, 1, 1--14.
22. Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. 2012. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems 27, 5, 387--408.
23. Remy Cazabet and Frederic Amblard. 2011. Simulate to detect: A multi-agent system for community detection. In Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT’11), Vol. 2. IEEE, Los Alamitos, CA, 402--408.
24. Rémy Cazabet and Frédéric Amblard. 2014. Dynamic community detection. In Encyclopedia of Social Network Analysis and Mining. Springer, 404--414.
25. Remy Cazabet, Frederic Amblard, and Chihab Hanachi. 2010. Detection of overlapping communities in dynamical social networks. In Proceedings of the 2nd International Conference on Social Computing (SocialCom’10). IEEE, Los Alamitos, CA, 309--314.
26. Remy Cazabet, Rathachai Chawuthai, and Hideaki Takeda. 2015. Using multiple-criteria methods to evaluate community partitions. arXiv:1502.05149.
27. Rémy Cazabet, Hideaki Takeda, Masahiro Hamasaki, and Frédéric Amblard. 2012. Using dynamic community detection to identify trends in user-generated content. Social Network Analysis and Mining 2, 4, 361--371.
28. Zhengzhang Chen, Kevin A. Wilson, Ye Jin, William Hendrix, and Nagiza F. Samatova. 2010. Detecting and tracking community dynamics in evolutionary networks. In Proceedings of the International Conference on Data Mining Workshops (ICDMW’10). IEEE, Los Alamitos, CA, 318--327.
29. Aaron Clauset, Mark E. J. Newman, and Cristopher Moore. 2004. Finding community structure in very large networks. Physical Review E 70, 6, 066111.
30. Anne Condon and Richard M. Karp. 2001. Algorithms for graph partitioning on the planted partition model. Random Structures and Algorithms 18, 2, 116--140.
31. Michele Coscia, Fosca Giannotti, and Dino Pedreschi. 2011. A classification for community discovery methods in complex networks. Statistical Analysis and Data Mining: The ASA Data Science Journal 4, 5, 512--546.
32. Harry Crane. 2014. The cut-and-paste process. Annals of Probability 42, 5, 1952--1979.
33. Harry Crane and Walter Dempsey. 2015. Community detection for interaction networks. arXiv:1509.09254.
34. Jean Creusefond, Thomas Largillier, and Sylvain Peyronnet. 2016. On the evaluation potential of quality functions in community detection for different contexts. In Proceedings of the International Conference and School on Network Science. 111--125.
35. Leon Danon, Albert Díaz-Guilera, and Alex Arenas. 2006. The effect of size heterogeneity on community identification in complex networks. Journal of Statistical Mechanics: Theory and Experiment 2006, 11, P11010.
36. Zeineb Dhouioui and Jalel Akaichi. 2013. Overlapping community detection in social networks. In Proceedings of the International Conference on Bioinformatics and Biomedicine (BIBM’13). IEEE, Los Alamitos, CA, 17--23.
37. Zeineb Dhouioui and Jalel Akaichi. 2014. Tracking dynamic community evolution in social networks. In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’14). IEEE, Los Alamitos, CA, 764--770.
38. Dongsheng Duan, Yuhua Li, Yanan Jin, and Zhengding Lu. 2009. Community mining on dynamic weighted directed graphs. In Proceedings of the 1st International Wworkshop on Complex Networks Meet Information 8 Knowledge Management. ACM, New York, NY, 11--18.
39. Dongsheng Duan, Yuhua Li, Ruixuan Li, and Zhengding Lu. 2012. Incremental K-clique clustering in dynamic social networks. Artificial Intelligence Review 38, 2, 129--147.
40. N. Duhan, A. K. Sharma, and K. K. Bhatia. 2009. Page ranking algorithms: A survey. In Proceedings of the International Advance Computing Conference (IACC’09). IEEE, Los Alamitos, CA, 1530--1537.
41. Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD’96), Vol. 96. 226--231.
42. Tanja Falkowski, Jorg Bartelheimer, and Myra Spiliopoulou. 2006. Mining and visualizing the evolution of subgroups in social networks. In Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence (WI’06). IEEE, Los Alamitos, CA, 52--58.
43. Tanja Falkowski, Anja Barth, and Myra Spiliopoulou. 2008. Studying community dynamics with an incremental graph mining algorithm. In Proceedings of the Americas Conference on Information Systems (AMCIS’08). 1--11.
44. Tanja Falkowski and Myra Spiliopoulou. 2007. Data mining for community dynamics. Kunstliche Intelligenz 21, 3 (2007), 23--29.
45. Ying Fan, Menghui Li, Peng Zhang, Jinshan Wu, and Zengru Di. 2007. Accuracy and precision of methods for community identification in weighted networks. Physica A: Statistical Mechanics and Its Applications 377, 1, 363--372.
46. James P. Ferry and J. Oren Bumgarner. 2012. Community detection and tracking on networks from a data fusion perspective. arXiv:1201.1512.
47. Gary William Flake, Steve Lawrence, and C. Lee Giles. 2000. Efficient identification of Web communities. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, 150--160.
48. Francesco Folino and Clara Pizzuti. 2010. Multiobjective evolutionary community detection for dynamic networks. In Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation. ACM, New York, NY, 535--536.
49. Francesco Folino and Clara Pizzuti. 2014. An evolutionary multiobjective approach for community discovery in dynamic networks. Transactions on Knowledge and Data Engineering 26, 8, 1838--1852.
50. Santo Fortunato. 2010. Community detection in graphs. Physics Reports 486, 3, 75--174.
51. Santo Fortunato and Marc Barthélemy. 2007. Resolution limit in community detection. Proceedings of the National Academy of Sciences 104, 1, 36--41.
52. Santo Fortunato and Darko Hric. 2016. Community detection in networks: A user guide. Physics Reports 659, 1--44.
53. Yaniv Frishman and Ayellet Tal. 2004. Dynamic drawing of clustered graphs. In Proceedings of the Symposium on Information Visualization (INFOVIS’04). IEEE, Los Alamitos, CA, 191--198.
54. Marco Gaertler, Robert Görke, and Dorothea Wagner. 2007. Significance-driven graph clustering. Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science, Vol. 4508. Springer, 11--26.
55. Laetitia Gauvin, André Panisson, and Ciro Cattuto. 2014. Detecting the community structure and activity patterns of temporal networks: A non-negative tensor factorization approach. PloS One 9, 1, e86028.
56. Lise Getoor and Christopher P. Diehl. 2005. Link mining: A survey. ACM SIGKDD Explorations Newsletter 7, 2, 3--12.
57. Amir Ghasemian, Pan Zhang, Aaron Clauset, Cristopher Moore, and Leto Peel. 2016. Detectability thresholds and optimal algorithms for community structure in dynamic networks. Physical Review X 6, 3, 031005.
58. Michelle Girvan and Mark E. J. Newman. 2002. Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99, 12, 7821--7826.
59. Bogdan Gliwa, Stanislaw Saganowski, Anna Zygmunt, Piotr Bródka, Przemyslaw Kazienko, and Jaroslaw Kozak. 2012. Identification of group changes in blogosphere. In Proceedings of the International Conference on Advances in Social Networks Analysis and Mining (ASONAM’12). IEEE, Los Alamitos, CA, 1201--1206.
60. Mark Goldberg, Malik Magdon-Ismail, Srinivas Nambirajan, and James Thompson. 2011. Tracking and predicting evolution of social communities. In Proceedings of the 3rd International Conference on Privacy, Security, Risk, and Trust (PASSAT’11) and the 3rd International Conference on Social Computing (SocialCom’11). IEEE, Los Alamitos, CA, 780--783.
61. Mao-Guo Gong, Ling-Jun Zhang, Jing-Jing Ma, and Li-Cheng Jiao. 2012. Community detection in dynamic social networks based on multiobjective immune algorithm. Journal of Computer Science and Technology 27, 3, 455--467.
62. Robert Görke, Tanja Hartmann, and Dorothea Wagner. 2012. Dynamic graph clustering using minimum-cut trees. Journal of Graph Algorithms and Applications 16, 2, 411--446.
63. Robert Görke, Pascal Maillard, Andrea Schumm, Christian Staudt, and Dorothea Wagner. 2013. Dynamic graph clustering combining modularity and smoothness. Journal of Experimental Algorithmics 18, 1--5.
64. Robert Görke, Pascal Maillard, Christian Staudt, and Dorothea Wagner. 2010. Modularity-driven clustering of dynamic graphs. In Proceedings of the 9th International Conference on Experimental Algorithms (SEA’10). 436--448.
65. Clara Granell, Richard K. Darst, Alex Arenas, Santo Fortunato, and Sergio Gómez. 2015. Benchmark model to assess community structure in evolving networks. Physical Review E 92, 1, 012805.
66. Derek Greene, Donal Doyle, and Padraig Cunningham. 2010. Tracking the evolution of communities in dynamic social networks. In Proceedings of the International Conference on Advances in Social Networks Analysis and Mining (ASONAM’10). IEEE, Los Alamitos, CA, 176--183.
67. Roger Guimerà, Marta Sales-Pardo, and Luís A. Nunes Amaral. 2007. Module identification in bipartite and directed networks. Physical Review E 76, 3, 036102.
68. Chonghui Guo, Jiajia Wang, and Zhen Zhang. 2014. Evolutionary community structure discovery in dynamic weighted networks. Physica A: Statistical Mechanics and Its Applications 413, 565--576.
69. Manish Gupta, Jing Gao, Yizhou Sun, and Jiawei Han. 2012. Integrating community matching and outlier detection for mining evolutionary community outliers. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, 859--867.
70. Tanja Hartmann, Andrea Kappes, and Dorothea Wagner. 2016. Clustering evolving networks. In Algorithm Engineering. Springer, 280--329.
71. Keith Henderson and Tina Eliassi-Rad. 2009. Applying latent Dirichlet allocation to group discovery in large graphs. In Proceedings of the ACM Symposium on Applied Computing. ACM, New York, NY, 1456--1461.
72. Tue Herlau, Morten Mørup, and Mikkel N. Schmidt. 2013. Modeling temporal evolution and multiscale structure in networks. In Proceedings of the 30th International Conference on Machine Learning. 960--968.
73. Anne-Sophie Himmel, Hendrik Molter, Rolf Niedermeier, and Manuel Sorge. 2016. Enumerating maximal cliques in temporal graphs. In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’16). IEEE, Los Alamitos, CA, 337--344.
74. Petter Holme and Jari Saramäki. 2012. Temporal networks. Physics Reports 519, 3, 97--125.
75. John Hopcroft, Omar Khan, Brian Kulis, and Bart Selman. 2004. Tracking evolving communities in large linked networks. Proceedings of the National Academy of Sciences 101, 1, 5249--5253.
76. Yifan Hu, Stephen G. Kobourov, and Sankar Veeramoni. 2012. Embedding, clustering and coloring for dynamic maps. In Proceedings of the Pacific Visualization Symposium (PacificVis’12). IEEE, Los Alamitos, CA, 33--40.
77. Nagehan İlhan and Şule Gündüz Öğüdücü. 2015. Predicting community evolution based on time series modeling. In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’15). ACM, New York, NY, 1509--1516.
78. Katsuhiko Ishiguro, Tomoharu Iwata, Naonori Ueda, and Joshua B. Tenenbaum. 2010. Dynamic infinite relational model for time-varying relational data analysis. In Advances in Neural Information Processing Systems 23 (NIPS’10). 919--927.
79. Manel Ben Jdidia, Céline Robardet, and Eric Fleury. 2007. Communities detection and analysis of their dynamics in collaborative networks. In Proceedings of the 2nd International Conference on Digital Information Management (ICDIM’07), Vol. 2. IEEE, Los Alamitos, CA, 744--749.
80. Vikas Kawadia and Sameet Sreenivasan. 2012. Online detection of temporal communities in evolving networks by estrangement confinement. arXiv:1203.5126.
81. Min-Soo Kim and Jiawei Han. 2009. A particle-and-density based evolutionary clustering method for dynamic networks. Proceedings of the VLDB Endowment 2, 1, 622--633.
82. Mikko Kivel, Alex Arenas, Marc Barthelemy, James P. Gleeson, Yamir Moreno, and Mason A. Porter. 2014. Multilayer networks. Journal of Complex Networks 2, 3, 203--271. arXiv:/oup/backfile/content_public/journal/comnet/2/3/10.1093_comnet_cnu 016/2/cnu016.pdf
83. Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. 2011. Temporal motifs in time-dependent networks. Journal of Statistical Mechanics: Theory and Experiment 2011, 11, P11005.
84. Andrea Lancichinetti and Santo Fortunato. 2009. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E 80, 1, 016118.
85. Andrea Lancichinetti, Santo Fortunato, and János Kertész. 2009. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics 11, 3, 033015.
86. Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. 2008. Benchmark graphs for testing community detection algorithms. Physical Review E 78, 4, 046110.
87. Matthieu Latapy, Tiphaine Viard, and Clémence Magnien. 2017. Stream graphs and link streams for the modeling of interactions over time. arXiv:1710.04073.
88. Pei Lee, Laks V. S. Lakshmanan, and Evangelos E. Milios. 2014. Incremental cluster evolution tracking from highly dynamic network data. In Proceedings of the 30th International Conference on Data Engineering (ICDE’14). IEEE, Los Alamitos, CA, 3--14.
89. Sungmin Lee, Luis E. C. Rocha, Fredrik Liljeros, and Petter Holme. 2012. Exploiting temporal network structures of human interaction to effectively immunize populations. PloS One 7, 5, e36439.
90. Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005. Graphs over time: Densification laws, shrinking diameters and possible explanations. In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. ACM, New York, NY, 177--187.
91. Xiao-Li Li, Aloysius Tan, S. Yu Philip, and See-Kiong Ng. 2011. ECODE: Event-based community detection from social networks. In Proceedings of the International Conference on Database Systems for Advanced Applications (DASFAA’11). 22--37.
92. Yu-Ru Lin, Yun Chi, Shenghuo Zhu, Hari Sundaram, and Belle L. Tseng. 2008. FacetNet: A framework for analyzing communities and their evolutions in dynamic networks. In Proceedings of the 17th International Conference on World Wide Web (WWW’08). ACM, New York, NY, 685--694.
93. Yu-Ru Lin, Yun Chi, Shenghuo Zhu, Hari Sundaram, and Belle L. Tseng. 2009. Analyzing communities and their evolutions in dynamic social networks. Transactions on Knowledge Discovery From Data 3, 2, 8.
94. Yu-Ru Lin, Jimeng Sun, Nan Cao, and Shixia Liu. 2010. Contextour: Contextual contour visual analysis on dynamic multi-relational clustering. In Proceedings of the International Conference on Data Mining. 418--429.
95. Hao-Shang Ma and Jen-Wei Huang. 2013. Cut: Community update and tracking in dynamic social networks. In Proceedings of the 7th Workshop on Social Network Mining and Analysis. ACM, New York, NY, 6.
96. Kevin T. Macon, Peter J. Mucha, and Mason A. Porter. 2012. Community structure in the United Nations general assembly. Physica A: Statistical Mechanics and Its Applications 391, 1, 343--361.
97. Naoki Masuda and Renaud Lambiotte. 2016. A Guide to Temporal Networks. Vol. 4. World Scientific.
98. Catherine Matias and Vincent Miele. 2016. Statistical clustering of temporal networks through a dynamic stochastic block model. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 79, 4, 1119--1141.
99. Catherine Matias, Tabea Rebafka, and Fanny Villers. 2015. Estimation and Clustering in a Semiparametric Poisson Process Stochastic Block Model for Longitudinal Networks: Semiparametric Estimation in PPSBM. Available at https://hal.archives-ouvertes.fr/hal-01245867v1.
100. Aaron F. McDaid, Derek Greene, and Neil Hurley. 2011. Normalized mutual information to evaluate overlapping community finding algorithms. arXiv:1110.2515.
101. K. Miller and T. Eliassi-Rad. 2009. Continuous time group discovery in dynamic graphs. In Proceedings of the NIPS 2009 Workshop on Analyzing Networks and Learning With Graphs.
102. Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298, 5594, 824--827.
103. Matteo Morini, Patrick Flandrin, Eric Fleury, Tommaso Venturini, and Pablo Jensen. 2017. Revealing evolutions in dynamical networks. arXiv:1707.02114.
104. Matteo Morini, Pablo Jensen, and Patrick Flandrin. 2015. Temporal evolution of communities based on scientometrics data. In Proceedings of Sciences Des Données et Humanités Numeriques.
105. Peter J. Mucha, Thomas Richardson, Kevin Macon, Mason A. Porter, and Jukka-Pekka Onnela. 2010. Community structure in time-dependent, multiscale, and multiplex networks. Science 328, 5980, 876--878.
106. Paul Newbold. 1983. ARIMA model building and the time series analysis approach to forecasting. Journal of Forecasting (pre-1986) 2, 1, 23.
107. Mark E. J. Newman. 2003. The structure and function of complex networks. SIAM Review 45, 2, 167--256.
108. Mark E. J. Newman. 2004. Fast algorithm for detecting community structure in networks. Physical Review E 69, 6, 066133.
109. Mark E. J. Newman and Michelle Girvan. 2004. Finding and evaluating community structure in networks. Physical Review E 69, 2, 026113.
110. Nam P. Nguyen, Thang N. Dinh, Sindhura Tokala, and My T. Thai. 2011a. Overlapping communities in dynamic networks: Their detection and mobile applications. In Proceedings of the 17th Annual International Conference on Mobile Computing and Networking. ACM, New York, NY, 85--96.
111. Nam P. Nguyen, Thang N. Dinh, Ying Xuan, and My T. Thai. 2011b. Adaptive algorithms for detecting community structure in dynamic social networks. In Proceedings of the 30th International Conference on Computer Communications (INFOCOM’11). IEEE, Los Alamitos, CA, 2282--2290.
112. Gergely Palla, Albert-László Barabási, and Tamás Vicsek. 2007. Quantifying social group evolution. Nature 446, 7136, 664--667.
113. Gergely Palla, Imre Derényi, Illés Farkas, and Tamás Vicsek. 2005. Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 7043, 814--818.
114. Leto Peel and Aaron Clauset. 2015. Detecting change points in the large-scale structure of evolving networks. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI’15). 2914--2920.
115. Leto Peel, Daniel B. Larremore, and Aaron Clauset. 2017. The ground truth about metadata and community detection in networks. Science Advances 3, 5, e1602548.
116. Pascal Pons and Matthieu Latapy. 2006. Computing communities in large networks using random walks. Journal of Graph Algorithms and Applications 10, 2, 191--218.
117. Filippo Radicchi, Claudio Castellano, Federico Cecconi, Vittorio Loreto, and Domenico Parisi. 2004. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences of the United States of America 101, 9, 2658--2663.
118. Khairi Reda, Chayant Tantipathananandh, Andrew Johnson, Jason Leigh, and Tanya Berger-Wolf. 2011. Visualizing the evolution of community structures in dynamic social networks. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 1061--1070.
119. A. Rényi and P. Erdos. 1959. On random graphs. Publicationes Mathematicae 6, 290--297.
120. Giulio Rossetti. 2015. Social Network Dynamics. Ph.D. Dissertation. Computer Science Department, University of Pisa, Italy.
121. Giulio Rossetti. 2017. RDYN: Graph benchmark handling community dynamics. Journal of Complex Networks 5, 6, 893--912.
122. Giulio Rossetti, Riccardo Guidotti, Diego Pennacchioli, Dino Pedreschi, and Fosca Giannotti. 2015. Interaction prediction in dynamic networks exploiting community discovery. In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’15). ACM, New York, NY, 553--558.
123. Giulio Rossetti, Luca Pappalardo, Dino Pedreschi, and Fosca Giannotti. 2017. Tiles: An online algorithm for community discovery in dynamic social networks. Machine Learning 106, 8, 1213--1241.
124. Giulio Rossetti, Luca Pappalardo, and Salvatore Rinzivillo. 2016. A novel approach to evaluate community detection algorithms on ground truth. In Complex Networks VII. Springer, 133--144.
125. Martin Rosvall and Carl T. Bergstrom. 2010. Mapping change in large networks. PloS One 5, 1, e8694.
126. Stanisław Saganowski, Bogdan Gliwa, Piotr Bródka, Anna Zygmunt, Przemysław Kazienko, and Jarosław Koźlak. 2015. Predicting community evolution in social networks. Entropy 17, 5, 3053--3096.
127. Erin N. Sawardecker, Marta Sales-Pardo, and Luıs A. Nunes Amaral. 2009. Detection of node group membership in networks with group overlap. European Physical Journal B: Condensed Matter and Complex Systems 67, 3, 277--284.
128. Nico Schlitter and Tanja Falkowski. 2009. Mining the dynamics of music preferences from a social networking site. In Proceedings of the International Conference on Advances in Social Network Analysis and Mining (ASONAM’09). IEEE, Los Alamitos, CA, 243--248.
129. Jiaxing Shang, Lianchen Liu, Feng Xie, Zhen Chen, Jiajia Miao, Xuelin Fang, and Cheng Wu. 2014. A real-time detecting algorithm for tracking community structure of dynamic networks. arXiv:1407.2683.
130. Junming Shao, Zhichao Han, and Qinli Yang. 2014. Community detection via local dynamic interaction. arXiv:1409.7978.
131. Jianbo Shi and Jitendra Malik. 2000. Normalized cuts and image segmentation. Transactions on Pattern Analysis and Machine Intelligence 22, 8, 888--905.
132. Jimeng Sun, Christos Faloutsos, Spiros Papadimitriou, and Philip S. Yu. 2007. Graphscope: Parameter-free mining of large time-evolving graphs. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, 687--696.
133. Yizhou Sun, Jie Tang, Jiawei Han, Cheng Chen, and Manish Gupta. 2014. Co-evolution of multi-typed objects in dynamic star networks. Transactions on Knowledge and Data Engineering 26, 12, 2942--2955.
134. Yizhou Sun, Jie Tang, Jiawei Han, Manish Gupta, and Bo Zhao. 2010. Community evolution detection in dynamic heterogeneous information networks. In Proceedings of the 8th Workshop on Mining and Learning With Graphs. ACM, New York, NY, 137--146.
135. Lionel Tabourier, Anne-Sophie Libert, and Renaud Lambiotte. 2016. Predicting links in ego-networks using temporal information. EPJ Data Science 5, 1, 1.
136. Mansoureh Takaffoli, Farzad Sangi, Justin Fagnan, and Osmar R. Zaïane. 2011. MODEC-modeling and detecting evolutions of communities. In Proceedings of the 5th International Conference on Weblogs and Social Media (ICWSM’11). 30--41.
137. Biying Tan, Feida Zhu, Qiang Qu, and Siyuan Liu. 2014. Online community transition detection. In Proceedings of the International Conference on Web-Age Information Management. 633--644.
138. Lei Tang, Huan Liu, Jianping Zhang, and Zohreh Nazeri. 2008. Community evolution in dynamic multi-mode networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, 677--685.
139. Chayant Tantipathananandh, Tanya Berger-Wolf, and David Kempe. 2007. A framework for community identification in dynamic social networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, NY, 717--726.
140. Minh Van Nguyen, Michael Kirley, and Rodolfo García-Flores. 2012. Community evolution in a scientific collaboration network. In Proceedings of the Congress on Evolutionary Computation (CEC’12). IEEE, Los Alamitos, CA, 1--8.
141. Corinna Vehlow, Fabian Beck, Patrick Auwärter, and Daniel Weiskopf. 2015a. Visualizing the evolution of communities in dynamic graphs. In Computer Graphics Forum, Vol. 34. Wiley Online Library, 277--288.
142. Corinna Vehlow, Fabian Beck, and Daniel Weiskopf. 2015b. The state of the art in visualizing group structures in graphs. In Proceedings of the Eurographics Conference on Visualization (EuroVis’15)-STARs, Vol. 2.
143. Corinna Vehlow, Fabian Beck, and Daniel Weiskopf. 2016. Visualizing dynamic hierarchies in graph sequences. IEEE Transactions on Visualization and Computer Graphics 22, 10, 2343--2357.
144. Tiphaine Viard, Matthieu Latapy, and Clémence Magnien. 2016. Computing maximal cliques in link streams. Theoretical Computer Science 609, 245--252.
145. Yi Wang, Bin Wu, and Xin Pei. 2008. CommTracker: A core-based algorithm of tracking community evolution. In Proceedings of the 4th International Conference on Advanced Data Mining and Applications (ADMA’08). 229--240.
146. Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of small-world networks. Nature 393, 6684, 440--442.
147. Jierui Xie, Mingming Chen, and Boleslaw K. Szymanski. 2013a. LabelRankT: Incremental community detection in dynamic networks via label propagation. In Proceedings of the Workshop on Dynamic Networks Management and Mining. ACM, New York, NY, 25--32.
148. Jierui Xie, Stephen Kelley, and Boleslaw K. Szymanski. 2013b. Overlapping community detection in networks: The state-of-the-art and comparative study. ACM Computing Surveys 45, 4, 43.
149. Jierui Xie and Boleslaw K. Szymanski. 2013. LabelRank: A stabilized label propagation algorithm for community detection in networks. In Proceedings of the 2nd Network Science Workshop (NSW’13). IEEE, Los Alamitos, CA, 138--143.
150. Hao Xu, Zhenwen Wang, and Weidong Xiao. 2013a. Analyzing community core evolution in mobile social networks. In Proceedings of the International Conference on Social Computing (SocialCom’13). IEEE, Los Alamitos, CA, 154--161.
151. Hao Xu, Weidong Xiao, Daquan Tang, Jiuyang Tang, and Zhenwen Wang. 2013b. Community core evolution in mobile social networks. Scientific World Journal 2013, 781281.
152. Kevin S. Xu and Alfred O. Hero. 2014. Dynamic stochastic blockmodels for time-evolving social networks. Journal of Selected Topics in Signal Processing 8, 4, 552--562.
153. Jaewon Yang and Jure Leskovec. 2014. Structure and overlaps of ground-truth communities in networks. Transactions on Intelligent Systems and Technology 5, 2, 26.
154. Jaewon Yang and Jure Leskovec. 2015. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems 42, 1, 181--213.
155. Tianbao Yang, Yun Chi, Shenghuo Zhu, Yihong Gong, and Rong Jin. 2009. A Bayesian approach toward finding communities and their evolutions in dynamic social networks. In Proceedings of the International Conference on Data Mining. 990--1001.
156. Tianbao Yang, Yun Chi, Shenghuo Zhu, Yihong Gong, and Rong Jin. 2011. Detecting communities and their evolutions in dynamic social networks—a Bayesian approach. Machine Learning 82, 2, 157--189.
157. Anita Zakrzewska and David A. Bader. 2015. A dynamic algorithm for local community detection in graphs. In Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’15). ACM, New York, NY, 559--564.
158. Ding Zhou, Isaac Councill, Hongyuan Zha, and C. Lee Giles. 2007. Discovering temporal communities from social network documents. In Proceedings of the 7th International Conference on Data Mining (ICDM’07). IEEE, Los Alamitos, CA, 745--750.

Index Terms

• General and reference

  • Document types

    • Surveys and overviews

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Clustering and classification

  • Information systems applications

    • Data mining

      • Clustering

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

• Networks

  • Network properties

    • Network dynamics

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis

      • Dynamic graph algorithms