基于节点依赖的社团划分算法研究

发布时间：2018-06-05 02:27

本文选题：复杂网络 + 社团划分　；参考：《山东师范大学》2017年硕士论文

【摘要】：作为对现实生活中复杂系统的抽象和建模,复杂网络的发展为理解现实生活中的复杂关系提供了很好的借鉴,通过对复杂网络的研究获得对象之间的共同特性。社团结构是复杂网络重要的局部特征,社团结构是指网络中节点之间相互连接比较紧密的子网络。社团结构的研究可以挖掘网络中潜在的小团体,通过对社团结构中节点连边关系的研究,从而预测网络潜在的行为,因此,社团结构的发现具有重要的理论意义和实际意义。本文就复杂网络中社团发现问题进行了相关研究,介绍了相关的社团发现算法,在分析相关算法的基础上提出了基于节点依赖的标签传播社团发现算法,本文所作的主要工作如下:(1)首先对相关的社团发现算法进行了介绍,重点对局部社团发现算法进行了分析,基于局部信息的标签传播算法因为划分速度较快而被广泛应用,但该算法同时也存在不稳定性、划分质量差等问题。本文针对该算法的缺点,根据节点之间的依赖关系提出了基于节点依赖的标签传播算法,改变节点的初始化策略,先对网络中的节点依据节点依赖度进行聚类,得到初始社团,然后再借助于标签传播算法对网络中的社团进行调整,从而改变了原来算法中的不稳定性,加快了算法收敛性,并在真实网络上对该算法进行了验证。(2)在第二部分中,基于收集到的专利合作企业之间的合作数据,构建了专利合作网络,并对网络的相关结构特征进行了分析,对网络的演化模型进了推导,并基于本文的社团划分算法对专利合作网络进了社团分析,对得到的社团结构在现实中意义进行了分析,进一步说明了本算法的所具有的划分的优势。同时也说明了本算法对于局部连接紧密的网络划分的效果较好。
[Abstract]:As the abstraction and modeling of complex systems in real life, the development of complex networks provides a good reference for understanding the complex relationships in real life, and obtains the common characteristics of objects through the study of complex networks. Community structure is an important local feature of complex network. Community structure refers to a network in which nodes are closely connected with each other. The study of community structure can excavate the potential small groups in the network, and predict the potential behavior of the network by studying the relationship between nodes and edges in the community structure. Therefore, the discovery of the community structure has important theoretical and practical significance. In this paper, the problem of community discovery in complex networks is studied, and the related community discovery algorithms are introduced. Based on the analysis of the related algorithms, a node-dependent label propagation community discovery algorithm is proposed. The main work of this paper is as follows: (1) first of all, the related community discovery algorithm is introduced, and the local community discovery algorithm is analyzed. The label propagation algorithm based on local information is widely used because of the high speed of partitioning. However, the algorithm also has some problems, such as instability, poor partition quality and so on. In view of the shortcomings of the algorithm, a label propagation algorithm based on node dependency is proposed according to the dependency relationship between nodes, which changes the initialization strategy of nodes. Firstly, the nodes in the network are clustered according to the degree of dependency, and the initial community is obtained. Then, with the help of tag propagation algorithm, the community in the network is adjusted, which changes the instability of the original algorithm, speeds up the convergence of the algorithm, and verifies the algorithm on the real network. Based on the cooperation data between patent cooperative enterprises, the patent cooperation network is constructed, and the related structure characteristics of the network are analyzed, and the evolution model of the network is deduced. Based on the community partition algorithm in this paper, the community analysis of patent cooperative network is carried out, and the significance of the community structure in reality is analyzed, which further explains the advantages of this algorithm. At the same time, it also shows that the algorithm has a good effect on the partitioning of locally connected networks.
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP301.6;O157.5

【参考文献】