Assessing Centrality Without Knowing Connections
This enables privacy-preserving analysis of social networks across multiple distrusting providers, though it appears incremental in applying differential privacy to a specific centrality measure.
The paper tackles the problem of computing node influence in distributed social networks while preserving privacy, achieving a low 1.07 relative error at strong privacy budget ε=0.1 on a Facebook graph.
We consider the privacy-preserving computation of node influence in distributed social networks, as measured by egocentric betweenness centrality (EBC). Motivated by modern communication networks spanning multiple providers, we show for the first time how multiple mutually-distrusting parties can successfully compute node EBC while revealing only differentially-private information about their internal network connections. A theoretical utility analysis upper bounds a primary source of private EBC error---private release of ego networks---with high probability. Empirical results demonstrate practical applicability with a low 1.07 relative error achievable at strong privacy budget $ε=0.1$ on a Facebook graph, and insignificant performance degradation as the number of network provider parties grows.