一种基于k-核的社会网络影响最大化算法

被引：59

作者：

曹玖新 ^{[1
,2
]}

董丹 ^{[1
,2
]}

徐顺 ^{[1
,2
]}

郑啸 ^{[1
,2
,3
]}

刘波 ^{[1
,2
]}

罗军舟 ^{[1
,2
]}

机构：

[1] 计算机网络和信息集成教育部重点实验室(东南大学)

[2] 东南大学计算机科学与工程学院

[3] 安徽工业大学计算机学院

来源：

计算机学报 | 2015年 / 38卷 / 02期

关键词：

社交网络; 影响最大化; 独立级联模型; k-核; 社会计算;

D O I：

暂无

中图分类号：

TP393.0 [一般性问题];

学科分类号：

摘要：

社会网络中影响最大化问题是指在特定传播模型下,获取一个指定大小的节点集合,使得该集合在网络中的聚合影响力最大.针对贪心算法运用于大规模社会网络时存在效率低下且不可扩展的问题,文中提出基于核数层次特征和影响半径的启发式算法——核覆盖算法(Core Covering Algorithm,CCA).该算法首先引入k-核概念,基于k-核分解求出每个节点的核数,然后根据核数分布的层次性,引入节点的影响半径参数,最后综合核数和度数两个属性,找出影响力节点集合.文中在两个数据集和两种传播模型上进行了实验,结果表明:(1)在传播概率较大的独立级联模型(Independent Cascade Model,IC)下,CCA能取得比现有启发式算法更优的影响效果;(2)在三价(TRIVALENCY Model,TR)模型下,CCA的表现也同样优于其他启发式算法;(3)与其他启发式算法相比,CCA的运行时间更少.

引用

页码：238 / 248

页数：11

共 3 条

[1] Identification of influential spreaders in complex networks [J].

Kitsak, Maksim ;

Gallos, Lazaros K. ;

Havlin, Shlomo ;

Liljeros, Fredrik ;

Muchnik, Lev ;

Stanley, H. Eugene ;

Makse, Hernan A. .

NATURE PHYSICS, 2010, 6 (11) :888-893

[2]

The anatomy of a large-scale hypertextual Web search engine[J] . Sergey Brin,Lawrence Page.Computer Networks and ISDN Systems . 1998 (1)

[3] THRESHOLD MODELS OF COLLECTIVE BEHAVIOR [J].

GRANOVETTER, M .

AMERICAN JOURNAL OF SOCIOLOGY, 1978, 83 (06) :1420-1443

← 1 →