一种社交网络中隐私保护DCIGN算法研究

毛海坤，崔 杰，李晓会，陈 鑫

一种社交网络中隐私保护DCIGN算法研究

毛海坤，崔 杰，李晓会，陈 鑫

（辽宁工业大学 电子与信息工程学院，辽宁 锦州 121001）

提出了DCIGN算法，该算法采取以中心度量方式划分社区，依据社区的关联相似性，通过增加和删除边的方式对社交网络匿名化，使社区不可被区分，这样不仅可以更好抵挡来自于图结构方面的攻击，并大幅提升了整个社交网络的数据可用性。通过仿真实验证明，该算法在数据损失、时间复杂度及匿名质量等方面都有所提升。

社交网络；隐私保护；社区划分；匿名化

社交网络[1]的高速发展，极大地促进了各大社交平台的兴起，以我国主流的手机APP应用“抖音”为例，根据报告来看，截至2021年，“抖音”用户数量已经高达6.8亿人。人们在各大社交平台进行交流，在这些交流的背后，不仅仅存在着用户间的社交关系，还存在着各种敏感的属性关系。如何对社交网络中的信息进行有效的保护，如今屹然成为隐私保护中的一大热点话题。

目前，很多专家致力于社交网络隐私保护或社区划分[2-3]，但鲜有人将社区划分融入到社交网络隐私保护之中，既要做到将社交网络划分社区，又要保护社交网络中的敏感信息。因此，将社交划分与社区网络隐私保护相融合的技术受到很多研究学者的青睐。

近年来，针对社交网络结构的隐私保护，研究学者们展开了深入的研究，黄海平等[4]提出BCPA保护方案，该方法基于边介数模型，使用dK模型获取2K序列，对2K序列依据边介数中心性进行重新排序，再次将排序结果聚类成多个单一序列，再分别对各序列进行加噪处理，最后根据加噪序列生成社交网络图进行发布，该方案隐私保护效果有所提升，且对数据可用性的影响较小；周艺华等[5]在基于社交网络中的用户关系和信息进行聚类处理，依据节点间距离将节点聚类为超点，且每个超点至少具有个节点，最后对超点进行匿名化处理，该方法在隐私保护力度的选取方法上进行了优化，有效地提高了数据的可用性；Day等[6]提出了2种基于聚合和累加直方图的方法来生成扰动图，通过降低敏感度的方法来生成假拓扑图，从而提出簇聚类匿名方法来保护隐私信息；吴梦婷等[7]提出一种基于约束聚类的k-匿名隐私保护方法。通过K近邻思想划分初始集群，根据设定的阈值将集群进行重新划分，划分过程始终遵循信息损失最小化原则，得到每个等价类元组数都在k与2k之间，过程中分类考察准标识符属性并充分考虑离群点对聚类结果的影响，有效降低匿名过程中的信息损失。

因此，本文提出一种基于中心度量同构分组算法(简称DCIGN算法)的隐私保护方案，DCIGN算法的基本思想是依据通过节点之间的最短路径及节点中心度得到个不同的中心节点，然后依据中心节点间的最短路径计算边介数进行社团划分，对划分完的社团依据社区之间的关联性进行同构处理，再进行发布。DCIGN算法不同于传统的K-同构[8]，传统的K-同构通过对原始图划分为个子图，通过增加或减少边数量，使各个子图近似相等，而DCIGN算法是首先进行社区划分，再依据社区之间的关联性进行匿名化处理，最后通过添加边的方式，使得各个子图不可分，使用DCIGN算法匿名后的社交网络图不仅有效地抵挡来自于图结构方面的攻击，同时还提高了数据的可用性。

1 相关工作原理

在本节主要给出一些相关概念及定义，包括邮件网络、社区划分、边介数[9]、节点中心度[10]等。

1.1 邮件网络

邮件网络属于社交网络，是一种抽象的电子邮件平台网络，邮件网络中的节点作为电子邮件用户的抽象表示，边作为用户之间的交互关系抽象表示，例如，A用户向B用户发送了至少1封电子邮件，则邮件网络中存在边缘关系(A，B)，这样电子邮件平台网络就抽象为一个由节点和边构成的一个无权无向的邮件网络。

1.2 社区划分

社区是指网络中基于某种特定关系所划分出来的密集群体[11]。社区内部的节点间相较于社区之间的关系更加密切。设邮件网络=(,)，社区划分是指将图划分成(≥1)个社区，=(1,2,…,C)为各社区定点集合，该集合构成的一个覆盖。社区划分[12]的算法可以大致分为2类：拓扑分析和流分析。邮件网络属于无向无权图[13]，可以归结为拓扑网络中的一种类型，邮件网络拓扑结构如图1所示。

图1 邮件网络拓扑结构图

1.3 边介数

对图=(,)，对中的连边∈，表示节点间的最短路径数量，()表示节点间最短路径中包含边的数量，则边的边介中心度值可以定义为：

边介数[14]基本思想是，每次都会选择边介数高的边删除，边介数越大，说明2个社区之间的关联性越强，该边越可能是2个社区连接的纽带，通过不断删除边介数高的边，进而把整个社交网络[15]划分成若干个社区。

1.4 社团最优评价指标

社团最优中心点评价指标用于评价节点选择是否合理，第一次选取社团中心节点即可对整个网络进行扫描，选择度最大的节点即可，但第二次选取社团中心节点不仅要考虑节点本身的节点中心度，还需要考虑该点与其他中心节点之间的距离，因此，构造一个中心节点评价指标来解决这个问题，评价计算方式如下：

其中表示距离中心度的权重系数；表示节点间最短路径的权重系数。经过多次试验，得到较为合理的权重分配占比为=(1/3)、=(2/3)，d(v,v)表示2点间的最短路径。

1.5 节点中心度

节点中心度是用来衡量节点重要性的指标，将那些和其他节点有较多连接边数的节点视为重要节点，与其他节点的关系越密切，节点度越大，说明该节点越重要，故节点v的中心度定义为：

其中D表示节点的度，表示网络中的节点个数。

1.6 信息损失度量方法

2 DCIGN匿名算法

2.1 系统设计思路

首先对邮件网络图进行数据预处理，通过对预处理后的邮件网络进行遍历、删除操作，选出个社区的中心节点，计算各中心节点的最短路径长度得出最大边介数，依据边介数完成社区划分，再对划分好的社区统计各社区之间的连接边数，从而计算出社区之间关联性，最后通过添加删除边的方式使得社区之间连边数量为-1，这样使社区有1/概率不可区分，从而保证匿名图’中社区的安全。

2.2 设计框架

本文提出的DCIGN匿名算法主要是由社区划分、社区匿名化2部分构成。

社区划分：先选取中心节点，然后通过计算中心节点之间的最短路径找出最大边介数完成社区划分。

社区匿名化：对划分好的社区统计每个社区与其他社区之间连接的边数，从而计算出社区之间关联性，再通过添加删除边的方式使得社区之间不可分。DCIGN算法设计框架如图2所示。

图2 DCIGN算法设计框架

2.3 算法描述

(2)计算所对应的邻接矩阵。

(3)计算每个节点所对应的节点中心度dc。/*依据等式（）*/

(6)选取节点中心度最大的节点。

(7)else

(9)计算max对应节点位置。

(10)重复4～8步骤加入到社区中心集v。

(13)重复11～12步骤，直至将网络分为社区。

(14)计算中所有节点的边介数。

(16)重复13～14，形成个边界点。

(17)while(＜-1)

(18)for←1 to

(21)if(＜-1)

(22)筛选一个不属于G的节点

(24)则重新筛选节点

(25)添加边(,)

(26)end if

(27) end if

(28) end for

(29) end while

2.4 算法隐私保护效果分析

3 实验结果分析

本算法使用Hadoop作为操作平台，使用Linux系统，采用spark作为系统框架，使用MyEclips开发工具进行实现，实验硬件配置为AMD Ryzen 7 4800H with Radeon Graphics 2.90 GHz处理器，16.0 GB RMB。本文采用的数据集为email-Eu-core network，该电子邮件数据集由一家大型欧洲研究机构生成，该数据集说明了邮件网络中用户之间的通信关系，具体参数如表1所示。本文对数据集进行数据预处理，对处理后的数据进行社区划分，最后可得到多个社区结构。

表1 数据集参数统计表

节点1005 边缘25571 最大WCC中的节点986(0.981) 最大WCC中的边缘255552(0.999) 最大SCC中的节点803(0.799) 最大SCC中的边缘24729(0.967) 平均聚类系数0.3994 直径7

本节将对DCIGN算法与一些相似算法进行比较，并从数据损失度、时间复杂度及匿名质量3方面进行分析比较，参与比较的算法有FRESP算法[16]和K-同构算法。

(1)数据损失度分析

在不同值的情况下，DCIGN算法与K-同构算法和FRESP算法在匿名前后数据的数据损失度差异比较，如图3所示。

图3 数据损失度变化曲线

由图3可知，在值不断增加的过程中，3种算法的信息损失量都在增大，但DCIGN算法相较于其他2种算法来说信息损失量低，即在相同的隐私保护程度下，DCIGN算法保存节点间的属性信息比FRESP算法和K-同构算法更具有优势。

(2)时间复杂度分析

通过对比3种算法在不同值的情况下的运行时间来比较3种算法的时间复杂度，如图4所示。

图4 运行时间

由图4可知，随着值的不断增大，3种算法的运行时间都在不断增加，但DCIGN算法明显优于其他2种算法，DCIGN算法在社区划分阶段，首先确定中心度节点，再进行社区划分，相比较于K-同构算法和FRESP算法而言，不需要遍历所有节点，运行时间相对更快，实验结果表明，在同等条件下，DCIGN算法的时间复杂度更低。

(3)匿名质量分析

对于匿名质量，实验采用DCIGN算法与FRESP算法和K-同构算法进行对比。采用社区攻击的方式进行测试，假定攻击者知道邮件网络的相关结构，随机地从原始邮件网络获取子图结构[17-18]作为攻击子图，通过多次实验发现，当=9时，对比效果最佳，匿名质量图如图5所示。

图5 匿名质量变化曲线

由图5可知，在攻击者不同的知识背景下，DCIGN算法的保护效果更好，由实验结果可以看出，DCIGN比其他2种算法的匿名质量相对提高，有效保护了用户隐私。

4 结束语

将社区划分技术和匿名保护技术相融合，采用节点中心度进行社区划分，再根据社区关联性，通过增加和删除边的方式对邮件网络进行匿名化处理，进而保护用户的隐私。实验结果表明，DCIGN算法有效提高了邮件网络的匿名质量，同时，运用社区划分技术使数据损失及时间复杂度都有所降低。该方法主要抵挡来自图结构方面的攻击，未来的工作将主要针对社区内部的隐私保护问题，以抵御各种不同的攻击方式。研究人员要不断对社交网络问题进行研究，才能使人们日常生活的交流更加安全。

[1] 吴振强, 胡静, 田堉攀, 等. 社交网络下的不确定图隐私保护算法[J]. 软件学报, 2019, 30(4): 25-28.

[2] 王婷婷, 龙士工, 丁红发. 大型社交网络的差分隐私保护算法[J]. 计算机工程与设计, 2020, 41(6): 17-22.

[3] 朴杨鹤然, 崔晓晖. 社交网络中用户隐私推理与保护研究综述[J]. 计算机工程与应用, 2020, 56(19): 54-56.

[4] 黄海平, 王凯, 汤雄, 等. 基于边介数模型的差分隐私保护方案[J]. 通信学报, 2019, 40(5): 11-17.

[5] 周艺华, 张冰, 杨宇光, 等. 基于聚类的社交网络隐私保护方法[J]. 计算机科学, 2019, 15(12): 22-33.

[6] Day W Y, Li N, Lyu M. Publishing Graph Degree Distribution with Node Differential Privacy[C]. ACM, 2016: 123-138.

[7] 吴梦婷, 孙丽萍, 刘援军, 等. 基于约束聚类的k-匿名隐私保护方法[J]. 计算机工程与设计, 2021, 42(3): 17-19.

[8] 张晓琳, 李玉峰, 王颖. 动态社会网络隐私保护方法研究[J]. 计算机应用研究, 2012, 29(4): 33-45.

[9] Girvan M, Newman M. Community structure in social and biological networks[J]. PNAS, 2002, 99: 18-25.

[10] 戴爱明, 高学东, 王立敏. 一个基于中心度的社团结构发现新算法[J]. 计算机应用研究, 2011, 28(8): 12-22.

[11] 颜飞, 张兴, 李畅, 等. 基于差分隐私的海量数据发布方法研究[J]. 计算机应用与软件, 2018, 35(11): 7-11.

[12] 高阳, 张宏莉. 动态网络社区发现综述[J]. 智能计算机与应用, 2020(1): 3-24.

[13] 吴振强, 胡静, 田堉攀, 等. 社交网络下的不确定图隐私保护算法[J]. 软件学报, 2019, 30(4): 1106-1120.

[14] 赵菲, 余本国, 冀庆斌. 基于边聚类系数的谱聚类社区划分方法研究[J]. 华中师范大学学报: 自然科学版, 2020, 54(1): 6-19.

[15] 李宇溪, 周福才, 徐紫枫. 支持K-近邻搜索的移动社交网络隐私保护方案[J]. 计算机学报, 2021, 44(7): 1481-1500.

[16] 张晓琳, 李玉峰, 刘立新, 等. 社会网络隐私保护中K-同构算法研究[J]. 微电子学与计算机, 2012, 29(5): 5-15.

[17] Reza K J, Islam M Z, Estivill-Castro V. Privacy protection of online social network users, against attribute inference attacks, through the use of a set of exhaustive rules[J]. Neural Computing and Applications, 2021, 14(22): 1-31.

[18] Yang Y, Hu J, Yang Y. Research on Data Protection Algorithm Based on Social Network[C]. 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS) IEEE, 2020: 12-14.

Research on DCIGN Algorithm for Privacy Protection in Social Network

MAO Hai-kun, CUI Jie, LI Xiao-hui, CHEN Xin

（School of Electronics & Information Engineering, Liaoning University of Technology, Jinzhou 121001, China）

In order to solve the privacy leakage problem of users in the process of data publishing, this paper proposes the DCIGN algorithm. The algorithm divides the community by means of central measurement, and anonymizes the social network by adding and deleting edges according to the association similarity of the community, so that the community can not be distinguished. This can not only better resist attacks from the graph structure, but also greatly improve the data availability of the entire social network. The simulation results show that the algorithm has improved in data loss, time complexity and anonymous quality.

social network; privacy protection; community partition; anonymization

10.15916/j.issn1674-3261.2023.03.005

TP311

A

1674-3261(2023)03-0164-05

2022-08-15

国家自然科学基金项目(61802161)

毛海坤(1996-)，男，辽宁朝阳人，硕士生。

崔 杰(1972-)，女，辽宁鞍山人，副教授，硕士。

责任编辑：孙 林