Differential Privacy for Network Connectedness Indices
2026-03-16 • Cryptography and Security
Cryptography and SecurityComputers and SocietySocial and Information Networks
AI summaryⓘ
The authors address the challenge of releasing statistics about how people connect in networks without compromising privacy. They focus on measures that show how similar connected individuals are, but these measures are hard to protect using usual privacy methods. Their approach adds noise to individuals' attributes before calculating the statistics and then adds another layer of noise to protect the connections themselves, ensuring privacy. The authors prove that their method gives reliable results and works well even on small network datasets.
network connectednessassortative mixingdifferential privacyedge-adjacent privacyglobal sensitivitynoise additionstatistical debiasingconsistencyasymptotic normalitysocial networks
Authors
Tom A. Rutter, Yuxin Liu, M. Amin Rahimian
Abstract
Researchers increasingly use data on social and economic networks to study a range of social science questions, but releasing statistics derived from networks can raise significant privacy concerns. We show how to release network connectedness indices that quantify assortative mixing across node attributes under edge-adjacent differential privacy. Standard privacy techniques perform poorly in this setting both because connectedness indices have high global sensitivity and because a single node's attribute can potentially be an input to connectedness in thousands of cells, leading to poor composition. Our method, which is straightforward to apply, first adds noise to node attributes, then analytically debiases downstream statistics, and finally applies a second layer of noise to protect the presence or absence of individual edges. We prove consistency and asymptotic normality of our estimators for both discrete and continuous labels and show our method works well in simulations and on real networks with as few as 200 nodes collected by social scientists.