The Effect of Symmetry on the De-Anonymizability of Social Networks

Social network de-anonymization, which refers to re-identifying users by mapping an anonymized network to a correlated real-name network, is an important problem in network science that has received intensive study. Although different de-anonymization algorithms have been proposed, the performance limit of any algorithm on a de-anonymization problem remains less explored. In this paper, we investigate the Optimal De-Anonymization Yield (ODAY), i.e., the maximum extent to which the network can be de-anonymized, of a given de-anonymization problem. Specifically, due to the uncertainty of the true mapping, we define ODAY as the maximum expected number of correctly mapped nodes, and propose general approaches for its quantification in general networks. Therefore, ODAY can be viewed as a quantitative and non-asymptotic concretization of the concept of network de-anonymizability, which is mostly investigated in an asymptotic manner in prior art. Inspired by the effect of network symmetry on the de-anonymizability, we show that for a graph pair with arbitrary topologies, ODAY equals the maximum diagonal sum of a matching probability matrix generated from graph homomorphisms. Due to the exponential complexity of enumerating all the possible homomorphisms, we further obtain an upper bound of ODAY by counting the orbits of each of the two graphs, which significantly reduces the computational cost. Two case studies apply our general findings on symmetry and ODAY to specific network models, and a sampling-based algorithm framework is proposed for ODAY calculation in practice. Extensive experiments are performed to validate our findings. To the best of our knowledge, this work is the first effort that quantifies the de-anonymizability of general networks in a non-asymptotic manner from the perspective of network symmetry, and thus sheds light on privacy enhancement for social network design.