论文部分内容阅读
生活中存在着大量的复杂系统,这些复杂系统可被抽象表示为复杂网络,例如传染病网络、生物网络、人际网络等。社团结构可以揭示复杂网络的结构和功能特性,是复杂网络最基本的特征。发现社团结构的过程就是社团检测。随着复杂网络的种类愈来愈多,社团检测算法面临新的挑战,这就需要研究人员考虑不同的情况,提出高效,准确的社团检测算法。本文针对目前社团检测中两种不同的问题,提出了两个社团检测算法:DCDC和Vortex。DCDC算法以互k近邻连接的方式发现社团核心,克服了该类算法难以出检测任意结构,任意规模社团的局限性。Vortex算法是Black Hole算法的改进算法,Vortex算法以基于高阶结构motif的引力模式发现社团核心来进行社团检测,克服了Black Hole算法在节点度差别很大网络上表现较差的缺点。DCDC算法和Vortex算法的基本原理及优势如下:(1)DCDC如何检测任意结构,任意规模的社团是社团检测领域的一个难点。为解决该问题,提出了一种可以通过k最近邻发现社团核心的社团检测算法DCDC。该算法首先遍历所有节点,将两个互为近邻的相似节点及它们的共同邻居聚集到一个社团核心中;然后,在遍历过程中,若不在核心中的节点与某个社团核心内任何节点存在互近邻关系,那么该节点也会被吸引到这个社团核心中;接着,该算法检测出社团核心中的异常节点,并将其标记为无类标节点;最终,该算法利用影响力分配无类标节点,得到最终的社团结构。该算法简单且时间复杂度较低。此外,该算法不需要社团个数作为先验参数。通过在4个真实网络以及3个不同规模的LFR人工合成网络的综合测试表明:DCDC算法能检测出任意结构与任意规模的社团,且发现的社团质量高于所用的5个基准算法。(2)Vortex大部分社团检测算法在节点的度差别较大的网络上都很难检测出高质量的社团结构。Black Hole算法是一个鲁棒性较强的图嵌入算法,该算法通过graph drawing中的图嵌入方法得到网络在二维平面上合力最小的分布,再通过DBSCAN聚类算法得到最终的社团结构。由于仅考虑到节点之间的低阶联系,即节点间的边,该算法在节点的度差别较大的网络上表现不佳。为了解决这个不足,引入了高阶结构motif,提出了基于motif引力模式发现社团核心的社团检测算法Vortex。引入高阶结构motif进行图嵌入时,可从全局角度考虑两个节点的相似性,这使得Vortex算法能不受网络间节点联系稀疏影响并发现节点间隐含的联系。此外,Vortex算法还提出了基于motif来分配无类标节点的方法。实验结果表明:无论对度差别较大的人工网络,还是对6个有真实类标签的小网络及8个无真实类标签的较大的网络,Vortex算法检测到的社团结构在大多数情况下不但较Black Hole算法质量高,而且较其它6个对比算法更高。