Equitable Partition Realizability for Dynamics-preserving and Privacy-aware Network Reconstruction
Abstract
Degree-sequence realizability is the combinatorial basis of configuration models, but degree constraints alone do not ensure the preservation of graph dynamics. Hence, configuration models are unable to recover centrality measures, unless these are strongly correlated with the degree sequence. To address this matter, we introduce EP-realizability, the analogue problem induced by an equitable partition (EP): given the EP of a graph, decide whether the partition is realized by a simple undirected loopless graph and therefore construct such a graph. After defining the problem, we solve it by reducing it to sub-problems related to Havel--Hakimi and the Gale--Ryser theorem. We also face the challenge of solving the problem with an Approximate Equitable Partition (ε-EP), so that it is possible to reconstruct a network starting from partial and more privacy-preserving information. We evaluate privacy with edge overlap, deriving also, for our proposed ε-EP-realizability solution, a predictor for this metric. Experiments on Karate, Cora, CiteSeer and PubMed datasets show that our algorithm achieves a favourable and tunable privacy--utility trade-off, comparing the results with Havel--Hakimi algorithm, Newman's configuration model and a stochastic block model. Finally, both with real data and random graphs, we show that our algorithm has approximately linear time complexity with respect to the number of edges.
Related
- Particle-Number-Preserving Quantum Signal Processing for Thermal Properties: Canonical-Ensemble Estimation and Grand-Canonical Reconstruction
- Feature-preserving interface reconstruction using piecewise circles and cusps
- Toward Human-Perceptive 6G: Privacy-Preserving Network Intelligence from Human Dynamics
- Structure-preserving diffuse-domain accelerated saddle dynamics for wetting transitions
- Preserving Unstable Modes Through Inverse Dynamics in JEPA World Models
BibTeX
@misc{porcedda2026equitable,
title = {{Equitable Partition Realizability for Dynamics-preserving and Privacy-aware Network Reconstruction}},
author = {Riccardo Porcedda},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.16762},
eprint = {2609.16762},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.16762},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Equitable Partition Realizability for Dynamics-preserving and Privacy-aware Network Reconstruction
AU - Riccardo Porcedda
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.16762
UR - https://arxiv.org/abs/2609.16762
AB - Degree-sequence realizability is the combinatorial basis of configuration models, but degree constraints alone do not ensure the preservation of graph dynamics. Hence, configuration models are unable to recover centrality measures, unless these are strongly correlated with the degree sequence. To address this matter, we introduce EP-realizability, the analogue problem induced by an equitable partition (EP): given the EP of a graph, decide whether the partition is realized by a simple undirected loopless graph and therefore construct such a graph. After defining the problem, we solve it by reducing it to sub-problems related to Havel--Hakimi and the Gale--Ryser theorem. We also face the challenge of solving the problem with an Approximate Equitable Partition (ε-EP), so that it is possible to reconstruct a network starting from partial and more privacy-preserving information. We evaluate privacy with edge overlap, deriving also, for our proposed ε-EP-realizability solution, a predictor for this metric. Experiments on Karate, Cora, CiteSeer and PubMed datasets show that our algorithm achieves a favourable and tunable privacy--utility trade-off, comparing the results with Havel--Hakimi algorithm, Newman's configuration model and a stochastic block model. Finally, both with real data and random graphs, we show that our algorithm has approximately linear time complexity with respect to the number of edges.
ER -