基于耦合强度的多项式时间社团探测算法  

Polynomial Time Community Detection Algorithm Based on Coupling Strength

作　　者：杨卓璇 马源培 严冠 YANG Zhuo-xuan;MA Yuan-pei;YAN Guan(School of Economics and Management,North China Electric Power University,Beijing 102206,China;School of Management Science and Engineering,Central University of Finance and Economics,Beijing 100081,China)

机构地区：[1]华北电力大学经济与管理学院,北京102206 [2]中央财经大学管理科学与工程学院,北京100081

出　　处：《计算机科学》2020年第S01期102-107,共6页Computer Science

基　　金：国家自然科学基金(71401233);北京市自然科学基金(9182015)。

摘　　要：在资本市场中,根据交易者联系的密切程度,可以划分出众多团体,从而产生特定的社团结构。社团结构探测是一项非常重要而具有挑战性的工作,已经引起来自不同领域学者的广泛关注。然而,极少有多项式时间算法能够快速、准确地探测社团结构。基于著名的模块化设计优化理论,用新颖的k强度关系代表两个节点之间的耦合距离这一想法随之产生。社团结构探测算法使用基于k强度矩阵的广义模块度测量。为了得到最优社团数量,一种新颖的无参数结构得以使用,该结构使用特定转移矩阵的特征值之差作为社团划分边界。最后,将此算法应用于基准网络和实际网络,以评估其有效性。理论分析和实证结果表明,该算法可以快速、准确地探测社团,且易于扩展至大型实际网络。In capital markets,groups can be divided according to how closely traders are connected,resulting in specific community structures.Community structure detection is one of the most interesting issues in the study of social networks.However,there are few polynomial time algorithms that can detect the community structure quickly and accurately.Inspired by the famous theory of modularity design optimization,in this paper,the idea of using a novel k-strength relationship to represent the coupling distance between two nodes is proposed.Community structure detection algorithm is presented using a generalized modularity measure based on the k-strength matrix.To obtain the optimal number of communities,a new parameter-free structure is adopted,which uses the difference of eigenvalues of specific transition matrix as the boundary of community classification.Finally,the algorithm is applied on both benchmark network and real network.Theoretical analysis and experiments show that the algorithm can detect communities quickly and accurately,and is easy to be extended to large scale real networks.

关 键 词：社团结构 社会网络 耦合距离 k强度关系 最优社团数量 多项式时间 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]