论文部分内容阅读
现实世界中存在诸多复杂网络,如生物网、科技网和社交网等。近年来复杂网络的研究吸引了来自计算机、物理、数学和生物等众多领域的研究者,已成为多学科交叉研究的热点之一。复杂网络聚类旨在揭示出复杂网络中真实存在的网络社团结构,主要包括对无符号网络、符号网络、有权网络和有向网络等不同类型的复杂网络进行社团结构检测。复杂网络之所以在当前的研究课题中具有如此重要的社会价值和应用价值,是因为对复杂网络的聚类分析,在对预测复杂网络的网络行为、分析网络拓扑结构和挖掘网络潜在功能方面起到积极作用。本文分别针对无符号网络和符号网络的社团结构检测问题进行了研究,提出了基于随机游走算法的社团结构检测方法。本文的主要研究工作如下:(1)在无符号网络中,根据社团结构是否明显,可以将社团分为强社团和弱社团等多种类型。现有的社团结构检测算法在挖掘强社团结构时,可以表现出优异的性能,在挖掘弱社团结构时,算法性能仍存在略微不足。本文基于假设---社团中的点游走到社团内其他点的概率大于游走到社团外点的概率,提出一种利用随机游走算法检测社团结构的方法。该方法从全局网络出发找到局部最大度节点,根据该局部最大度节点找到局部最小完全子图视为局部社团,并将网络中节点根据是否在局部社团中分为聚类节点以及未聚类节点。进而,利用基于随机游走的条件概率模型,计算未聚类节点属于每个社团的概率,并将该未聚类节点加入其最可能归属的社团。最后,对己聚类社团进行优化。在随机网络和真实网络上,利用NMI值和F1值作为算法性能衡量指标,对算法性能进行评估,并与经典的网络聚类算法进行了比较。实验结果表明该算法能够较好地检测出网络社团结构,尤其在检测弱社团结构方面,大大的提高了检测精度,相比其他社团结构检测算法具有明显优势。(2)在符号网络中,边既包括表示“友好、联盟”等关系的正向边,又包括表示“敌视、竞争””等关系的负向边。现有的部分符号网络社团结构检测算法由于未充分利用网络的负边信息,导致对社团的检测精度存在一定的影响。针对上述问题,本文提出一种基于网络中的正负边信息,利用随机游走模型,检测符号网络中社团结构的方法。该方法将网络中每个节点的正度和负度的绝对值之和加起来作为该节点的度。根据节点的度找到局部最小社团,以网络中节点是否在局部社团内,将节点分为聚类节点以及未聚类节点。利用随机游走算法计算出每个未聚类节点加入局部社团的正概率和负概率。通过比较正概率与负概率的大小来判断该未聚类节点是否加入局部社团或是否由该未聚类节点动态挖掘一个新的局部社团。利用社团优化方法对聚类社团进行优化,形成最终的网络划分结果。本文所提方法充分利用了符号网络中负边的信息,保证了算法的稳定性。在真实符号网络和随机符号网络上验证了本文所提方法的可行性和有效性。同时,与其他符号网络社团结构检测算法相比,该算法检测精度更高。