基于KFCMSA的(k，l)加权社交网络匿名算法

史伟　王园园　李刚　张兴

摘 要：图数据隐私保护的研究目前主要集中在简单图，适应范围有限。将权重图数据的隐私保护作为研究对象，可以改善权重图发布之后数据的可用性及有效性。针对在利用聚类匿名化方法处理社交网络数据时，需要增删大量的边和节点，造成严重的数据失真的问题进行了研究。提出了（k，l）加权社交网络匿名算法KFCMSA（联合k成员模糊聚类和模拟退火），并利用改进的簇划分算法将权重社交网络聚类成不同的簇，对同一簇中节点的边权重进行泛化，使节点满足l多样性。在实现k度匿名的同时有效减少了边的改变量，提高了数据的可用性，实现最优聚类的同时防止了同质性攻击。聚类质量实验和数据可用性分析表明该算法具有较高的性能优势和较高的边保留率。

关键词：社交网络；权重图数据；隐私保护；模糊聚类；模拟退火

中图分类号：TP309.2 文献标志码：A 文章编号：1001-3695（2023）10-041-3149-06

doi：10.19734/j.issn.1001-3695.2022.11.0836

（k，l） weighted anonymous algorithm for social network based on KFCMSA

Shi Wei1，2，Wang Yuanyuan1，2，Li Gang1，2，Zhang Xing1，2

（1.School of Electronics & Information Engineering，Liaoning University of Technology，Jinzhou Liaoning 121001，China;2.Key Laboratory of Security for Network & Data in Industrial Internet of Liaoning Province，Jinzhou Liaoning 121001，China）

Abstract：The general research of graph data privacy protection mainly focuses on simple graphs，which has a limited scope of application.Taking the privacy protection of the weight graph data as the research object can improve the availability and effectiveness of the data after the weight graph is published.This paper studied the problem of serious data distortion caused by the need to add and delete a large number of edges and nodes when using the clustering anonymization method to process social network data.It proposed the （k，l） weighted social network anonymity algorithm KFCMSA（combined k-member fuzzy clustering and simulated annealing），and clustered the weighted social network into different clusters using the improved clustering algorithm.It generalized the edge weights of nodes in the same cluster to make nodes satisfy l diversity.While implementing k-degree anonymity，it effectively reduced the amount of edge changes，improved the availability of data，and prevented homogeneity attacks while achieving optimal clustering.The clustering quality experiment and data availability analysis show that the algorithm has high performance advantages and high edge retention rate.

Key words：social network；weight graph data；privacy protection；fuzzy clustering；simulated annealing

0 引言

隨着社交网络的发展走向成熟化，更多互联网使用者参与进来，在平台上分享信息。在这个交互过程中产生了海量行为数据，包含用户的身份信息和社交关系等敏感信息。这些信息一旦被恶意攻击者获取后，将会对用户造成物质甚至精神上的伤害。例如，2021年，淘宝用户昵称和手机号被盗事件，造成11.81亿用户隐私泄露；镇江丹阳30人非法贩卖6亿条个人信息获利800余万，社会危害严重。为平衡用户的隐私需求和数据分析之间的矛盾，数据在发布之前必须进行隐私保护。

社交网络中的用户和用户关系可以被抽象成图中的节点和边，通过对图结构进行研究实现对社交网络的隐私保护［1］。刘宇涵等人［2］剖析了图数据的隐私风险，分析了当前可行的图数据隐私攻击与攻击量化算法及其算法原理，并且总结了四种数据隐私防御技术。目前这四类研究的图结构隐私保护方法为：

a）k-匿名方法。2015年，Li等人［3］提出了一种新的匿名化方法NHDS，该方法利用网络图结构减少候选集的大小，利用用户的文件信息，识别出高可信度的用户，实现了较高的检测精度。2017年，Sharma等人［4］制定了 K-BGP 问题并给出了硬度结果，开发了TSH1和TSH2两个启发式方法来解决约束问题。在此背景下提出了一个集成框架，用于在存在授权机制的情况下确保用户隐私。2018年，Arshad等人［5］提出了一个匿名化方案，通过制作图和开发节点度来保证隐私安全，减少了0.43%的信息丢失。2020年，Kotra等人［6］研究了在可能的攻击下为k匿名选择最佳匿名级别的问题，由此提出了一种新颖的博弈论框架来模拟共享组织和攻击者之间的交互，允许在k匿名化中确定 k 的最佳值。2022年，张强等人［7］发现最优k-等价集无法完全代表k-匿名的最优等价集，于是提出了一种最优k-匿名数据隐私保护机制，利用了贪心算法和二分聚类思想，解决了最优化问题。

b）图聚类方法。2015年，Wang等人［8］提出了一种MASN聚类算法，将敏感属性考虑在内，和SaNGreeA算法相比更好地保护了用户隐私。2018年，Yu等人［9］应用度数相同的顶点属性随机交换的策略，构造虚假目标，并且采用聚类和局部扰动策略减少信息损失。2018年，Qian等人［10］提出两种聚类方法来聚合柱状图，即基于序列感知和局部密度的聚类方法，有效保护了数据隐私。2020年，Paul等人［11］提出了基于图形聚类的前处理和后处理技术，提高了Kronecker社交网络的准确性。2021年，卜湛等人［12］针对在传统的图聚类方法假设节点属性与网络拓扑所对应的类簇结构完全一致，而真实的社交网络并不一致的问题，将属性图聚类建模为多目标优化的问题，提出了一种基于动态类簇形成博弈的属性图聚类方法。

c）差分隐私方法。2017年，Li等人［13］为保护加权图，提出了MB-CI策略，在直方图的基础上实现差分隐私，提高了数据的准确性。2018年，Gao等人［14］定义了无向图上基于组的局部差分隐私概念，通过将网络分解为1邻域图并应用基于HRG的方法，通过添加和删除足够多的边保持局部图的差分隐私和降低噪声尺度，直到满足其隐私需求。2019年，Ahmed等人［15］提出了一种随机矩阵的方法来发布在线社交网络图的特征向量，通过减少邻接矩阵的维度来实现空间效率，通过添加少量的噪声实现差分隐私。2022年，Zhang等人［16］提出一种基于局部差分隐私模型（LDPCD）的社区检测方法，通过采用局部差分隐私的截断拉普拉斯机制，提高了用户扰动数据的准确性。

d）图结构扰动。2014年，Bonchi等人［17］对图像和图像匿名进行了本质上的区分，并使用熵量化来衡量扰动图所提供的匿名级别，还提出了一种随机稀疏化方法，在实现匿名化的同时仍然保留了原始图的特征。2017年，Casas-Roma等人［18］提出了不确定图的（k，ε）混淆概念，通过细粒度的图结构扰动提高数据的可用性。2018年，Palanisamy等人［19］开发了一种基于密钥的可逆图结构扰动技术，该技术可以防止特权较低的用户访问图结构，同时允许特权用户恢复原始图结构。2021年，Kiabod等人［20］引入了一种图匿名化算法来提高匿名化速度，并提高图效用。该算法在图修改步骤中使用数字分解从图中删除最佳边，同时选择所有适当的边并使用NaFa算法将其添加到图中。

在上述已有的社交网络隐私保护的研究基础上，提出了基于KFCMSA的权重图匿名保护方法。主要贡献如下：

a）针对权重图和数据失真问题，提出了基于KFCMSA的加权图隐私保护方法，对节点度进行最优簇划分，利用边权重泛化保证了同一簇中至少存在l个节点，可以有效抵御同质性攻击。

b）通过与已有方法对比，证明本文方法有更高的数据可用性和数据准确性。

1 相关基础知识

1.1 权重社交网络的基本定义和相关概念

定义1 带权重的社交网络。使用无向加权图G建立社交网络模型，边的连接情况表示用户之间的关系，边的权重表示成员关系的亲密程度，用G=（V，E，W）表示。表1为函数相关含义。

定义2 （k，l）-图匿名模型。（k，l）-图匿名由k匿名模型和l多样性模型共同构成，分别作用于权重图的节点和边权重的隐私保护，如图1（a）为原始图，图1（b）为不考虑权重的k度匿名图，图1（c）是一个（2，2）度匿名模型。

2 基于KFCMSA的隐私保护方法

现有的社交网络数据更多是在简单图模型的基础上实现隐私保护，没有考虑到带权重的社交网络数据，同时对节点度进行簇划分时存在较大的信息损失，因此针对这些问题，提出了加权社交网络匿名算法。首先联合k成员模糊聚类和模拟退火（KFCMSA），利用改进的簇划分算法对节点进行最优聚类，实现k度匿名的同时有效减少了重构图时边的改变量。其次为了防止同质性攻击，对同一簇中节点边权重进行泛化使簇中节点满足l多样性。

图数据中节点的度D（d1，d2，…，dn）是非常重要的信息，有时可以唯一确定一个节点。为了保护数据的隐私，利用k匿名保证图中至少k个节点具有相同的度。

匿名化加权社交网络的基本思想为：首先利用算法1得到最优度划分序列，将得到的度序列利用算法2构造k-度匿名图，最后通过算法3泛化部分边实现（k，l）匿名图。

2.1 最优簇划分

首先利用模糊C均值聚类算法（FCM）［23］计算数据对聚类中心的隶属程度，该隶属程度用一个数值表示，根据式（2）對FCM聚类结果c（c1，c2，…，cp）中节点数量小于k的簇进行合并或添加元素，具体方式需要判断对应簇中节点的个数。若节点较少，添加元素时，容易破坏其他簇的平衡；若节点较多，合并两个簇会产生较大误差，最终得到新的聚类，且每个簇中都至少有k个元素。

将作为SA的初始解，再将初始解赋值给最优解，根据需求设置参数后进行迭代，在每一次迭代中，将新解与最优解进行比较，挑选出新的最优解并保存，不断迭代直到满足条件输出最优解作为最优划分。产生新的方式如图2所示，此时k=2。

2.2 构造匿名图

为减少原始网络中节点对最短路径和节点中心度等拓扑属性的改动，在修改节点度时，尽可能利用邻居节点修改，具体步骤如算法2所示。

在算法2中，根据度变化前后的值将度序列d′分为三类，d′+{d′i|〈d′-d〉>0}为需要增边的节点度，d′-{d′i|〈d′-d〉<0}为需要删边的节点度，需要分别处理这两种度对应的节点。

2.3 加权边泛化

在每一个簇c′i{vj|vj∈c′i}，首先得到簇中节点的权重矩阵，对节点的权重序列进行递减排序，并根据序列间的互信息划分为iterm/L」个组，保证每个组至少有L个成员，对每一项进行比较，如果Wi，j>η×Wp，q，η=2则定义Wi，j为比Wp，q大的节点，将两个边权重投影到一个区域值中，即泛化为

3 分析与比较

实验环境为Intel CoreTM i5-7200U CPU @ 2.50 GHz，8 GB内存，程序采用Python语言实现。

考虑到典型的度聚类匿名算法Greedy聚类［24］、动态规划聚类［25］和KFCM［26］，通过度对节点进行最优划分，将其与KFCMSA进行实验对比。使用的数据集来自网络数据仓库http：//networkrepository.com。soc-wiki-elec为真实数据集，friend、p-hat1500-3为合成数据集。这三种数据集的部分图属性如表2所示，|V|代表图G中顶点的个数，|E|代表图G中边的个数，Gdensity代表图的密度， dmax代表节点的最大度，dmin代表节点的最小度，daverage代表节点度的平均值。

3.1 度量标准

量化匿名化方法［27］可以衡量隐私保护的优劣程度，匿名化技术不同，指标的需求也不一样。为了衡量k度匿名结果的好坏和重构图中真实数据的可用性，使用以下量化指标进行度量。

定义4 聚类误差CE。CE是平均簇内距离和平均簇间距离的比值，用来衡量聚类误差大小，CE越大，聚类误差越大。centervi是节点vi所在簇聚类中心；centerj和centerk分别是簇c′j和c′k的聚类中心；为简化公式，簇c′的个数‖c′‖用t代替。CE关系式如式（3）所示。

定义7 边保留率AErr。E是原始图G中的边集合，由真实边组成，E′是待发布的匿名化重构图G′的边集合，由真实边和假边组成。在重构图边集合中，真实边占混合边E′的比例为边保留率AErr，即为

定义8 边权重的有效率SErr。权重泛化之前的边权重为Wedge，泛化后的边权重用区间［Wmin，Wmax］表示。δ表示偏差率，δ=0.2；VEi是单条边权重泛化后的有效率，匿名图中边权重的有效率SErr由下式得出：

3.2 聚类质量分析

考虑到k成员模糊聚类结果对初始点的选取具有较高的随机性，于是对其取10次聚类结果的平均值。图4（a）～（b）给出了度变化量L1随k变化的规律，从图中可以看出，各个数据的L1和k值成正比，匿名代价随着k值的增加而增加。这是因为随着k值的增加导致簇中节点数量增加，需要在一个簇内匿名化更多节点，造成匿名代价增加。图4（b）中L1（Gree-dy）和L1（动态规划）比L1（KFCMSA）高出41.8%，L1（KFCM）比L1（KFCMSA）高出12.5%，这是因为数据集soc-wiki-elec的密度较低并且节点度的值比较分散，所以KFCMSA算法更准确。

算法以簇节点中度的平均值为簇中心点，簇中分散点越多，信息损失越大。图5给出了归一化互信息NMI在不同k值下的变化量，随着k值增加，度序列的变化量增加，误差增加，造成NMI下降，但可以看出KFCMSA方法一直优于其他几种方法。图5（b）中，四种方法得到的NMI值非常接近，这是因为度变化量虽然大，数据集p-hat1500-3的平均度也同样很大，总的度变化量占比很小，对NMI的影响很小。

图6展示了四种方法在三种数据集上产生聚类误差的变化量。从图中可知，聚类误差和k值成正比，KFCM和KFCMSA两种方法的上升趋势更平缓，两条曲线几乎重合，因为这两种算法属于同类型算法，产生结果的差值很小。Greedy和动态规划方法划分下产生的误差曲线呈线性增加，对度序列的划分不是很理想。图6中曲线的变化趋势与图4中基本相同，证明度变化量是影响聚类误差的主要因素。

3.3 數据可用性分析

图7比较了四种方法在图重构之后边的保留率随k值变化的趋势，实验数据为p-hat1500-3。当k值增加时，KFCMSA边保留率最高，在90%以上；随着k值减少，其下降趋势比较平缓。Greedy和动态规划构造后边的保留率较差，呈直线下降趋势。主要原因是KFCM和KFCMSA的度变化误差最小，有效提高了边的有效率；同时Greedy和动态规划划分方法由于自身设定问题，得到的新的度序列值均大于原始度序列，即d′i≥di，在构造匿名图时只能执行增边操作；KFCM和KFCMSA可以同时使用增边和删边构造匿名图，避免添加过度的边。

将正整数value∈［1，100］赋值给原图边，为了满足长尾理论，取值概率pvalue=1e0.69×value。利用定义9衡量图信息有效率，设k=15，如图8所示，可以看到随着l值增大，图信息有效率不断降低，并且变化趋势更加明显。相比较其他两种方法，KFCM和KFCMSA两种方法的信息有效率一直处在较高水平，但KFCMSA的信息有效率更高且更平稳；而Greedy和动态规划划分方法对边的改动数量较多，进而泛化的边数量也多，造成较低的图信息可用率。由此可见，KFCMSA方法是构造匿名图最适合的方法。

基于KFCMSA度序列划分算法在不同数据集上使用不同的衡量方法都要优于KFCM算法，更优于Greedy和动态规划算法。特别是在节点数量较大、图密度较低的数据集中这种优势变得更加明显。因此，KFCMSA方法在图的聚类匿名化发布方面除了能够达到隐私保护的目的，还具有较大的性能优势。

4 结束语

基于KFCMSA算法，本文提出了权重图隐私保护方法。首先对节点度进行最优簇划分，利用边权重泛化可以有效抵御同质性攻击。在真实数据集与合成数据集的基础上，与其他算法进行了比较，实验结果表明，信息有效率高于其他三种方法，边保留率更高，误差更小，在质量分析上具有显著优势。然而，此方法还存在一些有待深入研究的问题：有些参数已经提前设定，具有一定的限制性，如何减少对这些参数的需求，降低属性约束是下一步需要考虑的问题，并且图节点之间的關系对算法的影响是需要考虑的，这也是下一步工作的重点。

参考文献：

［1］刘向宇，王斌，杨晓春.社会网络数据发布隐私保护技术综述［J］.软件学报，2014，25（3）：576-590.（Liu Xiangyu，Wang Bin，Yang Xiaochun.Survey on privacy preserving techniques for publishing social network data［J］.Journal of Software，2014，25（3）：576-590.）

［2］刘宇涵，陈红，刘艺璇，等.图数据上的隐私攻击与防御技术［J］.计算机学报，2022，45（4）：702-734.（Liu Yuhan，Chen Hong，Liu Yixuan，et al.State-of-the-art privacy attacks and defenses on graphs［J］.Chinese Journal of Computers，2022，45（4）：702-734.）

［3］Li Huaxin，Chen Qingrong，Zhu Haojin，et al.Privacy leakage via de-anonymization and aggregation in heterogeneous social networks［J］.IEEE Trans on Dependable and Secure Computing，2020，17（2）：350-362.

［4］Sharma A，Pathak S.Enhancement of k-anonymity algorithm for privacy preservation in social media［J］.International Journal of Engineering & Technology，2018，7（2）：40-45.

［5］Arshad M U，Felemban M，Pervaiz Z，et al.A privacy mechanism for access controlled graph data［J］.IEEE Trans on Dependable and Secure Computing，2019，16（5）：819-832.

［6］Kotra A，Eldosouky A R，Sengupta S.Every anonymization begins with k：a game-theoretic approach for optimized k selection in k-anonymization［C］//Proc of International Conference on Advances in Computing and Communication Engineering.Piscataway，NJ：IEEE Press，2020：1-6.

［7］张强，叶阿勇，叶帼华，等.最优聚类的k-匿名数据隐私保护机制［J］.计算机研究与发展，2022，59（7）：1625-1635.（Zhang Qiang，Ye Ayong，Ye Guohua，et al.K-anonymity data privacy protection me-chanism based on optimal clustering［J］.Computer Research and Development，2022，59（7）：1625-1635.）

［8］Wang R，Zhang M，Feng D，et al.A clustering approach for privacy-preserving in social networks［C］//Proc of the 17th International Conference on Information Security and Cryptology.Berlin：Springer International Publishing，2015：193-204.

［9］Yu Fahong，Chen Meijia，Yu Bolin，et al.Privacy preservation based on clustering perturbation algorithm for social network［J］.Multi-media Tools and Applications，2018，77（9）：11241-11258.

［10］Qian Qing，Li Zhixu，Zhao Pengpeng，et al.Publishing graph node strength histogram with edge differential privacy［C］//Proc of the 23rd International Conference on Database Systems for Advanced Applications.Berlin：Springer International Publishing，2018：75-91.

［11］Paul A，Suppakitpaisarn V，Bafna M，et al.Improving accuracy of differentially private Kronecker social networks via graph clustering［C］//Proc of International Symposium on Networks，Computers and Communications.Piscataway，NJ：IEEE Press，2020：1-6.

［12］卜湛，王煜尧，马丽娜，等.基于动态类簇形成博弈的属性图聚类方法［J］.计算机学报，2021，44（9）：1824-1840.（Bu Zhan，Wang Yuyao，Ma Lina，et al.Attribute graph clustering method based on dynamic cluster forming game［J］.Chinese Journal of Computers，2021，44（9）：1824-1840）

［13］Li Xiaoye，Yang Jing，Sun Zhenlong，et al.Differential privacy for edge weights in social networks［J］.Security and Communication Networks，2017，2017：1-10.

［14］Gao Tianchong，Li Feng，Chen Yu，et al.Local differential privately anonymizing online social networks under HRG-based model［J］.IEEE Trans on Computational Social Systems，2018，5（4）：1009-1020.

［15］Ahmed F，Liu A X，Jin Rong.Publishing social network graph eigenspectrum with privacy guarantees［J］.IEEE Trans on Network Science and Engineering，2019，7（2）：892-906.

［16］Zhang Zhejian.LDPCD：a novel method for locally differentially private community detection［J］.Computational Intelligence and Neuroscience，2022，2022：1-18.

［17］Bonchi F，Gionis A，Tassa T.Identity obfuscation in graphs through the information theoretic lens［J］.Information Sciences，2014，275：232-256.

［18］Casas-Roma J，Herrera-Joancomartí J，Torra V.A survey of graph-modification techniques for privacy-preserving on networks［J］.Artificial Intelligence Review，2017，47（3）：341-366.

［19］Palanisamy B，Liu Lin，Zhou Yang，et al.Privacy-preserving publi-shing of multilevel utility-controlled graph datasets［J］.ACM Trans on Internet Technology，2018，18（2）：1-21.

［20］Kiabod M，Dehkordi M N，Barekatain B.A fast graph modification method for social network anonymization［J］.Expert Systems with Applications，2021，180：115148.

［21］Hppner F，Klawonn F，Kruse R，et al.Fuzzy cluster analysis：methods for classification，data analysis and image recognition［M］.Hoboken：Wiley，1999.

［22］Mu Caihong，Xie Jin，Liu Yong，et al.Memetic algorithm with simulated annealing strategy and tightness greedy optimization for community detection in networks［J］.Applied Soft Computing，2015，34：485-501.

［23］Bezdek J C，Ehrlich R，Full W.FCM：the fuzzy C-means clustering algorithm［J］.Computers & Geosciences，1984，10（2-3）：191-203.

［24］Honda K，Kawano A，Notsu A，et al.A fuzzy variant of k-member clustering for collaborative filtering with data anonymization［C］//Proc of IEEE International Conference on Fuzzy Systems.2012：1-6.

［25］Liu Kun，Terzi E.Towards identity anonymization on graphs［C］//Proc of ACM SIGMOD International Conference on Management of Data.New York：ACM Press，2008：93-106.

［26］Zhang Xiaoyan，Wang Mengjuan.Improved SVM classification algorithm based on KFCM and LDA［J］.Journal of Physics：Confe-rence Series，2020，1693（1）：012107.

［27］Kelly D J，Raines R A，Grimaila M R，et al.A survey of state-of-the-art in anonymity metrics［C］//Proc of the 1st ACM workshop on Network Data Anonymization.New York：ACM Press，2008：31-40.

收稿日期：2022-11-16；修回日期：2023-02-20基金項目：国家自然科学基金资助项目（61802161）；辽宁省教育厅科学研究项目（JZL202015404，LJKZ0625）；辽宁省应用基础研究计划资助项目（2022JH2/101300280）

作者简介：史伟（1978-），女，辽宁锦州人，实验师，硕士，主要研究方向为信息安全、隐私保护；王园园（1996-），女（通信作者），河南周口人，硕士研究生，主要研究方向为图数据的隐私保护（wyyuand@163.com）；李刚（1995-），男，陕西宝鸡人，硕士，主要研究方向为大数据隐私与保护；张兴（1975-），男，辽宁葫芦岛人，教授，硕导，博士，主要研究方向为网络体系架构与协议、信息安全等.