文摘

的数量和规模不断扩大的社交网站导致了社会网络数据的爆炸性增长。挖掘和分析社交网络数据可以带来巨大的经济价值和社会效益,但它会导致隐私泄露等问题。社会网络数据发布的研究重点是发布数据,同时保证隐私。针对社交网络数据可用性低的问题节点三角形计数出版在微分隐私,本文提出一种边缘三角形计数的隐私保护方法。首先,提出了一种基于边缘edge-removal投影算法TSER三角形计数排序,提出了获得灵敏度的上界。然后,两个边三角形计算直方图出版方法满足边缘差分隐私给出基于TSER算法。最后,实验结果表明,与现有算法相比,TSER算法可以保留更多的三角形在原始图,减少发表数据和原始数据之间的误差,并提高发布的数据可用性。

1。介绍

近年来,社交网站如新浪微博、微信、Facebook、LinkedIn和Twitter已经改变了人们在线交流的方式。人们使用社交网站交朋友,寻找就业机会,共享资源,分享生活1),等等。社交网络的大规模收集的数据已经成为一个丰富的了解基本的社会现象,如流行病学、信息传播、市场营销(2),等等。大多数社交网络数据图表的形式。这些图形数据的发布和分析有巨大的潜在的社会福利,比如提供更人性化的服务,发布官方统计数据,为机器学习(提供数据集3]。然而,攻击者将从数据推断出用户的敏感信息引起了隐私泄漏如果社交网络数据直接发表。成熟的数据挖掘技术,隐私泄露的问题变得越来越严重,和隐私保护已成为普遍关注的一个热门话题(4]。大量的研究已经为社交网络提供了隐私保护数据发布。《理发师陶德》等。5)首次提出K-anonymity保护模式,然后一系列的数据隐私保护技术出现了,比如l-diversity [6],t-closeness [7],M-invariance [8),等等。这些模型可以防止身份披露(如ID、名称、和其他标识符)但无法抗拒背景知识攻击(9]。微分隐私模型可以成功地抵抗背景知识攻击和有严格的数学定义,这是广泛应用于数据发布10,11]。

子图的分布查询社交网络数据发布是一个研究热点,包括节点和边数,三角形计数,k三角形计数、k恒星计数、度分布、节点强度分布(2]。作为一种重要的统计图的特点,三角形计算起着至关重要的作用在复杂网络分析(12,13]。它已广泛应用于角色识别垃圾邮件检测和保护网络图数据发布的焦点。

这是一个巨大的挑战来减少查询函数的灵敏度,提高可用性的数据发表在微分隐私数据发布。原始图像映射到一个新的图像敏感性较低的关键是实现和更好的利用微分隐私。截断的方法通常是用来降低微分隐私的敏感性。截断的方法通常是删除节点或边缘,项目原始图像到一个新的图阈值以下,并保留了尽可能多的信息的原始图的投影(2]。Kasiviswanathan et al。14)使用微分隐私技术首次研究图的数据。他们展示了如何估计三角形的数量满足边缘微分隐私在社交网络和如何校准子图的噪声计数。做et al。15)优化加密矩阵通过修改现有安全矩阵数据传输协议实现多方安全计算三角形。Shoaran et al。16]在社交网络和组的三角形度量定义提出了一个0知识隐私(ZKP)机制来提供隐私保护数据发布。丁等。17,18)首次提出保护隐私三角形计数问题的节点和节点使用微分隐私保护大规模图的三角形数。他们项目图一个新的图灵敏度较低的灵敏度得到上界在不同的分布。虽然投影的方法可以减少查询敏感,它会导致一个大损失的原始数据和相对较低的数据可用性。此外,为了实现节点三角形的设置的阈值计数、大量的边缘需要被删除,和他们提出的方法极大地损害了原始图结构。基于丁等,提出了一种边缘三角形计数的隐私保护方法。

三角形的主要目标计数分布出版物出版近似分布尽可能接近真实的三角形分布的原始图的情况下微分隐私。发布节点三角形计数分布的方法,大量的边缘需要删除满足节点阈值,从而导致严重的图形数据信息损失和较低的数据可用性。因此,本文提出了一种边缘三角形计数分布发布方法,可以保留更多的图像信息,提高数据可用性,当会议边缘阈值。

为了进一步减少三角形的敏感性计算出版微分隐私约束下,提出了一种新的投影方法。基于这种投影方法,两个直方图出版机制满足边缘微分隐私。本文的主要贡献可以概括如下:(1)首先,保护隐私三角形计算问题提出了边缘,和一个方法来提高数据可用性,提出了满足隐私保护。提出了一种三角形edge-removal算法(TSER)。排序根据三角形边缘计数的边缘。从边缘开始处理最大的三角形数,并去除边缘与最小的三角形数的边缘形成一个三角形的边。最后,边缘三角形数限制在一个给定的阈值。这种方法可以保留原始图像中更多的三角形,同时减少敏感性,发布数据的可用性大大提高。(2)基于TSER投影方法,两个直方图出版edge-triangle计数分布的方法在微分隐私给出:edge-triangle计数分布直方图和edge-triangle累积分布直方图 ,并证明了这两个直方图出版机制满足边缘微分隐私的定义。(3)不同的真实数据集上的实验结果表明,相对于传统方法,与节点三角形计数分布出版相比,边缘三角形计数分布出版方法基于TSER本文算法可以更好地保留原始图像的结构特点和提高出版数据的可用性。

本文的其余部分组织如下:部分2阐述了相关的工作。部分3介绍了社会网络和微分隐私保护算法的初步知识。部分4介绍了算法TSER提出并给出了两个直方图出版方法基于TSER算法。部分5进行实验验证和数据分析工具测量的算法。部分6本文总结了,期待下一个工作。

2。相关工作

微分隐私是一个隐私保护模型提出的Dwork et al。19]。通过添加随机噪声干扰的敏感信息数据隐私保护的目的是实现在保持整体的有用的信息数据20.]。基于原则的数据失真,微分隐私模型提供了严格的数学理论支持。微分隐私也可以成功地抵抗背景攻击和广泛应用于社交网络,位置隐私,推荐系统,和其他领域2]。微分隐私的主要研究问题包括输入和输出数据的性质、机制设计和参数设置。数据发布基于微分隐私大致可以分为两类:节点微分隐私(14)和边缘微分隐私(21]。

在节点微分隐私,只有一个节点是不同的两个邻居图。任何添加或删除一个节点对查询结果几乎没有影响。刘等人。22)研究了基于节点的节点强度分布微分隐私,减少敏感性通过限制重量和学位。钱等。23】提出了一种基于边缘微分隐私隐私节点强度发布方法。相比之下,黔之边缘微分隐私et al .,刘等人的节点微分隐私的方法可以提供强大的隐私保护,但它有较低的数据可用性。Zhang et al。24]针对更大的敏感性问题的节点的度分布在节点微分隐私的定义,并提出了一个edge-removal投影法SER基于程度排序。度分布的两个直方图机制下节点差分隐私给出:SER-histogram SER-cumulative直方图。吴et al。25)提出了两种不确定图的隐私保护隐私保护算法的社交网络图。不确定图是一种隐私保护方法,将确定性图转换成概率图。不确定的边缘概率分配算法基于微分隐私具有较高的隐私保护,适用于高的场景在社交网络隐私保护需求,但其数据可用性需要改善。丁等。17,18)首次提出保护隐私三角形计算节点的问题,提出新的投影算法DL和英航获得灵敏度分布在不同的上界。两个三角形计算节点的分布直方图给出了微分隐私:三角形计数分布直方图和累积分布直方图。这个投影算法降低查询的灵敏度,但数据处理造成很大损失的原始图像信息,和数据可用性相对较低。

在边缘差分隐私,只有一个边缘的区别这两个邻居图。添加或删除图中任意两个节点之间边的对查询结果的影响可以忽略不计。Kasiviswanathan et al。14]使用微分隐私技术研究图表数据首次提出使用截断方法项目原始图降低灵敏度,并展示了如何估计的三角形数量满足微分隐私在社交网络边缘。虽然这种方法可以降低敏感度,它删除许多不必要的边缘和失去很多有效信息的原始图。太阳et al。26)提出了k三角形数的组合图,首次提出了一个复合图出版方法边缘差分隐私,使出版综合图准确应对三角形计数查询任意常数k。社交网络的度分布图形,钱等。23)提出,度分布并不能完全代表节点和图形的特点。他们进一步研究了基于边缘节点强度直方图出版不同隐私,建造了一个t-bound图边缘大小的限制重量,并提出两个水桶基于序列和密度聚类方法来优化出版的精确性。

保护三角形数,研究三角形计数保护节点,而三角形计数保护边缘仍是空白。此外,节点三角形的投影算法计算导致大型原始图的信息丢失和较低的数据可用性。这是一个巨大的挑战提高出版数据的可用性,同时保证微分隐私保护。本文提出了一种新的投影方法来提高隐私保护的数据可用性三角形边的计算问题。

3所示。预备知识

3.1。社交网络

社交网络是一个虚拟应用程序平台创建和管理用户在互联网上,提供信息交流、共享、传播和新闻。社交网络为人们提供丰富的各种应用程序提供了很大的方便,如社交、学术资源共享、多媒体共享、电子支付、求职信息,等等。社交网络数据通常映射到图形结构(以无向图未加权的为例),如图1。

社交网络数据图表示 ,在哪里是节点和是优势。网络图中节点数据指的是用户或相关机构和组织,和边指用户和用户之间的交互,用户和组织,组织和组织。用户通常是相互之间的关系;一般来说,社交网络图是一个无向图。用户在社交网络几乎不可能独立存在,或多或少与外界相连。

每个元素的节点、边和网络图结构可能涉及私人信息在社交网络。社交网络的隐私信息可以分为三个部分:节点的隐私,隐私,隐私和网络结构(9]。社交网络节点的隐私包括节点存在,节点身份识别,和节点属性信息。边缘隐私主要包括边缘连接,体重,边缘和边缘属性。隐私的网络图结构通常指的是社交网络的拓扑结构的分析来获取隐私信息,如度分布、路径长度、子图结构。子图包括三角形、k里,k明星(2]。

出版社交网络数据可能导致用户隐私被罪犯和损害用户的利益。主要在社交网络上的攻击类型是背景知识攻击,推理攻击,主动攻击和被动攻击。背景知识攻击意味着攻击者已经掌握了一些网络结构或属性信息来识别攻击的目标。一个面向属性攻击将识别出目标通过节点或边的隐私属性。网络structure-oriented攻击主要包括子图攻击、节点度攻击,边缘重攻击。在社交网络,最严重的威胁是背景知识攻击,因为攻击通常掌握大量的网络图中的信息通过一些手段攻击目标对象。

微分隐私可以成功地抵抗背景知识攻击和广泛应用于社会网络的隐私保护。

3.2。微分隐私的基本知识

3.2.1之上。微分隐私

定义1。(相邻的数据集)。假设数据集和有相同的属性结构,对称的区别是什么 ; 表示数量的记录 ,如果 ,也就是说,只有一个记录之间的区别和 ,称为相邻的数据集,用吗 。
各种数据集的映射功能被定义为查询功能,和 是用来表示一组查询功能。算法流程查询的结果实现隐私保护条件,叫做隐私保护数据集的机制 。

定义2。( - - - - - -微分隐私)[19]。对于任何两个相邻数据集和 ,有一个随机算法 ;算法对所有可能的输出结果和是 。如果算法满足: 然后算法给了 - - - - - -微分隐私。在概率公关[]是由算法的随机性 ,也称为隐私被泄露的风险。代表了隐私预算(27]。从定义可以看出2,较小的ε是,算法的输出概率越接近两个相邻的数据集上,强大的隐私保护。然而,小e越大,微分隐私噪声的降低将导致数据的可用性。

3.2.2。灵敏度

微分隐私达到隐私保护的目的通过将随机噪声添加到查询结果隐藏相邻的数据集之间的差异。查询函数的灵敏度是指查询结果的最大区别在相邻的数据集,也就是说,查询结果的最大变化当只有一个记录的数据变化。

定义3。(灵敏度)28]。给定一个查询功能 , 是查询的所有输出函数在数据集 。对于任何相邻的数据集和 ,的敏感性定义如下: 的敏感性只有相关的查询类型,它决定了大量的干扰噪声。灵敏度越高,噪声越大添加和数据可用性越低。

3.2.3。噪声机制

噪声机制是主要的技术实现微分隐私保护。拉普拉斯机制(28)和指数机制(29日)通常用于实现微分隐私。拉普拉斯机制适用于数字数据的保护,和指数机制通常是适用于非数值数据的保护。

定义4。(指数机制)29日]。假设 数据集的评分功能吗D,这是用来测量输出的质量,和它的灵敏度是Δ问。如果机制米满足ε微分隐私,那么满足

定义5。(拉普拉斯机制)28]。给定一个数据集 ,有一个函数 ,和它的敏感性 。如果这一机制米满足ε微分隐私,那么它遵循以下方程: 在哪里是随机噪声和尺度参数和服从拉普拉斯分布吗 。机制表明,噪声的大小与查询的灵敏度函数f和隐私预算ε。
拉普拉斯机制是广泛应用于数字数据保护,所以本文使用拉普拉斯噪声机制。

3.3。节点微分隐私和边缘微分隐私

节点微分隐私是指任意添加或删除一个节点图中,有一个非常小的对查询结果的影响。节点的相邻图像微分隐私的定义如下:网络图和 ,如果一个节点是网络图中添加或删除得到 ,然后他们被称为邻近图。换句话说,图表和只有一个节点不同,如图2。节点微分隐私保护节点属性安全,使攻击者无法推测网络中节点的存在和拥有强大的隐私保护能力。随机删除/添加节点时,最坏的情况下,节点连接到所有剩余的节点图,和查询节点的敏感性微分隐私是相对较大。

边缘微分隐私意味着添加或删除一个边缘图中任意两个节点之间的对查询结果的影响可以忽略不计。邻居在边缘图像微分隐私的定义如下:两个网络图和 ,如果两个图形只相差k边,然后和相邻的图,在哪里 是使用最广泛的21),如图3。边缘微分隐私关注保护边缘属性隐私,如友谊、合作、贸易、查询和信任,灵敏度相对较小。

查询敏感引起的变化的一个节点图的大小成正比。对大规模网络图,节点的敏感性微分隐私往往高于边缘微分隐私,所以添加噪声干扰大,不能保证足够的数据效用。节点微分隐私可以提供强大的隐私保护,但边缘微分隐私的隐私保护已经满足了实际需要在大多数应用程序中,尤其是在大型社交网络,所以边缘微分隐私是更广泛的应用。因此,本文保护边缘三角形计数在社交网络基于边缘微分隐私。

3.4。效用指标

为了全面评估不同的三角形计数分布算法的性能,本文采用以下三个评价指标。(1)三角形留存比率 。三角形留存比率可以衡量的损失造成的社会网络图结构投影算法,在那里的总数是在原始图像和三角形代表三角形投影后的总数。一般来说,更大的价值 ,更多的三角形投影算法可以保留,保留原始图像的信息越高,算法的效果就越好。(2)l₁错误(14]。l₁误差图像的直方图分布数据之间的误差后添加噪音和原始图像数据的直方图。越小l₁错误越多,前后的直方图算法类似,和数据可用性越高。两个边缘三角形计数分布和长度为米,l₁它们之间的误差如下: 而对于边缘三角形计数小于长度的分布米,它充满了0米为了方便。(3)KS距离(30.]。KS距离是用来比较两个经验分布是否有显著差异,反映了两者之间的距离直方图。KS距离越小,越接近添加噪声后的直方图是原始的直方图,和更高的可用性数据。KS的距离是基于累积分布函数。两个三角形数分布和 ,它们之间的KS距离如下: 在哪里是累积分布函数值时,三角形指望直方图分布吗D是 。

4所示。微分隐私边缘三角形计算直方图出版

成对的友谊在社交网络的早期阶段是很常见的。随着网络的发展,用户建立更多的友谊关系,形成更多的三角关系。三角形的数量在社交网络可以测量网络是否成熟,广泛应用于信息传播,市场营销、电子商务的建议,等等。然而,出版三角形计数结果将直接导致用户隐私泄漏。在出版三角形计数数据之前,需要相应的隐私保护措施。

4.1。隐私保护的边缘三角形计数

一个简单的模型是用来简要解释边的三角形计数问题隐私保护的过程中社会网络数据发布。

给定一个无向和未加权社会网络结构,《社交网络》有10个用户节点和边缘17关系,如图4。这些图形数据的发布和分析有很大的潜在的社会效益。数据持有人公布边缘三角形数的分布直方图,如图5。柱状图的横坐标是边缘三角形数,纵坐标是边缘连接的数量x三角形。

假设有一个攻击者有很强的背景知识,他知道社交网络除了边缘的关系E₆。攻击者并不确定是否有秘密交易两个用户之间的连接E₆。一旦攻击者获得边缘三角形计数分布的直方图从互联网上,他发现一条边连接到四个三角形,和另一个优势是连接三个三角形。通过对比背景知识已经掌握了《社交网络》中,攻击者可以推断E₆必须存在。

边三角形的数量也可以代表两个用户之间的共同的朋友数量联系在一起的边缘。攻击者很容易我用户的隐私的社会边缘三角形数。因此,在发布之前需要隐私保护措施边缘三角形计数分布。微分隐私可以抵抗背景知识攻击和广泛用于数据发布。本文研究了隐私保护边缘三角形的计算基于边缘微分隐私。

4.2。提出TSER算法

本文提出了一种新的图像投影算法为了获得灵敏度上界的三角形数分布,叫做三角形那种edge-removal (TSER)。该算法可以在投影过程中保留更多的三角形来提高出版数据的可用性。所示的算法是算法1。

该算法首先计算边缘三角形的边的数量 ,记录在 ,显示和排序的边缘由大变小 。边三角形的边数大于阈值θ记录在一组 ,然后边形成的三角形是记录。在 ,每个三角形标志着边缘的最小的数边缘三角形和记录 。为 ,三角形的数量从小型到大型排序,然后用最小数量的边缘三角形删除先后到 。重复以上操作的每条边直到所有边缘三角形满足阈值,算法结束。

为了说明算法的过程1更直观地说,图6显示了两个图投影方法的例子。设置阈值θ= 2,可以看出图从原始图6(一)的边缘三角形计数和分别是3和4都超过阈值。

r是一个随机edge-removal算法。从边缘最大的边缘三角形数,r算法随机删除和以满足阈值。为边缘,r算法随机删除为了满足阈值边缘。图形处理的r算法最后保留四个三角形,如图6 (b)。

TSER算法用于本文如图6 (c)。边缘三角形项和大于阈值和记录 ,和从大到小排序根据边缘三角形数。从边缘开始预处理最大的边缘三角形数。记录边缘形成的三角形是 ,和边缘在每个三角形是最小的三角形数 。删除边和最小的边缘三角形数反过来,直到满足边缘三角形计数阈值2。更新整个图和遍历的边缘一次。重复以上操作并返回投影图 当所有边缘三角形数量满足阈值,算法结束。本文根据TSER投影算法,八个三角形可以保留。

无论投影算法,最终目标是让边缘三角形数满足给定阈值并获得灵敏度的上界。从图的实例分析6,可以看出r算法可能会导致大量的三角形删除边随机时丢失。TSER本文算法可以保留更多的三角形当会议阈值和近似原始图的最大程度上降低投影图像和原始图像之间的误差,以提高数据的可用性在微分隐私保护。

4.3。基于TSER微分隐私发布方法

TSER投影算法的基础上,本文提出了两个直方图发布方法:TSER-edge三角形计数分布直方图和TSER-edge三角形计数累积分布直方图 。

4.3.1。

边缘三角形计数分布直方图 代表的边数边三角形计数 。从定义可以看出3查询函数的灵敏度是指查询结果的最大区别在相邻的数据集,也就是说,当只有一个边缘在G的变化(删除或添加任意一条边),它的最大区别是直方图TSER_His (G)前的变化和改变后的直方图TSER_His (G)。给定查询功能 ,有多少边缘连接三角形的图 吗?根据定理1的敏感性上界出版是 。

定理1。对于任何相邻的数据集和只相差一个边缘,有:

证明。假设,不失一般性,图表 和相差只有一个优势 。在最坏的情况下,连接三角形的图 。当边被删除,三角形被删除。删除1三角形影响最多2不同边缘除外 ,所以删除三角形影响最多边缘。和带来的变化映射到每个边缘直方图是2,和带来的变化边是 。此外,本身原因1变化,所以总变化带来的删除边缘直方图是最大的 。因此,灵敏度上界出版是 。
TSER-edge三角形计数分布直方图算法所示2。

4.3.2。

的敏感性的上界发布方法 ,这仍然是非常高的。为了进一步降低灵敏度,提出了另一个发布方法。边三角形数的累积分布直方图 代表的边数边三角形计数小于或等于 。给定查询功能 ,有多少三角形连接的边缘小于或等于什么 吗?根据定理2的敏感性上界出版是 。

定理2。对于任何相邻的数据集和只相差一个边缘,有

证明。假设,不失一般性,图表 和 相差只有一个优势 。在最坏的情况下,连接三角形的图 。当边被删除,三角形被删除。当删除一个三角形,它将影响最多两个不同边缘除外 ,和删除三角形将影响最多边缘。每条边的变化累积直方图是1,和的变化边 。此外,本身原因1变化,所以累积直方图的最大总变差 当边缘的变化。它可以看到从灵敏度上界的证明的是 。
TSER-edge三角形计数累积分布直方图出版算法如算法所示3。

5。实验和分析

本节使用真正的社交网络数据集实验提出TSER投影算法,比较和分析了和直方图发布方法与以前的算法。

5.1。数据集和设置

实验使用四个真实数据集从斯坦福大学大型网络数据集收集网站(31日):(1)Facebook是一个匿名社会数据集;(2)Wiki-Vote维基百科是一个网络投票;(3)Cit-HepTh是高能物理论文的引文网络;和(4)Epinions这样who-trust-whom在线社交网络的消费者评论网站Epinions.com。会员的网站才能决定是否“信任”。在这四个数据集的数据量从小型到大型。的每个数据集的详细统计数据如表所示1。在数据集是三角形的总和;最大数量的边缘三角形计数;和是所有边缘三角形数的平均值。在这篇文章中,所有指示图预处理成无向。所有的实验都是运行在PC与AMD Ryzen 74800 h和Radeon图形CPU和64位Windows操作系统。

在这篇文章中,阈值根据参考序列被选中 (32,33),和隐私的价值预算是在0.5和1.5之间22,23]。由于拉普拉斯算子的随机噪声,为了更好地衡量算法性能,为每个算法中,我们使用100年的平均误差。实验1比较了 指数的边缘三角形计数法和节点三角形计数法(17]。实验2比较l₁错误和KS的距离 , , ,和在不同的数据集上运行。

5.2。分析实验结果

实验1。三角形留存比率 边的三角形和节点三角形发布方法。

三角形留存比率 可以衡量的损失造成的社会网络图结构投影算法。越高 ,保留原始图像信息,和更好的性能。实验结果如图所示7。

(Facebook的数据集小于512,所以它的阈值θ在实验中被设置为256)。

从实验结果可以看到在图7:(1)不同阈值的所有数据集,三角形留存比率 边缘三角形计数出版本文方法比节点三角形计数发布方法。这是因为三角形连接到节点的数量远远超过连接的边缘,为了达到阈值,节点三角形计数出版方法通常需要删除大量的边缘在投影过程中,导致大量减少图中三角形的数量,低保留原始图像的结构信息和数据可用性差。相反,当边缘三角形计算满足阈值,少边删除,保留更多的三角形。因此,边缘三角形计数分布法提出了可以更好地保留原始图像的信息。(2)对于相同的数据集,阈值越大是,三角形留存比率越高 ,原始图像的完整性更好的保证。然而,随着的增加 ,它可以看到从定理1和2上界的敏感性也将增加,和微分隐私噪音也将增加。因此,不能说就越大值是越好。在实际应用程序中,需要设置值根据数据集本身的特点和不同需求的出版数据的可用性和隐私。

实验2。评价l₁错误和KS距离 , , 和 。

文献[18)提出了一个有效的策略来减少图像数据信息的损失,被称为最好的适应(BA)。英航算法首先去除边缘最大的三角形数到满足节点阈值。是一个累积直方图出版方法基于BA。DL投影算法(17]删除链接节点的边缘,有一个更大的程度。是一个累积直方图出版方法基于DL。

l₁错误和KS距离用于全面衡量的直方图 , ,和 。L1错误和KS距离越小,差别越小的直方图微分隐私保护和原始的直方图,和更高的数据可用性。128是一种常用的中间值阈值来更好地适应大型和小型数据集。(下一个实验将讨论的影响在数据可用性)。当阈值被设置为128,效果不同的隐私预算在出版直方图如图8。

图8显示的曲线l₁错误和KS距离每个出版方法改变的价值在四个数据集。实验结果表明:(1)为不同的数据集和不同 ,的l₁错误和KS距离的两个发布的方法和摘要比小的多和 。它表明,出版方法基于摘要TSER投影更接近原始数据,明显提高了数据的可用性。(2)比较三个累积直方图 , ,和 ,的l₁错误和KS的距离都是低于和 。的原因可能是英航和DL投影算法删除太多边缘达到阈值时,失去了很多有效的原始图像中的信息,所以直方图的误差太大。三发布算法,算法效果最好。(3)比较这两个发布方法和本文提出不同的数据集和不同的实验分析表明,l₁错误和KS的距离远小于 。它可以用定理来解释1和2分布直方图的敏感性高于累积直方图,导致大量的噪音补充说,一个大的错误在直方图,和相对较低的数据可用性。所以有一个小错误,可以更好地描述原始图像的信息。(4)比较l₁错误和KS距离相同的数据集,隐私越小预算是,越大l₁错误和KS的距离,这是一致的定义2微分隐私。隐私越小预算 ,较强的隐私保护,但相应的噪声越大,直方图误差越大。在实际应用中,隐私的预算应根据安全保护设置不同的数据需求和数据可用性需求。如果发布数据需要高强度的隐私保护,隐私的预算将更小,但数据可用性相对较低。如果数据需要更好的可用性和更低的隐私保护需求,可以设置隐私预算有点大。简而言之,隐私的预算应合理设置在确保数据隐私安全的前提下。

通过上面的分析,与现有的算法相比,边缘三角形计数出版本文方法可以更好地保留原始图像信息,同时保证数据隐私和提高数据的可用性。的影响发布方法优于 , ,和 。

阈值也是一个重要的参数;的价值会影响数据的可用性。当设置为1时,不同的效果发布方法如图9。

(Facebook的数据集小于512,所以它的阈值θ在实验中被设置为256)。

图9显示的曲线l₁错误和KS距离改变的价值在每个数据集。从图可以看出:(1)在不同的数据集和不同的方面θ值,l₁错误和KS的距离本文算法都是最小的,这表明本文发布方法更接近原始数据,提高出版数据的可用性。(2)的价值有很大的差异的影响,不同类型和规模的数据集。的l₁错误和KS距离曲线的两个较小的数据集Facebook和Wiki-Vote通常是类似的趋势值的变化,而变化曲线的两个大型数据集Cit-HepTh和Epinions这样是相似的。(3)Wiki-Vote等相对较小的数据集的曲线l₁错误和KS距离增加价值增加。对于这些较小的数据集,当的价值较大,虽然可以保留了更多的原始图像信息,它还会导致更大的噪声,提高吗l₁错误和KS距离,和较低的数据可用性。因此,直方图在这种情况下的误差主要是由大的噪音。(4)在大型数据集,如Epinions这样的值l₁错误和KS距离时最大是64。如果θ值设置为很小,产生的噪音也小。然而,太小的阈值θ将导致大量的边缘被删除在图投影,这严重破坏了图结构和失去了大量的信息,导致大型出版直方图中的错误和低数据可用性。

从上面的分析,可以看出阈值对不同的发布方法产生重大影响,不同类型和规模的社交网络数据集。大的噪音会导致更大的错误在小数据集,所以一个较小的阈值可以设置为提高数据可用性。过程中大规模社会网络数据发布,如果阈值将小,大量的信息将丢失图像投影的过程。因此,一个相对较大的阈值可以设置为提高数据可用性。

基于实验1和2的分析结果,本文发布方法可以减少发表数据和原始数据之间的误差,同时保护隐私和提高数据可用性。隐私的价值预算和阈值将影响出版数据的可用性。因此,在复杂的应用程序场景中,需要设置的值和合理根据不同的隐私需求,不同类型和大小的数据集,和不同的应用场景。至关重要,全面权衡隐私保护和数据可用性和找到最好的隐私保护和数据可用性之间的平衡。

6。结论和未来的工作

隐私保护已在学术界越来越多的关注,工业和日常生活中,社会网络的隐私保护已成为一个热点话题。如何发布可用数据同时保护隐私已经成为摆在我们面前亟待解决的重大问题之一。微分隐私满足严格的数学定义和能抗拒的背景知识的攻击,是一个社会网络隐私保护的重要技术。

本文主要研究了子图在社会网络的隐私保护。首先,隐私保护边缘三角形的计算,提出了和一个edge-removal投影算法(TSER)提出了基于边缘三角形分类。然后,原始图TSER算法获得预计的上界的敏感性已发布的数据。最后,基于TSER投影算法,两个边三角形计算直方图出版方法满足边缘微分隐私。真实数据集的实验表明,与现有算法相比,TSER投影算法提出了可以保留更多的三角形信息在原始图。累计直方图发布基于TSER双重优势的方法l₁错误和KS距离,使出版直方图更接近原来的边缘三角形计数分布和提高数据可用性。由于本文只针对未加权的社交网络,下一步是关注加权社会网络的隐私保护和扩展算法加权社会网络。

数据可用性

可以获得的数据https://snap.stanford.edu/data/ socnets。

的利益冲突

作者宣称没有利益冲突。

确认

这项研究是由中国国家自然科学基金(批准号:U1836103)。