论文部分内容阅读
社团结构指的是复杂网络内部聚合的情况。复杂网络的聚类情况对研究复杂网络的网络行为、拓扑结构和信息传播与挖掘都有十分重要的意义。所以,近几年,越来越多的学者投身到复杂网络的社团结构检测中,同时,大量的算法也被提出。而不同的网络,由于其网络特性的差异,其社团结构的检测方法也存在不同,且存在一定的问题。如在重叠社团检测上重叠界限要求过于严格,而对于有向加权网络和二分网络的社团检测,研究过程中则可能存在信息丢失等问题,需进一步的探究。为此,本文针对不同的网络提出了三种不同的基于相似度的社团结构检测算法,主要工作和创新点如下: (1)提出了一个基于关键节点的重叠社团划分算法。算法通过对复杂网络的节点进行预处理,筛选出其中的关键节点,并形成以关键节点为中心的核心区域,随后吸收与该核心区域关系紧密的节点以形成初始社团,再根据吸收度扩大社团。算法利用了一种初始网络筛选方法和最新的吸收度函数对重叠社团进行检测。实验结果表明了该算法能有效地检测出网络的社团结构,且算法时间复杂度相对较低。 (2)提出了一种基于非对称亲密度的有向加权网络的社团检测算法。通过对有向加权网络节点间的关系特点的研究,给出了一种既能体现节点对间直接关系又能体现其间接关系的亲密度参数,并将其设计和引申至社团间的亲密关系。利用节点间的关系对网络进行聚类分析,最终根据最优模块度选择出最终的划分结果。通过对比试验发现了该算法的优越性和亲密度参数设计的合理性。 (3)提出了一种二分网络社团结构检测算法。通过分析二分网络中节点间的互连特点,设计出分别体现二分网络中同种类型节点间与异种类型节点间的亲密度关系。利用该亲密度关系分析和聚类节点,形成多个子社团,再通过社团间的关系参数,进一步合并子社团,以形成最终的社团结构。实验结果很好的反映了算法和参数设计的优越性,并能有效地检测出网络的二分社团结构。 本文设计和实现了针对不同网络所提出的三种不同的基于网络中节点间的亲密关系的社团检测算法,研究不断地深入、递进。其中基于关键节点的重叠社团划分方法和非对称亲密度的算法针对的是单分网络,而第三种算法则应用于二分网络。针对不同的网络,本文使用不同的评价参数进行分析,最终实验结果也表明算法设计的有效性和优越性。