基于局部扩张的社团发现算法研究

发布时间：2018-06-01 23:31

本文选题：复杂网络分析 + 社团发现　；参考：《南京大学》2016年硕士论文

【摘要】：当今世界复杂网络无处不在,网络型系统已深深嵌入到我们生产生活的过程之中。复杂网络分析越来越受到学术界和工业界的关注。复杂网络中的社团结构揭示了网络中的节点个体之间边连接关系之上更高层的交互关系,研究社团关系能够使研究者更好地理解一个复杂网络的结构及功能。目前,已经有许多学者将社团发现应用于多种实际应用场景之中。因此,社团发现对于复杂网络理论研究及实际应用都具有非凡的意义。本文就社团发现中的局部社团发现相关问题进行研究,分析目前局部社团发现算法的共性及存在的问题,并提出两种新的局部社团发现算法,论文主要工作如下：1)分析了多种局部社团发现算法,发现其在局部社团扩张过程中存在多种节点划分错误问题,指出错误的原因在于算法无法区分真实社团的内部边及外部边,为了解决该问题,本文基于边聚类系数提出了一种区分内部边外部边的边度量方法,该度量应用于本文提出的两种局部社团发现算法之中。2)为了解决目前局部社团发现算法普遍存在的枢纽节点及长尾结构之上的社团划分错误问题,基于本文提出的改进的边聚类系数,提出了局部社团发算法CELCD,算法使用一种简洁有效的种子边选取方法,并提出了一种新的适应度函数。本文分别在真实世界复杂网络及计算机生成网络上对CELCD算法进行了实验分析,实验结果表明该算法社团划分效果优于对比算法。3)基于单一适应度函数的局部社团发现算法在社团扩张选取节点时存在一些局限性；且在局部社团扩张初期,社团结构还未稳定,此时基于内部边外部边比值进行定义的适应度函数易发生扩张至社团外部节点的情况。基于以上分析,本文提出了基于多目标节点适应度函数思想的局部社团发现算法MOLCD,该算法使用两个节点适应度函数,结合帕累托最优的集合计算来选取加入社团的候选节点。实验分析表明MOLCD算法减少了算法迭代次数,提高了效率,且划分效果在多数情况下优于CELCD及其他对比算法。
[Abstract]:In today's world, the complex network is ubiquitous, and the network system has been embedded in the process of our production and life. Complex network analysis has attracted more and more attention from academia and industry. The community structure in a complex network reveals a higher level of interaction over the edge connection relationship between nodes and individuals in the network, and the study of community relations can enable researchers to better understand the structure and functions of a complex network. At present, many scholars have applied community discovery to many practical application scenarios. Therefore, community discovery is of great significance for the theoretical research and practical application of complex networks. In this paper, the problems related to local community discovery in community discovery are studied, the commonness and existing problems of local community discovery algorithms are analyzed, and two new local community discovery algorithms are proposed. The main work of this paper is as follows: (1) this paper analyzes several local community discovery algorithms, and finds that there are many node division errors in the process of local community expansion, and points out that the reason of the error lies in the fact that the algorithm can not distinguish the inner and outer edges of the real community. In order to solve this problem, an edge measurement method based on edge clustering coefficients is proposed to distinguish internal and external edges. This metric is applied to the two local community discovery algorithms proposed in this paper. Based on the improved edge clustering coefficient proposed in this paper, a local community distribution algorithm (CELCDD) is proposed. The algorithm uses a simple and effective seed edge selection method, and a new fitness function is proposed. In this paper, the CELCD algorithm is experimentally analyzed on real world complex networks and computer generated networks, respectively. The experimental results show that the algorithm has some limitations in selecting nodes for community expansion, and in the initial stage of local community expansion, the algorithm is superior to the contrast algorithm .3) the local community discovery algorithm based on a single fitness function has some limitations. The structure of the community is not stable, and the fitness function defined based on the ratio of the inner edge and the outer edge is easy to expand to the external node of the community. Based on the above analysis, this paper proposes a local community discovery algorithm, MOLCDD, which is based on the idea of multi-objective node fitness function. The algorithm uses two node fitness functions and combines Pareto optimal set calculation to select candidate nodes to join the community. The experimental results show that the MOLCD algorithm reduces the number of iterations and improves the efficiency, and the partition effect is better than that of CELCD and other contrast algorithms in most cases.
【学位授予单位】：南京大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP301.6;O157.5

【参考文献】