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

An Algorithm Based on Triangle Ring for Detecting Community Structure

作　　者：李学强[1] 钟大伟[1] 孙圣民[1] LI Xue-qiang,ZHONG Da-wei,SUN Sheng-ming（Shenyang Sport University Department of Information Technology,Shenyang 110102,China）

机构地区：[1]沈阳体育学院体育信息技术系,辽宁沈阳110102

出　　处：《电脑知识与技术》2013年第3期1540-1542,1550,共4页Computer Knowledge and Technology

摘　　要：在大型复杂网络中自动搜寻或发现社区具有重要的实际应用价值。该文把超图模型以及基于此的聚类算法应用到社区结构发现领域。对于简单图的社区发现,引入了边凝聚系数和三角环等概念,提出了基于三角环的社区结构发现方法。通过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.

关 键 词：社区结构 三角环 边凝聚系数 社会网络 

分 类 号：TP393[自动化与计算机技术—计算机应用技术;自动化与计算机技术—计算机科学与技术]