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.
Supplemental Material
Available for Download
Supplemental movie, appendix, image and software files for, Community Discovery in Dynamic Networks: A Survey
- 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. Google ScholarDigital Library
- Uri Alon. 2007. Network motifs: Theory and experimental approaches. Nature Reviews Genetics 8, 6, 450--461.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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).Google Scholar
- Shweta Bansal, Sanjukta Bhowmick, and Prashant Paymal. 2011. Fast community detection for dynamic complex networks. In Complex Networks. Springer, 196--207.Google Scholar
- Albert-László Barabási and Réka Albert. 1999. Emergence of scaling in random networks. Science 286, 5439, 509--512.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Kevin Boyack, Katy Börner, and Richard Klavans. 2008. Mapping the structure and evolution of chemistry research. Scientometrics 79, 1, 45--60.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Rémy Cazabet and Frédéric Amblard. 2014. Dynamic community detection. In Encyclopedia of Social Network Analysis and Mining. Springer, 404--414.Google Scholar
- 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. Google ScholarDigital Library
- Remy Cazabet, Rathachai Chawuthai, and Hideaki Takeda. 2015. Using multiple-criteria methods to evaluate community partitions. arXiv:1502.05149.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Aaron Clauset, Mark E. J. Newman, and Cristopher Moore. 2004. Finding community structure in very large networks. Physical Review E 70, 6, 066111.Google ScholarCross Ref
- Anne Condon and Richard M. Karp. 2001. Algorithms for graph partitioning on the planted partition model. Random Structures and Algorithms 18, 2, 116--140. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Harry Crane. 2014. The cut-and-paste process. Annals of Probability 42, 5, 1952--1979.Google ScholarCross Ref
- Harry Crane and Walter Dempsey. 2015. Community detection for interaction networks. arXiv:1509.09254.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Tanja Falkowski and Myra Spiliopoulou. 2007. Data mining for community dynamics. Kunstliche Intelligenz 21, 3 (2007), 23--29.Google Scholar
- 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.Google ScholarCross Ref
- James P. Ferry and J. Oren Bumgarner. 2012. Community detection and tracking on networks from a data fusion perspective. arXiv:1201.1512.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Santo Fortunato. 2010. Community detection in graphs. Physics Reports 486, 3, 75--174.Google ScholarCross Ref
- Santo Fortunato and Marc Barthélemy. 2007. Resolution limit in community detection. Proceedings of the National Academy of Sciences 104, 1, 36--41.Google ScholarCross Ref
- Santo Fortunato and Darko Hric. 2016. Community detection in networks: A user guide. Physics Reports 659, 1--44.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Lise Getoor and Christopher P. Diehl. 2005. Link mining: A survey. ACM SIGKDD Explorations Newsletter 7, 2, 3--12. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Tanja Hartmann, Andrea Kappes, and Dorothea Wagner. 2016. Clustering evolving networks. In Algorithm Engineering. Springer, 280--329.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Petter Holme and Jari Saramäki. 2012. Temporal networks. Physics Reports 519, 3, 97--125.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Vikas Kawadia and Sameet Sreenivasan. 2012. Online detection of temporal communities in evolving networks by estrangement confinement. arXiv:1203.5126.Google Scholar
- 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. Google ScholarDigital Library
- 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.pdfGoogle ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. 2008. Benchmark graphs for testing community detection algorithms. Physical Review E 78, 4, 046110.Google ScholarCross Ref
- Matthieu Latapy, Tiphaine Viard, and Clémence Magnien. 2017. Stream graphs and link streams for the modeling of interactions over time. arXiv:1710.04073.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Naoki Masuda and Renaud Lambiotte. 2016. A Guide to Temporal Networks. Vol. 4. World Scientific.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google Scholar
- Aaron F. McDaid, Derek Greene, and Neil Hurley. 2011. Normalized mutual information to evaluate overlapping community finding algorithms. arXiv:1110.2515.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Matteo Morini, Patrick Flandrin, Eric Fleury, Tommaso Venturini, and Pablo Jensen. 2017. Revealing evolutions in dynamical networks. arXiv:1707.02114.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Paul Newbold. 1983. ARIMA model building and the time series analysis approach to forecasting. Journal of Forecasting (pre-1986) 2, 1, 23.Google Scholar
- Mark E. J. Newman. 2003. The structure and function of complex networks. SIAM Review 45, 2, 167--256.Google ScholarDigital Library
- Mark E. J. Newman. 2004. Fast algorithm for detecting community structure in networks. Physical Review E 69, 6, 066133.Google Scholar
- Mark E. J. Newman and Michelle Girvan. 2004. Finding and evaluating community structure in networks. Physical Review E 69, 2, 026113.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Gergely Palla, Albert-László Barabási, and Tamás Vicsek. 2007. Quantifying social group evolution. Nature 446, 7136, 664--667.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- Leto Peel, Daniel B. Larremore, and Aaron Clauset. 2017. The ground truth about metadata and community detection in networks. Science Advances 3, 5, e1602548.Google ScholarCross Ref
- Pascal Pons and Matthieu Latapy. 2006. Computing communities in large networks using random walks. Journal of Graph Algorithms and Applications 10, 2, 191--218.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- A. Rényi and P. Erdos. 1959. On random graphs. Publicationes Mathematicae 6, 290--297.Google Scholar
- Giulio Rossetti. 2015. Social Network Dynamics. Ph.D. Dissertation. Computer Science Department, University of Pisa, Italy.Google Scholar
- Giulio Rossetti. 2017. RDYN: Graph benchmark handling community dynamics. Journal of Complex Networks 5, 6, 893--912.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Martin Rosvall and Carl T. Bergstrom. 2010. Mapping change in large networks. PloS One 5, 1, e8694.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google Scholar
- Junming Shao, Zhichao Han, and Qinli Yang. 2014. Community detection via local dynamic interaction. arXiv:1409.7978.Google Scholar
- Jianbo Shi and Jitendra Malik. 2000. Normalized cuts and image segmentation. Transactions on Pattern Analysis and Machine Intelligence 22, 8, 888--905. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- Lionel Tabourier, Anne-Sophie Libert, and Renaud Lambiotte. 2016. Predicting links in ego-networks using temporal information. EPJ Data Science 5, 1, 1.Google ScholarCross Ref
- 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.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google ScholarDigital Library
- Tiphaine Viard, Matthieu Latapy, and Clémence Magnien. 2016. Computing maximal cliques in link streams. Theoretical Computer Science 609, 245--252. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of small-world networks. Nature 393, 6684, 440--442.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- Hao Xu, Weidong Xiao, Daquan Tang, Jiuyang Tang, and Zhenwen Wang. 2013b. Community core evolution in mobile social networks. Scientific World Journal 2013, 781281.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Jaewon Yang and Jure Leskovec. 2014. Structure and overlaps of ground-truth communities in networks. Transactions on Intelligent Systems and Technology 5, 2, 26. Google ScholarDigital Library
- Jaewon Yang and Jure Leskovec. 2015. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems 42, 1, 181--213. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- Community Discovery in Dynamic Networks: A Survey
Recommendations
A classification for community discovery methods in complex networks
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 ...
Multi-objective optimization algorithm based on characteristics fusion of dynamic social networks for community discovery
AbstractThe network structure exhibits a variety of changes over time. Fusing this structure and the development of communities in dynamic networks plays an important role in analyzing the evolution and development of the entire network. How ...
Evolutionary community discovery in dynamic social networks via resistance distance
Highlights- We propose a dynamic community evolution method based on resistance distance.
- ...
AbstractTraditional social community discovery methods concentrate mainly on static social networks, but the analysis of dynamic networks is a prerequisite for real-time and personalized social services. Through the study of community changes, ...
Comments