基于三角模体的社团发现算法研究与应用

发布时间：2018-01-02 18:23

本文关键词：基于三角模体的社团发现算法研究与应用　出处：《南京理工大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着复杂网络领域的发展,尤其是在互联网高速发展下的社交网络,涌现了一批新颖并且重要的发现,吸引了各个学科的众多研究者投入其中。社团结构作为它的普遍存在的拓扑特性之一,对于它的探索有助于揭示网络结构与功能之间的关系,因此发现网络中的社团结构具有重要的理论和实际意义。本文主要针对现有社团发现算法进行研究,文中介绍并分析了现有的基于边表示网络的社团发现算法,针对其计算瓶颈的问题,设计了一种基于三角模体和期望极大的社团结构发现(Community structure discovery based on triangular motifs and expectation-maximization,CSDTME)模型的社团发现算法。本文的主要工作如下:(1)针对现有采用边表示网络的社团发现算法的计算瓶颈问题,本文设计了一种基于三角模体的社团发现算法。本文通过三角模体对观测网络进行表示,简化网络结构假设,为设计有效的算法提供基础。通过对三角模体生成过程建模,设计了一个基于三角模体和期望极大的社团结构发现(Community structure discovery based on triangular motifs and expectation-maximization,CSDTME)模型,以此来模拟观测网络,并提出了相应的社团发现算法,在算法中采用全三角模体和两边三角模体作为计算对象,在保证网络真实结构的同时,通过减少计算对象来提高算法的效率,返回节点的社团混合隶属度及社团间的链接概率,并通过实验证明了文中提出算法的可行性和有效性。(2)针对基于CSDTME模型的社团发现算法执行效率问题,本文设计了一种基于CSDTME模型的社团发现算法的改进方法。基于CSDTME模型的社团发现算法在时间效率上已经有了很大的改进,但是通过对该算法的进一步的研究,发现可以在时间和空间上还可以对该算法进行更进一步的改进,可以更快速的发现网络中的社团结构。基于CSDTME模型的社团发现算法在对参数求解的过程中在时间和空间上存在的问题,分别提出了在空间和时间上的应对策略,主要是通过减少迭代次数及中间变量的存储,来提高算法的执行效率。最后通过实验,验证了改进后的基于CSDTME模型的社团发现算法的可行性和有效性。并在此算法的基础上,设计并实现了一个简单的基于CSDTME模型的社团划分系统。
[Abstract]:With the development of the complex network field, especially the social network with the rapid development of the Internet, a number of novel and important discoveries have emerged. Community structure is one of its ubiquitous topological characteristics, and its exploration will help to reveal the relationship between network structure and function. Therefore, it is of great theoretical and practical significance to discover the community structure in the network. This paper mainly focuses on the existing community discovery algorithm, and introduces and analyzes the existing community discovery algorithm based on edge representation network. Aiming at the problem of calculating bottleneck. A community structure discovery method based on triangular motifs and expectation maximization is proposed. Community structure discovery based on triangular motifs and. Expectation-maximization. CSDTME-based community discovery algorithm. The main work of this paper is as follows: 1) aiming at the bottleneck problem of the existing community discovery algorithm using edge representation network. In this paper, a community discovery algorithm based on triangular motifs is designed. In this paper, the observation network is represented by triangular motifs and the assumption of network structure is simplified. It provides the foundation for designing effective algorithm. Modeling the process of triangular motif generation. A community structure discovery based on triangular motifs and expectation maximization is designed. Community structure discovery based on triangular motifs and. Expectation-maximization. CSDTME-based model is used to simulate the observation network, and the corresponding community discovery algorithm is proposed. In the algorithm, the full triangle motifs and the two side triangular motifs are used as the computing objects. While ensuring the real structure of the network, the efficiency of the algorithm is improved by reducing the computing objects, and the community membership degree and the link probability between the communities are returned. The experiment proves the feasibility and effectiveness of the proposed algorithm. 2) aiming at the efficiency of community discovery algorithm based on CSDTME model. This paper designs an improved method of community discovery algorithm based on CSDTME model. The community discovery algorithm based on CSDTME model has been greatly improved in terms of time efficiency. But through the further study of the algorithm, it is found that the algorithm can be further improved in time and space. Community structure in the network can be found more quickly. Community discovery algorithm based on CSDTME model in the process of solving the parameters in the process of time and space problems. Respectively put forward in space and time coping strategies, mainly by reducing the number of iterations and the storage of intermediate variables to improve the efficiency of the algorithm. Finally, through experiments. The improved community discovery algorithm based on CSDTME model is proved to be feasible and effective. A simple community partition system based on CSDTME model is designed and implemented.
【学位授予单位】：南京理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】