摘要
社团结构是复杂网络最普遍和最重要的拓扑属性之一,社团结构的划分方法对分析复杂网络相关统计特性具有十分重要的理论意义.为了提高社团划分精度,提出了一种新的基于信息熵(information entropy)模块度的社团划分算法(简称IE算法).在有着确定社团结构的数据集和不确定社团结构的数据集上,通过选取Q值、社团划分个数、社团最大连通分量大小和强弱社团个数比例4个重要参数,将IE算法与两种最主要的基于模块度的划分算法GN(Girvan-Newman)和FastGN(Fast Girvan-Newman)进行对比,实验结果证明了IE算法在社团划分性能上优于GN和FastGN;将IE和其他7种最主要的经典社团算法进行时间复杂度分析,并在随机网络和真实网络上进行实验,结果表明该算法时间复杂度在GN与FastGN之间,时间复杂度小于GN而精确度优于GN,证明了在大多数数据集上IE算法的社团划分准确度优于传统基于点边比率的社团划分算法的准确度.
Community structure is the most basic and important topologic characteristic of complex network and community detection method is therefore significant to its character statistics.A new theoretic model of modularity Q based on information entropy（IE） with low complexity and better accuracy is proposed to promote clustering accuracy.IE algorithm reaches better community detecting results than GN and FastGN algorithm on network with definite community structure and unidentified community structure,while computation complexity declines.The simulation results mentioned above show that IE will find more accurate community structure than traditional methods of edge rate on most classic complex network dataset.According to simulation result compared with the seven main classic community detecting methods on simulated random networks and real networks,information entropy based modularity is more accurate than traditional modularity of edge rate.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2012年第4期725-734,共10页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60905025
90924029
61074128)
关键词
信息熵
复杂网络
社团结构
模块度
社团划分
information entropy
complex network
community structure
modularity
community detection
