【作者】 黄勋；

【导师】 杨茂林；

【作者基本信息】 华中科技大学 ， 计算机技术， 2016， 硕士

【摘要】 当前,社区发现是人们研究网络和分析网络的热点。社区结构信息能够帮助人们清晰了解网络组成,认知网络中节点间的相似性。社区挖掘对于复杂网络的认知和应用具有重要意义。虽然,对于静态网络的社区发现算法的研究已经取得了不少的成果。但是,大部分静态网络发现算法在面对动态网络的时候存在时间复杂度过高的问题。标签传播算法是一种快速,简单的社区发现算法。不过,该算法具有准确率低,随机性高等缺点。论文分析了原始标签传播算法缺点的产生原因,指出了目前主要标签传播算法的改进算法在社区核心选择上存在的问题,给出了标签传播算法的改进算法PR-LPA。PR-LPA算法基于影响力模型提出,以Page Rank算法计算各节点影响力数值。各节点基于影响力模型向周边邻居节点传播标签形成社区结构。针对动态图的社区挖掘,论文提出算法D-PR-LPA。D-PR-LPA算法根据已有社区结构对存在变动的节点进行分析,得出需要进行标签更新的部分节点,随后对部分节点进行更新。实验表明,本文的PR-LPA社区发现算法能够得到令人满意的社区划分效果,D-PR-LPA算法在面对复杂动态网络时,能够以更少的时间获得和PR-LPA算法十分相近的社区挖掘效果。更多还原

【Abstract】 At present, Community detection is a focus of research and analysis of network.Community information can help people clearly understand the network structure, cognize the similarity between nodes in a network. In a word, the discovery of community structure in a network is of great significance to the cognition and application of complex network.Although, the research of community discovery algorithm for the static network has made many achievements, most of the them exists the problem of high time complexity when they are faced the dynamic network.Label propagation algorithm is a rapid and simple community discovery algorithm.However, this algorithm has shortcomings like low accuracy and high randomness. This paper analyses causes of the faults of original label propagation algorithm and the problems of key nodes in those improved algorithms. Then this paper put forward PR-LPA which is an improved label propagation algorithm. PR-LPA is based on influence model,and use PageRank algorithm to calculate the influence value of all nodes. Each node spread its label to the neighbors, basing on the influence model. In view of dynamic network, this paper puts forward D-PR-LPA algorithm. According the existing community structure and those changed nodes, D-PR-LPA algorithm can analysis and make sure those nodes which label need to be updated.Then the algorithm will update those nodes.Experiments show that PR-LPA algorithm can get satisfactory effect. And in facing dynamic network, the D-PR-LPA algorithm can get a very similar results to to PR-LPA,only using relatively less time.更多还原