【作者】 李勇；

【导师】 吴建设； 岳博；

【作者基本信息】 西安电子科技大学 ， 工程硕士（专业学位）， 2015， 硕士

【摘要】 复杂网络作为数据挖掘领域中一个重要的方向,近年来受到国内外学者的广泛关注。在过去的几十年里,针对其中的社区检测、链路预测、动力学等问题已经有了大量的研究。本文着重于研究社区检测算法,对其中一些典型算法进行了分析,针对Dense Shrink算法进行改进,提出了Improved Dense Shrink算法;将用于一般网络的模型扩展到符号网络,提出了一种基于网络动力学的社区检测算法;并且针对符号网络的特点,提出了一种基于相似度的社区检测方法。具体如下:(1)本文通过对多种相似度进行分析,提出了简化卡兹相似度Skatz(Simplified Katz),使得在不影响相似度精确性的前提下,缩短计算所需的时间。由于在Dense Shrink算法中最耗时的步骤合并微社区与合并密度对相比并不总具有优势,且使用信息量更全的相似度可以减少微社区出现的概率。因此,本文通过使用SKatz相似度和用合并密度对替代合并微社区步骤提出了Improved Dense Shrink算法。(2)本文通过对一般网络所用模型进行分析,引入负耦合系数对网络模型进行扩展以适应符号网络的特点。其中,正耦合系数使具有正连接节点的相位趋于靠近;负耦合系数使具有负连接节点的相位趋于远离。同时对同步方程中的系数(正、负耦合系数)的取值以及其对同步结果的影响进行了分析。针对符号网络,提出了一种基于网络动力学的社区检测算法。(3)本文通过对符号网络的边进行分析可知,其具有符号属性和连接属性。符号属性对应边权值的正负,表示节点间积极性或消极性的关系;连接属性对应边权值为零或非零,表示节点间是否存在关系。根据这两种属性,形成了符合符号网络特点的相似性指标,结合模块度优化思想提出了一种基于相似度的社区检测算法。更多还原

【Abstract】 As one of the important direction in the field of data mining, complex networks have received extensive attention of a number of scholars both at home and abroad. In the past years, considerable research has been conducted on community detection, link prediction and dynamic problems. This paper mainly focuses on community detection algorithm, in which the typical community detection algorithm is analyzed, the Dense Shrink algorithm is improved and the Improved Dense Shrink algorithm is proposed. Meanwhile, this paper extends the model used in general network to signed network, then proposes a dynamics-based community detection algorithm; Finally, according to the characteristics of signed network, we propose a similarity-based community detection algorithm. The research includes:In this paper, we propose the simplified Katz similarity through the analysis of varies similarities, which not only have little influence on accuracy, but also can shorten the time of calculation. Compare to merge dense pair, the most time-consuming step-- merge micro community does not always perform well in the Dense Shrink algorithm, and using the similarity of more information can reduce the probability of micro communities. Therefore,this paper puts forward the Improved Dense Shrink algorithm by using SKatz similarity and replacing the step of merging micro communities with merging dense pairs.This paper introduces the negative coupling coefficient which extends the network model to adapt to the characteristics of signed network through the analysis of the general used network model. The positive coupling coefficient is to make the nodes with positive connection tend to be closer; and the negative coupling coefficient is to make the nodes with negative connection far away from each other. At the same time, the value of the coefficient(both positive and negative coupling coefficient) in the synchronization equation and its influence to the synchronization result are analyzed. According to the characteristics of signed network, we propose a dynamics-based community detection algorithm.In this paper, the edges in signed network is analyzed, from which the symbol properties and connection properties are found. The symbol properties correspond to the positive and negative attribute of the weights of the edges, which means whether the relationship between the nodes is positive or negative; and the connection properties correspond whether the weights of the edges is zero or nonzero, the property represents the existence of the relationship between nodes. According to the two properties, a similarity matched the characteristics of signed network is formed, then we propose the similarity-based community detection algorithm combined with the idea of modularity optimization.更多还原