基于仿射传播的复杂网络社区发现算法研究

发布时间：2018-11-09 19:49

【摘要】：许多研究表明,复杂网络中普遍存在着社区结构,即社区内部的节点联系紧密,而社区之间的节点联系则相对稀疏。复杂网络内部的社区结构具有十分重要的理论意义和应用价值,可以帮助人们理解复杂网络的功能、发现复杂网络中潜在的规律和预测复杂网络的行为。本课题主要围绕复杂网络社区发现和仿射传播算法进行了研究,包括以下三个方面的内容:首先,提出一种基于结构相似度仿射传播的社区发现算法(SS-FAP)。该算法首先选取结构相似度作为节点之间的相似性度量,并采用一种优化的方法来计算相似度矩阵;其次将计算得到的相似度矩阵作为输入,采用快速仿射传播算法进行聚类;最后得到最终的社区结构集合。实验结果表明,无论在模拟网络上还是在真实网络上,SS-FAP都具有很好的社区发现能力,能够发现高质量的社区结构。其次,提出一种基于模块度仿射传播的社区发现算法(MAP)。该算法的主要思想是将模块度函数Q嵌入到AP算法的迭代过程中,基于模块度优化来得到最优的社区发现结果。实验结果表明,与传统的LPA算法、FN算法、BGLL算法以及原始的AP算法对比,MAP算法能够更加有效地发现网络中的社区结构。最后,实现一个社区发现算法原型系统,该原型系统主要实现了SS-FAP算法、MAP算法、LPA算法以及4种社区发现评价标准,分别是规范化互信息、FM指标、准确率与模块度,并且利用力引导布局算法来可视化显示网络。
[Abstract]:Many studies have shown that there is a common community structure in complex networks, that is, the nodes within the community are closely connected, but the node connections between the communities are relatively sparse. The community structure within complex networks has very important theoretical significance and application value, which can help people understand the functions of complex networks, discover the potential laws in complex networks and predict the behavior of complex networks. This paper mainly focuses on the complex network community discovery and affine propagation algorithms, including the following three aspects: first, a community discovery algorithm based on structural similarity affine propagation (SS-FAP) is proposed. Firstly, the structural similarity is selected as the similarity measure between nodes, and an optimized method is used to calculate the similarity matrix. Secondly, the calculated similarity matrix is used as input, and the fast affine propagation algorithm is used to cluster. Finally, the final community structure set is obtained. The experimental results show that SS-FAP has good community discovery ability and high quality community structure both on simulated and real networks. Secondly, a community discovery algorithm (MAP). Based on modular affine propagation is proposed. The main idea of the algorithm is to embed the modular degree function Q into the iterative process of the AP algorithm and obtain the optimal community discovery result based on the modularity optimization. The experimental results show that compared with the traditional LPA algorithm, FN algorithm, BGLL algorithm and the original AP algorithm, the MAP algorithm can find the community structure in the network more effectively. Finally, a community discovery algorithm prototype system is implemented. The prototype system mainly implements SS-FAP algorithm, MAP algorithm, LPA algorithm and four community discovery evaluation criteria, which are normalized mutual information, FM index, accuracy and module degree, respectively. And the force-guided layout algorithm is used to visualize the network.
【学位授予单位】：中国矿业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【参考文献】