一种基于三角环的社区发现算法

摘要

在大型复杂网络中自动搜寻或发现社区具有重要的实际应用价值.该文把超图模型以及基于此的聚类算法应用到社区结构发现领域.对于简单图的社区发现,引入了边凝聚系数和三角环等概念,提出了基于三角环的社区结构发现方法.通过Zachary网络的实例验证和算法的对比分析,证明了该算法在时间复杂度上能提高一个数量级.%The automatic search and community discovery in large and complex network has important practical applications. The hyper graph based model and cluster algorithm in community structure discovery is applied. This paper introduces the con?cept of Edge Clustering Coefficient and Triangle Ring to community structure discovery of simple graph and proposes an algo?rithm of Community discovery based on Triangle Ring. Through validation of Zachary network and comparative analysis of algo?rithm, it is proved that this algorithm can significantly improve the time complexity.