Conference Proceedings

Assessing Centrality Without Knowing Connections

Leyla Roohi, Benjamin IP Rubinstein, Vanessa Teague

24th Pacific-Asia Conference, PAKDD 2020, Singapore, May 11–14, 2020, Proceedings, Part I | Springer International Publishing | Published : 2020

Abstract

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 Fa..

View full abstract