2019年8月 计算机工程与设计 Aug. 2019
第 40 卷 第 8 期 COMPUTER ENGINEERING AND DESIGN Vol. 40 No. 8
基于节点覆盖范围的影响力最大化算法高菊远，王志晓！芮晓彬，何
［候梦男
（中国矿业大学计算机科学与技术学院，江苏 徐州
221116
）
摘 要：为解决传统影响力最大化算法时间复杂度高！选出节点过于集中！导致富人俱乐部现象（tchcklb）的问题！提
出一种基于节点覆盖范围的影响力最大化算法！将节点覆盖范围作为节点选取的中心性评价指标
，有效避免选取种子节点
时节点过于集中。为进一步减少运行时间！对该算法进行CELF优化。在各种规模网络上的实验结果表明！该算法能够有
效选取最具影响力的节点。关键词：社交网络；影响力最大化；节点覆盖范围；富人俱乐部现象；种子节点识别
中图法分类号：TP393 文献标识号：A 文章编号
：1000-7024 （2019
） 08-2211-05
doi： 10. 16208/j. issnl000-7024. 2019. 08. 018
NodecoveragebasedalgorithmforinfluencemaximizationGAO Ju-yuan
, WANGZhixiao, RUI Xiao-bin, HEJing, HOU
Meng-nan
(School of Computer Science and Technology & China University of Mining and Technology & Xuzhou 221116 & China)Abstract： The time-consumption of traditional influence maximization algorithm is high and the selected nodes
are concentrated.
So&thesAopeofinfluenAeislimited.Tosolvetheseproblems&aninfluenAemaximizationalgorithmbasedonnodeAoveragewas proposed.ThenodeAoveragewasseleAtedastheAentralevaluationindex.Inthisway&itavoidedseednodesfrombeingAonAen- trated.To deArease running time&the proposed algorithm was optimized using CELF strategy.Experimental results show that theproposedalgorithmAanseleAtthemostinfluentialnodesmoreefeAtivelyinvarioussizesofnetworks.
Key words： social network； influence maximization； node coverage； rich-club;
seed node identification
0引言随着网络的发展，在线社交网络带给市场营销各种可
能。利用在线社交网络进行病毒营销（）,往往会以极小的 成本获得巨大影响，影响力最大化是解决这类问题的关 键其可广泛应用于市场营销策略、广告定向传播、舆 情预测和控制⑶’影响力最大化问题是社交网络分析领域的热点问题4' 国内外研究学者提出许多求解影响力最大化问题的算法, 主要集中于基于传播的算法和基于拓扑结构的算法。基于 传播的算法其时间复杂性高，在较大规模网络中无法运行。 而传统的基于拓扑结构的算法未能很好解决节点在传播过 程中的重复邻居的问题，使得算法的精度较低且适应性差。本文针对选出的节点在传播过程中有大量的共同邻居, 导致影响范围有限的问题，提出了基于节点覆盖范围的影 响力 大 算法 （nodeAoveragealgorithm, NCA）, 果表明，本算法相比于其它基于拓扑结构的算法时间代价 极低，并具有很高的影响范围。
1相关工作Kempe等5证明了影响力最大化问题的优化是NP- hard问题，
提出了一个基于传播的爬山贪心算法
general
greedy algorithm，该算法有着很好的准确度，但因为每一
次选取最大影响范围的种子需要遍历整个网络，在网络规
模扩大时&效率很低。
优化的
贪心算法
（Cost-Effective La-
zyForward, CELF）6解决了运行效率问题，该算法利用函
数的子模特性，减少了节点在影响力范围评估上的时间，
实验结果表明CELF在选择节点时有近700倍的速度提升。
收稿日期：201806-25；修订日期：2018-08-13
基金项目：国家自然科学基金项目（61402482）；中国博士后基金项目（2015T80555）；江苏省博士后基金项目（1501012A）作者简介：高菊远（1995 -）,女&辽宁丹东人&硕士研究生&研究方向为影响力最大化；王志晓（1979 -）,男&河南平顶山人&博士&
副教授&研究方向为社交网络分析；芮晓彬（1992-）,男&江苏徐州人&博士研究生&研究方向为谣言传播动力学；何嬪
（1994-）
,女&
江苏常州人&硕士研究生&研究方向为动态社区发现；候梦男（1993 -）,女&湖北黄冈人&硕士研究生&研究方向为层次化社区发现°
E-mail:
gaojuyuanu@163.com• 2212
-
计算机工程与设计
2019 年
然而，CELF仍然需要花费几个小时来运行几万个节点的
网络。Cheng等□提出的StaticGreedy算法以保存静态快照
和计算边际增益的方法来优化运行时间，但在大规模网络
中仍存在运行时间长的问题。以上这几种算法均为基于传 播的影响力最大化算法，可以看出这种算法需要进行影响 力传播过程的优化。另一种算法为基于拓扑结构选择算法，其关注于网络
的拓扑结构或中心性，
该类算法不需要考虑影响力范围过
程的最优，所以运行时间很短。但是影响范围相对较小，
且对于不同的网络结构表现不稳定。在早期的研究中，将
度，距离8等作为评价指标。DegreeDiscount算法
9对度
进行改进，提升了度指标的效果，但提升有限'Lu等(0)
通过寻找局部度值最大节点，提出了 LIR算法。若网络比 较平均，该算法选出的节点可能太过于边缘，
严重影响传
播范围。Nguyen
等〔⑴
将选出的第一批种子节点重新排序
筛选出不相邻的节点作为最终的种子节点，
提出了
proba
bility-based multi-hop
diffusion
算法(下文简称 pBmH 算
法)，节点的重新筛选操作将消耗时间，若能直接选出符合 要求的节点将大大缩短时间复杂度。上述两类算法各有优缺点，基于传播的算法能够保证
算法的精度，但算法效率低，不适合大规模网络；基于拓 扑结构的算法具有较高的运行效率，但影响范围不及基于
传播的算法
，且在不同的网络结构上表现不
稳
定
'
Rich-club 高基于 算法性能的
有效途径。
Rich-club现象是选出的节点在传播过程中有
大量的共同邻居，这将严重限制了影响范围。如基于度 的影响力最大化选择策略，选择出的具有较大度的节点
间有许多的共同邻居，导致传播过程中只能影响到有限 的节点。
LIR算法虽解决了 Rich-club现象
，
但在某些网
络中得到的影响范围有限。pBmH算法需要对选出的种 子节点进行重新的筛选，过滤掉种子节点集合中互为邻
居的节点。如果在选取种子节点的时候能够将重叠的邻居忽略, 着重考虑种子节点的覆盖范围，就能够有效地避免
Rich-
club现象。因此本文则从节点覆盖范围的角度进行研究。
2算法描述及其优化本文利用节点覆盖范围来更好地解决Rich-club现象，
计算种子集合与其它节点的共同覆盖范围，选择具有更大
覆盖范围的节点作为种子节点，
重复此操作直至选够所需
要数量的种子节点，并根据CELF对更新节点覆盖范围进 行了时间上的优化，提高算法效率
。
节点的覆盖范围是指节点能直接影响到的范围，
即为
邻居节点集合。N为节点'的邻居集合，两个节点的覆盖
范围N为
Nv = N, u
N
因此种子节点集合S的覆盖范围
N,如下所示
N, = N⑴ u N …u — $ = S ,1，'…i # S
)
算法1： NCA
算法
输入：网络
#=($%
)，种子节点数3
： 子 S(1) Initialize S = arg max{ Degree, & # $
}
(2) for i = 2 to 3 do
(3) for all j#V do
(4) N, = N, U 凡
#
5) endMor
(6) select u = arg
max
{
N& & # V\S
};
(7) S= S U {
"
};
(8) endfor
9) return
S
假设网络#= (V,E)有”个节点，m条边。计算节点 覆盖范围的复杂度为0($)，需要选取
3个种子节点，
则
NCA算法的复杂度为O(n)。
每次选择一个种子节点后都需要重新更新网络中其它 节点的覆盖范围，这个过程比较费时，故使用了
CELF优
化策略衡量节点覆盖范围的增益效果来对NCA算法进行优
化。选出一个种子节点后，其它节点的覆盖范围会与种子
节点集合有重叠。因此，其它节点的覆盖范围增益将变小。
如若更新后节点的增益比其它未更新的节点增益大，此时
不需要更 其 的 益值
子
集合即可。节点&的覆盖范围增益计算公式如下
gain” = N, U N” / S — N,
其中，N”为节点”的邻居集合，N为种子集合S的节点覆 盖范围，S为网络中不属于种子节点的集合。
算法2: NCA优化算法NCA
_ CELF
输入：网络
G=(V，E)，种子节点数3
: 子 S(1) Initialize ur(”)= 0 // cur 为更新标志，1
表
更 0 未更
;
(2) for al ” # V
do
(3) gain, = d” ]/ d”
为节点v的度值
(4) endfor
(5) Initialize S = arg max{gain, ” # V
}
(6) gain, =— 1
//
增益置负
(7) for
i=2to3
do
(8) select u = arg mox{gain&
”
# V
\ S
}
(9) if (ur(u) = = 1
)
(10)
S =S u
{u
}
(11) / ' update seed node coverage N
,
'
/
(12)
gain
u =—1