动态网络社团检测与演变分析方法的研究与实现

发布时间：2018-01-27 12:04

本文关键词： 动态网络局部优先标签传播重叠社团非重叠社团　出处：《西安电子科技大学》2015年硕士论文　论文类型：学位论文

【摘要】：复杂网络能够刻画现实世界中的大量现象,对复杂网络的研究受到了人们越来越多的关注。在现实世界中,复杂网络的结构并不是一成不变的,而是随着时间的变化而不断改变,从而形成了动态网络。动态网络对于刻画随时间变化的自然和社会现象具有极大的潜力,对动态网络的研究具有很强的现实意义。传统的动态网络社团发现算法往往分别对每一个时刻的网络快照进行聚类,然后分析相邻时刻社团之间的演化关系。这种方法的缺点之一就是没有考虑动态网络的时序特点,聚类仅仅基于单一时刻网络的结构,难以刻画社团的演化特性。基于这一观察,本文提出了一种局部优先的演化聚类方法LEOD以及一种基于标签传播的演化聚类算法DLPAE。对于LEOD,它针对某个时间点的快照网络,以网络中的每个结点为中心,首先在该节点的邻居网络上通过标签传播算法检测得到Ego社团。然后将这些局部Ego社团不断合并,从而得到网络的全局社团结构。在执行社团合并的过程中,通过引入社团相似度和关联度两个概念,并利用演化聚类框架,实现了局部优先的动态网络社团检测与演化分析。在DLPAE中,节点的社团标签由其邻居节点投票决定,且每个邻居节点对该结点都具有各自的影响力,我们称之为置信度。在聚类的过程中,节点的置信度的计算不仅要考虑当前时刻的网络结构,同时需要考虑前一时刻网络的结构,从而保证了聚类的时序特性。同时,对于每一个节点,DLPAE计算其节点的置信度方差,并按照节点置信度方差从大到小的顺序更新节点的标签,从而提高社团检测结果的稳定性与准确率。在DLPAE中,每个节点可以持有一个或者多个社团标签,该属性使得DLPAE能够同时发现动态网络中的重叠社团与非重叠社团。本文在真实和人工数据集上进行了大量的实验来评估本文提出算法的性能。实验结果表明,LEOD能够有效地检测出动态网络中的重叠社团结构,发现网络中潜在的信息;而DLPAE能够同时检测网络中的重叠社团和非重叠社团;和同类算法相比,本文提出的算法表现出了较好的性能。
[Abstract]:Complex networks can describe many phenomena in the real world, the research on complex networks have attracted more and more attention. In the real world, the complex network structure is not immutable and frozen, but with the change of time and change, thus forming a dynamic network. The dynamic network for characterization of natural and social phenomena change with time has great potential, has a strong practical significance to research on the dynamic network. The traditional dynamic network community discovery algorithm often separately for each time snapshot of the network clustering, and then analyze the evolutionary relationship between adjacent communities. One of the disadvantages of this method is that there is no consideration of the timing characteristics of dynamic network, clustering only based on the structure of a single network, difficult to characterize the evolution characteristics of society. Based on this observation, this paper proposes a local priority algorithm LEOD clustering method and a DLPAE. clustering algorithm based on evolution of label propagation for LEOD, aiming at a point in time snapshot of the network, with each node in the network as the center, first in the network through the neighbor node label propagation algorithm detected by the Ego society. Then the local Ego community continue to merge in order to get the global community structure of the network. In the implementation process of community integration, through the introduction of community similarity and correlation degree of the two concepts, and using the evolutionary clustering framework, realized the detection and analysis of the dynamic evolution of network community local priority. In DLPAE, nodes of the community label decided by its neighbor nodes and each neighbor vote. The node has its own node influence, we call confidence. In the process of clustering, calculate the confidence of the nodes should not only consider the current network structure, At the same time the need to consider the structure of the former network, thus ensuring the timing characteristics of clustering. At the same time, for each node, the variance of confidence in the calculation of DLPAE, and in accordance with the node reliability variance order from large to small update node labels, so as to improve the stability of community detection results and accuracy. In DLPAE, each node can hold one or more community label, this property makes DLPAE can also find out the overlapping community in dynamic networks and non overlapping community. Based on the real and artificial data sets on a large number of experiments to evaluate the performance of the proposed algorithm. The experimental results show that LEOD can effectively detect the overlapping community structure in dynamic networks, the network is found in the potential information; while DLPAE can simultaneously detect overlapping and non overlapping community network; and compared with other algorithms, this paper proposes The algorithm shows good performance.

【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【参考文献】