MLDA:a multi-level k-degree anonymity scheme on directed social network graphs  

作　　者：Yuanjing HAO Long LI Liang CHANG Tianlong GU 

机构地区：[1]Guangxi Key Laboratory of Trusted Software,Guilin University of Electronic Technology,Guilin 541004,China [2]Engineering Research Center of Trustworthy AI(Ministry of Education),Jinan University,Guangzhou 510632,China

出　　处：《Frontiers of Computer Science》2024年第2期199-215,共17页中国计算机科学前沿（英文版）

基　　金：supported by the National Natural Science Foundation of China (Grant Nos.61966009,U22A2099).

摘　　要：With the emergence of network-centric data,social network graph publishing is conducive to data analysts to mine the value of social networks,analyze the social behavior of individuals or groups,implement personalized recommendations,and so on.However,published social network graphs are often subject to re-identification attacks from adversaries,which results in the leakage of users’privacy.The-anonymity technology is widely used in the field of graph publishing,which is quite effective to resist re-identification attacks.However,the current researches still exist some issues to be solved:the protection of directed graphs is less concerned than that of undirected graphs;the protection of graph structure is often ignored while achieving the protection of nodes’identities;the same protection is performed for different users,which doesn’t meet the different privacy requirements of users.Therefore,to address the above issues,a multi-level-degree anonymity(MLDA)scheme on directed social network graphs is proposed in this paper.First,node sets with different importance are divided by the firefly algorithm and constrained connectedness upper approximation,and they are performed different-degree anonymity protection to meet the different privacy requirements of users.Second,a new graph anonymity method is proposed,which achieves the addition and removal of edges with the help of fake nodes.In addition,to improve the utility of the anonymized graph,a new edge cost criterion is proposed,which is used to select the most appropriate edge to be removed.Third,to protect the community structure of the original graph as much as possible,fake nodes contained in a same community are merged prior to fake nodes contained in different communities.Experimental results on real datasets show that the newly proposed MLDA scheme is effective to balance the privacy and utility of the anonymized graph.

关 键 词：directed social network graph graph publishing k-degree anonymity community structure graph utility 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP391.1[自动化与计算机技术—控制科学与工程]