Social Network De-anonymization Under Scale-free User Relations

We tackle the problem of user de-anonymization in social networks characterized by scale-free relationships between users. The network is modeled as a graph capturing the impact of power-law node degree distribution, which is a fundamental and quite common feature of social networks. Using this model, we present a de-anonymization algorithm that exploits an initial set of users, called seeds, that are known a priori. By employing bootstrap percolation theory and a novel graph slicing technique, we develop a rigorous analysis of the proposed algorithm under asymptotic conditions. Our analysis shows that large inhomogeneities in the node degree lead to a dramatic reduction of the size of the seed set that is necessary to successfully identify all other users. We characterize this set size when seeds are properly selected based on the node degree as well as when seeds are uniformly distributed. We prove that, given n nodes, the number of seeds required for network de-anonymization can be as small as n^epsilon, for any small epsilon>0. Additionally, we discuss the complexity of our de-anonymization algorithm and validate our results through numerical experiments on a real social network graph.