Inferring Networks From Random Walk-Based Node Similarities

Authors:
Jeremy Hoskins Yale University
Cameron Musco Massachusetts Institute of Technology
Christopher Musco Mass. Institute of Technology
Babis Tsourakakis Boston University

Introduction:

Digital presence in the world of online social media entails significant privacy risks.

Abstract:

Digital presence in the world of online social media entails significant privacy risks. In this work we consider a privacy threat to a social network in which an attacker has access to a subset of random walk-based node similarities, such as effective resistances (i.e., commute times) or personalized PageRank scores. Using these similarities, the attacker seeks to infer as much information as possible about the network, including unknown pairwise node similarities and edges.

You may want to know: