基于三角结构的局部社团发现方法

发布时间：2017-12-31 02:40

本文关键词：基于三角结构的局部社团发现方法　出处：《南京大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着真实世界的复杂网络规模变大,对于网络全局信息很难把握,一些经典的社团发现方法的时间复杂度也随之变高。因此,一种基于网络局部信息的局部社团发现方法被提出来。局部社团发现方法是一种不依靠复杂网络的全局信息进行社团挖掘,而是基于一个初始节点或社团,通过某个节点或者边的局部信息进行扩散的方法。局部社团发现方法相比于其他方法更加适用于大型的复杂网络。论文主要工作如下:1.本文分析得出目前大多数的局部社团发现算法中存在以下两点问题:选取初始种子的原始位置对社团扩散的最终结果具有重要的影响;选取初始种子后,初始社团扩散阶段的速度较慢;2.由于选取的初始种子原始位置对社团扩散的最终结果具有重要的影响,为了选取的初始种子原始位置更具中心性,使得社团在扩散阶段更加稳定,本文基于核心三角的种子选取方法,提出了一种基于核心三角的局部社团发现方法TLCD算法。通过实验结果表明该算法对于局部社团的社团划分在多数情况下优于其他算法;3.为了解决初始社团扩散阶段速度较慢的问题,本文提出了一种基于多三角群组扩张的局部社团发现方法MTCD算法,该算法通过寻找核心节点的多三角群组形成初始社团,再经过加入遗漏节点以及合并冗余社团的步骤形成基本的社团结构,最后处理重叠节点得到最终的社团划分。本文分别在人工合成网络和真实复杂网络上对MTCD算法进行实验分析,实验结果表明该算法在局部社团发现上具有一定的优势。
[Abstract]:With the scale of the real world complex network becomes large, for the global network information is difficult to grasp, some of the classic community detection method of time complexity becomes high. Therefore, a local community network based on local information discovery method is proposed. The local community detection method is a global information society does not rely on the complex network of mining, but an initial node or community based on the method of diffusion through the local information of a node or edge. The local community discovery method compared with other methods is more suitable for the large-scale complex network. The main work is as follows: 1. this paper analyzes the current most of the local community and found the following two problems the algorithm has an important impact on the final results of the original position of the selected community diffusion initial seed; selecting initial seeds, the initial community diffusion stage The speed is slow; 2. as the end result of the selection of the initial seed association diffusion original position has important influence to the selection of the initial seed original location more central, make society more stable in the diffusion stage, the core of the triangular seed selection method based on a local community discovery based on triangular core method of TLCD algorithm. The experimental results show that the algorithm for the local community of communityclassification in most cases is better than other algorithms; 3. in order to solve the initial community diffusion stage is slow, this paper presents a method that MTCD algorithm for local communities of triangle group expansion based on the algorithm by finding the core nodes in multi triangle the group formed the initial community, then add the missing node and combining the redundant associations step to form the basic structure of society, finally the overlapping section Finally, we get the final community partition. In this paper, we analyze the MTCD algorithm on synthetic networks and real complex networks respectively. The experimental results show that the algorithm has some advantages in finding local communities.

【学位授予单位】：南京大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】