基于改进标签传播算法的社区挖掘研究

发布时间：2018-06-21 08:00

本文选题：复杂网络 + 社区挖掘　；参考：《中国矿业大学》2015年硕士论文

【摘要】：研究表明,复杂网络普遍存在社区结构,社区内部节点之间具有更加密切的联系。社区挖掘的目的是从复杂网络中挖掘出社区结构,进一步认识网络的拓扑结构和功能,探索网络的动力学特性及其演化机制。社区挖掘研究具有十分重要的理论意义和实际应用价值。本课题主要针对基于标签传播的社区挖掘算法准确率低、稳定性差的缺点,给出两种改进标签传播算法,有效利用网络节点中心性在社区挖掘中的作用,降低因平等对待每个节点,并按照随机顺序更新标签造成的社区划分错误和不稳定性。主要工作包括:第一,给出一种基于局部核心节点的标签传播算法,该算法利用节点度中心性定义局部核心节点,分别给这些节点及其邻居分配相同的标签,然后进行标签更新,实验结果表明该算法能有效提高社区挖掘质量及算法稳定性,同时维持标签传播算法的近线性时间复杂度;第二,给出节点的Leader Rank中心性和中心节点的概念,并给出一种基于Leader Rank中心节点扩展的标签传播算法,该算法首先找出局部Leader Rank中心节点,并以它们为标签传播源,以节点Leader Rank中心性为标签更新优先度,采用新的更新策略进行标签传播,从而挖掘出社区结构,实验结果表明,该算法相较于其他几种代表性算法的社区挖掘准确率及稳定性都得到大大提升。
[Abstract]:The research shows that there is a community structure in complex networks, and there is a closer relationship between the nodes within the community. The purpose of community mining is to excavate the community structure from complex networks, to further understand the topology and function of networks, and to explore the dynamic characteristics and evolution mechanism of networks. Community mining research has very important theoretical significance and practical application value. Aiming at the shortcomings of low accuracy and poor stability of the community mining algorithm based on label propagation, two improved label propagation algorithms are presented to effectively utilize the role of network node centrality in community mining. Reduce community partitioning errors and instability caused by equal treatment of each node and updating labels in random order. The main contributions are as follows: first, a label propagation algorithm based on local core nodes is proposed. The algorithm defines local core nodes by using node centrality, and assigns the same labels to these nodes and their neighbors, respectively. The experimental results show that the algorithm can effectively improve the quality of community mining and stability of the algorithm, while maintaining the near linear time complexity of the label propagation algorithm. Second, In this paper, the concept of Leader Rank centrality and central node is given, and a label propagation algorithm based on leader Rank central node extension is given. Firstly, the local leader Rank central node is found and used as label propagation source. The node Leader Rank centrality is regarded as the priority of tag updating, and the new updating strategy is adopted to propagate the tag, thus mining out the community structure. The experimental results show that, Compared with other typical algorithms, the accuracy and stability of community mining are greatly improved.
【学位授予单位】：中国矿业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5;TP301.6

【共引文献】