基于信息熵的复杂网络社团划分建模和验证

被引：16

作者：

邓小龙

王柏

吴斌

杨胜琦

机构：

[1] 北京邮电大学智能通信软件与多媒体北京市重点实验室

来源：

计算机研究与发展 | 2012年 / 49卷 / 04期

关键词：

信息熵; 复杂网络; 社团结构; 模块度; 社团划分;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

摘要：

社团结构是复杂网络最普遍和最重要的拓扑属性之一,社团结构的划分方法对分析复杂网络相关统计特性具有十分重要的理论意义.为了提高社团划分精度,提出了一种新的基于信息熵(information entropy)模块度的社团划分算法(简称IE算法).在有着确定社团结构的数据集和不确定社团结构的数据集上,通过选取Q值、社团划分个数、社团最大连通分量大小和强弱社团个数比例4个重要参数,将IE算法与两种最主要的基于模块度的划分算法GN(Girvan-Newman)和FastGN(Fast Girvan-Newman)进行对比,实验结果证明了IE算法在社团划分性能上优于GN和FastGN;将IE和其他7种最主要的经典社团算法进行时间复杂度分析,并在随机网络和真实网络上进行实验,结果表明该算法时间复杂度在GN与FastGN之间,时间复杂度小于GN而精确度优于GN,证明了在大多数数据集上IE算法的社团划分准确度优于传统基于点边比率的社团划分算法的准确度.

引用

页码：725 / 734

页数：10

共 8 条

[1] 复杂网络聚类方法 [J].

杨博 ;

刘大有 ;

金弟 ;

马海宾 .

软件学报, 2009, 20 (01) :54-66

[2] 基于信息瓶颈的社区发现 [J].

沈华伟 ;

程学旗 ;

陈海强 ;

刘悦 .

计算机学报, 2008, (04) :677-686

[3] 基于回溯机制的互联网AS拓扑的Betweenness算法 [J].

张国强 ;

张国清 .

计算机研究与发展, 2006, (10) :1790-1796

[4] Multidimensional views on mobile call network [J].

Yang, Shengqi ;

Wu, Bin ;

Wang, Bai .

FRONTIERS OF COMPUTER SCIENCE IN CHINA, 2009, 3 (03) :335-346

[5] Detecting community structure in networks [J].

Newman, MEJ .

EUROPEAN PHYSICAL JOURNAL B, 2004, 38 (02) :321-330

[6]

The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J] . David Lusseau,Karsten Schneider,Oliver J. Boisseau,Patti Haase,Elisabeth Slooten,Steve M. Dawson.Behavioral Ecology and Sociobiology . 2003 (4)

[7]

A faster algorithm for betweenness centrality*[J] . Ulrik Brandes.The Journal of Mathematical Sociology . 2001 (2)

[8] Authoritative sources in a hyperlinked environment [J].

Kleinberg, JM .

JOURNAL OF THE ACM, 1999, 46 (05) :604-632

← 1 →