用于社团发现的Girvan-Newman改进算法

被引：12

作者：

朱小虎 ^{[1
,2
]}

宋文军 ^{[1
,2
]}

王崇骏 ^{[1
,2
]}

谢俊元 ^{[1
,2
]}

机构：

[1] 南京大学计算机软件新技术国家重点实验室

[2] 南京大学计算机科学与技术系

来源：

计算机科学与探索 | 2010年 / 12期

关键词：

社会网络分析; 社团结构发现; Girvan-Newman算法; 贪心策略;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

070104 ;

摘要：

为了克服Girvan-Newman算法运行效率的不足,提出了一个基于modularity极值近似的社团发现算法MEA。该算法采用modularity增量作为社团结构的度量,使用贪心策略获得最优社团分划的近似解。通过理论分析,并在实际的数据集上进行实验验证,结果表明MEA算法是快速、有效的。

引用

页码：1101 / 1108

页数：8

共 5 条

[1]

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

[2]

An Information Flow Model for Conflict and Fission in Small Groups[J] . Wayne W. Zachary.Journal of Anthropological Research . 1977 (4)

[3]

A Set of Measures of Centrality Based on Betweenness[J] . Sociometry . 1977 (1)

[4] EFFICIENCY OF A GOOD BUT NOT LINEAR SET UNION ALGORITHM [J].

TARJAN, RE .

JOURNAL OF THE ACM, 1975, 22 (02) :215-225

[5]

Scientific collaboration networks. Ⅱ. Shortest paths, weighted networks, and centrality .2 Newman MEJ. Physical Review E Statistical, Nonlinear and Soft Matter Physics . 2001

← 1 →