Graph reconstruction method balances privacy and dynamics preservation
Equitable Partition Realizability for Dynamics-preserving and Privacy-aware Network Reconstruction
Data Structures and Algorithms
Summary
Sometimes, knowing just how many connections each node has in a network isn't enough to recreate the whole network accurately, especially if we want the rebuilt network to behave like the original. The authors study a way to recreate networks based on grouping nodes that behave similarly, called equitable partitions. They also allow for approximate groups that protect privacy by sharing less precise information. Their approach lets users control the trade-off between keeping the network’s behavior and keeping its details private, and it runs efficiently on real-world data.
What this means in practice
- •For data privacy engineers: Construct networks reflecting original dynamics while limiting data exposure using approximate equitable partitions.
- •For social network analysts: Rebuild social networks that preserve key behavioral patterns beyond just node degrees for accurate analyses.
Authors
Riccardo Porcedda
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 ($\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.