1. On Social Network De-Anonymization With Communities: A Maximum A Posteriori Perspective
- Author
-
Jiapeng Zhang, Qi Li, Luoyi Fu, Haisong Zhang, Huquan Kang, Xinbing Wang, Shan Qu, and Guihai Chen
- Subjects
Random graph ,Theoretical computer science ,Social network ,De-anonymization ,Computer science ,business.industry ,media_common.quotation_subject ,Parameterized complexity ,Computer Science Applications ,Computational Theory and Mathematics ,Maximum a posteriori estimation ,Quality (business) ,business ,Heuristics ,Empirical evidence ,Information Systems ,media_common - Abstract
A crucial privacy-driven issue nowadays is re-identifying anonymized social networks by mapping them to correlated crossdomain auxiliary networks. Prior works are typically based on modeling social networks as random graphs representing users and their relations, and subsequently quantify the quality of mappings through cost functions that are proposed with insufficient theoretical support. Also, it remains unknown how to algorithmically meet the demand of such quantifications, i.e., to find the minimizer of the cost functions. We address those concerns in a social network modeling parameterized by community structures that can be leveraged as side information for de-anonymization. By Maximum A Posteriori (MAP) estimation, our first contribution is a series of MAP-based cost functions, which, when minimized, enjoy superiority to previous ones in finding the correct mapping with the highest probability. The feasibility of the cost functions is then for the first time algorithmically characterized.We prove the general multiplicative inapproximability, and thus propose two heuristics, which, respectively, enjoy an -additive approximation and a conditional optimality in carrying out successful user re-identification. Our theoretical findings are also empirically validated, with one of the datasets extracted from rare true cross-domain networks that reproduce genuine social network de-anonymization. Both theoretical and empirical observations manifest the importance of community information in enhancing privacy inferencing.
- Published
- 2023