The Effect of Symmetry on the De-Anonymizability of Social Networks
文献类型：期刊论文
| 作者 | Fu, Luoyi3; Tang, Jianzhi3; Miao, Benjie3; Lin, Xiaojun2; Wang, Xinbing3; Zhou, Chenghu1 |
| 刊名 | IEEE TRANSACTIONS ON INFORMATION THEORY
 |
| 出版日期 | 2023-11-01 |
| 卷号 | 69期号:11页码:7357-7372 |
| ISSN号 | 0018-9448 |
| 关键词 | Wireless sensor networks Delays Uncertainty Topology Routing Receivers Steiner trees Social network de-anonymization de-anonymizability network symmetry graph homomorphism |
| DOI | 10.1109/TIT.2023.3288048 |
| 通讯作者 | Wang, Xinbing(xwang8@sjtu.edu.cn) |
| 英文摘要 | 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. |
| WOS关键词 | COMPLEXITY |
| 资助项目 | NSF China[62020106005] ; NSF China[42050105] ; NSF China[62061146002] ; NSF China[61960206002] ; Shanghai Pilot Program for Basic Research, Shanghai Jiao Tong University ; Deep-time Digital Earth(DDE) Big Science Program |
| WOS研究方向 | Computer Science ; Engineering |
| 语种 | 英语 |
| 出版者 | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC |
| WOS记录号 | WOS:001098100800026 |
| 资助机构 | NSF China ; Shanghai Pilot Program for Basic Research, Shanghai Jiao Tong University ; Deep-time Digital Earth(DDE) Big Science Program |
| 源URL | [http://ir.igsnrr.ac.cn/handle/311030/200093]  |
| 专题 | 中国科学院地理科学与资源研究所 |
| 通讯作者 | Wang, Xinbing |
| 作者单位 | 1.Chinese Acad Sci, Inst Geog Sci & Nat Resources Res, Beijing 100101, Peoples R China 2.Purdue Univ, Sch Elect & Comp Engn, W Lafayette, IN 47907 USA 3.Shanghai Jiao Tong Univ, Sch Elect Informat & Elect Engn, Shanghai 200240, Peoples R China |
| 推荐引用方式 GB/T 7714 | Fu, Luoyi,Tang, Jianzhi,Miao, Benjie,et al. The Effect of Symmetry on the De-Anonymizability of Social Networks[J]. IEEE TRANSACTIONS ON INFORMATION THEORY,2023,69(11):7357-7372. |
| APA | Fu, Luoyi,Tang, Jianzhi,Miao, Benjie,Lin, Xiaojun,Wang, Xinbing,&Zhou, Chenghu.(2023).The Effect of Symmetry on the De-Anonymizability of Social Networks.IEEE TRANSACTIONS ON INFORMATION THEORY,69(11),7357-7372. |
| MLA | Fu, Luoyi,et al."The Effect of Symmetry on the De-Anonymizability of Social Networks".IEEE TRANSACTIONS ON INFORMATION THEORY 69.11(2023):7357-7372. |
入库方式： OAI收割
来源：地理科学与资源研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。