République Algérienne Démocratique et Populaire

Ministère de l'Enseignement Supérieur et de la Recherche Scientifique

École nationale Supérieure d'Informatique

Présentée pour obtenir le grade de

DOCTORAT EN SCIENCES

Souâad Boudebza

Approche pour la Détection de Communautés dynamiques dans les Réseaux Sociaux

Directeur de thèse : Omar Nouali

Co-Directeur de thèse : Faiçal Azouaou

Soutenue le : 14/04/2022, devant le jury composé de:

M. Amar Balla,     Professeur, ESI,     Président

Mme Fatima Si Tayeb,     Professeur, ESI,     Examinatrice

M. Hachem Slimani,     Professeur, Université de Béjaïa,     Examinateur

Mme Malika Bessedik,     MCA, ESI,     Examinatrice

M. Omar Nouali,     Directeur de Recherche, CERIST,     Directeur de thèse

People's and Democratic Republic of Algeria

Ministry of Higher Education and Scientific Research

Higher National School of Computer Science

To obtain the degree of

DOCTOR OF SCIENCE

Souâad Boudebza

An Approach for Detecting Dynamic Communities in Social Networks

Under the supervision of: Omar Nouali

and  Faiçal Azouaou

Defended on: 14/04/2022, in front of a jury composed by:

Board of Examiners

Mr Amar Balla,     Professor, ESI,     Chairman

Mrs Fatima Si Tayeb,     Professor,ESI,     Examiner

Mr Hachem Slimani,     Professor, University of Bejaia,     Examiner

Mrs Malika Bessedik,     MCA, ESI,     Examiner

Mr Omar Nouali,     Director of Research, CERIST,     Advisor

tocchapterList of Figures
tocchapterList of Tables

[remember picture,overlay]
[yshift=-5cm] (0) at (current page.north west)
[remember picture, overlay]
[fill=grisclaire] (0,0) rectangle
GN=[circle,fill=grisfonce, draw,text=white,font=,font=,
minimum size=3cm]
PN=[circle,fill=white, draw,text=black,scale=0.4]
node[GN] (0) at (3.3,3)
node[PN] (1) at (5.3,3.3)
node[PN] (2) at (6,2)
node[PN] (3) at (7.1,2.75)
node[PN] (4) at (6.2,4.25)
node[PN] (5) at (7.75,4)
node[PN] (6) at (8.2,2.5)
node[PN] (7) at (9,3.3)
node[PN] (8) at (10,4)
node[PN] (9) at (10.8,2.4)
node[PN] (10) at (12.9,3.25)
node[PN] (11) at (12.3,3.8)
node[PN] (12) at (13.9,3)
node[PN] (13) at (16,2.5)
node[PN] (14) at (17,3)
node[PN] (15) at (18.3,2.5)
node[PN] (16) at (17.1,2.25) ;
rounded corners=16pt,inner sep=11pt,
fill=grisfonce,font=] (17)
[line width=0mm,   black] (0)–(1)–(2)–(3)–(4)–(1)–(3)–(6)–(7)–(5)–(4);
[line width=0mm,   black] (7)–(8)–(9)–(7)–(11)–(10)–(9)–(11)–(8);
[line width=0mm,   black] (10)–(12)–(13)–(16)–(15)–(14)–(12)–(15);
[line width=0mm,   black] (13)–(17);

[remember picture,overlay]
[yshift=-5cm] (0) at (current page.north west)
[remember picture, overlay]
[fill=grisclaire] (0,0) rectangle
GN=[circle,fill=grisfonce, draw,text=white,font=,font=,
minimum size=3cm]
PN=[circle,fill=white, draw,text=black,scale=0.4]
node[GN] (0) at (3.3,3)
node[PN] (1) at (5.3,3.3)
node[PN] (2) at (6,2)
node[PN] (3) at (7.1,2.75)
node[PN] (4) at (6.2,4.25)
node[PN] (5) at (7.75,4)
node[PN] (6) at (8.2,2.5)
node[PN] (7) at (9,3.3)
node[PN] (8) at (10,4)
node[PN] (9) at (10.8,2.4)
node[PN] (10) at (12.9,3.25)
node[PN] (11) at (12.3,3.8)
node[PN] (12) at (13.9,3)
node[PN] (13) at (16,2.5)
node[PN] (14) at (17,3)
node[PN] (15) at (18.3,2.5)
node[PN] (16) at (17.1,2.25) ;
[anchor=east,xshift=.95,rectangle, rounded corners=16pt,inner sep=11pt,fill=grisfonce,text width=120mm,font=] (17) #1;
[line width=0mm,   black] (0)–(1)–(2)–(3)–(4)–(1)–(3)–(6)–(7)–(5)–(4);
[line width=0mm,   black] (7)–(8)–(9)–(7)–(11)–(10)–(9)–(11)–(8);
[line width=0mm,   black] (10)–(12)–(13)–(16)–(15)–(14)–(12)–(15);
[line width=0mm,   black] (13)–(17);

[remember picture,overlay]
[yshift=-5cm] (0) at (current page.north west)
[remember picture, overlay]
[fill=grisclaire] (0,0) rectangle
GN=[circle,fill=grisfonce, draw,text=white,font=,font=,
minimum size=3cm]
PN=[circle,fill=white, draw,text=black,scale=0.4]
node[GN] (0) at (3.3,3)
node[PN] (1) at (5.3,3.3)
node[PN] (2) at (6,2)
node[PN] (3) at (7.1,2.75)
node[PN] (4) at (6.2,4.25)
node[PN] (5) at (7.75,4)
node[PN] (6) at (8.2,2.5)
node[PN] (7) at (9,3.3)
node[PN] (8) at (10,4)
node[PN] (9) at (10.8,2.4)
node[PN] (10) at (12.9,3.25)
node[PN] (11) at (12.3,3.8)
node[PN] (12) at (13.9,3)
node[PN] (13) at (16,2.5)
node[PN] (14) at (17,3)
node[PN] (15) at (18.3,2.5)
node[PN] (16) at (17.1,2.25) ;
rounded corners=16pt,inner sep=11pt,
fill=grisfonce,font=] (17)
[line width=0mm,   black] (0)–(1)–(2)–(3)–(4)–(1)–(3)–(6)–(7)–(5)–(4);
[line width=0mm,   black] (7)–(8)–(9)–(7)–(11)–(10)–(9)–(11)–(8);
[line width=0mm,   black] (10)–(12)–(13)–(16)–(15)–(14)–(12)–(15);
[line width=0mm,   black] (13)–(17);

[remember picture,overlay]
[yshift=-5cm] (0) at (current page.north west)
[remember picture, overlay]
[fill=grisclaire] (0,0) rectangle
rounded corners=16pt,inner sep=11pt,
fill=grisfonce,font=] (17)

[1]
Agarwal, M. K., Ramamritham, K., and Bhide, M. (2012).
Real time discovery of dense clusters in highly dynamic graphs:
identifying real world events in highly dynamic environments.
arXiv preprint arXiv:1207.0138.

[2]
Aktunc, R., Toroslu, I. H., Ozer, M., and Davulcu, H. (2015).
A dynamic modularity based community detection algorithm for
large-scale networks: Dslm.
In Proceedings of the 2015 IEEE/ACM international conference on
advances in social networks analysis and mining 2015, pages 1177–1183.

[3]
Albert, R. and Barabási, A.-L. (2002).
Statistical mechanics of complex networks.
Reviews of modern physics, 74(1):47.

[4]
Alvari, H., Hajibagheri, A., and Sukthankar, G. (2014).
Community detection in dynamic social networks: A game-theoretic
In 2014 IEEE/ACM International Conference on Advances in Social
Networks Analysis and Mining (ASONAM 2014), pages 101–107. IEEE.

[5]
Arenas, A., Fernandez, A., and Gomez, S. (2008).
Analysis of the structure of complex networks at different resolution
New journal of physics, 10(5):053039.

[6]
Asadi, M. and Ghaderi, F. (2018).
Incremental community detection in social networks using label
propagation method.
In 2018 23rd Conference of Open Innovations Association
(FRUCT), pages 39–47. IEEE.

[7]
Asur, S., Parthasarathy, S., and Ucar, D. (2009).
An event-based framework for characterizing the evolutionary behavior
of interaction graphs.
ACM Transactions on Knowledge Discovery from Data (TKDD),

[8]
Aynaud, T., Fleury, E., Guillaume, J.-L., and Wang, Q. (2013).
Communities in evolving networks: definitions, detection, and
analysis techniques.
In Dynamics On and Of Complex Networks, Volume 2, pages
159–200. Springer.

[9]
Aynaud, T. and Guillaume, J.-L. (2010).
Static community detection algorithms for evolving networks.
In 8th International Symposium on Modeling and Optimization in
Mobile, Ad Hoc, and Wireless Networks, pages 513–519. IEEE.

[10]
Aynaud, T. and Guillaume, J.-L. (2011).
Multi-step community detection and hierarchical time segmentation in
evolving networks.
In Proceedings of the 5th SNA-KDD workshop.

[11]
Bansal, S., Bhowmick, S., and Paymal, P. (2011).
Fast community detection for dynamic complex networks.
In Complex Networks, pages 196–207. Springer.

[12]
Barabási, A.-L. (2013).
Network science.
Philosophical Transactions of the Royal Society A: Mathematical,
Physical and Engineering Sciences, 371(1987):20120375.

[13]
Barabási, A.-L. and Albert, R. (1999).
Emergence of scaling in random networks.
science, 286(5439):509–512.

[14]
Barabási, A.-L. and Bonabeau, E. (2003).
Scale-free networks.
Scientific american, 288(5):60–69.

[15]
Barnes, E. R. (1982).
An algorithm for partitioning the nodes of a graph.
SIAM Journal on Algebraic Discrete Methods, 3(4):541–550.

[16]
Bassett, D. S., Porter, M. A., Wymbs, N. F., Grafton, S. T., Carlson, J. M.,
and Mucha, P. J. (2013).
Robust detection of dynamic community structure in networks.
Chaos: An Interdisciplinary Journal of Nonlinear Science,

[17]
Beiró, M. G., Busch, J. R., and Alvarez-Hamelin, J. I. (2010).
Visualizing communities in dynamic networks.
In LAWDN-Latin-American Workshop on Dynamic Networks, pages

[18]
Bhat, S. Y. and Abulaish, M. (2014).
Hoctracker: Tracking the evolution of hierarchical and overlapping
communities in dynamic social networks.
IEEE Transactions on Knowledge and Data engineering,

[19]
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. (2008).
Fast unfolding of communities in large networks.
Journal of statistical mechanics: theory and experiment,

[20]
Boettcher, S. (1999).
Extremal optimization of graph partitioning at the percolation
Journal of Physics A: Mathematical and General, 32(28):5201.

[21]
Boratto, L., Carta, S., Chessa, A., Agelli, M., and Clemente, M. L. (2009).
Group recommendation with automatic identification of users
In Proceedings of the 2009 IEEE/WIC/ACM International Joint
Conference on Web Intelligence and Intelligent Agent Technology - Volume 03,
WI-IAT '09, pages 547–550, Washington, DC, USA. IEEE Computer Society.

[22]
Borgatti, S. P., Mehra, A., Brass, D. J., and Labianca, G. (2009).
Network analysis in the social sciences.
science, 323(5916):892–895.

[23]
Bóta, A., Csizmadia, L., and Pluhár, A. (2010).
Community detection and its use in real graphs.

[24]
Bóta, A., Krész, M., and Pluhár, A. (2011).
Dynamic communities and their detection.
Acta Cybernetica, 20(1):35–52.

[25]
Boudebza, S., Azouaou, F., and Nouali, O. (2015).
Ontology-based approach for temporal semantic modelling of social
In 3rd International Conference on Future Internet of Things and
Cloud, pages 736–741. IEEE.

[26]
Boudebza, S., Cazabet, R., Azouaou, F., and Nouali, O. (2018).
Olcpm: An online framework for detecting overlapping communities in
dynamic social networks.
Computer Communications, 123:36–51.

[27]
Boudebza, S., Cazabet, R., Nouali, O., and Azouaou, F. (2019).
Detecting stable communities in link streams at multiple temporal
arXiv preprint arXiv:1907.10453.

[28]
Bourqui, R., Gilbert, F., Simonetto, P., Zaidi, F., Sharan, U., and Jourdan, F.
Detecting structural changes and command hierarchies in dynamic
social networks.
In 2009 International Conference on Advances in Social Network
Analysis and Mining, pages 83–88. IEEE.

[29]
Brandes, U. and Erlebach, T. (2005).
Network Analysis: Methodological Foundations (Lecture Notes in
Computer Science).
Springer-Verlag, Berlin, Heidelberg.

[30]
Bródka, P., Saganowski, S., and Kazienko, P. (2013).
Ged: the method for group evolution discovery in social networks.
Social Network Analysis and Mining, 3(1):1–14.

[31]
Cazabet, R. and Amblard, F. (2011).
Simulate to detect: a multi-agent system for community detection.
In Proceedings of the 2011 IEEE/WIC/ACM International
Conferences on Web Intelligence and Intelligent Agent Technology-Volume 02,
pages 402–408. IEEE Computer Society.

[32]
Cazabet, R. and Amblard, F. (2014).
Dynamic community detection.
Encyclopedia of Social Network Analysis and Mining, pages

[33]
Cazabet, R., Amblard, F., and Hanachi, C. (2010).
Detection of overlapping communities in dynamical social networks.
In 2010 IEEE second international conference on social
computing, pages 309–314. IEEE.

[34]
Cazabet, R. and Rossetti, G. (2019).
Challenges in community discovery on temporal networks.
arXiv preprint arXiv:1907.11435.

[35]
Chakrabarti, D., Kumar, R., and Tomkins, A. (2006).
Evolutionary clustering.
In Proceedings of the 12th ACM SIGKDD international conference
on Knowledge discovery and data mining, pages 554–560.

[36]
Chen, J., Liu, D., Hao, F., and Wang, H. (2020).
Community detection in dynamic signed network: an intimacy
evolutionary clustering algorithm.
Journal of Ambient Intelligence and Humanized Computing,

[37]
Chen, Z., Wilson, K. A., Jin, Y., Hendrix, W., and Samatova, N. F. (2010).
Detecting and tracking community dynamics in evolutionary networks.
In 2010 IEEE International Conference on Data Mining Workshops,
pages 318–327. IEEE.

[38]
Cheraghchi, H. S. and Zakerolhosseini, A. (2017).
Toward a novel art inspired incremental community mining algorithm in
dynamic social network.
Applied Intelligence, 46(2):409–426.

[39]
Chi, Y., Song, X., Zhou, D., Hino, K., and Tseng, B. L. (2007).
Evolutionary spectral clustering by incorporating temporal
In Proceedings of the 13th ACM SIGKDD international conference
on Knowledge discovery and data mining, pages 153–162.

[40]
Chong, W. H. and Teow, L. N. (2013).
An incremental batch technique for community detection.
In Proceedings of the 16th International Conference on
Information Fusion, pages 750–757. IEEE.

[41]
Clauset, A., Newman, M. E., and Moore, C. (2004).
Finding community structure in very large networks.
Physical review E, 70(6):066111.

[42]
Cordeiro, M., Sarmento, R. P., and Gama, J. (2016).
Dynamic community detection in evolving networks using locality
modularity optimization.
Social Network Analysis and Mining, 6(1):15.

[43]
Coscia, M., Rossetti, G., Giannotti, F., and Pedreschi, D. (2012).
Demon: a local-first discovery method for overlapping communities.
In Proceedings of the 18th ACM SIGKDD international conference
on Knowledge discovery and data mining, pages 615–623.

[44]
Costa, L. d. F., Rodrigues, F. A., Travieso, G., and Villas Boas, P. R. (2007).
Characterization of complex networks: A survey of measurements.
Advances in physics, 56(1):167–242.

[45]
Crane, H. and Dempsey, W. (2015).
Community detection for interaction networks.
arXiv preprint arXiv:1509.09254.

[46]
Dakiche, N., Tayeb, F. B.-S., Slimani, Y., and Benatchba, K. (2019).
Tracking community evolution in social networks: A survey.
Information Processing & Management, 56(3):1084–1102.

[47]
Danon, L., Diaz-Guilera, A., Duch, J., and Arenas, A. (2005).
Comparing community structure identification.
Journal of Statistical Mechanics: Theory and Experiment,

[48]
Deng, W., Patil, R., Najjar, L., Shi, Y., and Chen, Z. (2014).
Incorporating community detection and clustering techniques into
collaborative filtering model.
In Proceedings of the Second International Conference on
Information Technology and Quantitative Management, ITQM 2014, National
Research University Higher School of Economics (HSE), Moscow, Russia, June
3-5, 2014, pages 66–74.

[49]
Dhouioui, Z. and Akaichi, J. (2014).
Tracking dynamic community evolution in social networks.
In 2014 IEEE/ACM International Conference on Advances in Social
Networks Analysis and Mining (ASONAM 2014), pages 764–770. IEEE.

[50]
Dinh, T. N., Xuan, Y., and Thai, M. T. (2009).
Towards social-aware routing in dynamic communication networks.
In 2009 IEEE 28th International Performance Computing and
Communications Conference, pages 161–168. IEEE.

[51]
Donath, W. E. and Hoffman, A. J. (2003).
Lower bounds for the partitioning of graphs.
In Selected Papers Of Alan J Hoffman: With Commentary, pages
437–442. World Scientific.

[52]
Duan, D., Li, Y., Jin, Y., and Lu, Z. (2009).
Community mining on dynamic weighted directed graphs.
In Proceedings of the 1st ACM international workshop on Complex
networks meet information & knowledge management, pages 11–18.

[53]
Duan, D., Li, Y., Li, R., and Lu, Z. (2012).
Incremental k-clique clustering in dynamic social networks.
Artificial Intelligence Review, 38(2):129–147.

[54]
Duch, J. and Arenas, A. (2005).
Community detection in complex networks using extremal optimization.
Physical review E, 72(2):027104.

[55]
Erdös, P. and Rényi, A. (1959).
On random graphs i.
Publicationes Mathematicae Debrecen, 6:290–297.

[56]
Falkowski, T., Bartelheimer, J., and Spiliopoulou, M. (2006).
Mining and visualizing the evolution of subgroups in social networks.
In Proceedings of the 2006 IEEE/WIC/ACM International Conference
on Web Intelligence, pages 52–58. IEEE Computer Society.

[57]
Falkowski, T., Barth, A., and Spiliopoulou, M. (2008).
Studying community dynamics with an incremental graph mining
AMCIS 2008 Proceedings, page 29.

[58]
Falkowski, T. and Spiliopoulou, M. (2007).
Users in volatile communities: Studying active participation and
community evolution.
In International Conference on User Modeling, pages 47–56.

[59]
Fenn, D., Porter, M., McDonald, M., Williams, S., Johnson, N., and Jones, N.
Dynamic communities in multichannel data: An application to the
foreign exchange market during the 2007–2008 credit crisis.
Chaos, 19:033119–8.

[60]
Ferrara, E., Meo, P. D., Catanese, S., and Fiumara, G. (2014).
Detecting criminal organizations in mobile phone networks.
CoRR, abs/1404.1295.

[61]
Fiedler, M. (1973).
Algebraic connectivity of graphs.
Czechoslovak mathematical journal, 23(2):298–305.

[62]
Folino, F. and Pizzuti, C. (2010).
Multiobjective evolutionary community detection for dynamic networks.
In GECCO, pages 535–536.

[63]
Fortunato, S. (2010).
Community detection in graphs.
Physics reports, 486(3-5):75–174.

[64]
Fortunato, S. and Barthelemy, M. (2007).
Resolution limit in community detection.
Proceedings of the national academy of sciences, 104(1):36–41.

[65]
Fortunato, S. and Hric, D. (2016).
Community detection in networks: A user guide.
Physics reports, 659:1–44.

[66]
Fournet, J. and Barrat, A. (2014).
Contact patterns among high school students.
PloS one, 9(9):e107878.

[67]
Freeman, L. C. (1978).
Centrality in social networks conceptual clarification.
Social networks, 1(3):215–239.

[68]
Gao, W., Luo, W., and Bu, C. (2016).
Evolutionary community discovery in dynamic networks based on leader
In 2016 International Conference on Big Data and Smart Computing
(BigComp), pages 53–60. IEEE.

[69]
Gauvin, L., Panisson, A., and Cattuto, C. (2014).
Detecting the community structure and activity patterns of temporal
networks: a non-negative tensor factorization approach.
PloS one, 9(1):e86028.

[70]
Ghasemian, A., Zhang, P., Clauset, A., Moore, C., and Peel, L. (2016).
Detectability thresholds and optimal algorithms for community
structure in dynamic networks.
Physical Review X, 6(3):031005.

[71]
Girvan, M. and Newman, M. E. (2002).
Community structure in social and biological networks.
Proceedings of the national academy of sciences,

[72]
Goldberg, M., Magdon-Ismail, M., Nambirajan, S., and Thompson, J. (2011).
Tracking and predicting evolution of social communities.
In 2011 IEEE Third International Conference on Privacy,
Security, Risk and Trust and 2011 IEEE Third International Conference on
Social Computing, pages 780–783. IEEE.

[73]
Gong, M.-G., Zhang, L.-J., Ma, J.-J., and Jiao, L.-C. (2012).
Community detection in dynamic social networks based on
multiobjective immune algorithm.
Journal of Computer Science and Technology, 27(3):455–467.

[74]
Görke, R., Hartmann, T., and Wagner, D. (2009).
Dynamic graph clustering using minimum-cut trees.
In Workshop on Algorithms and Data Structures, pages 339–350.

[75]
Görke, R., Maillard, P., Schumm, A., Staudt, C., and Wagner, D. (2013).
Dynamic graph clustering combining modularity and smoothness.
Journal of Experimental Algorithmics (JEA), 18:1–1.

[76]
Görke, R., Maillard, P., Staudt, C., and Wagner, D. (2010).
Modularity-driven clustering of dynamic graphs.
In International Symposium on Experimental Algorithms, pages
436–448. Springer.

[77]
Greene, D., Doyle, D., and Cunningham, P. (2010).
Tracking the evolution of communities in dynamic social networks.
In 2010 international conference on advances in social networks
analysis and mining, pages 176–183. IEEE.

[78]
Grünwald, P. (2000).
Model selection based on minimum description length.
Journal of Mathematical Psychology, 44(1):133–152.

[79]
Grünwald, P. D. and Grunwald, A. (2007).
The minimum description length principle.
MIT press.

[80]
Guimera, R., Sales-Pardo, M., and Amaral, L. A. N. (2004).
Modularity from fluctuations in random graphs and complex networks.
Physical Review E, 70(2):025101.

[81]
Guo, C., Wang, J., and Zhang, Z. (2014).
Evolutionary community structure discovery in dynamic weighted
Physica A: Statistical Mechanics and its Applications,

[82]
Guo, Q., Zhang, L., Wu, B., and Zeng, X. (2016).
Dynamic community detection based on distance dynamics.
In 2016 IEEE/ACM International Conference on Advances in Social
Networks Analysis and Mining (ASONAM), pages 329–336. IEEE.

[83]
Hagberg, A., Swart, P., and S Chult, D. (2008).
Exploring network structure, dynamics, and function using networkx.
Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM
(United States).

[84]
Hartmann, T., Kappes, A., and Wagner, D. (2016).
Clustering evolving networks.
In Algorithm Engineering, pages 280–329. Springer.

[85]
He, J. and Chen, D. (2015).
A fast algorithm for community detection in temporal network.
Physica A: Statistical Mechanics and its Applications,

[86]
Herlau, T., Mørup, M., and Schmidt, M. (2013).
Modeling temporal evolution and multiscale structure in networks.
In International Conference on Machine Learning, pages
960–968. PMLR.

[87]
Himmel, A., Molter, H., Niedermeier, R., and Sorge, M. (2016).
Enumerating maximal cliques in temporal graphs.
2016 IEEE/ACM International Conference on Advances in Social
Networks Analysis and Mining (ASONAM), pages 337–344.

[88]
Holme, P. and Saramäki, J. (2012).
Temporal networks.
Physics reports, 519(3):97–125.

[89]
Hopcroft, J., Khan, O., Kulis, B., and Selman, B. (2004).
Tracking evolving communities in large linked networks.
Proceedings of the National Academy of Sciences, 101(suppl

[90]
Hu, Y., Yang, B., and Lv, C. (2016).
A local dynamic method for tracking communities and their evolution
in dynamic networks.
Knowledge-Based Systems, 110:176–190.

[91]
İlhan, N. and Öğüdücü, Ş. G. (2015).
Predicting community evolution based on time series modeling.
In 2015 IEEE/ACM International Conference on Advances in Social
Networks Analysis and Mining (ASONAM), pages 1509–1516. IEEE.

[92]
Ishiguro, K., Iwata, T., Ueda, N., and Tenenbaum, J. (2010).
Dynamic infinite relational model for time-varying relational data
In Proceedings of the 23rd International Conference on Neural
Information Processing Systems-Volume 1, pages 919–927.

[93]
Jain, A. K., Dubes, R. C., et al. (1988).
Algorithms for clustering data, volume 6.
Prentice hall Englewood Cliffs.

[94]
Jdidia, M. B., Robardet, C., and Fleury, E. (2007).
Communities detection and analysis of their dynamics in collaborative
In 2007 2nd International Conference on Digital Information
Management, volume 2, pages 744–749. IEEE.

[95]
Jiao, P., Wang, W., and Jin, D. (2018).
Constrained common cluster based model for community detection in
temporal and multiplex networks.
Neurocomputing, 275:768–780.

[96]
Kawadia, V. and Sreenivasan, S. (2012).
Sequential detection of temporal communities by estrangement
Scientific reports, 2(1):1–10.

[97]
Kernighan, B. W. and Lin, S. (1970).
An efficient heuristic procedure for partitioning graphs.
The Bell system technical journal, 49(2):291–307.

[98]
Khorasgani, R. R., Chen, J., and Zaiane, O. R. (2010).
Top leaders community detection approach in information networks.
In 4th SNA-KDD workshop on social network mining and analysis.

[99]
Kim, M.-S. and Han, J. (2009).
A particle-and-density based evolutionary clustering method for
dynamic networks.
Proceedings of the VLDB Endowment, 2(1):622–633.

[100]
Kitchovitch, S. and Lió, P. (2011).
Community Structure in Social Networks: Applications for
Epidemiological Modelling.
PloS one, 6(7):e22220.

[101]
Labatut, V. and Orman, G. K. (2017).
Community Structure Characterization, pages 1–13.
Springer New York, New York, NY.

[102]
Lancichinetti, A. and Fortunato, S. (2009a).
Benchmarks for testing community detection algorithms on directed and
weighted graphs with overlapping communities.
Physical Review E, 80(1):016118.

[103]
Lancichinetti, A. and Fortunato, S. (2009b).
Community detection algorithms: a comparative analysis.
Physical review E, 80(5):056117.

[104]
Lancichinetti, A., Fortunato, S., and Kertész, J. (2009).
Detecting the overlapping and hierarchical community structure in
complex networks.
New Journal of Physics, 11(3):033015.

[105]
Lancichinetti, A., Fortunato, S., and Radicchi, F. (2008).
Benchmark graphs for testing community detection algorithms.
Physical review E, 78(4):046110.

[106]
Latapy, M., Viard, T., and Magnien, C. (2017).
Stream graphs and link streams for the modeling of interactions over
CoRR, abs/1710.04073.

[107]
Laumann, E. O. and Pappi, F. U. (2013).
Networks of collective action: A perspective on community
influence systems.

[108]
Lee, P., Lakshmanan, L. V., and Milios, E. E. (2014).
Incremental cluster evolution tracking from highly dynamic network
In 2014 IEEE 30th International Conference on Data Engineering,
pages 3–14. IEEE.

[109]
Leskovec, J., Lang, K. J., Dasgupta, A., and Mahoney, M. W. (2009).
Community structure in large networks: Natural cluster sizes and the
absence of large well-defined clusters.
Internet Mathematics, 6(1):29–123.

[110]
Li, X., Gao, C., and Pu, R. (2014).
A community clustering algorithm based on genetic algorithm with
novel coding scheme.
In 2014 10th International Conference on Natural Computation
(ICNC), pages 486–491. IEEE.

[111]
Li, Z., Liu, J., and Wu, K. (2017).
A multiobjective evolutionary algorithm based on structural and
attribute similarities for community detection in attributed networks.
IEEE transactions on cybernetics, 48(7):1963–1976.

[112]
Li, Z., Zhang, S., Wang, R.-S., Zhang, X.-S., and Chen, L. (2008).
Quantitative function for community detection.
Physical review E, 77(3):036109.

[113]
Lin, Y.-R., Chi, Y., Zhu, S., Sundaram, H., and Tseng, B. L. (2008).
Facetnet: a framework for analyzing communities and their evolutions
in dynamic networks.
In Proceedings of the 17th international conference on World
Wide Web, pages 685–694.

[114]
Lin, Y.-R., Chi, Y., Zhu, S., Sundaram, H., and Tseng, B. L. (2009).
Analyzing communities and their evolutions in dynamic social
ACM Transactions on Knowledge Discovery from Data (TKDD),

[115]
Liu, F., Wu, J., Xue, S., Zhou, C., Yang, J., and Sheng, Q. (2020).
Detecting the evolving community structure in dynamic social
World Wide Web, 23(2):715–733.

[116]
Luce, R. D. and Perry, A. D. (1949).
A method of matrix analysis of group structure.
Psychometrika, 14(2):95–116.

[117]
Ludkin, M., Eckley, I., and Neal, P. (2018).
Dynamic stochastic block models: parameter estimation and detection
of changes in community structure.
Statistics and Computing, 28(6):1201–1213.

[118]
Ma, H.-S. and Huang, J.-W. (2013).
Cut: Community update and tracking in dynamic social networks.
In Proceedings of the 7th Workshop on Social Network Mining and
Analysis, pages 1–8.

[119]
Ma, X. and Dong, D. (2017).
Evolutionary nonnegative matrix factorization algorithms for
community detection in dynamic networks.
IEEE transactions on knowledge and data engineering,

[120]
MacQueen, J. et al. (1967).
Some methods for classification and analysis of multivariate
In Proceedings of the fifth Berkeley symposium on mathematical
statistics and probability, volume 1, pages 281–297. Oakland, CA, USA.

[121]
Márquez, R. (2020).
Overlapping community detection in static and dynamic networks.
In Proceedings of the 13th International Conference on Web
Search and Data Mining, pages 925–926.

[122]
Masuda, N. and Holme, P. (2019).
Detecting sequences of system states in temporal networks.
Scientific Reports, 9(1).

[123]
Matias, C. and Miele, V. (2017).
Statistical clustering of temporal networks through a dynamic
stochastic block model.
Journal of the Royal Statistical Society Series B,

[124]
Matias, C., Rebafka, T., and Villers, F. (2015).
Estimation and clustering in a semiparametric poisson process
stochastic block model for longitudinal networks.
arXiv: Methodology.

[125]
McDaid, A. and Hurley, N. (2010).
Detecting highly overlapping communities with model-based overlapping
seed expansion.
In 2010 International Conference on Advances in Social Networks
Analysis and Mining, pages 112–119. IEEE.

[126]
McKenzie-Mohr, D. and Smith, W. (1999).
Fostering Sustainable Behavior: An Introduction to
Community-based Social Marketing.
Education for sustainability. New Society Publishers.

[127]
Messaoudi, I. and Kamel, N. (2019).
A multi-objective bat algorithm for community detection on dynamic
social networks.
Applied Intelligence, 49(6):2119–2136.

[128]
Milgram, S. (1967).
The small world problem.
Psychology today, 2(1):60–67.

[129]
Miller, K. T. and Eliassi-Rad, T. (2009).
Continuous time group discovery in dynamic graphs.
In Notes of the 2009 NIPS Workshop on Analyzing Networks and
Learning with Graphs, Whistler, BC, Canada.

[130]
Mohammadmosaferi, K. K. and Naderi, H. (2020).
Evolution of communities in dynamic social networks: An efficient
map-based approach.
Expert Systems with Applications, 147:113221.

[131]
Moradi, F., Olovsson, T., and Tsigas, P. (2012).
An evaluation of community detection algorithms on large-scale email
In Experimental Algorithms - 11th International Symposium, SEA
2012, Bordeaux, France, June 7-9, 2012. Proceedings, pages 283–294.

[132]
Moreno, J. (1934).
Who shall survive?: A new approach to the problem of human
Nervous and Mental Disease Publishing Co, Washington, D.C.

[133]
Morini, M., Flandrin, P., Fleury, E., Venturini, T., and Jensen, P. (2017).
Revealing evolutions in dynamical networks.
arXiv preprint arXiv:1707.02114.

[134]
Mucha, P. J., Richardson, T., Macon, K., Porter, M. A., and Onnela, J.-P.
Community structure in time-dependent, multiscale, and multiplex
science, 328(5980):876–878.

[135]
Nath, K. and Roy, S. (2019).
Detecting intrinsic communities in evolving networks.
Social Network Analysis and Mining, 9(1):13.

[136]
Newman, M. (2010).
Networks: An Introduction.
Oxford University Press, Inc., New York, NY, USA.

[137]
Newman, M. E. (2004).
Fast algorithm for detecting community structure in networks.
Physical review E, 69(6):066133.

[138]
Newman, M. E. (2006).
Modularity and community structure in networks.
Proceedings of the national academy of sciences,

[139]
Newman, M. E. and Girvan, M. (2004).
Finding and evaluating community structure in networks.
Physical review E, 69(2):026113.

[140]
Nguyen, N. P., Dinh, T. N., Tokala, S., and Thai, M. T. (2011a).
Overlapping communities in dynamic networks: their detection and
mobile applications.
In Proceedings of the 17th annual international conference on
Mobile computing and networking, pages 85–96. ACM.

[141]
Nguyen, N. P., Dinh, T. N., Xuan, Y., and Thai, M. T. (2011b).
Adaptive algorithms for detecting community structure in dynamic
social networks.
In 2011 Proceedings IEEE INFOCOM, pages 2282–2290. IEEE.

[142]
Ning, H., Xu, W., Chi, Y., Gong, Y., and Huang, T. S. (2010).
Incremental spectral clustering by efficiently updating the
Pattern Recognition, 43(1):113–127.

[143]
Palla, G., Barabási, A.-L., and Vicsek, T. (2007).
Quantifying social group evolution.
Nature, 446(7136):664.

[144]
Palla, G., Derényi, I., Farkas, I., and Vicsek, T. (2005).
Uncovering the overlapping community structure of complex networks in
nature and society.
nature, 435(7043):814.

[145]
Pang, S., Chen, C., and Wei, T. (2009).
A realtime community detection algorithm: incremental label
In 2009 First International Conference on Future Information
Networks, pages 313–317. IEEE.

[146]
Paranjape, A., Benson, A. R., and Leskovec, J. (2017).
Motifs in temporal networks.
In Proceedings of the Tenth ACM International Conference on Web
Search and Data Mining, pages 601–610. ACM.

[147]
Peel, L. and Clauset, A. (2014).
Detecting change points in the large-scale structure of evolving
CoRR, abs/1403.0989.

[148]
Pons, P. and Latapy, M. (2005).
Computing communities in large networks using random walks.
In International symposium on computer and information
sciences, pages 284–293. Springer.

[149]
Porter, M. A., Onnela, J.-P., and Mucha, P. J. (2009).
Communities in networks.
Notices of the AMS, 56(9):1082–1097.

[150]
Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., and Parisi, D. (2004).
Defining and identifying communities in networks.
Proceedings of the National Academy of Sciences,

[151]
Raghavan, U. N., Albert, R., and Kumara, S. (2007).
Near linear time algorithm to detect community structures in
large-scale networks.
Physical review E, 76(3):036106.

[152]
Reichardt, J. and Bornholdt, S. (2006).
Statistical mechanics of community detection.
Physical Review E, 74(1):016110.

[153]
Rossetti, G. (2020).
Angel: efficient, and effective, node-centric community discovery in
static and dynamic networks.
Applied Network Science, 5(1):1–23.

[154]
Rossetti, G. and Cazabet, R. (2018).
Community discovery in dynamic networks: a survey.
ACM Computing Surveys (CSUR), 51(2):35.

[155]
Rossetti, G., Pappalardo, L., Pedreschi, D., and Giannotti, F. (2017).
Tiles: an online algorithm for community discovery in dynamic social
Machine Learning, 106(8):1213–1241.

[156]
Rosvall, M. and Bergstrom, C. T. (2008).
Maps of random walks on complex networks reveal community structure.
Proceedings of the National Academy of Sciences,

[157]
Rosvall, M. and Bergstrom, C. T. (2010).
Mapping change in large networks.
PloS one, 5(1):e8694.

[158]
Rozenshtein, P., Tatti, N., and Gionis, A. (2014).
Discovering dynamic communities in interaction networks.
In Joint European Conference on Machine Learning and Knowledge
Discovery in Databases, pages 678–693. Springer.

[159]
Said, A., Abbasi, R. A., Maqbool, O., Daud, A., and Aljohani, N. R. (2018).
Cc-ga: A clustering coefficient based genetic algorithm for detecting
communities in social networks.
Applied Soft Computing, 63:59–70.

[160]
Samie, M. E. and Hamzeh, A. (2018).
Change-aware community detection approach for dynamic social
Applied Intelligence, 48(1):78–96.

[161]
Sarantopoulos, I., Papatheodorou, D., Vogiatzis, D., Tzortzis, G., and
Paliouras, G. (2018).
Timerank: A random walk approach for community discovery in dynamic
In International Conference on Complex Networks and their
Applications, pages 338–350. Springer.

[162]
Seidman, S. B. (1983).
Network structure and minimum degree.
Social Networks, 5(3):269 – 287.

[163]
Seidman, S. B. and Foster, B. L. (1978).
A graph-theoretic generalization of the clique concept.
Journal of Mathematical sociology, 6(1):139–154.

[164]
Shang, J., Liu, L., Xie, F., Chen, Z., Miao, J., Fang, X., and Wu, C. (2014).
A real-time detecting algorithm for tracking community structure of
dynamic networks.
arXiv preprint arXiv:1407.2683.

[165]
Shao, J., Han, Z., Yang, Q., and Zhou, T. (2015).
Community detection based on distance dynamics.
In Proceedings of the 21th ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining, pages 1075–1084.

[166]
Simon, H. A. (1991).
The architecture of complexity.
In Facets of systems science, pages 457–476. Springer.

[167]
Stehlé, J., Voirin, N., Barrat, A., Cattuto, C., Isella, L., Pinton, J.,
Quaggiotto, M., Van den Broeck, W., Régis, C., Lina, B., and Vanhems, P.
High-resolution measurements of face-to-face contact patterns in a
primary school.
PLOS ONE, 6(8):e23176.

[168]
Sun, H., Huang, J., Zhang, X., Liu, J., Wang, D., Liu, H., Zou, J., and Song,
Q. (2014).
Incorder: Incremental density-based community detection in dynamic
Knowledge-Based Systems, 72:1–12.

[169]
Sun, J., Faloutsos, C., Papadimitriou, S., and Yu, P. S. (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, pages 687–696.

[170]
Sun, Y., Tang, J., Han, J., Gupta, M., and Zhao, B. (2010).
Community evolution detection in dynamic heterogeneous information
In Proceedings of the Eighth Workshop on Mining and Learning
with Graphs, pages 137–146.

[171]
Sun, Y., Tang, J., Pan, L., and Li, J. (2015).
Matrix based community evolution events detection in online social
In 2015 IEEE International Conference on Smart
City/SocialCom/SustainCom (SmartCity), pages 465–470. IEEE.

[172]
Tajeuna, E. G., Bouguessa, M., and Wang, S. (2015).
Tracking the evolution of community structures in time-evolving
social networks.
In 2015 IEEE International Conference on Data Science and
Advanced Analytics (DSAA), pages 1–10. IEEE.

[173]
Takaffoli, M., Sangi, F., Fagnan, J., and Zaiane, O. (2011).
Modec—modeling and detecting evolutions of communities.
In Proceedings of the International AAAI Conference on Web and
Social Media.

[174]
Tan, B., Zhu, F., Qu, Q., and Liu, S. (2014).
Online community transition detection.
In International Conference on Web-Age Information Management,
pages 633–644. Springer.

[175]
Tang, L. and Liu, H. (2010).
Graph mining applications to social network analysis.
In Managing and Mining Graph Data, pages 487–513. Springer.

[176]
Tingting, Z., Ping, L., Kiaqi, C., Yan, C., and Lanlan, Y. (2018).
Hyper-network based change point detection in dynamic networks.
In Proceedings of the 4th Workshop on Mining and Learning from
Time Series, MiLeTS'18.

[177]
Traag, V. A., Waltman, L., and Van Eck, N. J. (2019).
From louvain to leiden: guaranteeing well-connected communities.
Scientific reports, 9(1):1–12.

[178]
vanDongen, S. (2000).
A cluster algorithm for graphs.
Technical report, CWI (Centre for Mathematics and Computer Science),

[179]
Viard, T., Latapy, M., and Magnien, C. (2016).
Computing maximal cliques in link streams.
Theor. Comput. Sci., 609(P1):245–252.

[180]
Waltman, L. and Van Eck, N. J. (2013).
A smart local moving algorithm for large-scale modularity-based
community detection.
The European physical journal B, 86(11):1–14.

[181]
Wang, Q. and Fleury, E. (2010).
Mining time-dependent communities.
In LAWDN-Latin-American Workshop on Dynamic Networks, pages

[182]
Wang, Y., Chakrabarti, A., Sivakoff, D., and Parthasarathy, S. (2017).
Fast change point detection on dynamic social networks.
In Proceedings of the 26th International Joint Conference on
Artificial Intelligence, IJCAI'17, pages 2992–2998. AAAI Press.

[183]
Wang, Y., Wu, B., and Du, N. (2008).
Community evolution of social network: feature, algorithm and model.
arXiv preprint arXiv:0804.4356.

[184]
Wang, Z., Li, Z., Yuan, G., Sun, Y., Rui, X., and Xiang, X. (2018).
Tracking the evolution of overlapping communities in dynamic social
Knowledge-Based Systems, 157:81–97.

[185]
Wasserman, S. and Faust, K. (1994).
Social network analysis: Methods and applications, volume 8.
Cambridge university press.

[186]
Watts, D. J. and Strogatz, S. H. (1998).
Collective dynamics of ‘small-world’networks.
nature, 393(6684):440.

[187]
Xie, J., Chen, M., and Szymanski, B. K. (2013).
Labelrankt: Incremental community detection in dynamic networks via
label propagation.
In Proceedings of the Workshop on Dynamic Networks Management
and Mining, pages 25–32. ACM.

[188]
Xie, J. and Szymanski, B. K. (2013).
Labelrank: A stabilized label propagation algorithm for community
detection in networks.
In 2013 IEEE 2nd Network Science Workshop (NSW), pages
138–143. IEEE.

[189]
Xu, H., Wang, Z., and Xiao, W. (2013a).
Analyzing community core evolution in mobile social networks.
In 2013 International Conference on Social Computing, pages
154–161. IEEE.

[190]
Xu, H., Xiao, W., Tang, D., Tang, J., and Wang, Z. (2013b).
Community core evolution in mobile social networks.
The Scientific World Journal, 2013.

[191]
Xu, K. S. and Hero, A. O. (2014).
Dynamic stochastic blockmodels for time-evolving social networks.
IEEE Journal of Selected Topics in Signal Processing,

[192]
Xu, Z., Rui, X., He, J., Wang, Z., and Hadzibeganovic, T. (2020).
Superspreaders and superblockers based community evolution tracking
in dynamic social networks.
Knowledge-Based Systems, 192:105377.

[193]
Yang, T., Chi, Y., Zhu, S., Gong, Y., and Jin, R. (2009).
A bayesian approach toward finding communities and their evolutions
in dynamic social networks.
In Proceedings of the 2009 SIAM International Conference on Data
Mining, pages 990–1001. SIAM.

[194]
Yang, T., Chi, Y., Zhu, S., Gong, Y., and Jin, R. (2011).
Detecting communities and their evolutions in dynamic social
networks—a bayesian approach.
Machine learning, 82(2):157–189.

[195]
Yu, K., Yu, S., and Tresp, V. (2006).
Soft clustering on graphs.
In Advances in neural information processing systems, pages

[196]
Zakrzewska, A. and Bader, D. A. (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 2015, pages 559–564. ACM.

[197]
Zakrzewska, A. and Bader, D. A. (2016).
Tracking local communities in streaming graphs with a dynamic
Social Network Analysis and Mining, 6(1):65.

[198]
Zeng, X., Wang, W., Chen, C., and Yen, G. G. (2019).
A consensus community-based particle swarm optimization for dynamic
community detection.
IEEE Transactions on Cybernetics, 50(6):2502–2513.

[199]
Zhao, Z., Li, C., Zhang, X., Chiclana, F., and Viedma, E. H. (2019).
An incremental method to detect communities in dynamic evolving
social networks.
Knowledge-Based Systems, 163:404–415.

[200]
Zhou, D., Councill, I., Zha, H., and Giles, C. L. (2007).
Discovering temporal communities from social network documents.
In Seventh IEEE International Conference on Data Mining (ICDM
2007), pages 745–750. IEEE.

[201]
Zhu, J., Liu, J., Zhang, X., and Zhao, Y. (2016).
A reconstructed event-based framework for analyzing community
In 2016 IEEE International Conference on Big Data Analysis
(ICBDA), pages 1–4. IEEE.