基于局部信息的复杂网络社团挖掘算法研究

发布时间：2018-01-12 18:17

本文关键词：基于局部信息的复杂网络社团挖掘算法研究　出处：《燕山大学》2015年硕士论文　论文类型：学位论文

【摘要】：近年来,网络社团结构发现算法研究及应用成为多学科间共同研究的热点。尽管取得了一定的成果,但是现有的社团发现算法时间复杂度、聚类质量和算法稳定性仍不尽如人意,亟待解决的难题如下:在数据量大、拓扑结构复杂的网络中提高挖掘社团结构算法的聚类精度;重叠网络中的重叠结点有效划分;在缺少先验知识的前提下,划分社团结构结果的一致性。针对以上问题,本文在前人的研究基础上,提出了基于亚团贪婪扩张的非重叠社团划分算法,针对重叠社团结构网络提出了基于超边贪婪扩张的社团发现算法,并采用标准的虚拟数据集分别做对比实验,论文的主要内容如下。首先,概述了复杂网络的相关知识,并着重介绍了社团发现算法研究的研究现状,包括当下典型的社团发现算法,以及这些算法各自的特点和存在的不足。其次,在相对成熟的非重叠网络社团发现研究中,由于网络数据量较大、社团结构复杂导致算法的聚类精度下降,算法划分社团结果不一致。本文在基于局部信息算法的基础上提出亚团贪婪扩张的划分算法,该算法使用亚团做算法种子,有效的提高了算法聚类进度。然后,针对重叠复杂网络中社团重叠区域结点不易划分的难题,本文使用边作为度量工具,在基于局部信息贪婪扩张的算法研究工作之上,通过筛选网络中可聚度较高的边组成超边,并作为社团发现算法的种子,提出了基于超边种子的贪婪扩张算法,算法的聚类精度较高。最后,对本文提出的两个算法,分别在复杂网络中的标准数据集上做了实验,并和几个经典算法做对比,并在算法聚类精度和稳定性方面进行了分析。
[Abstract]:In recent years, the network community structure discovery algorithm research and application become interdisciplinary common research focus. Although achieved certain results, but the existing community detection algorithm time complexity, clustering quality and stability of the algorithm is still not satisfactory, problems to be solved are as follows: in the large amount of data and improve the accuracy of the clustering mining algorithm of community structure the topological structure of complex networks; overlapped nodes effectively divide in overlapping networks; in the premise of the lack of prior knowledge, the consistency of the partition of community structure. Aiming at the above problems, this paper based on previous studies, the sub group greedy expansion non overlapping partitioning algorithm based on overlapping community structure of the network super edge detection algorithm was proposed based on the greedy expansion of community, virtual data and using the standard set respectively do a comparative experiment, the main contents of this paper are as follows. First of all And summarizes the related knowledge of complex network, and emphatically introduces the research status of algorithm research found associations, including the typical community discovery algorithm, and their characteristics and shortcomings of these algorithms. Secondly, in the non overlapping community network discovery research is relatively mature, because a large amount of data, complex community structure lead to a decline in accuracy of clustering algorithm, the algorithm is not consistent results. Based on the partition of community partitioning algorithm based on local information on the algorithm of sub group proposed greedy expansion, the algorithm uses sub group algorithm seed, effectively improve the clustering progress. Then, in order to solve the problem of overlapping in complex network community overlap region node not classified in this paper, using the edge as a measurement tool, based on the algorithm of local information greedy expansion, poly degree higher edge composition by screening in super network The edge, and as a community discovery algorithm of seeds, propose the greedy expansion algorithm based on Super Edge seeds, high clustering accuracy algorithm. Finally, the two algorithms presented in this paper, the standard data respectively in the complex network set to do the experiment, and compare several classic algorithms, and analyzed in algorithm of clustering accuracy and stability.

【学位授予单位】：燕山大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【参考文献】