基于线图的复杂网络重叠社团发现算法研究

发布时间：2019-05-21 14:07

【摘要】：在重叠社团发现算法中,基于线图的重叠社团发现算法是最近几年兴起的比较新的领域,具有广阔的研究前景,线图是将边看作研究对象来发现复杂网络社团结构的一种方法,线图的最大优势就是可以利用非重叠社团发现算法发现重叠社团结构。本文就是基于线图提出了一种重叠社团发现算法。在真实世界中,很多复杂网络的社团个数是未知的,这使得一些依赖于社团个数先验知识的算法无法使用。因此,本文将基于拉普拉斯矩阵的Jordan型图特征分析应用到线图中,来获取线图社团个数的先验知识。然后,将基于拉普拉斯矩阵的谱聚类应用到线图中,通过拉普拉斯矩阵的特征向量将网络中的边映射到欧氏空间,欧氏空间中每个特征向量分量中的元素对应了线图中的节点,并且选择其中的两列构成特征向量空间,同时计算特征向量之间的相似度。最后,有了社团个数先验知识的支撑与铺垫,一方面选择K-means聚类算法对特征向量进行聚类来确定社团的划分结果,既利用了K-means算法简单快速的优点,又符合K-means算法依赖社团个数先验知识的特点,相得益彰;另一方面,使用层次聚类算法对特征向量进行聚类,在得到层次聚类树状图后,依据社团个数的先验知识对层次聚类树状图进行切割,从而确定最终的社团划分结果。实验结果表明,本文算法能够实现对复杂网络重叠社团结构的发现,比相关算法具有更好的性能。
[Abstract]:Among the overlapping community discovery algorithms, the overlapping community discovery algorithm based on graph is a relatively new field rising in recent years, and has a broad research prospect. Graph is a method to find the complex network community structure by taking the edge as the research object. The biggest advantage of graph is that the non-overlapping community discovery algorithm can be used to find the overlapping community structure. In this paper, an overlap community discovery algorithm based on graph is proposed. In the real world, the number of societies in many complex networks is unknown, which makes some algorithms that depend on the prior knowledge of the number of communities unusable. Therefore, in this paper, the Jordan type graph feature analysis based on Laplace matrix is applied to the graph to obtain the prior knowledge of the number of graph societies. Then, the spectral clustering based on Laplace matrix is applied to the graph, and the edges in the network are mapped to Euclidean space by the eigenvector of Laplace matrix. The elements in each eigenvector component in Euclidean space correspond to the nodes in the graph. Two columns are selected to form the feature vector space, and the similarity between the feature vectors is calculated at the same time. Finally, with the support and foreshadowing of the prior knowledge of the number of communities, on the one hand, the K-means clustering algorithm is selected to cluster the feature vectors to determine the segmentation results of the community, which makes use of the advantages of simple and fast K-means algorithm. It also accords with the characteristic that K-means algorithm depends on the prior knowledge of the number of communities and complements each other. On the other hand, the hierarchical clustering algorithm is used to cluster the feature vector. After the hierarchical clustering tree is obtained, the hierarchical clustering tree is cut according to the prior knowledge of the number of communities, so as to determine the final community partition results. The experimental results show that the proposed algorithm can discover the overlapping community structure of complex networks, and has better performance than the related algorithms.
【学位授予单位】：兰州大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5

【相似文献】