Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (25): 148-150.DOI: 10.3778/j.issn.1002-8331.2009.25.045

• 数据库、信息处理 • Previous Articles     Next Articles

New community structure discovery algorithm of simple graph

HU Jian1,DENG Zhi-juan1,YANG Bing-ru2   

  1. 1.School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou,Jiangxi 341000,China
    2.School of Information Engineering,University of Science and Technology Beijing,Beijing 100083,China
  • Received:2008-05-14 Revised:2008-07-28 Online:2009-09-01 Published:2009-09-01
  • Contact: HU Jian

一种新型简单图社区结构发现算法

胡 健1,邓志娟1,杨炳儒2   

  1. 1.江西理工大学 信息工程学院,江西 赣州 341000
    2.北京科技大学 信息工程学院,北京 100083
  • 通讯作者: 胡 健

Abstract: The automatic search and community discovery in large and complex network has important practical applications.The hypergraph based model and cluster algorithm in community structure discovery is applied.This paper introduces the concept of Edge Clustering Coefficient(ECC) to community structure discovery of simple graph and proposes an algorithm of community discovery based on ECC.Enron e-mail data sets will be test data sets.Through comparative analysis of algorithm,it is proved that this algorithm can significantly improve the time complexity.

Key words: community structure, community discovery, edge clustering coefficient

摘要: 在大型复杂网络中自动搜寻或发现社区具有重要的实际应用价值。该文把超图模型以及基于此的聚类算法应用到社区结构发现的领域。对于简单图的社区结构发现,引入边凝聚系数的概念,提出了基于边凝聚系数的社区发现算法。将安然邮件数据集作为测试数据集,通过算法对比分析,证明该算法在时间复杂度上可以提高一个数量级。

关键词: 社区结构, 社区发现, 边凝聚系数

CLC Number: