复杂网络中基于稳定社团结构的社区发现研究

发布时间：2018-03-23 11:21

本文选题：复杂网络　切入点：社区结构　出处：《太原理工大学》2017年硕士论文

【摘要】：社会中存在的各种关系都可以抽象成网络拓扑,对网络拓扑学的研究一直是复杂网络研究课题中的重要方面,研究内容涉及到划分社区以及对网络中关键属性特征的研究。近来社区发现方法层出不穷,从研究方向上分有静态社区研究和动态社区研究,从研究社区发现的算法上分有全局视角和局部视角,从社区发现的评价机制上分有计算社区模块度和社区互信息,也有另辟蹊径将社区稳定性作为社区评价标准,社区发现结果的好坏直接反映出社区发现方法的优劣。本文针对复杂网络的社区发现算法,从全局和局部两个角度对社区的稳定性进行分析,并对社区发现的质量进行评价,主要研究内容包括以下两个方面:(1)研究了如何运用局部扩张社区的方法探测网络中存在的稳定社区结构。局部优化网络不需要掌握整个网络的信息规模,对于大型网络在计算复杂度上会更有优势。研究发现网络的稳定性对于社区结构的发现有很大影响,对同一个网络运用不同的局部优化算法得到的社区划分结果并不是完全一样的,其中对相同的部分深入分析,能够发现网络中存在的稳定社区以及常驻节点。同时引入了节点和网络稳定度计算的方法,提出一种可探测社区稳定结构的局部社区发现算法。最后通过在LFR集成网络和真实网络中验证表明该算法能够准确的发现网络中存在的核心稳定社区。(2)研究了如何从全局角度出发探索网络中存在的稳定社区结构。全局优化方法最早为网络中的社区发现提供了思路,如图划分,层次聚类等。由于整个网络的节点数和连边数特别多,而且很大部分连接并不紧密,本文首先对网络进行预处理,通过对网络的随机震荡,发现网络中的核心稳定社区。所发现的核心稳定社区只是网络的一部分不能充分反映网络的整体信息,基于此将发现的核心社团作为超点,与剩余节点合并构成一个新的网络,使用最大化模块度的算法,发现出具有模块度高且稳定性高的社区。最后在真实网络和集成网络上测试算法结果,发现经过网络预处理后的网络稳定值和模块度都较高,提高了网络的鲁棒性。综上,本文分别应用了全局优化和局部优化的思想对复杂网络中的社区结构进行研究,主要内容是发现网络中固有的核心稳定社区。最后通过实验证明了本文算法的有效性,对于社区发现算法的进一步研究提供了理论资料。
[Abstract]:All kinds of relationships in society can be abstracted into network topology. The study of network topology has always been an important aspect in the research of complex networks. The research involves the division of communities and the study of the characteristics of key attributes in the network. Recently, community discovery methods have been emerging in endlessly, including static community research and dynamic community research. The algorithm of community discovery is divided into global perspective and local perspective, the evaluation mechanism of community discovery includes computing community module degree and community mutual information, and there is a new way to use community stability as community evaluation standard. The community discovery results directly reflect the advantages and disadvantages of the community discovery methods. This paper analyzes the community stability from the global and local perspectives, and evaluates the quality of community discovery, aiming at the community discovery algorithm of complex networks. The main research contents include the following two aspects: 1) how to use the method of local expansion community to detect the stable community structure in the network. The local optimization network does not need to master the information scale of the whole network. It is found that the stability of the network has great influence on the discovery of community structure. The results of community partition obtained by using different local optimization algorithms for the same network are not exactly the same, in which the same part is deeply analyzed. The stable community and resident nodes in the network can be found. At the same time, the method of node and network stability calculation is introduced. A local community discovery algorithm with detectable community stability structure is proposed. Finally, the verification in LFR integrated network and real network shows that the algorithm can accurately find the core stable community in the network. He explored the stable community structure in the network from a global perspective. The global optimization method was the first to provide ideas for community discovery in the network. Such as graph partition, hierarchical clustering and so on. Because there are many nodes and connected edges in the whole network, and most of the connections are not close, this paper preprocesses the network first, and through the random oscillation of the network, The core stable community found in the network is only a part of the network that can not fully reflect the overall information of the network. Based on this, the core community found in the network is regarded as a super point and merged with the remaining nodes to form a new network. Using the algorithm of maximization of modularity, the community with high degree of modularity and high stability is found. Finally, the results of the algorithm are tested on real network and integrated network, and it is found that the network stability and modularity are higher after network preprocessing. The robustness of the network is improved. In summary, the idea of global optimization and local optimization is applied to study the community structure in complex networks. The main content is to find the core stable community in the network. Finally, the effectiveness of the algorithm is proved by experiments, which provides theoretical data for the further study of the community discovery algorithm.
【学位授予单位】：太原理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】