基于带权图的层次化社区并行计算方法

被引：20

作者：

林旺群

卢风顺

丁兆云

吴泉源

周斌

贾焰

机构：

[1] 国防科学技术大学计算机学院

来源：

软件学报 | 2012年 / 23卷 / 06期

关键词：

社区发现; 带权图; 并行计算; 社会网络; 层次化树;

D O I：

暂无

中图分类号：

TP391.41 [];

学科分类号：

080203 ;

摘要：

提出了一种基于带权图并行分解的层次化社区发现方法,该方法采用图划分的方式定义社区结构,并在这种社区结构之上实现了社会网络社区发现并行算法P-SNCD(parallel social network community discovery).P-SNCD算法有效地避免了传统的基于"模块度"的社区发现方法倾向于发现相似规模社区的弊端.同时,该算法能够以可扩展的方式,在处理器规模为O(hmn)或O(hn2)的条件下,以并行计算时间复杂度为O(logn)高效地挖掘大规模复杂社会网络中社区密度为h的社区,其中,n为社会网络节点数,m为边数,h为用户指定的任意社区密度.所提出的算法对用户参数输入要求简单,从而使得算法具有较强的实用性.充分的实验数据验证了所提出算法的精确性和高效性.

引用

页码：1517 / 1530

页数：14

共 10 条

[1]

复杂网络社区挖掘—基于聚类融合的遗传算法[J]. 何东晓,周栩,王佐,周春光,王喆,金弟.自动化学报. 2010(08)

[2] 一种基于拓扑势的网络社区发现方法 [J].

淦文燕 ;

赫南 ;

李德毅 ;

王建民 .

软件学报, 2009, 20 (08) :2241-2254

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

杨博 ;

刘大有 ;

金弟 ;

马海宾 .

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

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

沈华伟 ;

程学旗 ;

陈海强 ;

刘悦 .

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

[5]

Fast unfolding of communities in large networks[J] . Vincent D Blondel,Jean-Loup Guillaume,Renaud Lambiotte,Etienne Lefebvre.Journal of Statistical Mechanics: Theory and Experiment . 2008 (10)

[6]

Clustering, community partition and disjoint spanning trees[J] . Cun-Quan Zhang,Yongbin Ou.ACM Transactions on Algorithms (TALG) . 2008 (3)

[7]

Finding communities in linear time: a physics approach[J] . F. Wu,B. A. Huberman.The European Physical Journal B . 2004 (2)

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

Newman, MEJ .

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

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

Kleinberg, JM .

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

[10]

Resolution limit in community detection .2 Fortunato S,Barthelemy M. Proc.the National Academy of Sciences . 2007

← 1 →