基于k-subgraph算法的社交网络隐私保护研究

宋喜忠，刘康明

（黄淮学院信息工程学院，河南驻马店463000）

摘要：针对社交网络隐私保护问题，本文提出一种新的隐私保护方法——k-subgraph划分算法，它通

过对社交网络进行分割，通过泛化顶点标签和扰乱图的结构特征，来对社交网络进行匿名化处理，拟达到隐私保护的目的。仿真实验表明，该方法可以有效的保护社交网络中个体的隐私信息，同时保证了社交网络中匿名数据的可用性。

关键词：社交网络；隐私保护；泛化；数据发布；信息损失中图分类号：TP393.02

文献标识码：A

文章编号：1001-7119（2015）07-0119-03

ResearchofPrivacyProtectionforPersonalInformationofSocialNetwork

ServiceBasedonK-subgraphAlgorithm

SongXizhong，LiuKangming

（CollegeofInformationEngineering，HuanghuaiUniversity，HenanZhumadian463000，China）Abstract：Inviewofthesocialnetworkprivacyprotectionissues,thispaperproposesanewprivacyprotectionmethod-k-subgraphdivisionrules,itthroughthesocialnetworksegmentation,throughgeneralizationvertexlabelsanddisruptthefigurestructurecharacteristics,cometoanonymizethesocialnetwork,isproposedtoachievethepurposeofprivacyprotection;Simulationexperimentsshowthatthistimealsocanguaranteeavailability.methodcanofferinanetworkofindividualprivacyprotection,anonymoussocialnetworkatthesameKeywords：socialnetworkservice；privacyprotection；generalization；datapublication；informationloss0引言

在信息数据中往往包含一些数据所有者的

敏感信息，这些信息易被攻击者获取。为了保护数据所有者的隐私，在社交网络数据发布之前要进行必要的敏感信息的属性处理。依赖数据的特征和对数据中的隐私保护及可用性方面的要求，需要对数据中敏感信息的属性进行修改或删除，确保数据所有者隐私信息的安全。目前在对社交网络数据中敏感信息的匿名处理比对单个表数据的匿名处理更复杂，因为在单个数据表中对某些记录的属性进行匿名处理时，由于记录之

间是相互独立的，所以对数据信息进行匿名处理

不会影响到数据表中其它记录。而在社交网络中，对数据敏感的信息进行匿名处理时，由于改变顶点和边的标签（删除或添加顶点和边）会影响到其它顶点和边，也会影响整个社交网络的结构特征。而且攻击者的背景知识也更加复杂更难模拟，给隐私保护带来更大的挑战，如何有效的解决数据发布中隐私保护问题，防止隐私信息被泄露，本文提出一种新的隐私保护方法——k-subgraph隐私规则，利用k-subgraph隐私规则算法实现社交网络数据信息的匿名处理，实验结果表明，社交网络数据满足k-subgraph规则的匿

收稿日期：2014-05-12基金项目：河南省科技攻关项目（No.122102210510）；河南省教育厅科技攻关项目（No.13A520786）。作者简介：宋喜忠（1977-），男，河南省驻马店驿城区人，讲师，硕士。研究方向：计算机网络、数据库。120科技名，可以有效地保护社交网络中的个体隐私信息的安全，保证社交网络中数据的可用性，为人们提供一个方便交流维护社会关系的社交网络平台。

1社交网络隐私模型

1.1

社交网络简介社交网络（socialnetworkservice，SNS）即社会性网络服务，旨在帮助人们建立社会性网络的互联网应用服务，是由代表不同个人或团体之间按照某种关系建立起来的社会网络结构。为人们提供一个方便交流维护社会关系的平台。利用社交网络这个交往平台，人们乐于将自己的个人信息，如爱好、日志、照片、状态，甚至姓名、生日等在社交网络上与他人共享。社交网络一般由节点（成员）和边（关系）构成。节点即社交网络的参与者，边则表示节点和节点之间的联系，它是基于成员之间的某些特定的社会关系，如朋友关系、业务关系或组织关系等而建立的。成员之间在建立了某种社会关系的基础上，就可以方便地实时进行信息交换和资源共享。1.2k-subgraph规则

在发布的社交网络中，目前采用标签匿名方法，由于该算法是保留原始图的结构特征，只对顶点的标签进行匿名处理，这样，就给攻击者提供了获取目标个体结构特征信息的途径，不能保证社交网络中数据信息的安全，数据信息易被攻击者获取。在匿名社交网络中，为了提高社交网络中隐私数据信息的安全性，阻止攻击者根据目标个体结构特征和标签信息识别目标个体，本文提出了一个新的隐私保护方法——k-subgraph隐私规则，k-subgraph隐私规则由k-subgraph结构图的划分、k-subgraphperturbation隐私扰乱规则和k-subgraph连通性三个组成部分。对社交网络进行匿名处理，graph通过k-subgraph划分和k-sub⁃征，实现目标个体的隐私信息的保护，扰乱规则泛化顶点标签和改变图的结构特有效地阻止了攻击者的破坏，从而降低隐私泄露的危险。下面给出相关定义：

定义１（社交网络）令无向图G=(V,E,L)为社

会网络，其中每个节点表示一个实体，

V表示社交网络中节点集合，任一条边来表示两个实体之

通报第31卷

间的关系，边的集合用E⊆V×V表示，L表示社

交网络图中节点的标签集合。假设每个节点的标签由t个属性A1v∈V，节点v,⋯,的At组成。对于任一节点标签可以表示为label(v)=(v.A1,⋯,v.At)，其中v.Ai上的值。

(1≤i≤t)表示顶点v在第i个属性Ai定义2（标签匿名）给定一个社交网络G=(V,E,L)，标签匿名是通过删除标签中的身份属性和随机泛化函数f:L→Lba生成一个与G同构的匿名化社交网络图GbaGk个节点具有相同的标签，=(Vba,Eba,Lba)。Eba=E，且在ba中，至少存在另外，对任一节点v∈Vba，至v′表示，∈V使得使得对所有的label(v)∈labeli(∈[1v)，

,其中少存d]都有label在v′(.vkA)∈个label节点

′′

(v)i∈v.Ai成立。

定义3（k-subgraph划分）给定一个社交网络G=(V,E,L)，图G的一个k-subgraph划分包含n个k子图Gs1

使各子图中的节点标签相同。

,⋯,Gsn

。对每个k-subgraph中的节点标

签泛化，定义4给定一个社交网络i

j

m

(1≤i≠j≤n)G的任意两个划分子图Gs,Gs，VSi

⋂VSj

=φ，

ESi

⋂ESj

=φ，定义5（扰乱规则∪VSi=1

i=V且|VSi

|≥K。

-k-subgraphperturbation）对社交网络G的任一k-subgraphGSt

如果G(1≤t≤m)，

St中每个顶点的度不相同，则通过删除或添加GSt

中的边，使GSt

中的所有顶点的度相同。

定义6（k-subgraph连通性）给定一个社交网络∃u∈GV的n个∈k-VsubgraphGs1

,⋯,Gsn

，当且仅当，Si

和∃uSj

使得u和v是边(u,v)∈E的两

个节点。则在Gsi

subgraph,Gsj

(1≤i≠j≤n)之间存在有k-连通性，且在连j

通性j

表中，存在一j

条

i>记录。特别地，ei=|Ei表示节点分别属于G(del)|，其中|Ei(del)|si

和Gsj

并在k-subgraph划分

中被删除了的边的条数。.

2k-subgraph算法

graph本文提出的隐私信息保护规则——征来阻止攻击者识别目标个体的隐私保护方法，划分，通过泛化顶点标签和扰乱图的结构特k-sub⁃实现k-subgraph划分规则的匿名数据。

第7期

宋喜忠等.基于k-subgraph算法的社交网络隐私保护研究

1212.1

算法描述

输入：原始数据G图，参数k输出：匿名数据G*subgraphStep1划分规则，：输入参数分割成k，图将原始数据n个子图GG图，根据k-S1

,⋯,GSn

；

行泛化处理；

Step2：对分割后的每个子图中的节点标签进构，根据Step3k-subgraph：使每个子图中的节点都有相同的结perturbation规则对每个子图来添加和删除边；

k-subgraphStep4：连接各子图构成新的连通图处理的子图重新连接构成新连通图连通性规则，将经过泛化处理和结构G*，根据G*。2.2算法应用

在对社会网络数据的发布中，为了更好的保护隐私信息的安全，防止个体隐私信息在社交网络中的泄露。利用本文提出的k-subgraph划分规则来保护社交网络中的隐私信息的安全。基于k-subgraph算法思想，首先对社交网络进行匿名化处理，将原始数据图G，按k-subgraph划分算法，分割图G成n个子图，然后对每个子图中的节点标签进行泛化处理，并使每个子图中的节点都有相同的结构，最后按照k-subgraph连通性规则将所有子图重新连接构成图G*。通过对社交网络进行匿名化处理，对社会网络的数据隐私拟达到保护的目的。

图1是一个合成的简单的Email通信的社会网络，图1中每个顶点表示一个通信联系人，边表示通信联系人之间存在graphemailsubgraph划分规则应用到图1社会网络中，通信。将通过k-sub⁃k-名数据，如图划分并对个体标签进行泛化处理后的匿2所示。

实验的所有源代码用C++语言实现，其过程如下：

设k=5，应用k-subgraph划分规则，根据定义3，通过对图G删除边G的两(E,W)和边(C,W)得到图1={A,B,D个,C,5-E}subgraph1G2,sW1

,和GH}s2

，其中VS，VS={P,Q,G。然后对Gs

1

和Gs2

中的节点标签进行泛化处理，使Gs和Gs2

中的每个节点具有相同标签。由于G1

s1和Gs2

中的节

点的度数不同，需要根据定义4，删除Gs中的边(B,E)和边(D,E)，删除G1

s2

中的边(Q,E)，使得Gs1

和

图1Email通信的社会网络(G)Fig.1Emailcommunicationsocialnetwork(G)

图2发布的匿名图数据Fig.2Anonymouschartdatareleased

Gs中的所有节点的度数为2。因为C,E∈VS，

W2

∈V1

S2

，显然Gs和Gs具有k-subgraph连通性，因

此，在G*

2

S1和G*1S2

之间存在一条权值为2的边，即在连通性表中包含<1,2,2>记录。在图2中，给出了对图G经过匿名后，发布的匿名数据图。

3实验结果与分析

3.1

隐私安全性分析

由于原始社会网络经过k-subgraph规则划分、扰乱，其原始的结构特征改变了，经过匿名变换后的发布匿名图是由多个具有相同顶点的标签且顶点的结构特征也相同的k-subgraph组成的，因此，攻击者并不能根据背景知识来精炼侯选集合。保证了社交网络中隐私信息的安全。3.2数据的可用性分析

通过对社会网络中的原始数据图进行匿名化处理，处理后的匿名图G*发布在社会网络中，由添加和删除边而导致的信息丢失量可以通过添加和删除的边的总数来衡量。匿名图G*中网络数据具有有效的数据分析。实现了保护隐私信息的目的，且数据发布者保证G*中的信息丢失量是可以接受的。

4结束语

（下转第125页）

第7期

马瑞华等.新型套管蒸发式冷凝器性能试验研究

125的增大加剧了液膜的湍动，使换热性能增强，但是另一方面水流量的增大使得管表面流体层流层厚度增加，热阻增大，使得换热性能减弱，正是由于这几个因素的共同影响使得管束的换热系数继续增大，只是变化程度变缓。

从图中可以看出随着水流量的不断增大，换热系数也不断增大，结合热流密度对换热系数的影响实验得出的结论，可以看出配水量为0.46m3/(h·kW)左右是一个最小配水量。在工程实践中考虑到水的飞散损失，工程实践的类似性，可以参考本次实验的最小配水量。

热系数随循环冷却水流量的增大不断增大。

4）在实验中，套管蒸发式冷凝器的换热系数可达2500W/（m2·K）以上，具有较好的应用价值。参考文献:

[1][2][3][4]

姜守忠.制冷原理与设备[M].北京，高等教育出版社，郑贤德.制冷原理与装置[M].北京，机械工业出版社，朱冬生，尹应德，蒋翔等.蒸发式冷凝制冷系统性能实验研究[J].太阳能学报，2011，32（8）：1163-1168.

ArmbrusterR，MitrovicJ.Evaporativecoolingofafallingwaterfilmonhorizontaltubes[J].ExperimentalThermalandFluidScience，1998，18(3):183-194.2000:118-123.2005:169-178.

3结论

设计的新型套管蒸发式冷凝器经测试可得

出如下结论：

1）在一定的送风量和循环冷却水流量的前提下，换热系数随热流密度的不断增大先增大后减小，存在换热系数的最大值。结合循环冷却水流量对换热系数的影响得出最小配水量约为0.46m3/(h·kW)，在实际的工程实践中考虑水的飞溅和工程实践的类似性等因素，可以本实验的配水量作为参考。

2）送风量对换热系数的影响较小，当水膜和空气的热湿交换充分后再增大送风量的对换热系数的影响甚微，得出最小配风量为3.288m3/（h·kW）。

3）循环冷却水流量对换热系数影响较大，换

（上接第121页）

[5]Maclain-CrossIL，BanksPJ.AGeneralTheoryofWet

SurfaceHeatExchangersandItsApplicationtoRegenera⁃tiveEvaporativeCooling[J].HeatTransfer，l981，103(3):579-584.

[6]GuoCQ，ZhuDS，JiangX.Numericalsimulationofheatandmasstransferinplate-typeevaporativecondenser[J].(3):53-57.

JournalofSouthChinaUniversityofTechnology，2009，37

[7]MetinErtuncH，MuratH.Comparativeanalysisofanevap⁃tiveneurofuzzyinferencesystem[J].InternationalJournal

orativecondenserusingartificialneuralnetworkandadap⁃ofRefrigeration，2008，31(8):1426-1436.

[8][9]

王铁军.喷淋蒸发翅片管式冷凝器传热传质研究[J].低温与超导，2006，34(4):299-302.

马瑞华，崔文智，项勇，等.新型套管蒸发式冷凝器的理论研究[J].制冷与空调，2007，7(2):32-35.

本文利用无向图G来模拟社会网络数据，图G中的每个顶点对应一个个体特征的多个属性组成的标签，图G中的边表示个体之间的关系。应用k-subgraph规则来划分并进行匿名处理原始社会网络数据，匿名处理后的数据发布到社会网络中，由于目标个体的标签和结构特征的改变，使攻击者无法根据背景知识来识别目标个体在匿名社会网络中的对应顶点。使得个体的隐私信息得到有效保护。通过仿真实验，结果表明，利用无向图G来模拟社交网络数据，应用k-sub⁃graph规则对社交网络数据进行匿名处理，对发

布的社交网络个体的隐私信息提供了安全的保

障，有效阻止了攻击者获取个体的隐私信息，同时保证匿名社交网络的可用性。解决了社交网络数据发布中的隐私泄露问题。参考文献：

[1][2][3]

刘建伟，李为宇，孙钰.社交网络安全问题及其解决方案张志勇，杨丽君，黄涛.多媒体社交网络中的数字内容安全分发研究[J].计算机科学，2012，39(4):94-97.

韦伟，李杨，张为群.一种基于GSNPP算法的社交网络隐私保护方法研究[J].计算机科学，2012，39(3):104-106.[J].中国科学技术大学学报，2011，41(7):565-575.