pith. sign in

arxiv: 1907.11435 · v1 · pith:Q5DKTRREnew · submitted 2019-07-26 · 💻 cs.SI · physics.soc-ph

Challenges in Community Discovery on Temporal Networks

Remy Cazabet , Giulio Rossetti This is my paper

Pith reviewed 2026-05-24 15:30 UTC · model grok-4.3

classification 💻 cs.SI physics.soc-ph
keywords community discoverytemporal networksdynamic communitiescommunity evolutionlink streamsnetwork science
0
0 comments X

The pith

Dynamic communities in temporal networks introduce challenges distinct from static community detection.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This review examines community discovery in temporal networks. It establishes that dynamic communities cannot be reduced to sequences of static communities identified at separate times. The authors highlight specific issues that arise due to the evolving nature of networks, such as defining community events during gradual changes, tracking identity as structure shifts, representing communities in link streams, enforcing smoothness across time steps, and managing various forms of algorithmic complexity. These distinctions matter because many real systems like social interactions or biological processes unfold over time rather than in fixed snapshots.

Core claim

Dynamic communities are not mere sequences of static ones; new challenges arise from their dynamic nature. In this chapter, we will discuss some of these challenges and recent propositions to tackle them. We will, among other topics, discuss on the question of community events in gradually evolving networks, on the notion of identity through change, on dynamic communities in link streams, on the smoothness of dynamic communities, and on the different types of complexity of algorithms for their discovery.

What carries the argument

Mechanisms for handling community events, identity through change, link stream representations, smoothness constraints, and algorithmic complexity types in evolving networks.

Load-bearing premise

The evolving nature of networks creates difficulties for community discovery that static methods cannot handle.

What would settle it

A demonstration that applying static community detection independently to each time slice fully captures all information about dynamic communities without missing events, identity shifts, or smoothness issues.

Figures

Figures reproduced from arXiv: 1907.11435 by Giulio Rossetti, Remy Cazabet.

Figure 1
Figure 1. Figure 1: Different types of community events [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the ship of Theseus paradox. Each horizontal line represents a node. A same color represents nodes belonging to the same community according to a topological criterion (e.g., SBM). The community A is progressively modified until reaching state B. Community C is composed of the same nodes as the other community at its start. Which cluster (B or C) has the same identity as A? What if all deta… view at source ↗
read the original abstract

Community discovery is one of the most studied problems in network science. In recent years, many works have focused on discovering communities in temporal networks, thus identifying dynamic communities. Interestingly, dynamic communities are not mere sequences of static ones; new challenges arise from their dynamic nature. In this chapter, we will discuss some of these challenges and recent propositions to tackle them. We will, among other topics, discuss on the question of community events in gradually evolving networks, on the notion of identity through change, on dynamic communities in link streams, on the smoothness of dynamic communities, and on the different types of complexity of algorithms for their discovery.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 0 minor

Summary. This manuscript is a survey chapter arguing that dynamic communities in temporal networks are not mere sequences of static communities and that their dynamic nature introduces distinct challenges. It surveys recent propositions on topics including community events in gradually evolving networks, the notion of identity through change, dynamic communities in link streams, the smoothness of dynamic communities, and different types of algorithmic complexity for their discovery.

Significance. As a structured overview of open problems and approaches in temporal network community detection, the chapter can usefully orient researchers in network science. Its framing of challenges as arising specifically from temporal dynamics provides a coherent organizing principle for the surveyed material.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript and for recommending acceptance. The review accurately captures the chapter's focus on challenges specific to dynamic communities in temporal networks and its role as an orienting overview for researchers.

Circularity Check

0 steps flagged

No significant circularity

full rationale

This is a survey chapter whose content consists of enumerating topics (community events, identity through change, link streams, smoothness, algorithmic complexity) without any derivations, equations, predictions, or formal claims whose validity depends on self-referential steps. The statement that dynamic communities are not mere sequences of static ones functions as scene-setting motivation rather than a load-bearing result that reduces to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is a review paper with no new mathematical model, parameters, or entities introduced beyond standard network science concepts.

pith-pipeline@v0.9.0 · 5621 in / 886 out tokens · 22945 ms · 2026-05-24T15:30:40.965177+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages · 2 internal anchors

  1. [1]

    Modularity and community structure in networks

    Mark EJ Newman. Modularity and community structure in networks. Proceedings of the national academy of sciences, 103(23):8577–8582, 2006

    work page 2006

  2. [2]

    Modular and hierarchically modular organization of brain networks

    David Meunier, Renaud Lambiotte, and Edward T Bull- more. Modular and hierarchically modular organization of brain networks. Frontiers in neuroscience , 4:200, 2010

    work page 2010

  3. [3]

    Community discovery in dynamic networks: a survey

    Giulio Rossetti and R´emy Cazabet. Community discovery in dynamic networks: a survey. ACM Computing Surveys (CSUR), 51(2):35, 2018

    work page 2018

  4. [4]

    Stream Graphs and Link Streams for the Modeling of Interactions over Time

    Matthieu Latapy, Tiphaine Viard, and Cl ´emence Mag- nien. Stream graphs and link streams for the modeling of interactions over time. CoRR, abs/1710.04073, 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  5. [5]

    Es- timation and clustering in a semiparametric poisson pro- cess stochastic block model for longitudinal networks

    Catherine Matias, Tabea Rebafka, and Fanny Villers. Es- timation and clustering in a semiparametric poisson pro- cess stochastic block model for longitudinal networks. 2015

    work page 2015

  6. [6]

    Detecting change points in the large-scale structure of evolving networks

    Leto Peel and Aaron Clauset. Detecting change points in the large-scale structure of evolving networks. CoRR, abs/1403.0989, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  7. [7]

    Community 2https://github.com/benmaier/tacoma structure in time-dependent, multiscale, and multiplex networks

    Peter J Mucha, Thomas Richardson, Kevin Macon, Ma- son A Porter, and Jukka-Pekka Onnela. Community 2https://github.com/benmaier/tacoma structure in time-dependent, multiscale, and multiplex networks. science, 328(5980):876–878, 2010

    work page 2010

  8. [8]

    Mining and visualizing the evolution of subgroups in social networks

    Tanja Falkowski, Jorg Bartelheimer, and Myra Spiliopoulou. Mining and visualizing the evolution of subgroups in social networks. In IEEE/WIC/ACM In- ternational Conference on Web Intelligence (WI), pages 52–58. IEEE, 2006

    work page 2006

  9. [9]

    Quantifying social group evolution

    Gergely Palla, Albert-L´aszl´o Barab´asi, and Tam´as Vic- sek. Quantifying social group evolution. Nature, 446(7136):664–667, 2007

    work page 2007

  10. [10]

    Dynamic com- munity detection

    R´emy Cazabet and Fr ´ed´eric Amblard. Dynamic com- munity detection. In Encyclopedia of Social Network Analysis and Mining, pages 404–414. Springer, 2014

    work page 2014

  11. [11]

    Tracking the evolution of communities in dynamic social networks

    Derek Greene, Donal Doyle, and Padraig Cunningham. Tracking the evolution of communities in dynamic social networks. In International conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 176–183. IEEE, 2010

    work page 2010

  12. [12]

    Finding and evaluating community structure in networks

    Mark EJ Newman and Michelle Girvan. Finding and evaluating community structure in networks. Physical review E, 69(2):026113, 2004

    work page 2004

  13. [13]

    Maps of ran- dom walks on complex networks reveal community struc- ture

    Martin Rosvall and Carl T Bergstrom. Maps of ran- dom walks on complex networks reveal community struc- ture. Proceedings of the National Academy of Sciences, 105(4):1118–1123, 2008

    work page 2008

  14. [14]

    Hierarchical block structures and high- resolution model selection in large networks

    Tiago P Peixoto. Hierarchical block structures and high- resolution model selection in large networks. Physical Review X, 4(1):011047, 2014

    work page 2014

  15. [15]

    Static com- munity detection algorithms for evolving networks

    Thomas Aynaud and Jean-Loup Guillaume. Static com- munity detection algorithms for evolving networks. In Proceedings of the 8th international symposium on Mod- eling and optimization in mobile, ad hoc and wireless networks (WiOpt), pages 513–519. IEEE, 2010

    work page 2010

  16. [16]

    Mapping change in large networks

    Martin Rosvall and Carl T Bergstrom. Mapping change in large networks. PloS one, 5(1):e8694, 2010

    work page 2010

  17. [17]

    Modec-modeling and detecting evolu- tions of communities

    Mansoureh Takaffoli, Farzad Sangi, Justin Fagnan, and Osmar R Za¨ıane. Modec-modeling and detecting evolu- tions of communities. In 5th International Conference on Weblogs and Social Media (ICWSM) , pages 30–41. AAAI, 2011

    work page 2011

  18. [18]

    Detecting and tracking community dynamics in evolutionary networks

    Zhengzhang Chen, Kevin A Wilson, Ye Jin, William Hen- drix, and Nagiza F Samatova. Detecting and tracking community dynamics in evolutionary networks. In 2010 IEEE International Conference on Data Mining Work- shops, pages 318–327. IEEE, 2010

    work page 2010

  19. [19]

    Modularity-driven clustering of dy- namic graphs

    Robert G ¨orke, Pascal Maillard, Christian Staudt, and Dorothea Wagner. Modularity-driven clustering of dy- namic graphs. In International Symposium on Experi- mental Algorithms, pages 436–448. Springer, 2010

    work page 2010

  20. [20]

    Detection of overlapping communities in dynamical so- Challenges in Community Discovery on Temporal Networks — 10/10 cial networks

    Remy Cazabet, Frederic Amblard, and Chihab Hanachi. Detection of overlapping communities in dynamical so- Challenges in Community Discovery on Temporal Networks — 10/10 cial networks. In 2010 IEEE second international confer- ence on social computing, pages 309–314. IEEE, 2010

    work page 2010

  21. [21]

    Tiles: an online algorithm for com- munity discovery in dynamic social networks

    Giulio Rossetti, Luca Pappalardo, Dino Pedreschi, and Fosca Giannotti. Tiles: an online algorithm for com- munity discovery in dynamic social networks. Machine Learning, 106(8):1213–1241, 2017

    work page 2017

  22. [22]

    Multiobjective evo- lutionary community detection for dynamic networks

    Francesco Folino and Clara Pizzuti. Multiobjective evo- lutionary community detection for dynamic networks. In GECCO, pages 535–536, 2010

    work page 2010

  23. [23]

    Multi-step community detection and hierarchical time segmentation in evolving networks

    Thomas Aynaud and Jean-Loup Guillaume. Multi-step community detection and hierarchical time segmentation in evolving networks. In Proceedings of the 5th SNA- KDD workshop, 2011

    work page 2011

  24. [24]

    Statistical clustering of temporal networks through a dynamic stochastic block model

    Catherine Matias and Vincent Miele. 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, 2017

    work page 2017

  25. [25]

    Detectability thresholds and op- timal algorithms for community structure in dynamic networks

    Amir Ghasemian, Pan Zhang, Aaron Clauset, Cristopher Moore, and Leto Peel. Detectability thresholds and op- timal algorithms for community structure in dynamic networks. Physical Review X, 6(3):031005, 2016

    work page 2016

  26. [26]

    Communities detection and analysis of their dynamics in collaborative networks

    Manel Ben Jdidia, C ´eline Robardet, and Eric Fleury. Communities detection and analysis of their dynamics in collaborative networks. In 2007 2nd International Con- ference on Digital Information Management, volume 2, pages 744–749. IEEE, 2007

    work page 2007

  27. [27]

    Computing maximal cliques in link streams

    Tiphaine Viard, Matthieu Latapy, and Cl´emence Magnien. Computing maximal cliques in link streams. Theoretical Computer Science, 609:245–252, 2016

    work page 2016

  28. [28]

    Community structure in social and biological networks

    Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7821–7826, 2002

    work page 2002

  29. [29]

    Fast unfolding of commu- nities in large networks

    Vincent D Blondel, Jean-Loup Guillaume, Renaud Lam- biotte, and Etienne Lefebvre. Fast unfolding of commu- nities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):P10008, 2008

    work page 2008

  30. [30]

    Olcpm: An online framework for detecting overlapping communities in dynamic social networks

    Souˆaad Boudebza, R´emy Cazabet, Faic ¸al Azouaou, and Omar Nouali. Olcpm: An online framework for detecting overlapping communities in dynamic social networks. Computer Communications, 123:36–51, 2018

    work page 2018

  31. [31]

    High-resolution measurements of face-to-face contact patterns in a primary school

    Juliette Stehl´e, Nicolas V oirin, Alain Barrat, Ciro Cattuto, Lorenzo Isella, Jean-Franc ¸ois Pinton, Marco Quaggiotto, Wouter Van den Broeck, Corinne R´egis, Bruno Lina, and Philippe Vanhems. High-resolution measurements of face-to-face contact patterns in a primary school. PLOS ONE, 6(8):e23176, 08 2011

    work page 2011

  32. [32]

    Temporal networks

    Petter Holme and Jari Saram ¨aki. Temporal networks. Physics reports, 519(3):97–125, 2012

    work page 2012

  33. [33]

    Using dynamic community detection to identify trends in user-generated content

    R´emy Cazabet, Hideaki Takeda, Masahiro Hamasaki, and Fr´ed´eric Amblard. Using dynamic community detection to identify trends in user-generated content. Social Net- work Analysis and Mining, 2(4):361–371, 2012

    work page 2012

  34. [34]

    The ground truth about metadata and community detection in networks

    Leto Peel, Daniel B Larremore, and Aaron Clauset. The ground truth about metadata and community detection in networks. Science Advances, 3(5):e1602548, 2017

    work page 2017

  35. [35]

    Defining and evaluating network communities based on ground-truth

    Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems, 42(1):181–213, 2015

    work page 2015

  36. [36]

    A bayesian approach toward finding com- munities and their evolutions in dynamic social networks

    Tianbao Yang, Yun Chi, Shenghuo Zhu, Yihong Gong, and Rong Jin. A bayesian approach toward finding com- munities and their evolutions in dynamic social networks. In Proceedings of the International Conference on Data Mining, pages 990–1001. SIAM, 2009

    work page 2009

  37. [37]

    Generative benchmark models for mesoscale structure in multilayer networks

    Marya Bazzi, Lucas GS Jeub, Alex Arenas, Sam D How- ison, and Mason A Porter. Generative benchmark models for mesoscale structure in multilayer networks. arXiv preprint arXiv:1608.06196, 2016

    work page arXiv 2016

  38. [38]

    Rdyn: Graph benchmark handling com- munity dynamics

    Giulio Rossetti. Rdyn: Graph benchmark handling com- munity dynamics. Journal of Complex Networks, 2017

    work page 2017

  39. [39]

    Benchmark model to assess community structure in evolving networks

    Clara Granell, Richard K Darst, Alex Arenas, Santo For- tunato, and Sergio G´omez. Benchmark model to assess community structure in evolving networks. Physical Re- view E, 92(1):012805, 2015

    work page 2015

  40. [40]

    Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities

    Andrea Lancichinetti and Santo Fortunato. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Physical Review E, 80(1):016118, 2009

    work page 2009

  41. [41]

    Facetnet: a framework for analyzing communities and their evolutions in dynamic networks

    Yu-Ru Lin, Yun Chi, Shenghuo Zhu, Hari Sundaram, and Belle L Tseng. Facetnet: a framework for analyzing communities and their evolutions in dynamic networks. In Proceedings of the 17th international conference on World Wide Web (WWW), pages 685–694. ACM, 2008

    work page 2008

  42. [42]

    Benchmark generator for dynamic overlapping communi- ties in networks

    Neha Sengupta, Michael Hamann, and Dorothea Wagner. Benchmark generator for dynamic overlapping communi- ties in networks. In 2017 IEEE International Conference on Data Mining (ICDM), pages 415–424. IEEE, 2017

    work page 2017

  43. [43]

    Ex- ploring network structure, dynamics, and function us- ing networkx

    Aric Hagberg, Pieter Swart, and Daniel S Chult. Ex- ploring network structure, dynamics, and function us- ing networkx. Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008

    work page 2008

  44. [44]

    The igraph software package for complex network research

    Gabor Csardi and Tamas Nepusz. The igraph software package for complex network research. InterJournal, Complex Systems:1695, 2006

    work page 2006

  45. [45]

    Snap: A general-purpose network analysis and graph-mining library

    Jure Leskovec and Rok Sosiˇc. Snap: A general-purpose network analysis and graph-mining library. ACM Trans- actions on Intelligent Systems and Technology (TIST) , 8(1):1, 2016

    work page 2016

  46. [46]

    When is a network a network?: Multi- order graphical model selection in pathways and temporal networks

    Ingo Scholtes. When is a network a network?: Multi- order graphical model selection in pathways and temporal networks. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1037–1046. ACM, 2017

    work page 2017