基于大规模复杂网络的重叠社团检测算法研究

发布时间：2018-03-30 10:43

本文选题：网络聚类　切入点：重叠社团结构　出处：《安徽大学》2017年硕士论文

【摘要】：近年来,由于社交网络的发展和大数据时代的兴起,大规模复杂网络社团检测已成为研究热点之一。社团检测作为复杂网络研究中一项基础而又重要的工作,旨在挖掘网络中一组节点集合,这些集合内部的节点连接紧密,而集合之间的节点连接稀疏。然而在现实世界网络中经常存在一些节点可能会同时属于多个社团的情况,即重叠社团结构。因此,对重叠社团结构的检测更加重要且具有应用价值。随着网络科学的不断发展,许多复杂网络的规模甚至包含数百万数量的节点和数十亿条边。对如此大规模的复杂网络进行重叠社团挖掘一直是该领域内的难点之一。基于此,本文对大规模复杂网络重叠社团检测问题进行了深入研究,提出了一种基于弱团渗流思想的重叠社团检测算法。此外,为了解决数百万数量级的超大规模复杂网络重叠社团检测问题,本文还提出一种基于局部邻居信息的快速重叠社团检测算法。这两种算法均是以检测大规模复杂网络重叠社团结构为目的,相比较其他重叠社团检测算法,本文所提算法计算效率更快,社团检测精度更高。本文的主要研究工作如下:(1)本文提出了一种基于弱团渗流的重叠社团检测算法。k-团渗流方法是当前最常用的重叠社团检测算法之一,其基本思想是将社团结构定义为由一系列共享很多节点的完全连通子图组成。k-团渗流方法需要检测网络中所有k-团(即,k-clique),然而k-团的检测是NP完全问题,因此基于k-团渗流方法的时间复杂度很高。为了提高重叠社团检测算法在大规模复杂网络上检测重叠社团的效率和准确性,本文利用网络中的局部拓扑信息快速挖掘网络中的弱团。本文将弱团定义为由网络中两个关键节点及其公共邻居组合而成,由于仅仅利用节点的邻居信息,因此检测弱团要比检测k-团高效很多。同时在渗流过程中,提出新的相似度指标来衡量两个弱团之间的相似性,并以此来判断两个弱团是否应该合并,以提升算法的准确性。在新的相似度指标中不仅考虑了两个弱团之间共享的节点数目还统计了弱团之间边的连接数目。在LFR基准数据集和真实网络数据集上的实验结果表明,与现有几种重叠社团检测算法相比,基于弱团渗流的重叠社团检测算法在计算效率和发现重叠社团质量方面都具有明显优势。(2)本文提出一种基于局部邻居信息的快速重叠社团检测算法。随着社交网络的兴起和互联网时代的发展,目前复杂网络的规模变得越来越巨大。为了能够在数百万数量级这种超大规模复杂网络中检测重叠社团结构,本文提出了一种基于局部邻居信息的快速重叠社团检测算法,称之为OCLN(Overlapping Community detection by using Local-Neighborhood information)算法。OCLN 算法的基本思想在于首先利用网络中节点的内部度数和外部度数这些局部结构快速扩充社团,随后根据社团中每个节点的局部邻居信息在该社团中的贡献度计算节点的隶属度指标。从社团中删除掉一些隶属度较低的节点,提高算法的准确性。由于整个算法全部利用网络的局部结构,因此OCLN算法的时间复杂度为线性,即O(n+m),n为网络中节点的数目,m为边的数目。通过对LFR基准网络和大规模真实网络上的实验分析表明,OCLN算法在算法运行时间和NMI精度性能上都明显优于其他几种重叠社团检测算法。
[Abstract]:In recent years , because of the development of social networks and the rise of large data era , large - scale complex network community detection has become one of the hot topics . This paper proposes a fast overlapping community detection algorithm based on local neighbor information . With the rise of social network and the development of Internet age , the scale of complex network becomes more and more huge . In order to detect overlapping community structure in the large - scale complex network on the order of millions of orders , this paper proposes a fast overlapping community detection algorithm based on local neighbor information .

【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】