基于谱聚类的社区发现技术研究

发布时间：2018-05-22 08:04

本文选题：动态社区发现 + 随机游走　；参考：《兰州交通大学》2017年硕士论文

【摘要】：现实世界中的许多系统均可以抽象成复杂网络的形式,而且复杂网络还普遍存在着社区结构特征。社区结构为复杂网络研究提供了可行的切入点,它可为复杂网络的其它研究提供重要的基础,相应地社区发现已成为复杂网络研究的主要热点之一。传统的社区发现研究主要关注静态网络中的社区发现,但在实际场景中社区随时间变化的情况更为常见,且目前多数动态网络社区发现研究主要是针对非加权网络,而权值的缺失会造成网络划分的失真,因此展开动态加权网络中的社区发现的研究显得尤为重要。论文以动态加权网络为研究对象,针对传统谱聚类算法相似矩阵构建过程较复杂的问题,引入capocci算法和随机游走理论,设计并实现了一种加权谱聚类动态社区发现算法,最后采用实际数据集验证了该算法的有效性。主要研究内容包括:1.综述了动态社区发现的相关概念,总结谱聚类算法以及图分割理论的基本思想,研究了Yun Chi进化谱聚类算法,并分析了该算法在构建加权网络的相似矩阵时存在的不足。2.针对Yun Chi算法存在的问题,分析了标准割函数、马尔科夫链以及转移概率矩阵之间的关系,利用这些关系优化了Yun Chi算法的求解目标函数,使其能够直接处理加权邻接矩阵,从而简化了算法的流程。3.设计实现了一种加权谱聚类动态社区发现算法,并基于中科院自动化所发布的合作网络数据集进行了对比实验,结果验证了该算法的有效性。
[Abstract]:Many systems in the real world can be abstracted into the form of complex networks. Community structure provides a feasible entry point for the study of complex networks, which can provide an important basis for other studies of complex networks. Accordingly, community discovery has become one of the main hotspots in the research of complex networks. Traditional community discovery studies focus on community discovery in static networks, but community changes over time are more common in actual scenarios, and most of the current dynamic network community discovery studies focus on unweighted networks. The lack of weights can lead to the distortion of network division, so it is very important to study community discovery in dynamic weighted networks. Aiming at the complex process of constructing similarity matrix of traditional spectral clustering algorithm, capocci algorithm and random walk theory are introduced to design and implement a weighted spectral clustering dynamic community discovery algorithm. Finally, the validity of the algorithm is verified by the actual data set. The main research contents include: 1. This paper summarizes the related concepts of dynamic community discovery, summarizes the basic ideas of spectral clustering algorithm and graph segmentation theory, studies the Yun Chi evolutionary spectral clustering algorithm, and analyzes the shortcomings of this algorithm in constructing the similarity matrix of weighted networks. Aiming at the problems of Yun Chi algorithm, the relations among standard cut function, Markov chain and transition probability matrix are analyzed. By using these relations, the solving objective function of Yun Chi algorithm is optimized, which enables it to deal with the weighted adjacency matrix directly. Thus simplifying the algorithm flow. 3. A dynamic community discovery algorithm based on weighted spectral clustering is designed and implemented. The validity of the algorithm is verified by a comparative experiment based on the cooperative network data set published by the automation institute of the Chinese Academy of Sciences.
【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13;O157.5

【参考文献】