pith. sign in

arxiv: 2402.10141 · v1 · submitted 2024-02-15 · ⚛️ physics.soc-ph

Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks

Giulio Virginio Clemente , Diego Garlaschelli This is my paper

Pith reviewed 2026-05-24 03:38 UTC · model grok-4.3

classification ⚛️ physics.soc-ph
keywords temporal networkscommunity detectionmodularitymemory effectsdetectability thresholdMarkovian networksdynamic graphscommunity quality
0
0 comments X

The pith

A modularity function that links memory directly to node memberships lowers the detectability threshold in Markovian temporal networks.

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

Temporal networks evolve with memory of prior connections, which standard community detection often ignores when measuring modularity. The paper introduces a modified modularity that folds memory effects straight into the expression for node group membership. This change is tested on synthetic networks where community signals sit near the usual detection limit. Simulations show communities become recoverable at weaker signal strengths than with memory-blind modularity. The same function applied to real data also yields a practical side benefit by suggesting suitable aggregation windows.

Core claim

By associating memory directly with nodes' memberships and considering it in the expression of the modularity, the detectability threshold can be lowered with respect to cases where memory is not considered, thereby enhancing the quality of the communities discovered.

What carries the argument

The novel modularity function that associates memory effects directly with node memberships inside the modularity expression for Markovian temporal networks.

If this is right

  • Communities become detectable at lower signal strengths than with conventional modularity.
  • Quality of recovered partitions improves in both synthetic and empirical temporal data.
  • The approach supplies an indirect criterion for choosing aggregation time windows in dynamic graphs.
  • Structural heterogeneity and memory-driven evolution can be handled within a single modularity score.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The lowered threshold may allow earlier identification of emerging groups in systems that change slowly.
  • If the memory association generalizes, similar gains could appear in non-Markovian temporal networks.
  • The method might combine with link-prediction tasks that already track memory to refine both detection and forecasting.
  • Scalability tests on networks larger than those in the simulations would reveal whether the gain persists at scale.

Load-bearing premise

Memory effects can be directly and validly associated with node memberships inside the modularity expression for Markovian temporal networks without introducing structural bias or requiring additional fitting steps.

What would settle it

A controlled simulation on a Markovian temporal network in which the new modularity recovers no more communities below the standard detectability threshold than the memory-free version.

Figures

Figures reproduced from arXiv: 2402.10141 by Diego Garlaschelli, Giulio Virginio Clemente.

Figure 1
Figure 1. Figure 1: FIG. 1: In figure are shown the performances using the [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2: Schematic Representation of Temporal [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3: In the figure, a schematic representation of the [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4: The figure represents three different profiles for [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5: In figure is displayed the average ARI values for [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6: In these figures, we present three heatmaps for each of the following modularity functions: the [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7: The figure displays the ARI values for 10 [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8: Figure displays the performance of community detection on a real network. Each point corresponds to a [PITH_FULL_IMAGE:figures/full_fig_p012_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: FIG. 9: The figure represents the normalized [PITH_FULL_IMAGE:figures/full_fig_p013_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: FIG. 10: Results from the numerical simulations [PITH_FULL_IMAGE:figures/full_fig_p017_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: FIG. 11: In these figures, we have a 3D representation of the average value behavior over 20 instances for [PITH_FULL_IMAGE:figures/full_fig_p019_11.png] view at source ↗
read the original abstract

Temporal Networks, and more specifically, Markovian Temporal Networks, present a unique challenge regarding the community discovery task. The inherent dynamism of these systems requires an intricate understanding of memory effects and structural heterogeneity, which are often key drivers of network evolution. In this study, we address these aspects by introducing an innovative approach to community detection, centered around a novel modularity function. We focus on demonstrating the improvements our new approach brings to a fundamental aspect of community detection: the detectability threshold problem. We show that by associating memory directly with nodes' memberships and considering it in the expression of the modularity, the detectability threshold can be lowered with respect to cases where memory is not considered, thereby enhancing the quality of the communities discovered. To validate our approach, we carry out extensive numerical simulations, assessing the effectiveness of our method in a controlled setting. Furthermore, we apply our method to real-world data to underscore its practicality and robustness. This application not only demonstrates the method's effectiveness but also reveals its capacity to indirectly tackle additional challenges, such as determining the optimal time window for aggregating data in dynamic graphs. This illustrates the method's versatility in addressing complex aspects of temporal network analysis.

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

1 major / 2 minor

Summary. The manuscript introduces a novel modularity function for community detection in Markovian temporal networks. By directly associating memory effects with node memberships inside the modularity expression, the authors claim that the detectability threshold is lowered relative to memory-agnostic baselines, yielding higher-quality communities. The claim is supported by numerical simulations on controlled synthetic networks and by application to real-world temporal data, where the method is also said to help select appropriate aggregation windows.

Significance. If the central claim holds after proper null-model calibration, the work would provide a concrete, usable improvement to the detectability limit in temporal networks—an issue that has limited the reliability of community detection in dynamic systems. The combination of controlled simulations and real-data validation is a positive feature; however, the absence of an explicit statement that the configuration-model (or degree-preserving temporal) null model has been correspondingly modified leaves the improvement vulnerable to being an artifact of an inconsistent baseline.

major comments (1)
  1. [Abstract] Abstract (and the paragraph describing the novel modularity): the central claim that memory association lowers the detectability threshold is load-bearing only if the expectation of the new modularity under a suitable null model remains zero (or appropriately calibrated) for networks lacking community structure. The manuscript does not indicate whether the null model is adjusted when memory terms tied to node memberships are inserted; without this adjustment the reported improvement could be an artifact rather than a genuine gain in detectability.
minor comments (2)
  1. The abstract refers to “extensive numerical simulations” and “real-world data” but supplies no quantitative metrics (e.g., NMI, adjusted Rand index, or explicit threshold values) that would allow immediate comparison with existing temporal modularity methods.
  2. Notation for the memory term and its integration into the modularity expression should be introduced with an explicit equation in the main text rather than left at the level of verbal description.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review and for identifying a key point regarding null-model calibration. We address the major comment below and will revise the manuscript accordingly to make the null-model treatment explicit.

read point-by-point responses

  1. Referee: [Abstract] Abstract (and the paragraph describing the novel modularity): the central claim that memory association lowers the detectability threshold is load-bearing only if the expectation of the new modularity under a suitable null model remains zero (or appropriately calibrated) for networks lacking community structure. The manuscript does not indicate whether the null model is adjusted when memory terms tied to node memberships are inserted; without this adjustment the reported improvement could be an artifact rather than a genuine gain in detectability.

    Authors: We agree that an explicit statement and derivation of the null model is necessary to substantiate the detectability claim. In the revised manuscript we will add a dedicated subsection deriving the memory-adjusted configuration-model null model. Under this null, edge probabilities and memory-transition probabilities are generated from the observed degree and memory-strength sequences with no planted communities; we will show analytically that the expectation of the new modularity expression is zero (to within finite-size corrections) when no community structure is present. Numerical checks on purely random Markovian temporal networks will also be included to confirm that the modularity remains centered at zero. These additions will make clear that the reported lowering of the detectability threshold is not an artifact of an inconsistent baseline. revision: yes

Circularity Check

0 steps flagged

No circularity identified; derivation remains self-contained

full rationale

The provided abstract and context describe a novel modularity that incorporates memory terms associated with node memberships to lower the detectability threshold, validated via numerical simulations and real-world applications. No equations, self-citations, or derivation steps are supplied that would allow identification of any reduction by construction (self-definitional, fitted-input prediction, or load-bearing self-citation). The central claim therefore rests on an independent functional modification rather than tautological reuse of inputs, consistent with a score of 0.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract supplies no explicit free parameters, axioms, or invented entities; full text would be required to populate this ledger.

pith-pipeline@v0.9.0 · 5737 in / 944 out tokens · 41863 ms · 2026-05-24T03:38:49.121836+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

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

  1. [1]

    We have previously demonstrated that, by adjustingA with τ ∗, its elements can be interpreted as those realized by an equivalent DSBM with independent snapshots [9, 31]

    to compute the DT can be re-adapted to our context, thereby implying a new and better threshold. We have previously demonstrated that, by adjustingA with τ ∗, its elements can be interpreted as those realized by an equivalent DSBM with independent snapshots [9, 31]. To extend this rationale to the entire matrix C, it is necessary to justify how the same d...

    work page 2009

  2. [2]

    Ide, Kiyotaka; Namatame, Akira; Ponnambalam, Lo- ganathan; Fu, Xiuju; Siow, Rick. A Study on Relation- ship between Modularity and Diffusion Dynamics in Net- works from Spectral Analysis Perspective, International Journal of Advanced Computer Science and Applica- tions, 5, (2014)

    work page 2014

  3. [3]

    Will a large complex system be stable?, Nature, 238, 5364, 413–414 (1972)

    May, Robert M. Will a large complex system be stable?, Nature, 238, 5364, 413–414 (1972)

    work page 1972

  4. [4]

    Local stability properties of complex, species-rich soil food webs with functional block structure

    de Castro, Francisco; Adl, Sina; Allesina, Stefano; Bard- gett, Richard; Bolger, Thomas; Dalzell, Johnathan; Em- merson, Mark; Fleming, Thomas; Garlaschelli, Diego; Grilli, Jacopo; Hannula, Silja; Vries, Franciska; Lindo, Zo¨ e; Maule, Aaron; Opik, Maarja; Rillig, Matthias; Vere- soglou, Stavros; Wall, Diana; Caruso, Tancredi. Local stability properties o...

    work page 2021

  5. [5]

    Prediction of link evolution using community detection in social network, Computing, 104, (2022)

    Kumari, Anisha; Behera, Ranjan; Sahoo, Bibudatta; Sa- hoo, Satya. Prediction of link evolution using community detection in social network, Computing, 104, (2022)

    work page 2022

  6. [6]

    Finding and Evaluat- ing Community Structure in Networks, Physical review

    Newman, Mark; Girvan, Michelle. Finding and Evaluat- ing Community Structure in Networks, Physical review. E, Statistical, nonlinear, and soft matter physics, 69, 026113 (2004)

    work page 2004

  7. [7]

    Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Physical review

    Decelle, Aurelien; Krzakala, Florent; Moore, Cristopher; Zdeborova, Lenka. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications, Physical review. E, Statistical, nonlinear, and soft matter physics, 84, 066106 (2011)

    work page 2011

  8. [8]

    Maps of Random Walks on Complex Networks Reveal Community Struc- ture, Proceedings of the National Academy of Sciences of the United States of America, 105, 1118-23 (2008)

    Rosvall, Martin; Bergstrom, Carl. Maps of Random Walks on Complex Networks Reveal Community Struc- ture, Proceedings of the National Academy of Sciences of the United States of America, 105, 1118-23 (2008)

    work page 2008

  9. [9]

    Community Struc- ture in Time-Dependent, Multiscale, and Multiplex Net- works, Science (New York, N.Y.), 328, 876-8 (2010)

    Mucha, Peter; Richardson, Thomas; Macon, Kevin; Porter, Mason; Onnela, Jukka-Pekka. Community Struc- ture in Time-Dependent, Multiscale, and Multiplex Net- works, Science (New York, N.Y.), 328, 876-8 (2010)

    work page 2010

  10. [10]

    Disentangling group and link persistence in Dynamic Stochastic Block models

    Barucca, Paolo; Lillo, Fabrizio; Mazzarisi, Piero; Tan- tari, Daniele. Detectability thresholds in networks with dynamic link and community structure. arXiv preprint arXiv:1701.05804 (2017)

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  11. [11]

    Ran- dom graph models for dynamic networks, The European Physical Journal B, 90, (2016)

    Zhang, Xiao; Moore, Cristopher; Newman, Mark. Ran- dom graph models for dynamic networks, The European Physical Journal B, 90, (2016)

    work page 2016

  12. [12]

    Maximum- Entropy Networks: Pattern Detection, Network Recon- struction and Graph Combinatorics, (2017)

    Squartini, Tiziano; Garlaschelli, Diego. Maximum- Entropy Networks: Pattern Detection, Network Recon- struction and Graph Combinatorics, (2017)

    work page 2017

  13. [13]

    Temporal networks with node-specific memory: unbiased inference of transition probabilities, relaxation times and structural breaks

    Clemente, Giulio Virginio; Tessone, Claudio J.; Gar- laschelli, Diego. Temporal networks with node-specific memory: unbiased inference of transition probabilities, relaxation times and structural breaks. arXiv:2311.16981 (2023)

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  14. [14]

    Inference and Phase Transitions in the Detection of Modules in Sparse Networks, Physical re- view letters, 107, 065701 (2011)

    Decelle, Aurelien; Krzakala, Florent; Moore, Cristopher; Zdeborova, Lenka. Inference and Phase Transitions in the Detection of Modules in Sparse Networks, Physical re- view letters, 107, 065701 (2011)

    work page 2011

  15. [15]

    Detectability Thresholds and Op- timal Algorithms for Community Structure in Dynamic Networks, Physical Review X, 6, (2016)

    Ghasemian, Amir; Zhang, Pan; Clauset, Aaron; Moore, Cristopher; Peel, Leto. Detectability Thresholds and Op- timal Algorithms for Community Structure in Dynamic Networks, Physical Review X, 6, (2016)

    work page 2016

  16. [16]

    High-Resolution Measure- ments of Face-to-Face Contact Patterns in a Primary School, PLOS ONE, 6, e23176 (2011)

    Stehl´ e, Juliette; Voirin, Nicolas; Barrat, Alain; Cattuto, Ciro; Isella, Lorenzo; Pinton, Jean-Fran¸ cois; Quaggiotto, Marco; Van den Broeck, Wouter; R´ egis, Corinne; Lina, Bruno; Vanhems, Philippe. High-Resolution Measure- ments of Face-to-Face Contact Patterns in a Primary School, PLOS ONE, 6, e23176 (2011)

    work page 2011

  17. [17]

    Community Detection in Graphs, Physics Reports, 486, (2009)

    Fortunato, Santo. Community Detection in Graphs, Physics Reports, 486, (2009)

    work page 2009

  18. [18]

    Null Models in Ecol- ogy

    Gotelli, Nicholas; Graves, Gary R. Null Models in Ecol- ogy. Ecology, 78, (1996)

    work page 1996

  19. [19]

    Finding Community Structure in Networks Using the Eigenvectors of Matrices

    Newman, M. Finding Community Structure in Networks Using the Eigenvectors of Matrices. Physical review. E, Statistical, nonlinear, and soft matter physics, 74, 036104 (2006)

    work page 2006

  20. [20]

    Unbiased sampling of network ensembles, New Journal of Physics, 17, (2015)

    Squartini, Tiziano; Mastrandrea, Rossana; Garlaschelli, Diego. Unbiased sampling of network ensembles, New Journal of Physics, 17, (2015)

    work page 2015

  21. [21]

    Detec- tion of topological patterns in complex networks: Corre- lation profile of the internet, Physica A: Statistical Me- chanics and its Applications, 333, 529-540 (2004)

    Maslov, Sergei; Sneppen, Kim; Zaliznyak, Alexei. Detec- tion of topological patterns in complex networks: Corre- lation profile of the internet, Physica A: Statistical Me- chanics and its Applications, 333, 529-540 (2004)

    work page 2004

  22. [22]

    Fluctuating ecological networks: A synthesis of maximum-entropy approaches for pattern de- tection and process inference

    Caruso, Tancredi; Clemente, Giulio; Rillig, Matthias; Garlaschelli, Diego. Fluctuating ecological networks: A synthesis of maximum-entropy approaches for pattern de- tection and process inference. Methods in Ecology and Evolution, 13, (2022)

    work page 2022

  23. [23]

    Park, Juyong; Newman, M. E. J. Statistical mechanics of networks, Phys. Rev. E, 70, 066117 (2004)

    work page 2004

  24. [24]

    Maximum likeli- hood: Extracting unbiased information from complex networks, Physical review

    Garlaschelli, Diego; Loffredo, Maria. Maximum likeli- hood: Extracting unbiased information from complex networks, Physical review. E, Statistical, nonlinear, and soft matter physics, 78, 015101 (2008)

    work page 2008

  25. [25]

    (Un)detectable Cluster Structure in Sparse Networks, Physical review letters, 101, 078701 (2008)

    Reichardt, J¨ org; Leone, Michele. (Un)detectable Cluster Structure in Sparse Networks, Physical review letters, 101, 078701 (2008)

    work page 2008

  26. [26]

    Graph Spectra and the Detectability of Community Structure in Networks, Physical review letters, 108, 188701 (2012)

    Nadakuditi, Raj; Newman, M. Graph Spectra and the Detectability of Community Structure in Networks, Physical review letters, 108, 188701 (2012)

    work page 2012

  27. [27]

    Stochastic Blockmodels: First Steps, Social Networks - SOC NETWORKS, 5, 109-137 (1983)

    Holland, Paul; Laskey, Kathryn; Leinhardt, Samuel. Stochastic Blockmodels: First Steps, Social Networks - SOC NETWORKS, 5, 109-137 (1983)

    work page 1983

  28. [28]

    Reconstruc- tion and estimation in the planted partition model, Prob- ability Theory and Related Fields, 162, (2014)

    Mossel, Elchanan; Neeman, Joe; Sly, Allan. Reconstruc- tion and estimation in the planted partition model, Prob- ability Theory and Related Fields, 162, (2014)

    work page 2014

  29. [29]

    Comparing Parti- tions, Journal of Classification, 2, 193-218 (1985)

    Hubert, Lawrence; Arabie, Phipps. Comparing Parti- tions, Journal of Classification, 2, 193-218 (1985)

    work page 1985

  30. [30]

    Community Discovery in Dynamic Networks: A Survey, ACM Computing Sur- veys, 51, (2017)

    Rossetti, Giulio; Cazabet, Remy. Community Discovery in Dynamic Networks: A Survey, ACM Computing Sur- veys, 51, (2017)

    work page 2017

  31. [31]

    Quantifying social group evolution, Nature, 446, 664-7 (2007)

    Palla, Gergely; Barabasi, Albert-Laszlo; Vicsek, Tam´ as. Quantifying social group evolution, Nature, 446, 664-7 (2007)

    work page 2007

  32. [32]

    Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian, Advances in Neural In- formation Processing Systems, 33, (2020)

    Dall’Amico, Lorenzo; Couillet, Romain; Tremblay, Nico- las. Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian, Advances in Neural In- formation Processing Systems, 33, (2020)

    work page 2020

  33. [33]

    Find- ing community structure in very large networks, Physical review

    Clauset, Aaron; Newman, M; Moore, Cristopher. Find- ing community structure in very large networks, Physical review. E, Statistical, nonlinear, and soft matter physics, 70, 066111 (2005). 15

    work page 2005

  34. [34]

    Effects of time window size and placement on the structure of aggre- gated networks, EPJ Data Science, 1, (2012)

    Krings, Gautier; Karsai, M´ arton; Bernharsson, Sebas- tian; Blondel, Vincent; Saram¨ aki, Jari. Effects of time window size and placement on the structure of aggre- gated networks, EPJ Data Science, 1, (2012)

    work page 2012

  35. [35]

    Persistence and period- icity in a dynamic proximity network, arXiv, 12117343, (2012)

    Clauset, Aaron; Eagle, Nathan. Persistence and period- icity in a dynamic proximity network, arXiv, 12117343, (2012)

    work page 2012

  36. [36]

    Robust De- tection of Dynamic Community Structure in Networks

    Bassett, Danielle; Porter, Mason; Wymbs, Nicholas; Grafton, Scott; Carlson, Jean; Mucha, Peter. Robust De- tection of Dynamic Community Structure in Networks. Chaos (Woodbury, N.Y.), 23, 013142 (2013)

    work page 2013

  37. [37]

    On the Exact Covariance of Products of Random Variables, Journal of the American Statistical Association, 64, 1439-1442 (1969)

    Bohrnstedt, George; Goldberger, Arthur. On the Exact Covariance of Products of Random Variables, Journal of the American Statistical Association, 64, 1439-1442 (1969)

    work page 1969

  38. [38]

    A new look at the statistical model identifi- cation

    Akaike, H. A new look at the statistical model identifi- cation. IEEE Transactions on Automatic Control, 19(6), 716-723 (1974). Appendix A: Supplementary Information

    work page 1974

  39. [39]

    (17), here recalled: H(G|⃗ α,⃗β) ≡ NX i=1 " αi TX t=1 ki(t) T + βi TX t=1 hi(t) T # (A1) In [12] it is provided an exact formulation for these quantities

    Explicit Expressions for pij and qij The expressions for pij and qij are derived from the solution to the problem defined by Hamiltonian in eq. (17), here recalled: H(G|⃗ α,⃗β) ≡ NX i=1 " αi TX t=1 ki(t) T + βi TX t=1 hi(t) T # (A1) In [12] it is provided an exact formulation for these quantities. Specifically, through appropriate reparametrization, the m...

    work page

  40. [40]

    Auto-covariance for the matrix B Our main argument for the computation of the DT in the case in which modularity using the persisting degree is employed exploits a heuristic, based on the assumption that after τ ∗ define in equation (28) all the matrices being in the sequence B and A can be considered independent. Using the argument in [36], we compute: C...

    work page

  41. [41]

    At this point, two different stochastic matrices are used to define the evolu- tion of connections in this initial network

    Generating Community-Preserving Graph T rajectories via Markov Chains Operationally, we begin by defining a network gener- ated according to a stochastic block model characterized by an internal cluster connection probability, pin, and an external connection probability, pout. At this point, two different stochastic matrices are used to define the evolu- ...

    work page

  42. [42]

    The algorithm aims to maximize the modularity function by changing the labels associated with each element of the network

    A Schematic Presentation of the Algorithm Here we explain the steps followed to optimize the modularity function. The algorithm aims to maximize the modularity function by changing the labels associated with each element of the network. We exploit the method proposed by Clauset and Moore in [32], by readapting it to use the Maximum Entropy null models. In...

    work page

  43. [43]

    Analyzing the Evolution of Detected Communities and the Role of Memory The purpose of this section is to present additional analyses that support the findings from the main sec- tions. In the first subsection, we conduct numerical sim- ulations to demonstrate how selecting the appropriate time window for data aggregation correlates with the observed memor...

    work page