Metraipolis › archive › dc_0ce085368ca9

Equitable Partition Realizability for Dynamics-preserving and Privacy-aware Network Reconstruction — arXiv:2609.16762

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.16762
License (as archived)
CC0-1.0
Archived
2026-10-15T21:59:12.600Z
SHA-256 of the archived text
93e884fb5da368b54d9ebfce38f4358e93020110a283346c088c43c9c5190e59
Stable URL of this page
https://metraipolis.com/documento/dc_0ce085368ca9

How to cite

Equitable Partition Realizability for Dynamics-preserving and Privacy-aware Network Reconstruction — arXiv:2609.16762 — arXiv (en), https://arxiv.org/abs/2609.16762 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0ce085368ca9 (Metraipolis archive dc_0ce085368ca9, sha256 93e884fb5da368b54d9ebfce38f4358e93020110a283346c088c43c9c5190e59)
BibTeX
@misc{dc0ce085368ca9,
  title = {Equitable Partition Realizability for Dynamics-preserving and Privacy-aware Network Reconstruction — arXiv:2609.16762},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.16762},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0ce085368ca9; sha256 93e884fb5da368b54d9ebfce38f4358e93020110a283346c088c43c9c5190e59},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.16762. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 ($\varepsilon$-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 $\varepsilon$-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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-16 in cs.DS).
Categorie arXiv: Methodology (stat.ME) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.16762 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T21:46:54.591Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).