社交网络隐私保护技术最新研究进展

第３２卷第５期　计算机应用研究　Ｖ０ｌ＿３２　Ｎｏ．５　２０１５年５月　Ａｐｐｌｉｃａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ　Ｍａｖ　２０１５　社交网络隐私保护技术最新研究进展冰　马飞　，蒋建国　，李娟　（１．合肥工业大学计算机与信息学院，合肥２３０００９；２．北方民族大学计算机科学与工程学院，银川７５００２１）　摘要：针对社交网络进行研究分析的同时不破坏其中的敏感隐私信息，研究者提出了各种各样面向社交网络　的隐私保护技术。从攻击者具有的背景知识、敏感数据信息的定义、信息的有用性三方面出发对社交网络隐私　保护技术进行了深入研究，重点对基于ｋ一匿名、Ｍａｒｋｏｖ链、聚类、随机化等技术的隐私保护方案的优点与不足进　行了深入比较与分析。最后，讨论了社交网络隐私保护技术所面临的挑战并对未来的研究方向进行了展望。　关键词：社交网络；隐私保护；背景知识；　一匿名；Ｍａｒｋｏｖ链；聚类　中图分类号：ＴＰ３９３．０８　文献标志码：Ａ　文章编号：１００１－３６９５（２０１５）０５—１２９１—０７　ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１—３６９５．２０１５．０５．００３　Ｌａｔｅｓｔ　ｒｅｓｅａｒｃｈ　ｐｒｏｇｒｅｓｓ　ｏｎ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｔｅｃｈｎｏｌｏｇｙ　ｏｆ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ　ＭＡ　Ｆｅｉ　一，ＪＩＡＮＧ　Ｊｉａｎ．ｇｕｏ’，ＬＩ　Ｊｕａｎ　（１．Ｃｏｌｌｅｇｅ　ｏｆＣｏｍｐｕｔｅｒ＆Ｉｎｆｏｒｍａｔｉｏｎ，Ｈｅｆｅｉ　ＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｈｅｆｅｉ　２３０００９，Ｃｈｉｎａ；２．Ｃｏｌｌｅｇｅ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ＆Ｅｎｇｉｎｅｅｒｉｎｇ，　口ｅ　ｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｎａｔｉｏｎａｌｉｔｉｅｓ，Ｙｉｎｃｈｕａｎ　７５００２１，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｒｅｓｅａｒｃｈ　ａｎｄ　ａｎａｌｙｚｅ　ｔｈｅ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ　ｗｉｔｈｏｕｔ　ｄｅｓｔｒｏｙｉｎｇ　ｐｒｉｖａｃｙ　ｏｆ　ｓｅｎｓｉｔｉｖｅ　ｉｎｆｏｒｍａｔｉｏｎ，ｔｈｅ　ｒｅ—　ｓｅａｒｃｈｅｒｓ　ｈａｖｅ　ｐｕｔ　ｆｏｒｗａｒｄ　ａ　ｖａｒｉｅｔｙ　ｏｆ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｔｅｃｈｎｏｌｏｇｉｅｓ　ｏｆ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ．Ｆｒｏｍ　ｔｈｅ　ｔｈｒｅｅ　ａｓｐｅｃｔｓ　ｏｆ　ｂａｃｋｇｒｏｕｎｄ　ｋｎｏｗｌｅｄｇｅ　ｏｆ　ａｔｔａｃｋｅｒｓ，ｔｈｅ　ｄｅｆｉｎｉｔｉｏｎ　ｏｆ　ｓｅｎｓｉｔｉｖｅ　ｉｎｆｏｒｍａｔｉｏｎ，ｕｔｉｌｉｔｙ　ｏｆ　ｉｎｆｏｒｍａｔｉｏｎ，ｔｈｉｓ　ｐａｐｅｒ　ｓｔｕｄｉｅｄ　ｔｈｅ　ｌａｔｅｓｔ　ｐｒｉｖａｃｙ　ｐｒｅ—　ｓｅｒｖｉｎｇ　ｔｅｃｈｎｏｌｏｇｉｅｓ　ｉｎ　ｄｅｔａｉｌ．Ｅｓｐｅｃｉａｌｌｙ，ｉｔ　ｃｏｍｐａｒｅｄ　ａｎｄ　ａｎａｌｙｚｅｄ　ｔｈｅ　ｉｍｐｏｒｔａｎｔ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｔｅｃｈｎｏｌｏｇｉｅｓ　ｂａｓｅｄ　ｏｎ　ｋ－　ａｎｏｎｙｍｉｔｙ，Ｍａｒｋｏｖ　ｃｈａｉｎ，ｃｌｕｓｔｅｒｉｎｇ，ｒａｎｄｏｍｉｚａｔｉｏｎ，ａｎｄ　ＳＯ　ｏｎ，ｉｎ　ｄｅｐｔｈ．Ｆｉｎａｌｌｙ，ｉｔ　ｄｉｓｃｕｓｓｅｄ　ｔｈｅ　ｃｈａｌｌｅｎｇｅｓ　ａｎｄ　ｎｅｗ　ｒｅ－　ｓｅａｒｃｈ　ｄｉｒｅｃｔｉｏｎｓ　ｏｆ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｓｏｃｉａｌ　ｎｅｔｗｏｒｋ；ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ；ｂａｃｋｇｒｏｕｎｄ　ｋｎｏｗｌｅｄｇｅ；ｋ－ａｎｏｎｙｍｉｔｙ；Ｍａｒｋｏｖ　ｃｈａｉｎ；ｃｌｕｓｔｅｒｉｎｇ　随着社交网络的快速发展，吸引了越来越多来自于数据挖　化、聚类的隐私保护技术作了深入研究与比较。　掘、社会学、数据库等领域的专家学者对其进行深入研究与分　析。目前的研究主要集中在发掘重要的网络特性及寻找有效　１　社交网络隐私定义、背景知识、有用性　可行的分析方法两方面。社交网络中通常会包含一些敏感的　对社交网络的隐私破坏主要分成实体信息破坏、链接信息　个体属性、个体间的关系、图形结构等信息，而这些隐私信息可　破坏、属性信息破坏三类。实体信息破坏指的是社交网络中的　能会在分析研究过程中被破坏，因此，如何对社交网络进行有　效挖掘研究的同时而不破坏其隐私信息成为目前社交网络研　个体ＩＤ与节点的关联关系被揭露；链接信息破坏指的是个体　间的敏感关系被揭露；属性信息揭露指的是与节点或边关联的　究领域中一个重要的研究课题。ＰＰＤＰ（ｐｒｉｖａｃｙ—ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　敏感属性被破坏。设计针对社交网络的隐私保护技术很大一　ｐｕｂｌｉｃａｔｉｏｎ）技术已被广泛应用于数据库数据的隐私保护中。　数据库表格数据很容易通过施加通用化、压缩和随机化等操作　部分困难在于如何模型化攻击者的背景知识及量化经匿名保　来获得隐私保护，并且操作产生的影响被严格地限定在元组内　护后的网络信息损失。所以，必须结合社交网络中的隐私定　而不会扩散到其他元组。但是，对社交网络对应的图节点和图　义、攻击者背景知识及对匿名社交网络的有用性进行度量来设　形结构进行通用化或扰动操作所面临的困难性更大，因为操作　计有效的隐私保护方案。　产生的影响有可能会在图中扩散并造成信息损失，进而影响研　１．１　社交网络隐私定义　究人员对数据进一步的深入分析与挖掘。所以，如何设计有效　隐私模型化是设计隐私保护方案很重要的一步。不同的　的面向社交网络的隐私保护技术是目前信息安全与数据挖掘　隐私定义会导致不同的问题产生，从而影响隐私保护方案的设　领域的研究热点之一。　　。计。由于社交网络所包含信息的复杂性，对隐私的定义也具有　本文从攻击者背景知识模型化、社交网络中的敏感数据信　很强的个性化。目前被看做隐私的信息主要有：　息定义、信息的有用性度量、匿名技术和解匿名技术几方面出　ａ）图形特征。在对社交网络进行分析与数据挖掘时，通　发，对当前重要的社交网络隐私保护技术进行了详尽的阐述与　常要提取图形的特征来分析社交网络对应的图形结构，这些特　分析，重点对基于ｋ－ａｎｏｎｙｍｉｔｙ、Ｍａｒｋｏｖ链、图形特征保持、随机　征包括介数、中心度、路径长度、度序列、可达性等，而这些特征　收稿日期：２０１４－０８－０６；修回日期：２０１４—０９—２９　基金项目：北方民族大学科研项目（２０１３ＸＹＺ０２９，２０１４ＸＹＺ１３）　作者简介：马飞（１９７６一），男，陕西榆林人，副教授，博士研究生，主要研究方向为网络安全、云计算、社交网络分析与隐私保护（ｆｅｉｘｉａｎｇｆｌｙｉｎｇ３３＠　ｎｘｕ．ｅｄｕ．ｃｎ）；蒋建国（１９５５－），男，安徽广德人，教授，博导，主要研究方向为云计算、隐私保护、图形图像处理；李娟（１９７５一），女，宁夏银川人，副教　授，硕士，主要研究方向为云计算、社会计算、社交网络与隐私保护．　・１２９２・　计算机应用研究　第３２卷　可被看做隐私。　种针对大规模社交网络的解匿名技术，该技术完全基于网络拓　扑，并利用目标网络与辅助网络的结构相似性来进行解匿名。　Ｈａｙ等人　提出一种针对社交网络中特定目标个体或个体集　ｂ）节点存在性。目标个体是否在社交网络中存在可被看　做是该个体的隐私。　Ｃ）敏感节点标签。社交网络中的节点标签可分为敏感和　非敏感两类。当社交网络中的特定目标被定位后，与之关联的　敏感标签也被泄露。　ｄ）敏感边标签。在一些社交网络中，边上通常会被赋予　的解匿名方法，攻击者通过揭露围绕在目标节点的Ｋ－ｈｏｐ子图　来对其进行定位，并使用随机图模型和真实数据来分析存在特　别链接关系的节点隐私性。￣Ｗｏｎｄｒａｃｅｋ等人“　利用从社交网　络中获得的群成员信息作为背景知识来对目标个体进行定位，　或者缩小目标个体候选集的规模，并通过理论分析和实验测试　特定的标签，而该标签类型也可分为敏感边标签和非敏感边标　签两种。敏感边标签的值通常被看做是隐私信息。　ｅ）链接关系。节点间的边表征了节点间的关联关系，而　这种关系也可被看做是个体间的隐私。　ｆ）节点结构属性。社交网络中的节点结构属性也常被看　做隐私。　ｇ）链接权重。在具有边权重的社交网络中，边上的权重　表征了顶点间的通信代价或关系的重要程度，该权重亦可被用　户看做是敏感隐私信息。　１．２背景知识与解匿名　攻击者能否对匿名社交网络成功解匿名主要依靠两个重　要因素：攻击者所获取的外部信息（背景知识）的强度及节点　或图形间的结构相似性。攻击者用所获得的背景知识来解匿　名节点及它们之间的关系，而节点或图形结构间的相似性却可　让目标个体隐藏到特定节点集合中以抵抗解匿名。所以，如何　模型化攻击者的背景知识在设计社交网络隐私保护方案中起　到很重要的作用。　Ｚｈｏｕ等人…列举了几种背景知识，包括节点属性、目标个　体之间的链接关系、节点的度、目标个体的邻居结构、嵌入子图　及图的特征等；Ｌｉｕ等人　以目标节点的度作为背景知识来破　坏目标个体的隐私；还有其他方案　使用目标节点的邻居结　构信息作为背景知识，甚至用户对网络的浏览记录亦可作为攻　击者的背景知识。　Ｂａｃｋｓｔｒｏｍ等人　以目标个体结构信息作为背景知识来对　隐私进行破坏，并提出了两种分别称为主动攻击与被动攻击的　解匿名技术。主动攻击需要在社交网络数据发布之前，在目标　个体周围构造有效的可识别子图来对目标个体解匿名。作者　创造了一个具有七个节点且包含哈密尔顿路径的子图并嵌入　到目标个体周围对其进行解匿名。研究结论表明，针对有向图　进行子图嵌入的主动攻击较易被检测，原因在于目标个体主动　连向嵌入子图的边几乎不存在或非常少。而被动攻击则需在　图中集合一定数量的共谋节点来为解匿名目标节点提供链接　关系信息。被动攻击虽然不需要事先进行子图嵌入，但只能解　匿名很少的目标个体。两种攻击方案都涉及到要在目标节点　周围创建或寻找Ｏ（１ｏｇＮ）个节点。Ｚｏｕ等人　也采用嵌入的　子图作为攻击者的背景知识。　利用个体的属性信息来进行解匿名已被广泛地应用于数　据库领域，而Ｙｉｎｇ等人　重点研究了利用节点属性和节点结　构信息作为背景知识来破坏具有多种属性的节点及多种不同　类型链接关系的复杂图中目标节点与链接关系的隐私。文献　［９—１１］考察了针对各种复杂网络，为抵抗各种复杂背景知识　而设计的隐私保护技术。Ｚｈｅｌｅｖａ和Ｌｉｕ等人　川研究了模型　化各种类型的背景知识及量化了因施加匿名操作而对所发布　的匿名社交网络带来的影响。Ｎａｒａｙａｎａｎ等人　成功提出一　对方法的有效性进行了评估。Ｃｏｒｄｅｌｉａ等人¨　提出ＶＦ算法　来对以图结构为背景知识的目标个体进行精确子图匹配或子　图同构判定。该算法与著名的乌尔曼回溯算法¨　相比具有更　低的复杂度。Ｔｉａｎ等人　设计了一种称为ＴＡＬＥ的图匹配算　法，该算法使用在混合索引结构中合并图的结构信息的新颖索　引方法来进行匹配。Ｚｈｏｕ等人　采用了称为１．ｎｅｉｇｈｂｏｒ—ｇｒａｐｈ　的攻击方案，该方案的实质就是使用最小深度优先搜索算法来　进行子图匹配。在Ｔｈｏｍｐｓｏｎ等人　以目标个体的度及与其　在／－ｈｏｐ距离之内的所有邻居的度被作为攻击者的背景知识来　进行解匿名。其他采用图形结构作为背景知识的解匿名方案　还包括基于图的随机游走算法　。。、ＥＭ算法　、ＳＶＤ算法　１］　以及基于编辑距离的近似图匹配算法等　。而这些算法由于　基本都涉及到复杂的矩阵与概率计算，都不适合于大规模社交　网络。　１．３信息损失与有用性　发布社交网络数据的重要目标是允许研究者对其进行深　入分析，不同的分析任务希望社交网络保持不同的有用性，但　是社交网络经过匿名保护后，通常会带来一定的信息损失，而　不同的信息损失将不同程度地降低社交网络数据的有用性，所　以必须在隐私保护与有用性的矛盾之间进行平衡。社交网络　数据的有用性主要考虑以下三方面：　ａ）图形拓扑属性。研究社交网络的重要目标之一是分析与　社交网络对应的网络图形属性。为了理解和利用图形信息，研　究人员利用各种技术手段从不同角度来揭示图形的结构及特　征　Ｊ。图的特征包括度序列、度分布、平均最短路径、聚类系数　等，一些文献［２，３，５，２４，２５］对这些杼陛进行了详尽的叙述。　ｂ）图的谱特征。图谱通常被定义为图的邻接矩阵或　Ｌａｐｌａｃｉａｎ矩阵及其他导出矩阵的特征值构成的集合。图谱与　图的许多特性具有非常紧密的关系，而且能对很多网络特性提　供全局性描述。拍Ｊ。在一些文献［２４，２５］中用是否保持图谱特　征来评价匿名随机图的有用性。　Ｃ）聚合网络查询。指计算满足特定查询条件的一些路径　或子图。研究者对匿名社交网络进行聚合网络查询返回结果　准确性的判定以及图有用性保持的度量进行了研究　’　”　。　对于数据库表中的记录，每条记录通常被假设为的，则可　使用对每条记录施加匿名操作而引起的信息损失之和来度量　整个匿名数据库表的损失。对于社交网络，不但要考虑图形结　构的改变引起的信息损失，同时也要考虑节点属性的变化带来　的信息损失。Ｚｏｕ等人　使用匿名前后对图进行修改的边数　来量化图形结构改变带来的信息损失，对原始图改变越小，带　来的信息损失越少。　由于社交网络的复杂性，在设计隐私保护方案时要综合考　虑隐私定义、背景知识及信息有用性三个方面，而它们的不同　第５期　马　飞，等：社交网络隐私保护技术最新研究进展　・１２９３・　组合会给设计隐私保护方案带来非常大的困难。　Ｚｏｕ等人　提出一种称为ｋ－ｍａｔｃｈ的算法使图形满足ｋ—　ａｕｔｏｍｏｒｐｈｉｓｍ性质以抵抗结构攻击，并对ｋ－ｍａｔｃｈ算法进行扩　展用来处理动态网络匿名发布问题。　３）ｋ－ｄｅｇｒｅｅ　ａｎｏｎｙｍｉｔｙ　２重要的社交网络隐私保护技术　２．１朴素匿名隐私保护技术　最简单但安全性也最低的隐私保护方法称之为ｎａ＇／ｖｅ　ａｎｏ—　Ｌｉｕ等人　指出实际社交网络中的度序列分布都具有比　较高的非均衡性，易让攻击者利用目标个体度的信息来进行隐　私破坏。为了解决该问题，研究者把ｋ－ａｎｏｎｙｍｉｔｙ模型应用到　关于度的隐私保护中。　ｎｙｍｉｚａｔｉｏｎ（朴素匿名）。数据发布者用随机ＩＤ来代替节点的　真实ＩＤ，而攻击者希望找到具有真实ＩＤ的原始Ｇ与具有随机　ＩＤ的匿名图Ｇｎ　之间的节点映射关系，但由于映射的随机性，　Ｇ　。中节点映射到Ｇ中任何节点的概率相等。朴素匿名隐私的　若图Ｇ＝（　，Ｅ）被称之为ｋ－ｄｅｇｒｅｅ　ａｎｏｎｙｍｉｔｙ，当且仅当Ｖｕ∈　优点是最大程度地保持了图的有用性，但无法有效保护图中的　隐私信息，攻击者可以利用目标节点的一些结构信息来解匿　名，所以，必须要提出更加高效与安全的隐私保护模型。　２．２基于ｋ－ａｎｏｎｙｍｉｔｙ模型的隐私保护技术　在数据库领域中比较著名的ＰＰＤＰ模型主要包括ｋ－ａｎｏ－　ｎｙｍｉｔｙ［　’　２９］、／－ｄｉｖｅｍｉｔｙ［∞　和￡一ｃｌｏｓｅｎｅｓｓ［３１，３２］以及相应的变体　（Ｏ／，ｊ｝）．ａｎｏｎｙｍｉｔｙ、（Ｃ，ｚ）．ｄｉｖｅｒｓｉｔｙ等，这些模型都已被成功借　鉴到社交网络隐私保护中。以下几种隐私保护技术就是借鉴　了ｋ－ａｎｏｎｙｍｉｔｙ模型的思想。　Ｉ）ｋ－ｃａｎｄｉｄａｔｅ　ａｎｏｎｙｍｉｔｙ　对节点ｘ进行结构查询Ｑ，若满足至少存在Ｋ一１个其他　在图中的节点与之匹配的条件，即ｆ　ｃａｎｄ（　）ｆ≥ｋ，则称该节点　满足ｋ－ｃａｎｄｉｄａｔｅ　ａｎｏｎｙｍｉｔｙ，此处　ｃａｎｄ（　）：｛Ｙ∈ＶＩＱ（ｙ）＝Ｑ（　）｝　（１）　若图形关于查询Ｑ满足ｋ－ｃａｎｄｉｄａｔｅ　ａｎｏｎｙｍｉｔｙ，当且仅当　所有节点关于查询Ｑ满足该定义。该定义意味着节点Ｋ在原　始图中都至少有Ｋ一１个候选节点，且这些候选节点是均匀概　率分布。Ｈａｙ等人　使用边随机修改技术来满足ｋ－ｃａｎｄｉｄａｔｅ　ａｎｏｎｙｍｉｔｙ。Ｈａｙ等人　提出了一种通用化技术，把满足特定条　件的节点与边划分到相应的“超点”与“超边”，以此来满足　－　ｃａｎｄｉｄａｔｅ　ａｎｏｎｙｍｉｔｙ条件。其他一些基于ｋ－ｃａｎｄｉｄａｔｅ　ａｎｏｎｙｍｉｔｙ　模型的解匿名攻击的方法也被先后提出，这些方法不同于以结　构信息作为背景知识的方法，　ｕ等人　假设攻击者仅仅知道　目标个体的节点度；Ｚｈｏｕ等人　假定已知目标节点直接邻居　的一个明确子图结构。　２）ｋ－ａｕｔｏｍｏｒｐｈｉｓｍ　ａｎｏｎｙｍｉｔｙ　Ｚｏｕ等人　综合考查目标个体周围所有可能的结构信息，　提出一种叫做ｋ－ａｕｔｏｍｏｒｐｈｉｓｍ　ａｎｏｎｙｍｉｔｙ的技术来抵抗任何以　图结构为背景知识的解匿名攻击以保证隐私不被破坏。如果　所发布的图Ｇ满足ｋ－ａｕｔｏｍｏｒｐｈｉｓｍ　ａｎｏｎｙｍｉｔｙ，则当攻击者尝试　通过“的子图来解匿名目标个体　时，将会在Ｇ中至少得到　种不同的子图来匹配其进行的子图查询，而　值越高，则成功　解匿名的概率越低。　Ｈａｙ等人　提出了等价自同构的概念，即对图中的节点进　行划分，每个划分块中的节点的结构是一致的。当划分块中的　节点数比较大时，攻击者将无法有效利用结构相似性背景知识　来对节点进行解匿名，反之，则可结合其他辅助信息来对节点　进行解匿名。Ｚｏｕ等人　采用更加通用化的假设：攻击者已知　与目标个体　关联的任何子图，若子图能够以很高的概率在　匿名网络中被识别，则　就会以很高的概率被定位。作者的　目标是构造一个图Ｇ　，Ｇ　中至少包含Ｋ一１个子图与　同构　（ＸｃＧ）。　，在　中至少有　一１个其他节点与“有相同的度。Ｌｉｕ等　人　研究了如何对图的结构进行一系列的边删除或添加操作　来构造一个满足ｋ－ｄｅｇｒｅｅ　ａｎｏｎｙｍｉｔｙ的图，同时要求对边的修　改尽量少以保持图的有用性。ｋ－ｄｅｇｒｅｅ　ａｎｏｎｙｍｉｔｙ的优点是能　够阻止攻击者利用特定用户的社会关系数量这一先验知识来　对个体进行定位。Ｌｉｕ等人　所提出的算法如下：　ａ）从原始图Ｇ。＝（　，Ｅ　）的度序列ｄ　开始，构造一个满　足ｋ－ａｎｏｎｙｍｉｔｙ的度序列ｄ　及一个距离　，要求ｄ６与ｄ。的距　离，即ｌ一范数最小化。　ｂ）构造一个新的Ｇ　：（　，　），满足Ｇ　的度序列等于ｄ　，　＝　，并且Ｅ　ｎＥ６＝Ｅｏ或　ｎ　一　。　第ａ）步可以用具有线性时间的动态规划算法来解决，第　ｂ）步可以通过基于已知度序列而进行的一系列图构造算法来　实现。实验结果显示他们所提出的算法能够有效地保持图形　结构的有用性并满足ｋ－ｄｅｇｒｅｅ　ａｎｏｎｙｍｉｔｙ。　在一些关于图形理论的文献［３３，３４］中，对实现具有约束　的度序列的图形构造问题进行了广泛研究。　４）ｋ－ｎｅｉｇｈｂｏｒｈｏｏｄ　ａｎｏｎｙｍｉｔｙ　若节点Ｕ被称之为ｋ．ｎ，ｅｉｇｈｂｏｒｈｏｏｄ　ａｎｏｎｙｍｉｔｙ，当且仅当至　少存在ｋ一１个其他节点　．－，　一　∈Ｖ，这些节点通过直接邻　居所构造的子图与　的直接邻居子图是同构的。而图Ｇ被称　之为ｋ－ｎｅｉｇｈｂｏｒｈｏｏｄ　ａｎｏｎｙｍｉｔｙ，当且仅当图中所有的节点都满　足ｋ－ｎｅｉｇｈｂｏｒｈｏｏｄ　ａｎｏｎｙｍｉｔｙ条件。该定义可以把目标顶点　的直接邻居扩展到　的ｄ步邻居，即ｄ－ｎｅｉｇｈｂｏｒｓ，其中ｄ＞１。　即给定一个图Ｇ＝（　，　），构造一个新图Ｇ　＝（　，Ｅ　）满足如　下性质：（ａ）Ｇｆ满足　一ｎｅｉｇｈｂｏｒｈｏｏｄ　ａｎｏｎｙｍｉｔｙ；（ｂ）Ｖ＝　；（Ｃ）　Ｅ　ｎ　＝层；（ｄ）Ｇ　应尽可能满足聚合网络查询。构造满足前三　个条件的ｋ－ｎｅｉｇｈｂｏｒｈｏｏｄ　ａｎｏｎｙｍｉｔｙ图形被证明是ＮＰ难问题　Ｚｈｏｕ等人　针对攻击者具有与目标节点直接邻接的子图　结构的背景知识，提出了一种贪婪修改算法来通用化节点标签　及对边进行插入操作，该算法直到目标节点至少与其他一　一１　个节点的邻居结构不可区分为止。所提出的算法主要有两个　步骤：（ａ）用邻接成员编码技术提取和表示网络中所有节点的　邻居；（ｂ）划分各节点进入相应的群，然后对相同群中的各节　点进行匿名操作，直到所有节点都满足ｋ－ｎｅｉｇｈｂｏｒｈｏｏｄ　ａｎｏｎｖ—　ｍｉｔｙ为止。该启发式算法从具有较高节点度值的节点开始，原　因是高度值节点更易受到结构攻击　该算法非常有利于比较　不同节点问邻居结构的差异性，且可以进行结构间的同构测　试。作者利用聚合网络查询的反馈结果来度量匿名社交网络　数据的有用性。　由于采用ｋ－ａｎｏｎｙｍｉｔｙ模型对原始图施加最小结构改变来　进行隐私保护是一个ＮＰ难问题，对社交网络进行匿名时需要　・１２９４・　计算机应用研究　第３２卷　在网络结构和数据隐私之间找到平衡点。　２．３基于随机化的隐私保护技术　除了ｋ－ａｎｏｎｙｍｉｔｙ方法，随机化是另一种被广泛采纳的隐　私保护策略。添加噪声的随机化方法已经被很好地应用于针　为了保持图的有用性，数据拥有者希望所发布的图形中一　些特别的特性保持在一个精确的范围内。Ｙｉｎｇ等人心　假设所　有满足度序列ｄ和特征约束ｓ的图形构成了一个图形空间　Ｇ　。从原始图开始，一系列的转换形成一个基于图形空间　的Ｍａｒｋｏｖ链，Ｙｉｎｇ等人所提出的算法能够以相等概率产生在　Ｇ女中的任何图。Ｈａｎｈｉｊａｒｖｉ等人　也提出了一种以非常高的　对数值型数据的隐私保护数据挖掘中。对于社交网络而言，以　下两种基于边随机化策略被普遍采用。　ａ）Ｒａｎｄ　ａｄｄ／ｄｅｌ。随机删除Ｊｊ｝条真实存在的边，随机添加　．ｊ｝条虚假的边，经修改后边的总数与原始图保持一致。　ｂ）Ｒａｎｄ　ｓ￣ｔｃｈ。随机转换一对现存的边（ｔ，ｗ）和（ｕ，　）　概率产生一个与原始图在图特性上非常接近的图生成算法。　通常增加特征约束条件将会减小图空间的大小，随之也会增加　隐私破坏的危险。Ｙｉｎｇ等人研究了如何利用所发布的图及特　征约束来破坏链接隐私，攻击者利用图形空间Ｇ　来计算某种　（要求边（ｔ，　）和（“，Ｗ）在图ｃ中不存在）变为（ｔ，　）和（　，Ｗ），　重复　次类似过程。随机化的过程与随机化参数　随着发布　链接存在的后验概率，比如，若在图形空间　中的大部分图都　的图形也被发布。该策略最大的优点是可保持每一个节点的　度。边随机化过程可看做是一种添加噪声形成扰动的过程，经　过施加随机化操作，随机化图与原始图是不同的，于是节点实　体及节点间的敏感隐私关系将被保护。　“ｕ等人　提出了两种针对具有边权重的敏感边隐私保　护技术：高斯随机化方案和贪婪扰动方案。这两种方案对于实　际网络而言其计算复杂性太高，并且没有考虑到具有边权重网　络的动态性本质这一问题。　随机化方法能有效对抗基于概率的解匿名攻击，但不能保　证随机化图直接满足ｋ－ｎａｏｎｙｍｉｔｙ条件。随机化方法的一个重　要优点是施加随机化操作的图可以很好地重构图特性，但重构　图形特征的方法会根据不同的随机化过程而不同，Ｌｉｕ和Ｈａｙ　等人　在其研究文献中有详细的论述。目前的边随机化技　术的主要缺点是有可能会改变图形中的某些具体特性，如最短　距离、节点可达性等。　２．４具有图谱特征保持的隐私保护技术　边随机化方法显著影响所发布的随机化图的可用性。为　保持其可用性，原始图的一些聚合特性应基本保持不变，或者　一些重要的图特性能够被从随机图中重构。然而，正如Ｙｉｎｇ　等人　的研究结果显示，由于随机化操作而使图的许多结构　特征被破坏，所以特征保留策略或者通用化策略的复杂性比随　机化策略更高。　图的谱矩阵与图的一些重要拓扑特征有紧密关系，如图的　直径、聚类系数、路径长度以及图的随机性等　。Ｙｉｎｇ等人提　出的一种能够保持图谱特征的随机化策略，其主要目标是在随　机化过程中保持图的两种重要特征值：邻接矩阵的最大特征值　和Ｌａｐｌａｃｉａｎ矩阵的第二小特征值。作者的研究显示：纯粹的　随机化技术倾向于把特征值向一个方向移动，并且随机化后的　特征值与原始图明显不同。针对该问题，作者提出了两种分别　叫做Ｓｐｃｔｒ　ａｄｄ／ｄｅｌ与Ｓｐｃｔｒ　ｓｗｉｔｃｈ的算法，算法目标是希望在　随机化过程中，新图与原始图的特征值差异性不可过大。经实　验评估显示，即使施加随机化程度非常高的操作，新图的许多　拓扑特性与原始图都非常接近。一些文献［２５，３７］中也分别　提出了几种随机转换技术，这些技术也能够保持实际社交网络　中的度序列及其他重要特性。　２．５基于Ｍａ￣ｏｖ链的特征保持隐私保护技术　图的度序列和拓扑特性是研究人员考察社交网络特性的　重要研究内容，所以，如果匿名图能够保持原始图的度序列和　某种（些）拓扑特征，则说明所采用的隐私保护方案能很好地　保持图的有用性，这对研究工作是非常有利的。　具有链接（ａ，ｂ），则原始图也有很大的可能性具有链接（ａ，ｂ），　因此攻击者关于链接（ａ，６）的后验概率可以通过下式计算：　１　Ｐ［Ｇ（Ⅱ，６）＝１ＩＧ女］＝　Ｇ　（。，６）　（２）　０ｔｒｄｓ　０　６ｔ　ｔ－ｄｚ　当已知度序列ｄ和特征约束Ｓ，攻击者从发布图的Ｍａｒｋｏｖ　链开始，产生．７、，个样本　∈Ｇ　（ｔ：１，２，…，Ⅳ），其满足基于图　１　Ｎ　形空间　的均匀分布，用公式专∑ＧｔＶ　ｔ　１　（ｏ，ｂ）来估计Ｐ［Ｇ（ｏ，ｂ）＝　１　Ｊ　］的值。攻击者把具有最高后验置信度的链接看做是候　选链接。该攻击模型能够工作的原因在于Ｍａｒｋｏｖ链的收敛并　不依赖于初始点。经实验结果显示，一些特征约束能够显著提　高与扩大攻击者的攻击精度和范围。　２．６基于聚类的隐私保护技术　为了进行隐私保护，既可使用ｋ－ａｎｏｎｙｍｉｔｙ，又可使用添加　边和删除边的随机化方法来修改图结构，然后对匿名图进行发　布。不同于以上两种方法，聚类技术是把一些特定节点与边归　于相应的集合，这些集合分别称之为超点和超边，个体的细节　将被隐藏在相应的集合中，这类聚类方法已被很好地应用于隐　私保护数据库数据中。对于社交网络，经聚类隐私保护后仍可　利用聚类后的图形特征来考察原始图的宏观特性。　１）顶点聚类隐私保护方法　Ｈａｙ等人　考察了一种节点和边都无标签的图模型，并针　对该模型提出一种利用图的结构信息，如目标顶点的完全或部　分邻居结构，及与ｈｕｂ节点的连接性等作为背景知识的节点解　匿名技术。攻击者对图施加诸如节点细化查询、子图查询和　ｈｕｂ指纹查询等解匿名攻击，Ｈａｙ等人针对以上攻击提出了一　种顶点聚类匿名技术。该技术利用图形结构的相似性原理，通　过对顶点及其结构施加变换而使顶点间的结构具有很高的相　似性，这样可把顶点间的结构差异性隐藏在等价类中，而社交　网络研究者仍可以对经过匿名操作后所发布的社交网络图进　行宏观分析。　　‘Ｔｈｏｍｐｓｏｎ等人　提出了两种新颖的针对元向图的节点　聚类算法来对目标节点进行隐私保护：有界Ｔ一均值聚类算法　和集合分割聚类算法。算法按照网络中节点相似性原则对节　点进行聚类，并利用Ｎｅｔｆｌｉｘ奖金数据集来验证其算法的有效　性。所提算法不但可以应用于社交网络，亦可应用到普通的数　据聚类中。　２）边聚类隐私保护方法　Ｚｈｅｌｅｖａ等人　研究了具有多类型边、单一类型顶点的社　交网络匿名问题。在所提出的模型中，假定在众多类型的边　中，某些边的类型是敏感的，需要被保护，而隐私破坏的程度与　第５期　马　飞，等：社交网络隐私保护技术最新研究进展　。１２９５・　被解匿名的敏感边的条数成正比。作者利用非敏感边对敏感　边的存在性提供预测信息这一条件用Ｎｏｉｓｙ—ｏｒ模型　副来对敏　感边进行预测。该模型中，假定每条非敏感边ｅ　都有一个噪　声参数Ａ　，每条　对敏感边的存在产生的影响互相。Ａ。　被称为泄露参数，它主要是度量其他隐含因素对敏感边存在的　概率影响。根据Ｎｏｉｓｙ　ｏｒ模型，敏感边存在概率用下式计算：　Ｐ（ｅ　＝１）＝Ｐ（ｅ；＝１ｆｅ　一，ｅ　）＝１一　（１一Ａ＾）　（３）　定义为第一种类型节点，所有从属组织定义为第二种类型的节　点，用户与从属组织之间的关系看做是隐私。他们提出二类通　用化技术来保护链接隐私。第一种技术称之为ｕｎｉｆｏｒｍ　ｌｉｓｔ，该　技术与Ｃｏｒｒ￣ｏｄｅ等人采用的匿名方法（　，ｚ）一ｇｒｏｕｐｉｎｇｓ　很相　似，他们通过创造“安全群”来抵抗一些常见的攻击，并且这些　“群”或“列”能够很好地保持原始图的基本特性。第二种技术　称为ｐａｒｔｉｔｉｏｎｉｎｇ　ａｐｐｒｏａｃｈ，作者采用能否对匿名图进行精确的　针对敏感边进行预测的攻击，作者提出了节点合并及边删　结构与特征分析作为有用性的度量标准。　Ｙｕａｎ等人　副首次提出了社交网络中部分节点敏感信息　除方案来进行应对，其中对边采用两种删除策略：ａ）仅移除敏　感边，而保留所有的非敏感边；ｂ）移除部分非敏感边，移除的　原则是当非敏感边有助于让攻击者利用其对敏感边的存在性　进行有效预测时，这类非敏感边要首先被删除。为了模型化图　形数据的有用性，对必须要删除的边进行计数，删除得越少，数　据的有用性越高。类似Ｎｏｉｓｙ—ｏｒ模型的概率预测方法还有　Ｂａｙｅｓｉａｎ网络及Ｍａｒｋｏｖ网络等。　３）顶点和边聚类隐私保护方法　Ｃａｍｐａｎ等人　把社交网络模型化为无向图，图中的每个　节点具有若干属性标签，边上无标签。不同的属性被分为三　类：ａ）ＩＤ属性，这类能唯一定位目标节点的属性应在社交网络　发布之前被移除；ｂ）ＱＩ属性，攻击者可以把该属性与背景知识　结合起来对目标节点进行解匿名；Ｃ）敏感属性，被定义为隐私　信息。Ｃａｍｐａｎ他们也是把数据库隐私保护方法中较成熟的ｋ—　ａｎｏｎｙｍｉｔｙ模型应用到社交网络的隐私保护中，在网络中，具有　相同特性的顶点的个数必须大于等于　；要求匿名方法对网络　中顶点的属性及结构改变尽可能地小。匿名顶点属性采用ｋ—　ａｎｏｎｙｍｉｔｙ的通用化方法，而边匿名方法则采用边通用化方法，　该方法类似于Ｚｈｅｌｅｖａ等人　所采用的方法。两者的显著不　同在于，Ｃａｍｐａｎ等人－３　的方法既考虑了通用化过程中的信息　损失，也考虑了结构损失，与Ｚｈｅｌｅｖａ等人所采用的方法类似，　他们在匿名过程中对顶点进行聚类划分，而为了匿名边，在相　同聚类中的顶点被聚集为一个超点，敏感的顶点属性与边都被　隐藏在超点中。对于图的可用性而言，Ｃａｍｐａｎ等人主要考察　通用化过程引起的结构改变对信息造成的损失。　４）顶点属性映射聚类隐私保护方法　设Ｇ＝（Ｖ，　，Ｅ）为二分图，ｌ　ｆ与ｆ　ｌ为两个不同类型的　顶点集，仅有不同类型节点之间才存在关联。在一些应用中，　实体及实体间的关系可被模型化为二分图，如Ｎｅ￣ｉｘ奖金数　据集　加　就可被看做为巨大而松散的二分图　，而二分图中的　边通常被看做隐私。　Ｃｏｒｍｏｄｅ等人　着重对二分图的匿名进行了研究，他们把　一种特别类型的网络数据模型化成为一个二分图。两类实体，　不同类型节点之间才存在关联性且被看做是隐私，且必须被保　护，而实体中的一些特性可被公开。Ｃｏｒｍｏｄｅ等人采用的匿名　方法能够通过屏蔽从实体到节点的映射而精确地保持图形结　构，而无须屏蔽或者改变图形结构本身。实验结果显示，对匿　名后的图进行基于图形结构的研究分析都是正确的。　５）其他重要的解匿名及隐私保护技术　Ｋｏｒｏｌｏｖａ等人　借鉴数据库隐私保护中的（８，　一ｄｉｆｆｅｒｅｎ．　ｔｉａｌ模型来对社交网络进行隐私保护。Ｂｈａｇａｔ等人　考察了针　对社交与从属关系网络这类复杂交互图的敏感链接关系揭露　问题。他们把社交与从属关系网络看做是二分图，所有的用户　允许被发布，部分节点的隐私信息不允许发布的子集匿名概　念，并具体研究了针对有标签网络及二分图进行如何添加最少　的边使其满足　标签序列子集匿名及　节点序列子集匿名的　问题。Ｆａｒｄ等人　重点考察了针对有向图的链接隐私揭露问　题，提出一种称为邻居随机化的结构感知随机化模型，经理论　与实验证明，所提算法在隐私保护敏感边的同时能够很好地保　持图的有用性。Ｗａｎｇ等人　提出了一种称为１　一邻居攻击　的针对经　－匿名隐私保护的社交网络攻击方案。方案假定攻　击者知道目标个体一跳范围内的所有邻居的节点度值以及“１一　邻居：’图的结构。利用这两个背景知识，攻击者能以超过１／ｋ　的概率来识别经　匿名保护的目标个体。为了抵抗该攻击，作　者针对外源性的社交网络定义了一个称之为无区别概率的关　键隐私属性，并且提出一种启发式的无辨别群匿名方案（ＨＩ—　ＧＡ）来产生出满足关键隐私属性的社交网络。实验结果显示，　经匿名的社交网络仍可以比较高的概率满足聚合查询的要求。　该文献将隐私保护、社交网络及云架构结合起来进行综合　研究。　３未来发展方向与面临问题　当前尽管提出了诸如基于ｋ－ａｎｏｎｙｍｉｔｙ、Ｍａｒｋｏｖ链、聚类等　思想的社交网络隐私保护技术，但并没有深入探讨与分析这些　技术应用的基本条件是什么，也没有深入细化和量化施加这些　技术后对社交网络造成的信息损失，所以，对这部分内容需要　进行深入研究与分析。需要设计新的实体匿名模型，因为现有　的技术主要是基于　一匿名及其变体。需要设计有效的针对敏　感链接关系隐私保护的图修饰算法，现在的随机化修饰算法由　于对图形结构的改变较大而不能很好地保持图的有用性。　对匿名社交网络进行解匿名技术研究目前主要集中在如　何用最少的辅助信息来进行最大化解匿名，甚至只用已发布匿　名社交网络的部分图形结构信息未完成解匿名操作，而这将重　点涉及到图形结构的匹配问题，该问题已被证明是ＮＰ难的。　目前常见的利用图形结构进行解匿名的算法通常都需从事先　插入社交网络中的种子节点出发来进行结构匹配，当社交网络　规模庞大，其对应的图形结构亦很复杂，用这种方法在进行近　似图形匹配将很难在有效时间完成。所以，如何设计面向大模　型复杂网络的隐私保护模型及解匿名技术是当前社交网络隐　私保护领域面临的一个重要难题。　与利用图形匹配来进行解匿名算法设计相反，研究者利用　扰动来改变图形结构以降低或阻止图匹配解匿名的可能性，并　且希望保持图形结构宏观特性以便社交网络研究人员对其进　行挖掘与分析。在文献［４５—４８］中虽然已利用差分隐私技术　对这方面问题进行了一定应用研究，但仍处于不成熟阶段，有　・１２９６・　计算机应用研究　第３２卷　必要对其进行深入分析。　现有的许多隐私保护及解匿名技术应用于小规模社交网　络时比较有效，但当社交网络随时间不断演化，其规模变得非　常庞大时，原有技术将因算法复杂度过高而不能很好地工作。　所以，如何对现有隐私保护与解匿名技术进行优化来应对社交　网络规模不断扩大的问题也是需要进一步研究的课题。　目前的隐私保护技术主要是针对无向图，在特定情况下，　社交网络中也需要研究实体节点关系的方向性问题。所以。需　要针对有向图的链接隐私保护技术进行研究，而这一部分的研　ｒａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｎｅｔｗｏｒｋ　ｐｕｂｌｉｃａｔｉｏｎ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　３５ｔｈ　Ｉｎｔｅｍａ—　ｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｖｅｒｙ　Ｌａｒｇｅ　Ｄａｔａ　Ｂａｓｅ．　２００９：９４６—９５７．　［８］ＹＩＮＧ　Ｘｉａｏ—ｗｅｉ，ｗｕ　Ｘｉｎ—ｔａｏ．Ｏｎ　ｌｉｎｋ　ｐｒｉｖａｃｙ　ｉｎ　ｒａｎｄｏｍｉｚｉｎｇ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ［ｃ］／／Ａｄｖａｎｃｅｓ　ｉｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ．　Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００９：２８－３９．　［９］ＢＨＡＧＡＴ　Ｓ，ＣＯＲＭＯＤＥ　Ｇ，ＫＲＩＳＨＮＡＭＵＲＴＨＹ　Ｂ，ｅｔ　ａ１．Ｃｌａｓｓ—　ｂａｓｅｄ　ｇｒａｐｈ　ａｎｏｎｙｍｉｚａｔｉｏｎ　ｆｏｒ　ｓｏｃｉｌａ　ｎｅｔｗｏｒｋ　ｄａｔａ［Ｊ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＶＬＤＢ　Ｅｎｄｏｗｍｅｎｔ，２００９，２（１）：７６６—７７７．　［１０］ＣＡＭＰＡＮ　Ａ，ＴＲＵＴＡ　Ｔ　Ｍ．Ａ　ｃｌｕｓｔｅｒｉｎｇ　ａｐｐｒｏａｃｈ　ｆｏｒ　ｄａｔａ　ａｎｄ　ｓｔｒｕｃ．　ｔｕｒａｌ　ａｎｏｎｙｍｉｔｙ　ｉｎ　ｓｏｃｉｌａ　ｎｅｔｗｏｒｋｓ［ｃ］／／Ｐｒｏｃ　ｏｆＰｒｉｖａｃｙ，Ｓｅｃｕｒｉｔｙ，ａｎｄ　Ｔｒｕｓｔ　ｉｎ　ＫＤＤ　Ｗｏｒｋｓｈｏｐ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００８：５６—７０．　究工作开展得较少。　目前在设计隐私保护技术时主要是针对特定的攻击背景　知识，而随着攻击者具备的背景知识越来越丰富，如何设计综　［１　１］ＣＯＲＭＯＤＥ　Ｇ，ＳＲＩＶＡＳＴＡＶＡ　Ｄ，Ｙｕ　Ｔｉｎｇ，ｅｔ　ａ１．Ａｎｏｎｙｍｉｚｉｎｇ　ｂｉ—　ｐａｒｔｉｔｅ　ｇｒａｐｈ　ｄａｔａ　ｕｓｉｎｇ　ｓａｆｅ　ｒｇｏｕｐｉｎｇｓ［Ｊ］．ＶＬＤＢ　Ｊｏｕｒｎａｌ，２０１０，１９　（１）：１１５—１３９．　合的、有效的、可扩展的隐私保护技术来保护实体、链接和属性　隐私等敏感信息将面临越来越大的挑战。现有的研究主要是　针对静态社交网络，较少考虑社交网络的动态性，而许多关于　演化动态社交网络的应用需要周期性地发布来支持对其进行　动态分析。当攻击者收集多次发布的静态社交网络的周期性　信息以作为背景知识去攻击匿名社交网络时，针对单次发布的　社交网络隐私保护技术已不能给其带来足够保护，所以必须针　对动态社交网络提出更加有效的隐私保护方案。　［１２］ＺＨＥＬＥＶＡ　Ｅ，ＧＥＴＯＯＲ　Ｌ．Ｐｒｅｓｅｒｖｉｎｇ　ｔｈｅ　ｐｒｉｖａｃｙ　ｏｆ　ｓｅｎｓｉｔｉｖｅ　ｒｅｌａ－　ｔｉｏｎｓｈｉｐｓ　ｉｎ　ｇｒａｐｈ　ｄａｔａ［Ｃ］／／Ｐｒｏｃ　ｏｆ　Ｐｒｉｖａｃｙ，Ｓｅｃｕｒｉｔｙ，ａｎｄ　Ｔｒｕｓｔ　ｉｎ　ＫＤＤ　Ｗｏｒｋｓｈｏｐ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２００８：１５３－１７１．　［１３］ＬＩＵ　Ｋｕｎ，ＤＡＳ　Ｋ，ＧＲＡＮＤＩＳＯＮ　Ｔ，ｅｔ　ａ１．Ｐｒｉｖａｃｙ—ｐｒｅｓｅｒｖｉｎｇ　ｄａｔａ　ａｎａｌｙｓｉｓ　ｏｎ　ｇｒａｐｈｓ　ａｎｄ　ｓｏｃｉｌａ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｎｅｘｔ　Ｇｅｎｅｒａｔｉｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ，２０１３，１（１）：７９－９２．　［１４］ＮＡＲＡＹＡＮＡＮ　Ａ，ＳＨＭＡＴＩＫＯＶ　Ｖ．Ｄｅ—ｎｏｎｙｍｉａｚｉｎｇ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ　［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　３０ｔｈ　ＩＥＥＥ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｓｅｃｕｉｒｔｙ　ａｎｄ　Ｐｒｉｖａｃｙ．　２００９：１７３—１８７．　针对分布式数据库的隐私保护已被广泛地研究，随着智能　手机、平板电脑的不断普及以及云计算技术的不断发展，越来　［１５］ＷＯＮＤＲＡＣＥＫ　Ｇ，ＨＯＬＺ　Ｔ，ＫＩＲＤＡ　Ｅ，ｅｔ　ａ１．Ａ　ｐｒａｃｔｉｃａｌ　ａｔｔａｃｋ　ｔｏ　ｄｅ—ｎｏｎｙｍｉａｚｅ　ｓｏｃｉａｌ　ｎ￣ｗｏｒｋ　ｕｓｅｒ８【Ｃ￣／／Ｐｒｏｃ《ＩＥＥＥ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｓｅｃｕｒｉｔｙ＆Ｐｒｉｖａｃｙ．２０１２：６９。８０．　越多的用户使用移动设备来访问社交网络和使用云环境，而目　前针对分布式社交网络及移动社交网络的隐私保护研究还相　对比较少，这也将成为以后的研究热点。　［１６］ＣＯＲＤＥＬＬＡ　Ｌ　Ｐ，ＦＯＧＧＩＡ　Ｐ，ＳＡＮＳＯＮＥ　Ｃ，ｅｔ　ａ１．Ａ（ｓｕｂ）ｇｒａｐｈ　ｉｓｏｍｏｒｐｈｉｓｍ　ｌａｇｏｉｒｔｈｍ　ｆｏｒ　ｍａｔｃｈｉｎｇ　ｌａｒｇｅ　ｒｇａｐｈｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００４，２６（１０）：１３６７—　１３７２．　４结束语　本文从攻击者的背景知识模型化、敏感数据信息定义、信　息的有用性三方面对当前基于ｋ－ａｎｏｎｙｍｉｔｙ、聚类、随机化、　［１７］ＵＬＬＭＡＮＮ　Ｊ　Ｒ．Ａｎ　ａｌｇｏｒｉｔｈｍ　ｏｒｆ　ｓｕｂｇｒａｐｈ　ｉｓｏｍｏｒｐｈｉｓｍ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　ｔｈｅ　ＡＣＭ，１９７６，２３（１）：３１—４２．　Ｍａｒｋｏｖ链等技术的重要的社交网络隐私保护方案进行了详尽　的阐述、比较与分析。最后对社交网络隐私保护技术的未来发　展方向及所面Ｉ临的挑战进行了展望和讨论。　参考文献：　［１］ＺＨＯＵ　Ｂｉｎ，ＰＥＩ　Ｊｉａｎ，ＬＵＫ　Ｗ　Ｓ．Ａ　ｂｒｉｅｆ　ｓｕｒｖｅｙ　ｏｎ　ａｎｏｎｙｍｉｚａｔｉｏｎ　ｔｅｃｈｎｉｑｕｅｓ　ｆｏｒ　ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｐｕｂｌｉｓｈｉｎｇ　ｏｆ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋ　ｄａｔａ　［１８］ＴＩＡＮ　Ｙｕａｎ－ｙｕａｎ，ＰＡＴＥＬ　Ｊ　Ｍ．ＴＡＬＥ：ａ　ｔｏｏｌ　ｆｏｒ　ａｐｐｒｏｘｉｍａｔｅ　ｌａｒｇｅ　ｒｇａｐｈ　ｍａｔｃｈｉｎｇ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　２４ｔｈ　ＩＥＥＥ　Ｉｎｔｅｎａｒｔｉｏｎａｌ　Ｃｏｆｎｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ．２００８：９６３－９７２．　［１９］ＴＨＯＭＰＳＯＮ　Ｂ，ＹＡＯ　Ｄａｎ—ｆｅｎｇ．Ｔｈｅ　ｕｎｉｏｎ・ｓｐｌｉｔ　ｌａｇｏｒｉｔｈｍ　ａｎｄ　ｃｌｕｓ－　ｔｅｒ－ｂａｓｅｄ　ａｎｏｎｙｍｉｚａｔｉｏｎ　ｏｆ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　４ｔｈ　Ｉｎ—　ｔｅｒｎａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｉｆｏｒｎｍａｔｉｏｎ，Ｃｏｍｐｕｔｅｒ，ａｎｄ　Ｃｏｍｍｕｎｉｃａ－　ｔｉｏｎｓ　Ｓｅｃｕｒｉｔｙ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２０１３：２１８—２２７．　［Ｊ］．ＳＩＧＫＤＤ　Ｅｘｐｌｏｒａｔｉｏｎｓ，２００８，ｌｏ（２）：１２—２２．　［２０］ＧＯＲＩ　Ｍ，ＭＡＧＧＩＮＩ　Ｍ，ＳＡＲＴＩ　Ｌ．Ｅｘａｃｔ　ａｎｄ　ａｐｐｒｏｘｉｍａｔｅ　ｇｒａｐｈ　ｍａｔｃｈｉｎｇ　ｕｓｉｎｇ　ｒａｎｄｏｍ　ｗａｌｋｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｐａ№ｍ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００５，２７（７）：１１００—１１１１．　［２］ＬＩＵ　Ｋｕｎ，ＴＥＲＺＩ　Ｅ．Ｔｏｗａｒｄｓ　ｉｄｅｎｔｉｔｙ　ａｎｏｎｙｍｉｚａｔｉｏｎ　ｏｎ　ｇｒａｐｈｓ［Ｃ］　／／Ｐｒｏｃ　ｏｆ　ＡＣＭ　ＳＩＧＭＯＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２００８：９３—１０６．　［２１］ＬＵＯ　Ｂｉｎ，ＨＡＮＣＯＣＫ　Ｅ　Ｒ．Ｓｔｒｕｃｔｕｒｌａ　ｇｒａｐｈ　ｍａｔｃｈｉｎｇ　ｕｓｉｎｇ　ｔｈｅ　ＥＭ　【３］ＨＡＹ　Ｍ，ＭＩＫＬＡＵ　Ｇ，ＪＥＮＳＥＮ　Ｄ，醣ａ１．Ｒｅｓｉｓｔｉｎｇ　ｓｔｒｎｃｔｕｒａｌ　ｒｅ—ｉｄｅｎ—　ｌａｇｏｒｉｔｈｍ　ａｎｄ　ｓｉｎｇｕｌａｒ　ｖｌａｕｅ　ｄｅｃｏｍｐｏｓｉｔｉｏｎ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｐａｔ－　ｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００１，２３（１０）：１　１２０—　１１３６．　ｔｉｉｆｅａｔｉｏｎ　ｉｎ　ａｎｏｎｙｍｉｚｅｄ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ［Ｊ］．ＶＬＤＢ　Ｊｏｕｒｎａｌ，２０１０，１９　（６）：７９７－８２３．　［４］ＨＡＹ　Ｍ，ＭＩＫＬＡＵ　Ｇ，ＪＥＮＳＥＮ　Ｄ，　ａ１．Ａｎｏｎｙｍｉｚｉｎｇ　ｓｏｃｉａｌ　ｎｅｔ－　［２２］ＭＹＥＲＳ　Ｒ，ＷＩＬＳＯＮ　Ｒ　Ｃ，ＨＡＮＣＯＣＫ　Ｅ　Ｒ．Ｂａｙｅｓｉｎａ　ｇｒａｐｈ　ｅｄｉｔ　ｄｉｓ－　ｔｎｃｅ［Ｊ］．ＩａＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｐａｔｔｅｒｎ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｍａｃｈｉｎｅ　Ｉｎｔｅｌｌｉ。　ｇｅｎｃｅ，２０００，２２（６）：６２８・６３５．　ｗｏｒｋｓ，ＴＲ０７－１９［Ｒ］．Ｂｏｓｔｏｎ：Ｕｎｉｖｅｒｓｉｔｙ　ｏｆＭａｓｓａｃｉｆｕｓｅｔｔｓ，２０１０．　［５］ＺＨＯＵ　Ｂｉｎ，ＰＥ［Ｊｉｎ．Ｐｒｅｓｅｒａｖｉｎｇ　ｐｒｉｖａｃｙ　ｉｎ　ｓｏｃｉｌ　ｎｅｔａｗｏｒｋｓ　ａｇａｉｎｓｔ　ｎｅｉｇｈｂｏｒｈｏｏｄ　ａｔｔａｃｋｓ［Ｃ］／／Ｐｒｃ　ｏｏｆ　ｔｈｅ　２４ｔｈ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎ－　ｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ．２００８：５０６—５１５．　［２３］ＣＯＳＴＡ　Ｌ　ｄａ　Ｆ，ＲＯＤＲＩＧＵＥＳ　Ｆ　Ａ，ＴＲＡＶＩＥＳＯ　Ｇ，ｅｔ　ａ１．Ｃｈｒａａｃｔｅ—　ｒｉｚａｔｉｏｎ　ｏｆ　ｃｏｍｐｌｅｘ　ｎｅｔｗｏｒｋｓ：ａ　ｓｕｒｖｅｙ　ｏｆ　ｍｅａｓｕｒｅｍｅｎｔｓ［Ｊ］．Ａｄ－　ｖａｎｃｅｓ　ｉｎ　Ｐｈｙｓｉｃｓ，２００７，５６（１）：１６７—２４２．　［６］ＢＡＣＫＳＴＲＯＭ　Ｌ，ＤＷＯＲＫ　Ｃ，ＫＬＥＩＮＢＥＲＧ　Ｊ．Ｗｈｅｒｅｆｏｒｅ　ａｒｔ　ｔｈｏｕ　Ｒ３４７９ｘ？：ａｎｏｎｙｍｉｚｅｄ　ｓｏｃｉｌ　ｎｅｔａｗｏｒｋｓ，ｈｉｄｄｅｎ　ｐａｔｔｅｒｎｓ，ａｎｄ　ｓｔｒｕｃｔｕ—　［２４］ＹＩＮＧ　Ｘｉａｏ－ｗｅｉ，ｗｕ　Ｘｉｎ—ｔａｏ．Ｒａｎｄｏｍｉｚｉｎｇ　ｓｏｃｉｌａ　ｎｅｔｗｏｒｋｓ：ａ　ｓｐｅｃ—　ｔｒｕｍ　ｐｒｅｓｅｒｖｉｎｇ　ａｐｐｒｏａｃｈ［Ｃ］／／Ｐｒｏｃ　ｏｆｔｈｅ　１ｌｔｈ　ＳＩＡＭ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ．２００８：７３９—７５０．　ｒａｌ　ｓｔｅｆａｎｏｇｒａｐｈｙ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　１６ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｗｏｒｌｄ　Ｗｉｄｅ　Ｗｅｂ　Ｃｏｎｆｅｒｅｎｃｅ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２００７：１８１—１９０．　［７］ＺＯＵ　Ｌｅｉ，ＣＨＥＮ　Ｌｅｉ．Ｋ－ａｕｔｏｍｏｒｐｈｉｓｍ：ａ　ｇｅｎｅｒｌａ　ｆｒａｍｅｗｏｒｋ　ｆｏｒ　ｐｒｉ—　［２５］ＹＩＮＧ　Ｘｉａｏ－ｗｅｉ，ｗｕ　Ｘｉｎ—ｔａｏ．Ｇｒａｐｈ　ｇｅｎｅｒａｔｉｏｎ　ｗｉｔｈ　ｐｒｅｓｃｉｒｂｅｄ　ｆｅａ—　第５期　马飞，等：社交网络隐私保护技术最新研究进展　・１２９７・　ｔｕｒｅ　ｃｏｎｓｔｒａｉｎｔｓ［Ｃ　Ｊ／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　９ｔｈ　ＳＩＡＭ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉ　ｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ．２００９：７８０。７９１．　ｎｉｎｇ．２００９：９６６—９７７．　［３８］　ＰＥＡＲＬ　Ｊ．Ｐｒｏｂａｂｉｌｉｓｔｉｃ　ｒｅａｓｏｎｉｎｇ　ｉｎ　ｉｎｔｅｌｌｉｇｅｎｔ　ｓｙｓｔｅｍｓ：ｎｅｔｗｏｒｋｓ　ｏｆ　［２６］ＳＥＡＲＹ　Ａ，ＲＩＣＨＡＲＤＳ　Ｗ．Ｓｐｅｃｔｒａｌ　ｍｅｔｈｏｄｓ　ｆｏｒ　ａｎａｌｙｚｉｎｇ　ｎａｄ　ｖｉｓｕａ—　ｐｌａｕｓｉｂｌｅ　ｉｎｆｅｒｅｎｃｅ［Ｍ］．Ｓａｎ　Ｆｒｎａｃｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ，１９８８．　ｌｉｚｉｎｇ　ｎｅｔｗｏｒｋｓ：ａｎ　ｉｎｔｒｏｄｕｃｔｉｏｎ［Ｊ］．Ｄｙｎａｍｉｃ　Ｓｏｃｉａｌ　Ｎｅｔｗｏｒｋ　［３９］　ＣＡＭＰＡＮ　Ａ，ＴＲＵＴＡ　Ｔ　Ｍ．Ａ　ｃｌｕｓｔｅｒｉｎｇ　ａｐｐｒｏａｃｈ　ｆｏｒ　ｄａｔａ　ｎａｄ　ｓｔｒｕｔ－　Ｍｏｄｅｌｉｎｇ　ａｎｄ　Ａｎａｌｙｓｉｓ，２００３，３（４）：２０９—２２８．　ｔｕｒｌａ　ｎａｏｎｙｍｉｔｙ　ｉｎ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　２ｎｄ　ＡＣＭ　ＳＩＧＫ—　［２７］ＮＥＲＧＩＺ　Ｍ　Ｅ，ＣＬＩＦＴＯＮ　Ｃ．Ｔｈｏｕｇｈｔｓ　ｏｎ　ｋ－ａｎｏｎｙｍｉｚａｔｉｏｎ［Ｊ］．Ｄａｔａ＆　ＤＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｐｒｉｖａｃｙ，Ｓｅｃｕｒｉｔｙ，ａｎｄ　Ｔｒｕｓｔ　ｉｎ　ＫＤＤ．　Ｋｎｏｗｌｅｄｇｅ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００７，６３（３）：６２２—６４５．　Ｎｅｗ　Ｙ０ｒｋ：ＡＣＭ　Ｐｒｅｓｓ。２０１０：１１０—１２３．　［２８］ＮＥＲＧＩＺ　Ｍ　Ｅ，ＣＬＩＴＦＯＮ　Ｃ，ＮＥＲＧＩＺ　Ａ　Ｅ．Ｍｕｈｉｒｅｌａｔｉｏｎａｌ　ｋ－ａｎｏ－　［４０］　Ｎｅｔｌｆｉｘ　ｐｒｉｚｅ［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｎｅｔｌｆｉｘｐｒｉｚｅ．ｃｏｒｎ．　ｎｙｍｉｔｙ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，　［４１］　ＫＯＲＯＬＯＶＡ　Ａ，ＫＥＮＴＨＡＰＡＤＩ　Ｋ，ＭＩＳＨＲＡ　Ｎ，ｅｔ　ａ１．Ｒｅｌｅａｓｉｎｇ　２０１２，２４（８）：１１０４－１１１７．　ｓｅａｒｃｈ　ｑｕｅｒｉｅｓ　ａｎｄ　ｃｌｉｃｋｓ　ｐｒｉｖａｔｅｌｙ［Ｃ］／／Ｐｒｃｏ　ｏｆ　ｈｔｅ　１８ｔｈ　Ｉｎｔｅｎｒａｔｉｏ－　［２９］ＳＷＥＥＮＥＹ　Ｌ．ｋ－ａｎｏｎｙｍｉｔｙ：ａ　ｍｏｄｅｌ　ｆｏｒ　ｐｒｏｔｅｃｔｉｎｇ　ｐｒｉｖａｃｙ［Ｊ］．Ｉｎｔｅｒ－　ｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｗｏｒｌｄ　ｄｅ　Ｗｅｂ．Ｎｅｗ　Ｙ０ｒｋ：ＡＣＭ　Ｐｒｅｓｓ．２００９：　ｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｏｎ　Ｕｎｃｅｒｔａｉｎｔｙ，Ｆｕｚｚｉｎｅｓｓ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ—　１７１—１８０．　ｂａｓｅｄ　Ｓｙｓｔｅｍｓ，２００２，１０（５）：５５７－５７０．　［４２］　ＹＵＡＮ　Ｍｉｎｇ－ｘｕａｎ，ＣＨＥＮ　Ｌｅｉ，ＹＵ　Ｐ　Ｓ．Ｐｅｒｓｏｎａｌｉｚｅｄ　ｐｒｉｖａｃｙ　ｐｒｏｔｅｃ—　［３０］ＭＡＣＨＡＮＡＶＡＪＪＨＡＬＡ　Ａ，ＧＥＨＲＫＥ　Ｊ，ＫＩＦＥＲ　Ｄ．１－ｄｉｖｅｒｓｉｔｙ：ｐｒｉ・　ｔｉｏｎ　ｉｎ　ｓｏｃｉｌａ　ｎｅｔｗｏｒｋｓ［Ｊ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ＶＬＤＢ　Ｅｎｄｏｗ—　ｖａｃｙ　ｂｅｙｏｎｄ　ｋ－ａｎｏｎｙｍｉｔｙ［Ｊ］．ＡＣＭ　Ｔｒａｎｓ　ｏｆｆ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏ－　ｍｅｎｔ，２０１０，４（２）：１４１－１５０．　ｖｅｒｙ　ｆｒ０ｍ　Ｄａｔａ，２００７，１（１）：２４－３５．　［４３］ＦＡＲＤ　Ａ　Ｍ，ＷＡＮＧ　Ｋｅ．Ｎｅｉｇ｝ｌｂｏｒｈｏｏｄ　ｒａｎｄｏｍｉｚａｔｉｏｎ　ｏｆｒ　ｌｉｎｋ　ｐｒｉｖａｃｙ　［３　１］ＬＩ　Ｎｉｎｇ—ｈｕｉ，ＬＩ　Ｔｉａｎ—ｚｈｅｎｇ．ＶＥＮＫＡＴＡＳＵＢＲＡＭＡＮＩＡＮ　Ｓ．Ｃｌｏｓｅ—　ｎｅｓｓ：ａ　ｎｅｗ　ｐｒｉｖａｃｙ　ｍｅａｓｕｌ￣ｆｏｒ　ｄａｔａ　ｐｕｂｌｉｓｈｉｎｇ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｆｆ　ｉｎ　ｓｏｃｉｌａ　ｎｅｔｗｏｒｋ　ａｎａｌｙｓｉｓ［Ｊ］．Ｗｏｒｌｄ　Ｗｉｄｅ　Ｗｅｂ　Ｊｏｕｒｎａｌ，２０１３，２４　（７）：１３４．１４５．　Ｋｎｏｗｌｅｄｇｅ＆Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２０１０，２２（７）：９４３・９５６．　［４４】ＷＡＮＧ　Ｇｕｏ－ｊｕｎ，ＬＩＵ　Ｑｉｎ，ＬＩ　Ｆｅｎｇ，ｅｔ　ａ１．Ｏｕｔｓｏｕｒｃｉｎｇ　ｐｒｉｖａｃｙ—ｐｒｅ—　［３２］ＬＩ　Ｎｉｎｇ—ｈｕｉ，ＬＩ　Ｔｉａｒａ－ｅｈｅｎｇ．ｔ－ｃｌｏｓｅｎｅｓｓ：ｐｒｉｖａｃｙ　ｂｅｙｏｎｄ　ｋ－ａｎｏｎｙｍｉｔｙ　ａｎｄ／－ｄｉｖｅｒｓｉｔｙ［Ｃ］／／Ｐｒｏｃ　ｏｆＩＣＤＥ．２００７：１０６・１１５．　ｓｅｒｖｉｎｇ　ｓｏｃｉｌａ　ｎｅｔｗｏｒｋｓ　ｔｏ　ａ　ｃｌｏｕｄ［Ｃ］／／Ｐｒｃｏ　ｏｆ　ＩＥＥＥ　ＩＮＦＯＣＯＭ．　［３３］ＤＩＥＳＴＥＬ　Ｒ．Ｇｒａｐｈ　ｔｈｅｏｒｙ［Ｍ］．４ｔｈ　ｅｄ．Ｈｅｉｄｅｌｂｅｒｇ：Ｓｐｒｉｎｇｅｒ—Ｖｅｌｆａｇ，　２０１３：２８８６—２８９４．　２０１０．　［４５］ＤＷＯＲＫ　Ｃ．Ｄｉｆｅｒｅｎｔｉｌａ　ｐｉｒｖａｃｙ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　３３ｒｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　［３４］ＧＲＯＳＳ　Ｊ，ＹＥＬＬＥＮ　Ｊ．Ｇｒａｐｈ　ｔｈｅｏｒｙ　ａｎｄ　ｉｔｓ　ａｐｐｌｉｃａｔｉｏｎｓ［Ｍ】．２ｎｄ　Ｃｏｌｌｏｑｕｉｕｍ　ｏｎ　Ａｕｔｏｍａｔａ，Ｌａｎｇｕａｇｅｓ　ａｎｄ　Ｐｒｏｇｒａｍｍｉｎｇ．２００６：１—１２．　ｅｄ．『Ｓ．Ｉ．］：ＣＲＣ　Ｐｒｅｓｓ，２００５．　［４６］ＤＷＯＲＫ　Ｃ．Ｄｉｆｆｅｒｅｎｔｉｌａ　ｐｒｉｖａｃｙ：ａ　ｓｕｒｖｅｙ　ｏｆ　ｒｅｓｕｌｔｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　［３５］ＬＩＵ　Ｌｉａｎ，ＷＡＮＧ　Ｊｉｅ，ＬＩＵ　Ｊｉｎ—ｚｅ，ｅｔ　ａ１．Ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ｉｎ　ｓｏｃｉｌａ　５ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｔｈｅｏｒｙ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎｓ　ｏｆ　Ｍｏｄｅｌｓ　ｏｆ　ｎｅｔｗｏｒｋｓ　ａｇａｉｎｓｔ　ｓｅｎｓｉｔｉｖｅ　ｅｄｇｅ　ｄｉｓｃｌｏｓｕｒｅ，ＣＭＩＤＡ—ＨｉＰＳＣＣＳ　００６—０８　Ｃｏｍｐｕｔａｔｉｏｎ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，２０１０：１—１９．　［Ｒ］．Ｋｅｎｔｕｃｋｙ：Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｋｅｎｔｕｃｋｙ，２００８．　［４７］ＨＡＹ　Ｍ，ＬＩ　Ｃｈａｏ，ＭＩＫＬＡＵ　Ｇ，ｅｔ　ａ１．Ａｃｃｕｒａｔｅ　ｅｓｔｉｍａｔｉｏｎ　ｏｆｔｈｅ　ｄｅ—　［３６　Ｊ　ＣＡＲＭＩＮＡＴＩ　Ｂ，ＦＥＲＲＡＲＩ　Ｅ，ＰＥＲＥＧＯ　Ａ．Ｐｒｉｖａｔｅ　ｒｅｌａｔｉｏｎｓｈｉｐｓ　ｉｎ　ｇｒｅｅ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｏｆ　ｐｒｉｖａｔｅ　ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　９ｔｈ　ＩＥＥＥ　Ｉｎｔｅｒ－　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　２３ｒｄ　ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ．２００９：１６９—１７８．　ｏｎ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ．２００７：１６３－１７１．　［４８］ＭＩＲ　Ｄ　Ｊ，ＷＲＩＧＨＴ　Ｒ　Ｎ．Ａ　ｄｉｆｅｒｅｎｔｉｌａｌｙ　ｐｒｉｖａｔｅ　ｇｒａｐｈ　ｅｓｔｉｍａｔｏｒ　［３７］ＨＡＮＨＨＡＲＶＩ　Ｓ，ＧＡＲＲＩＧＡ　Ｇ　Ｃ，ＰＵＯＬＡＭ．￣ＫＩ　Ｋ．Ｒａｎｄｏｍｉｚａｔｉｏｎ　［Ｃ］／／Ｐｒｅｅ　ｏｆ　ｔｈｅ　９ｔｈ　ＩＥＥＥ　Ｉｎｔｅｎｒａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ．　ｔｅｃｈｎｉｑｕｅｓ　ｆｏｒ　ｇｒａｐｈｓ［Ｃ］／／Ｐｒｏｃ　ｏｆ　ｔｈｅ　ＳＩＡＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒ－　２００９：１２２—１２９．　（上接第１２９０页）　［２３］ＰＩＣＡＲＤ　Ｒ　Ｒ，ＣＯＯＫ　Ｒ　Ｄ．Ｃｒｏｓｓ－ｖａｌｉｄａｔｉｏｎ　ｏｆ　ｒｅｇｒｅｓｓｉｏｎ　ｍｏｄｅｌｓ　［１５］ＭＡＲＫＡＴＯＵ　Ｍ，ＴＩＡＮ　Ｈｏｎｇ，ＢＩＳＷＡＳ　Ｓ，ｅｔ　ａ１．Ａｎａｌｙｓｉｓ　ｏｆ　ｖａｒｉａｎｃｅ　［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　ｔｈｅ　Ａｍｅｒｉｃａｎ　Ｓｔａｔｉｓｔｉｃａｌ　Ａｓｓｏｃｉａｉｔｏｎ，１９８４，７９　ｏｆ　ｃｒｏｓｓ．ｖａｌｉｄａｔｉｏｎ　ｅｓｔｉｍａｔｏｒｓ　ｏｆ　ｔｈｅ　ｇｅｎｅｒａｌｉｚａｔｉｏｎ　ｅｒｒｏｒ『Ｊ］．Ｊｏｕｒｎａｌ　（３８７）：５７５—５８３．　０ｆ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ　Ｒｅｓｅａｒｃｈ，２００５，６：１１２７－ｌ１６８．　［２４］ＢＲＥＩＭＡＮ　Ｌ，ＳＰＥＣＴＯＲ　Ｐ．Ｓｕｂｍｏｄｅｌ　ｓｅｌｅｃｔｉｏｎ　ａｎｄ　ｅｖａｌｕａｔｉｏｎ　ｉｎ　ｒｅ—　［１６］ＹＩＬＤＩＺ　０　Ｔ．Ｏｍｎｉｖａｒｉａｔｅ　ｒｕｌｅ　ｉｎｄｕｃｔｉｏｎ　ｕｓｉｎｇ　ａ　ｎｏｖｅｌ　ｐａｉｒｗｉｓｅ　ｓｔａｔｉｓ－　ｇｒｅｓｓｉｏｎ：ｔｈｅ　Ｘ．ｒａｎｄｏｍ　ｃａｓｅ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｓｔａｔｉｓｔｉｃａｌ　Ｒｅｖｉｅｗ，　ｔｉｅａｌ　ｔｅｓｔ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　ａｎｄ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，　１９９２，６０（３）：２９１－３１９．　２０１３，２５（９）：２１０５－２１１８．　［２５］ＢＵＲＭＡＮ　Ｐ．Ａ　ｃｏｍｐａｒａｔｉｖｅ　ｓｔｕｄｙ　ｏｆ　ｏｒｄｉｎａｒｙ　ｃｒｏｓｓ—ｖｌａｉｄａｔｉｏｎ．ｖ－ｆｏｌｄ　［１７］ＦＵ　Ｗｅｎ－ｊｉｎａｇ，ＣＡＲＲＯＬＬ　Ｒ　Ｊ，ＷＡＮＧ　Ｓｕｏ－ｊｉｎ．Ｅｓｔｉｍａｔｉｎｇ　ｍｉｓｃｌａｓ—　ＣｒｏＳＳ—ｖａｌｉｄａｔｉｏｎ　ａｎｄ　ｔｈｅ　ｒｅｐｅａｔｅｄ　ｌｅａｒｎｉｎｇ—ｔｅｓｔｉｎｇ　ｍｅｔｈｏｄｓ［Ｊ］．Ｂｉｏｍｅ－　ｓｉｆｉｅａｔｉｏｎ　ｅｒｒｏｒ　ｗｉｔｈ　ｓｍａｌｌ　ｓａｍｐｌｅｓ　ｖｉａ　ｂｏｏｔｓｔｒａｐ　ＣＲＯＳＳ－ｖａｌｉｄａｔｉｏｎ［Ｊ］．　ｔｎｋａ，１９８９，７６（３）：５０３—５１４．　Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，２００５，２１（９）：１９７９－１９８６．　［１８］ＬＡＲＳＯＮ　Ｓ　Ｃ．ＴＩｌｅ　ｓｈｒｉｎｋａｇｅ　ｏｆ　ｔｈｅ　ｃｏｅｆｆｉｃｉｅｎｔ　ｏｆ　ｍｕｌｔｉｐｌｅ　ｃｏｒｒｅｌａｔｉｏｎ　［２６］ＣＲＡＶＥＮ　Ｐ，ＷＡＨＢＡ　Ｇ．Ｓｍｏｏｔｈｉｎｇ　ｎｏｉｓｙ　ｄａｔａ　ｗｉｔｈ　ｓｐｌｉｎｅ　ｆｕｎｃｔｉｏｎｓ：　Ｅｓｔｉｍａｔｉｎｇ　ｔｈｅ　ｃｏｒｒｅｃｔ　ｄｅｇｒｅｅ　ｏｆ　ｓｍｏｏｔｈｉｎｇ　ｂｙ　ｔｈｅ　ｍｅｔｈｏｄ　ｏｆ　ｇｅｎｅｒａ—　［Ｊ］．Ｊｏｕｒｎａｌ　Ｅｄｕｃａｔｉｏｎａｌ　Ｐｓｙｃｈｏｌｏｇｙ，１９３１，２２（１）：４５—５５．　［１９］ＤＥＶＲＯＹＥ　Ｌ，ＷＡＧＮＥＲ　Ｔ　Ｊ．Ｄｉｓｔｉｒｂｕｔｉｏｎ－ｆｒｅｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｂｏｕｎｄｓ　ｌｉｚｅｄ　ｃｒｏｓｓ－ｖａｌｉｄａｔｉｏｎ［Ｊ］．Ｎｕｍｅｒｉｓｃｈｅ　Ｍａｔｈｅｍａｔｉｋ，１９７９，３１（４）：　３７７．４０３．　ｆｏｒ　ｐｏｔｅｎｔｉｌａ　ｆｕｎｃｔｉｏｎ　ｒｕｌｅｓ［Ｊ］．ＩＥＥＥ　Ｔｒａｎｓ　ｉｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ，　１９７９，２５（５）：６Ｏｌ一６０４．　［２７］ＭＯＬＩＮＡＲＯ　Ａ　Ｍ，ＳＩＭＯＮ　Ｒ。ＰＦＥＩＦＦＥＲ　Ｒ　Ｍ．Ｐｒｅｄｉｃｔｉｏｎ　ｅｌＴｏｒ　ｅｓｔｉ—　［２０］ＧＥＩＳＳＥＲ　Ｓ．Ｔｈｅ　ｐｒｅｄｉｃｔｉｖｅ　ｓａｍｐｌｅ　ｒｅｕｓｅ　ｍｅｔｈｏｄ　ｗｉｈｔ　ａｐｐｌｉｃａｔｉｏｎｓ　ｍａｔｉｏｎ：ａ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｒｅｓａｍｐｌｉｎｇ　ｍｅｔｈｏｄｓ［Ｊ］．Ｂｉｏｉｎｆｏｒｍａｔｉｃｓ，　［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　ｔｈｅ　Ａｍｅｒｉｃａｎ　Ｓｔａｔｉｓｔｉｃａｌ　Ａｓｓｏｃｉａｔｉｏｎ，１９７５，７０　２００５，２１（１５）：３３０１—３３０７．　（３５）：３２０—３２８．　［２８］胡军艳．基于生物信息数据的几种交叉验证方法比较［Ｄ］．太原：　［２１］ＳＨＡＯ　Ｊｕｎ．Ｌｉｎｅａｒ　ｍｏｄｅｌ　ｓｅｌｅｃｔｉｏｎ　ｂｙ　ＣｏｒＳＳ－ｖｌａｉｄａｔｉｏｎ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　山西大学，２０１３．　ｔｈｅ　Ａｍｅｒｉｃａｎ　Ｓｔａｔｉｓｔｉｃａｌ　Ａｓｓｏｃｉａｔｉｏｎ，１９９３，８８（４２２）：４８６－４９４．　［２９］ＢＲＥＩＭＡＮ　Ｌ，ＦＲＩＥＤＭＡＮ　Ｊ　Ｈ，ＳＴＯＮＥ　Ｃ　Ｊ，ｅｔ　ｏｉ．Ｃｌａｓｓｉｉｆｃａｔｉｏｎ　ａｎｄ　［２２］ＺＨＡＮＧ　Ｐｉｎｇ．Ｍｏｄｅｌ　ｓｅｌｅｃｔｉｏｎ　ｖｉａ　ｍｕｈｉｆｏｌｄ　ｃｒｏｓｓ　ｖａｌｉｄａｔｉｏｎ［Ｊ］．Ａｎ－　ｒｅｇｒｅｓｓｉｏｎ　ｔｒｅｅｓ［Ｍ］／／Ｗａｄｓｗｏｒｔｈ　Ａｄｖａｎｃｅｄ　Ｂｏｏｋｓ　ａｎｄ　Ｓｏｆｗｔａｒｅ．『Ｓ．　ｎａｌｓ　ｏｆ　Ｓｔａｔｉｓｔｉｃｓ，１９９３，２１（１）：２９９—３１３．　１．］：Ｃｈａｐｍａｎ＆Ｈａｌｌ／ＣＲＣ．１９８４．