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

摘要

在资本市场中,根据交易者联系的密切程度,可以划分出众多团体,从而产生特定的社团结构.社团结构探测是一项非常重要而具有挑战性的工作,已经引起来自不同领域学者的广泛关注.然而,极少有多项式时间算法能够快速、准确地探测社团结构.基于著名的模块化设计优化理论,用新颖的k强度关系代表两个节点之间的耦合距离这一想法随之产生.社团结构探测算法使用基于k强度矩阵的广义模块度测量.为了得到最优社团数量,一种新颖的无参数结构得以使用,该结构使用特定转移矩阵的特征值之差作为社团划分边界.最后,将此算法应用于基准网络和实际网络,以评估其有效性.理论分析和实证结果表明,该算法可以快速、准确地探测社团,且易于扩展至大型实际网络.