计算机论文哪里有?本文从复杂网络的各种特性出发,简单概述了相关的概念并对经典的社团划分算法与隐私保护方法的优缺点进行了详细的分析,设计了两种社团划分算法,又根据社团划分中节点重要性的概念设计了一种隐私保护方法。最后对设计的算法与方法进行了简单的应用。
第一章 绪论
1.2 国内外研究现状
18 世纪,由 Euler 提出的“哥德堡七桥问题”成为了启蒙科学家们对传统规则网络研究的基础。上世纪中叶,保罗·厄多斯与伦伊提出了有关随机网络的概念与模型[26]。他们根据在模型中得到的“任意两点出现连边的概率相同”这一结论而做出网络是没有规则的推断。但随着研究的深入,人们发现现实生活中的网络并不是完全无规则或是完全随机的,于是人们根据这种特性提出了复杂网络的概念。信息时代,人们的生活被“数字”包围,有研究学者开始利用新兴的技术基于图论、随机过程等方法论来研究生活中各种的复杂网络。
最早的社团划分算法采用图论和聚类的思想。科研人员将网络划分成若干个社团,然后再按照某种规则进行聚类,其中最著名的算法是谱平分法[27-29]。谱平分法主要采用线性代数中矩阵特征值的思想,先计算拉普拉斯矩阵的特征值,再利用该值将网络平均分成两部分,这两部分中包含的节点数量相同。该方法虽然时间复杂度较低,但是由于每次都只能将网络均分成两个社团,当社团多于两个时需要重复执行该算法,结果不够准确。
2003 年,Girvan 和 Newman 提出了一种基于边介数的社团划分算法[30-31]。网络中任意一条边可能经过若干条最短路径,将目标边所属于的最短路径数量总和与网络中全部最短路径数量总和相比,得到的结果就是目标边的边介数。GN 算法主要是通过不断剥离边介数大的边,从而获得最终的划分结果。这一成果极大的启发了研究人员,许多来自不同领域的研究人员提出了许多新的算法,如基于索引的 GN 算法[32]、基于边聚类系数的 GN 算法[33]等。2004年,Girvan 和 Newman 又提出关于模块度 Q 的相关概念[34]。后来,模块度 Q 被广泛应用在社团划分中,作为检验社团划分结果质量的标准。模块度 Q 值与社团划分结果质量呈正相关性,Q 值越高表示社团结构越清晰,社团划分结果质量越高,反之亦然。随后有科研人员提出基于模块度的 FN (Fast Newman) 算法,该算法主要利用贪心法的思想,以获得最大模块度Q 值增益为目标对网络进行划分。2006 年,Danon 等人[35]提出了一种可以将模块度 Q 值进行标准化的算法,解决了 GN 算法中出现的小社团问题。2008 年,Agarwal 等人[36]利用最优化的方法,通过非线性规划中的二次规划来获得最大的模块度 Q 值,但该方法复杂度非常高,当网络规模非常大时,计算非常耗时。2010 年,Good 等人[37]对模块度 Q 进行了深入的研究,他们发现在现实中模块度 Q 取决于网络规模和社团数量,并且存在最大化衰退等问题。
第三章 基于改进的 RA 相似度的标签传播算法研究
3.1 IRA-LPA 设计与分析
为了解决标签传播算法随机性高的问题,本章提出了一种基于改进 RA 相似度的标签传播算法 IRA-LPA(Label propagation algorithm based on improved RA similarity)。该算法将 RA相似度与标签传播算法相结合,首先针对 RA 相似度算法的计算结果中存在较多关联性的节点但相似度为零或无法计算的情况,引入了 SimRank 算法的思想对 RA 相似度算法进行了改进,并用改进的 RA 算法计算节点相似度从而得到初始社团,然后用 LPA 算法基于初始社团来完成最终的社团划分。
IRA-LPA 综合了各种问题提出了 SimRank 算法改进公式,降低了 SimRank 算法的计算复杂度,将其与传统 RA 相似度算法相结合,弥补了传统 RA 相似度算法的缺陷,又针对传统RA 相似度算法的其他不足提出了改进的 RA 算法 IRA。然后将 IRA 与 LPA 相结合,解决了LPA 初始节点分配标签的随机性问题以及资源消耗的问题,既充分发挥了二者的优势,又弥补了它们的不足。相较于所涉及的各个原始算法,IRA-LPA 在算法的稳定性以及准确性上都有提高。
为了验证 IRA-LPA 的性能,本文在经典的社会网络 Zachary 空手道俱乐部成员数据集和美国大学足球队赛事网络数据集以及人工生成数据集分别进行了相应的实验。因 IRA-LPA 划分的结果具有随机性,为保证算法的准确性,本文对上述数据集均做了多次试验并与多种不同的算法进行比较分析。
第五章 基于节点重要性的社会网络匿名保护方法研究
5.1 传统匿名保护方法存在的问题
传统 k-对称匿名可用于抵御基于结构知识的攻击,但是利用它对社会网络进行处理后,获得的匿名网络包含了大量冗余的节点和边,匿名成本较高。有研究者提出了一些减少节点和边的加入以降低匿名成本的方法,比如汪燕[71]选择对处理结果中节点度最大的节点之外的所有节点都进行对称复制以降低开销;王奇伟[72]选择只对处理结果中节点度最小的节点进行对称复制,使结果不再是呈规律性的对称,但这些方法都只考虑了节点的度,而忽略了节点在其他方面的重要性。事实上,在社会网络中重要的节点往往在网络结构中起支配作用,因此应该加强对重要节点的隐私保护,而对那些不太重要的节点只需要利用基本的匿名方法对它们进行处理即可。
为抵御基于结构知识的攻击以及更好地保护用户的隐私,本章设计了一种基于节点重要性的社会网络隐私保护方法(NI-PP)。该方法在 k-对称匿名的基础上加入了用 k-shell 方法计算的节点重要性,实现了对重要节点着重保护的目的,并提供了能完全还原原始网络结构的新的还原算法,利用在原始数据集上添加的标签对那些在还原过程中被误删的节点进行复原,以此提高匿名网络的可用性,减少网络还原中的信息损失。
5.2 NI-PP 算法的设计与分析
衡量节点重要性的方法有度中心性、介数中心性、特征向量中心性、k-shell 等,但考虑到算法的效率以及攻击者可以很容易获得节点度等结构信息,本文选用 k-shell 方法作为衡量节点重要性的指标。
k-shell 方法[73-74]的目的是分离网络中节点度小于等于 k 的节点,使节点按照 ks 值分层。具体划分过程是:在不存在孤立节点(度为 0 的节点)的网络中,先找到所有 k=1 的节点和对应的边将其从网络中剔除,然后继续迭代剔除网络中新出现的那些 k=1 的节点和对应的边直至网络中没有 k=1 的节点。此时,所有被剔除的节点形成了第一层 shell,我们称这层 shell为 1-shell,它们的 ks=1。再继续使用同样的方法对网络中余下的所有节点进行处理,可得到2-shell 以至于 k-shell,当网络中的每一个节点都有相应的 ks 信息后,算法停止。
由于在对原始社会网络进行对称匿名处理的过程中向网络中添加了许多新的节点和边,使得匿名后的网络拓扑结构与原始网络拓扑结构有了很大的区别。本文为保证匿名后网络的可用性和解决普通还原算法无法做到完全还原出原始网络结构的问题而设计的还原算法步骤如下:
Step1:分析匿名图的邻接矩阵,找出矩阵中相同的列并依次删除,直至矩阵中没有与之 相同的列。
Step2:找出矩阵中相同的行并依次删除,直至矩阵中没有与之相同的行,此时得到初始还原矩阵。
Step3:根据匿名算法第一步中添加的标签,对初始还原矩阵进行审查,若发现节点的同构点的个数与标签中的个数不相符,则进行对称复制操作,直至所有节点的同构点个数都与其标签记录相同。此时得到的还原矩阵即为最终的结果。
Step4:按照最终的还原矩阵生成原始社会网络图。
第七章 总结与展望
7.2 展望
本文主要从社团划分和隐私保护两个方向来对复杂网络进行研究,提出了两种社团划分算法和一种隐私保护方法,各个算法与方法都具有较高的性能和丰富的应用场景。但由于个人水平与时间限制,上述算法与方法也存在一定的局限性,未来还可以从以下几个方面进行更深入的研究:
(1)本文主要研究的是无向无权网络,各个节点与边都是无属性的,这是一种相对“理想化”的情况。而真实世界中,大部分网络中的节点和边都是具有相应“意义”的,它们包含方向、权重等重要信息。因此在今后的研究中可以针对不同的网络场景将相应的网络属性引入算法中进行处理,使结果更具物理意义。
(2)IRA-LPA 与 JLCD 两种算法虽然有着较高的性能,但二者都是针对复杂网络中的静态的非重叠社团进行研究的,而在真实社会中社团结构还会有重叠社团与动态社团等情况,因此可以对静态非重叠社团划分算法中的相关概念与工具进行拓展与利用,将研究层次提高至对动态重叠社团划分相关算法的研究。
(3)NI-PP 算法从图论中的相关概念出发,通过对节点进行重要性划分并结合匿名保护的手段达到了对重要节点着重保护的目的,但这种方式只适合于中小型网络,处理大型网络时,对称匿名技术仍会消耗很多资源。因此,在未来的研究中可以引入区块链、差分隐私等新的安全技术,以此来提高隐私保护的性能。
参考文献(略)