许成伟,邹晓红,2,*

(1.燕山大学 信息科学与工程学院,河北 秦皇岛 066004;2.燕山大学 河北省计算机虚拟技术与系统集成重点实验室,河北 秦皇岛 066004)

0 引言

Domingos和Richardsom等[1-2]在2001年首次提出有关社交网络影响力最大化问题(Influence maximization),简称IM问题。IM问题是指在网络图中选定k个种子节点作为信息源点,使其在特定信息传播模型下进行信息传播,目的是在一定时间内尽可能多地影响并激活其他的节点。到目前,IM问题大多数是基于静态图进行分析研究的,但针对具有动态性特征的社交网络,不能简单地将其表示为静态图模型进行处理,比如生物信息网络、通信网络、道路交通网络等网络结构,节点间只在某段时间或某一时间发生交互作用,存在一定的时间关系特性,并且具有明显的交互顺序,具有这样特征的网络被称为时序网络[3-4]。鉴于时序社交关系更能真实地反映现实中信息传播的实际情况,一些学者[5-7]便开始在时序网络中展开IM问题的研究,并提出一系列基于时序网络的影响力最大化算法。

k个种子节点的选取是研究IM问题最主要的目标之一,但却没有考虑种子节点在实际应用的过程中,可能会因自身某些原因或各种外界因素影响而无法投入使用。例如,有着高影响力的明星并不愿意代言某一产品,或是在代言过程中触犯解约条例被解约而无法继续代言等诸多现实问题,本文将这种现象称之为种子节点失效问题,称这样的节点为失效种子节点。种子节点失效问题所带来的影响与损失是不可忽视的,这种变化对组合效果最优的种子节点集所能发挥出影响效果造成了严重破坏,信息的扩散与传播将会受到极大影响。……