Exact solutions for models of evolving clustered networks with addition and deletion via age-resolved message passing
Abstract
Evolving networks experience vertex addition and deletion over time via processes which shape their structure and function. In many empirical networks, vertices do not arrive or depart in isolation but instead within groups or cohorts: for example, coauthorship networks grow by the addition of cliques whenever a new paper with multiple authors is published. In this paper, we propose a stochastic network evolution model based on block graphs that evolve through the addition of fully connected subgraphs (m-cliques) and the deletion of individual vertices. We derive a master equation governing the time evolution of the joint degree distribution and obtain an exact closed-form solution, valid for an arbitrary vertex deletion rate under uniform attachment, that describes both growing and constant-size networks. From this solution we obtain the marginal degree distributions and the clustering coefficient in closed form and the size of the giant connected component and percolation threshold governing robustness to random vertex failure using age-resolved message passing. Our results generalise existing single-vertex addition-deletion models to clique-based dynamics at arbitrary rates of turnover, and are confirmed by Monte Carlo simulation.
Related
- Age-targeted failure in evolving networks with addition and deletion of vertices
- Discrete Diffusion Models via Evolving Variational Autoregressive Networks
- Physics-informed neural networks for soliton solutions and parameter identification of the two-mode Korteweg–de Vries equation
- Prospective Coding and Path Integration Emerge as Equilibrium Solutions of Self-Organizing Neural Networks with Firing-Rate Adaptation
- On the robustness of noisy solutions in non-convex neural networks
BibTeX
@misc{mann2026exact,
title = {{Exact solutions for models of evolving clustered networks with addition and deletion via age-resolved message passing}},
author = {Peter Mann and Lei Fang and Simon Dobson},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18982},
eprint = {2609.18982},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18982},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact solutions for models of evolving clustered networks with addition and deletion via age-resolved message passing
AU - Peter Mann
AU - Lei Fang
AU - Simon Dobson
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.18982
UR - https://arxiv.org/abs/2609.18982
AB - Evolving networks experience vertex addition and deletion over time via processes which shape their structure and function. In many empirical networks, vertices do not arrive or depart in isolation but instead within groups or cohorts: for example, coauthorship networks grow by the addition of cliques whenever a new paper with multiple authors is published. In this paper, we propose a stochastic network evolution model based on block graphs that evolve through the addition of fully connected subgraphs (m-cliques) and the deletion of individual vertices. We derive a master equation governing the time evolution of the joint degree distribution and obtain an exact closed-form solution, valid for an arbitrary vertex deletion rate under uniform attachment, that describes both growing and constant-size networks. From this solution we obtain the marginal degree distributions and the clustering coefficient in closed form and the size of the giant connected component and percolation threshold governing robustness to random vertex failure using age-resolved message passing. Our results generalise existing single-vertex addition-deletion models to clique-based dynamics at arbitrary rates of turnover, and are confirmed by Monte Carlo simulation.
ER -