收稿日期:20190603;修回日期:20190802 基金项目:国家自然科学基金资助项目(61562065);内蒙古自然科学基金资助项目
(
2019MS06001)
作者简介:李健(1995),男,辽宁庄河人,硕士,主要研究方向为社会网络社区结构隐私保护;张晓琳(1966),女(通信作者),内蒙包头人,教
授,硕导,博士,主要研究方向为数据库理论与技术、大规模数据下社会网络隐私保护(zhangxl@imust.cn);刘娇(1995),女,河北唐山人,硕士,主
要研究方向为社会网络社区结构隐私保护;高鹭(1979),女,内蒙包头人,副教授,硕士,主要研究方向为社会网络社区结构隐私保护;张换香
(1979),女,内蒙乌兰察布人,博士研究生,主要研究方向为社会网络社区结构隐私保护、人工智能.
基于 Pregel的分布式保护节点影响力匿名算法
李 健
1
,张晓琳
1
,刘 娇
1
,高 鹭
1
,张换香
1,2
(1.内蒙古科技大学 信息工程学院,内蒙古 包头 014010;2.上海大学 计算机工程与科学学院,上海 200000)
摘 要:针对当前社会网络图数据规模不断增加,现有匿名算法大多只考虑匿名隐私强度,忽略匿名后节点影
响力变化的问题进行了研究。基于 Pregel模型提出分布式保护节点影响力的匿名算法(anonymousprotectingin
fluenceofnodes
,APIN)。算法分解社会网络图得到 k核图,核数代表节点影响力,分裂节点匿名的同时保证原节
点核数不变,从而保证节点影响力不变。为了提高
APIN算法隐私保护强度,针对社区结构提出保护社区中节点
影响力的社会网络匿名算法(anonymousprotectinginfluenceofnodesincommunity,APINC),基本思想是在社区中
实现
δ
shell安全分组,从而达到
δ
核匿名。在真实社会网络数据实验表明,所提出的算法在保持节点影响力的
同时很好地保护了图结构性质;最后展望了下一步研究方向。
关键词:社会网络;影响力;Pregel;k核;社区结构
中图分类号:TP309 文献标志码:A 文章编号:10013695(2020)11046342805
doi:10.19734/j.issn.10013695.2019.06.0294
DistributedprotectionnodeinfluenceanonymityalgorithmbasedonPregel
LiJian
1
,ZhangXiaolin
1
,LiuJiao
1
,GaoLu
1
,ZhangHuanxiang
1,2
(1.Dept.ofInformationEngineering,InnerMongoliaUniversityofScience&Technology,BaotouInnerMongolia014010,China;2.Dept.of
ComputerEngineering&Science,ShanghaiUniversity,Shanghai200000,China)
Abstract:Withtherapidincrementofthesizeofthegraphinthesocialnetwork,mostoftheexistinganonymousalgorithms
onlyconsidertheanonymousprivacyintensity,andignorethechangeofnodeinfluenceafteranonymity.Thispaperproposed
adistributedAPIN.Thealgorithmdecomposedthesocialnetworkgraphtoobtainthe
kcoregraph.Thecorenumberrepresen
tedtheinfluenceofthenode.Thesplitnodeanonymityalsoensuredthatthenodecorenumberintheoriginalgraphwasun
changed,thusensuringthatthenode’sinfluencewasunchanged.Inordertoimprovetheprivacyprotectionstrengthofthe
APINalgorithm
,thispaperproposedanAPINCforthecommunitystructure.Thebasicideawastoimplement
δ
shellsecurity
groupinginthecommunitytoachieve
δ
coreanonymity.Experimentsonrealsocialnetworkdatashowthattheproposedalgorithm
canprotectthestructureofthegraphwellwhilemaintainingtheinfluenceofthenode.Finally,thepaperforwardedtothenext
researchdirection.
Keywords:socialnetwork;influence;Pregel;kcore;communitystructure
随着社会网络的快速发展和普及,在线社会网络(online
socialnetwork
,OSN)存储了大量用户的个人信息,包括节点注
册信息 与用户 使 用 服 务 时 产 生 的 内 容。以 Facebook为例,
2017年其月活跃用户达到 20亿,每小时产生 PB级数据。然
而,人们在使用在线社交网络同时也面临着严重的隐私泄露和
恶意攻击问题。因此,研究大规模社会网络隐私保护技术有着
重要的意义。针对传统社会网络隐私保护技术有许多的研究
成果,如节点
k匿名
[1]
、子图 k匿名
[2]
、数据扰乱
[3]
和推演控
制
[4]
等技术。k匿名技术即攻击者基于一定的背景知识识别
任意节点的概率不大于 1/k。现有的社会网络隐私保护模型
没有考虑节点影响力在匿名前后变化。对此,针对基于 k核的
社会网络图隐私问题进行研究,主要工作和贡献如下:
a)针对大规模社会网络图,提出一种基于 Pregel的分布式
保护节点影响力的匿名算法(
APIN),算法通过 k核衡量节点
影响力,分裂节点匿名同时保证节点的核数不变。
b)为了提高 APIN算法匿名保护强度,针对社区结构提出
保护社区中节点影响力的社会网络匿名算法(APINC),该算法
通过社区划分,在每一个社区中分裂节点匿名满足
δ
shell安
全分组,最终社会网络图匿名。
1 相关工作
为了保护社会网络中的节点隐私,研究者提出了不同的隐
私方法。基于节点聚类的匿名算法是对节点、边或两者同时聚
类成簇,文献[
5]中每个聚类所包含的节点的个数
≥
k,同一聚
类内的节点具有相同的标签,这样能够唯一识别节点的概率为
1/k。文献[1]在发布匿名图时,根据分区密度发布聚类节点
与边;近年来,基于图修改方法实现社会网络图匿名已成为研
究热点,文献[6]基于 k度匿名概念,即在图中任意顶点至少
有 k-1个相同度顶点,以抵御节点度攻击,但是破坏了网络结
构。为了提高算法运行效率,文献[7]提出一种快速 k度匿名
算法,算法能够满足匿名强度的同时提高运行速度。文献[2]
根据 HRG划分社会网络得到不同社区的子图,在子图中添加
边实现 k度匿名。为了提高匿名图的数据可用性,文献[8]基
于贪心算法计算目标节点度,并在添加最少边的情况下达到 k
第 37卷第 11期
2020年 11月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol.37No.11
Nov.2020