基于时序图的替补种子节点挖掘算法研究

许成伟,邹晓红,2,*

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

0 引言

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

k个种子节点的选取是研究IM问题最主要的目标之一,但却没有考虑种子节点在实际应用的过程中,可能会因自身某些原因或各种外界因素影响而无法投入使用。例如,有着高影响力的明星并不愿意代言某一产品,或是在代言过程中触犯解约条例被解约而无法继续代言等诸多现实问题,本文将这种现象称之为种子节点失效问题,称这样的节点为失效种子节点。种子节点失效问题所带来的影响与损失是不可忽视的,这种变化对组合效果最优的种子节点集所能发挥出影响效果造成了严重破坏,信息的扩散与传播将会受到极大影响。因此,当网络中出现这样的问题时,为了继续维持网络影响力最大化的最初目标,及时在网络中挖掘寻找种子节点的替补节点是十分必要的。因此,本文对时序图中替补种子节点挖掘问题展开了研究,并提出了一种高效的可适用于大规模时序图的替补种子节点挖掘算法(Two-stage substitute seed mining algorithm,TSSM),算法TSSM将替补种子节点的挖掘分为启发式预选与贪心式终选两个阶段,预选阶段从失效种子节点入手,选取一部分具有最优局部替代效果的节点构建备选替补节点列表。终选阶段,通过计算备选替补节点的边际效应,进一步筛选出能够使网络全局影响力达到最优的替补种子节点。

1 相关工作

针对种子节点失效问题,Lappas等[8]首先提出了效应者的概念,效应者是指在网络中近似有相同传播效果的节点,所提算法实现了在特定群体内,效应者的影响力覆盖范围接近种子节点的传播效果。之后Li等[9]正式提出在社会网络中寻找种子节点继任者这一概念,充分考虑了替补节点现实意义,选择在种子节点的邻居节点中寻找继任者,马茜等[10]认为这种方法抛弃了影响力最大化的初衷,难以保证网络影响力全局最优,对此提出应该从网络整体出发去寻找替补种子节点,以达到网络全局影响力最大化的目的,以此为出发点,首次将该问题定义为在影响力最大化问题中挖掘替补种子节点(Substitutes discovery in influence maximization,SDIM),并给出了全局静态贪心算法(Global static greedy,GSG)。Xu等[11]针对算法GSG时间复杂度过高的问题,又提出了预选式贪心算(Pre-selected-based substitutes mining algorithm,P-S),该算法主要思想是在选取k个种子节点的同时便预先选定n个替补种子节点。以上2种算法筛选出的替补节点和失效种子节点的位置无关性较大,算法没有较好的实际应用意义,对此Sun等[12]提出将失效种子节点的邻居节点与网络中一定数量最大度的节点一起构成后继节点集,然后利用模拟退火的方法去处理后继结点与原种子节点的最优组合问题,以获取最终的新种子节点集,由于模拟退火算法收敛速度慢,该算法的时间效率较低。

2 基本概念

2.1 时序图

定义1时序图(Temporal graph,也被称为Temporal network[13]),给定网络GT(V,E,TE)表示节点间具有时序关系的社交网络有向时序图。其中V表示节点的集合,E表示边的集合,TE表示图中所有节点之间存在联系时刻的集合,T(u,v)表示节点u和v之间存在联系的时刻的集合,T(u,v)∈TE,u,v∈V。

时序图是指在边上带有时间戳的动态有向图,且节点间的边会随着边上时间戳的到来而被激活,它表示两节点在此刻时间存在联系。图1为一个简单的时序图,边上的数字代表着时间戳,以节点A、B为例,T(A,B)={1,3,5}表示节点A分别在1,3,5时刻与节点B存在联系并以传播概率P(A,B)尝试将其激活。

图1 时序图Fig.1 Temporal graph

2.2 问题定义

定义2SDIM问题:给定一个网络G,使用一定的IM算法找到含有k个节点的种子集合S,在种子节点工作过程中,出现t个无法继续工作的失效种子节点构成集合S1,目的是在剩余非种子节点中找出t个替补种子节点,构成替补种子节点集S2。新种子节点集S″=S2∪(S-S1),|S″|=k,使得最终在网络中的传播结果与原种子节点集S的传播结果的差值最小,即

其中,Inf(S)表示种子集S影响力大小。

由于S是提前给定的且认为是最优的,所以目标函数也可记作

定理1SDIM问题是NP难问题。

时序图替补种子节点挖掘是在影响力最大化算法基础上延伸出的新问题,是在已知种子节点集的基础上作进一步探究。SDIM问题可看作在VS中继续挖掘t个种子节点的问题,因此同种子节点挖掘算法一样,SDIM问题也是NP难的问题。

3 算法设计

在不脱离网络影响力最大化的前提下,考虑时序图中信息传播的时序性,提出了时序图两阶段替补种子节点挖掘算法TSSM,算法将时序图中替补种子节点的挖掘分为预选与终选两个阶段。

3.1 构建失效种子节点替补列表

在普通静态图中,可以根据节点与失效种子节点含有公共一阶后继节点的个数去评估节点的替补效果,例如在图2(a)中,节点A为失效种子节点,若网络中存在节点α,其与节点A含有全部公共一阶后继节点,则此种情况下节点α便可在种子节点A失效后较好地代替其继续工作。

图2 替补种子节点对信息传播路径的重构Fig.2 Reconstruction of information dissemination path by substitute seed nodes

由于时序图中信息传播存在时序性,信息在时序图中的传播过程与静态图不同,例如在图2(b)中,当种子节点A被移除后,其后继一阶信息传播路径,即时序边E(A,B)、E(A,C)直接遭到破坏,同时由于时序图中邻近两条边之间具有一定的时序关系,因此后继第二阶信息传播路径也间接受到影响,当替补节点α取代失效节点A后,其将会重新构建节点A后继两阶范围内的信息传播路径。在图2中可以看到只有边E(α,B)、E(B,D)、E(B,E)三条路径满足信息传播的时序关系,是信息可达的有效路径,而节点α在7时刻与节点C联系,此时节点C分别已经在更早的时刻4、6与其后继节点完成了联系,故节点α只能将信息传播至节点C而无法到达节点F、G,所以此时边E(C,F)、E(C,G)为信息不可达的无效路径。由此可见时序图中备选替补节点的寻找不能只关注公共一阶后继节点的个数,应从对失效种子节点后继二阶范围内构建有效可达信息传播路径的条数去衡量替补节点替补效果的优劣,基于此给出节点可替代度的概念如下。

定义3可替代度R:指网络中非种子节点α在失效种子节点A的后继两阶范围内重新构建的可达有效信息传播路径的条数,表示为RA(α) ,

式(3)给出了时序图中节点α对于失效种子节点A可替代度的计算方法,其中{O(A)∩O(α)}表示节点α与失效种子节点A的公共一阶后继节点集,|E(v,w)|min(T(α,v))≤max(T(v,w))|表示替补节点α在失效种子节点A后继第二阶构建的满足信息传播时序关系的可达有效信息传播路径的条数。为保证替补节点与原失效节点有着较强的位置关联性,且一个理想的替补节点的影响范围应与失效种子节点的影响范围有着较高的重合程度,即替补节点应对失效种子节点影响范围内的节点有着较高的激活率,这样才能达到最佳的替补效果。因此,算法在预选阶段从失效种子节点局部入手,将节点可替代度的大小作为备选替补节点的筛选依据为失效种子节点构建替补列表,具体步骤如下:

1) 确定节点可替代度的计算范围

算法只需要对与失效节点含有关联的其他节点进行遍历计算即可,这个关联是指与失效种子节点含有公共一阶后继节点的所有非种子节点,将满足这种关联关系的所有节点组成集合Q,该集合即为网络节点可替代度的计算范围,这样便有效地缩小了节点的筛选范围,避免了对网络所有节点均进行遍历的冗余计算问题。

2) 进行节点可替代度计算

采用式(3)所给出的节点可替代度计算方法,对步骤1)中所得节点集Q中所有节点进行遍历计算,并记录备选节点的可替代度值大小。

3) 为失效种子节点构建替补列表

替补列表容量过大可能会存在局部替代效果较差的节点进入替补列表,影响最终替补节点质量,且会导致算法在终选阶段存在冗余计算;容量过小则可能会导致替代效果较好的节点被过滤掉。综上所述,算法在预选阶段启发式地选取步骤2)中计算所得可替代度值最大的前50个节点为失效节点构建替补列表List。

3.2 筛选最终替补种子节点

定义4边际效应ϕ:节点u的边际效应是指将其加入种子节点集S中,所能带来的影响力增量ϕS(u),

在算法预选阶段中,已经获取了具有特定区域节点高覆盖率的备选替补节点,为保证替补种子节点加入原种子节点集之后仍具有较高的网络全局影响力,以继续实现影响力最大化的最初目标,在终选阶段,基于贪心算法思想,通过计算备选替补节点的边际效应,进一步筛选出能够使网络全局影响力到达最大化的最优种子节点组合。

传统方法计算某一节点边际效应通常是将该节点加入已有种子节点集中,然后通过模拟实验,计算新种子节点集的影响范围增量,此增量即为该节点边际效应值。该方法由于每计算一个节点的边际效应都要进行R次信息扩散模拟实验才可得出最终结果,具有极高的复杂程度。对此本文采用一种新的节点边际效应计算方法,以空间换时间的策略,首先将备选替补节点在时序图上进行信息模拟扩散传播,并读取每个节点的影响范围,例如当前种子集S的影响节点集合为W={A,B,C,D},备选替补节点u的影响节点集为U={B,E,F},则只需要计算差集U-W={E,F},并统计差集中元素个数即可得出节点u的边际效应,这样便有效地将节点边际效应计算的时间复杂度降低到了O(Rn)+O(1),其中R表示共进行R次节点影响范围实验模拟,n表示节点数。

算法TSSM伪代码及时间复杂度分析如下:

代码第1行表示将替补种子节点集初始化为空集;第2至7行表示获取节点计算范围;第8至10行表示对备选节点进行可替代度的遍历计算;第11至14行表示选取50个可替代度值最大的点构建替补列表;第15至17行表示对替补列表中备选节点进行边际效应的计算,第18行表示选定边际效应值最大的节点为最终的替补节点,第19、20行分别表示将筛选出替补种子节点加入种子节点集与替补节点集合中。其中构建待遍历节点集合Q的时间复杂度为O(n2)。遍历计算集合Q中所有节点的可替代度时间复杂度为O(n3);筛选可替代度值最大的50个节点构建替补列表的时间复杂度为O(nlog(n));模拟所有候选种子节点的影响范围时间复杂度为O(Rn),R表示节点影响范围实验模拟次数,利用本文所提出的影响力并集方法计算替补列表中备选替补节点的边际效应的时间复杂度为O(1);筛选出最终替补种子节点时间复杂度为O(n),故算法TSSM的时间复杂度为O(n(n+n2+log(n)+R)。

4 实验与分析

4.1 实验设置

1) 实验环境。操作系统Windows 10,处理器Intel Core i5-6300HQ ,内存8 G,编程语言Python 3.0,编程环境Pycharm。

2) 实验数据。本实验选取了2个不同规模的时序网络数据集,具体数据信息见表1所示。

表1 实验数据信息Tab.1 Experimental data information

Digg数据集记录了社交新闻网站Digg某段时间内用户间相互评论回复的信息;

Mathoverflow数据集是根据Mathoverflow网站上的问答信息生成的社交网络。

4.2 实验内容

定义5区域节点覆盖率C:替补种子节点能够成功激活原失效种子节点影响范围内的节点的比率,

其中,Scover表示原种子节点影响节点集,S'cover表示替补节点影响节点集。

本实验从替补种子节点的区域节点覆盖率和替补种子节点加入原种子节点集所组成的新种子节点集的网络全局影响力两方面,去衡量不同算法所得替补种子节点质量的优劣。除本文所提算法TSSM外,分别复现以下几种算法作为实验对比算法。

GSG算法[10]:从网络所有剩余非种子节点中,基于贪心算法选出能够使网络全局影响力达到最大的替补种子节点。

P-S算法[11]:在选择种子节点的同时便从剩余网络节点中选出t个替补节点。

SABS算法[12]:将失效种子节点的邻居节点与网络中一定数量最大度的节点一起构成后继节点集,然后利用模拟退火的方法处理后继结点与原种子节点的最优组合问题,以获取最终的新种子节点集。

实验中采用文献[7]所给出的时序图信息传播模型及大规模时序图种子节点挖掘算法CHG,在2个数据集上均预先选定出50个原始种子节点,其中失效种子节点的选取为每次从种子节点集中随机抽取t(t=2,4,6,8,10)个不放回,直至将种子节点集全部抽取为空或剩余种子节点数不够一次抽取则完毕,其中每次抽取都要挖掘其替补节点并计算区域节点覆盖率与新种子节点集的网络全局影响力,最终取数次实验结果的平均值作为最终结果。

4.3 实验结果与分析

1) 替补种子节点区域节点覆盖率

区域节点覆盖率是指让替补种子节点在基于时序图的信息传播模型下进行信息传播,其最终能够影响到的节点范围与原失效种子节点影响节点范围的重合程度,用以去测评替补种子节点对特定节点的激活率。4种算法在不同数据集下所得替补种子节点的特定区域节点覆盖率实验结果如图3所示。

图3 替补种子节点区域节点覆盖率Fig.3 Substitute seed node area node coverage

在数据集Digg下,算法TSSM所得替补种子节点区域节点覆盖率平均达到0.8左右,算法SABS处于0.4～0.5之间,算法GSG与P-S所得替补种子节点的区域节点覆盖率最低,大致在0.2～0.3。4种算法在该数据集下都表现出了相对较好的效果,这是因为数据集Digg所抽象表示出的时序图是较稠密的,边点比值较高,节点间联系较多,这样节点被激活的潜在可能性就更大。相反,数据集Mathoverflow所对应的时序图属于稀疏图,边点比值较低,其中算法TSSM所得替补种子节点区域节点覆盖率处于0.6～0.7水平,算法SABS区域节点覆盖率在0.2～0.3左右,而算法GSG与P-S区域节点覆盖率较低,分别处于0.2与0.1之下水平。

尽管在不同稀疏性的数据集下,算法TSSM挖掘得到的替补种子节点区域节点覆盖率有所波动,但仍处于较高水平,这是因为算法TSSM在预选阶段从失效种子节点入手,采用局部选点的策略,利用节点的可替代度筛选出备选替补节点,故其对原失效种子节点影响范围内的节点具有较高的激活率。算法SABS所得替补种子节点具有一定水平的区域节点激活率,但仍远低于算法TSSM,这是因为该算法直接选取失效种子节点的邻居节点为备选替补节点,其并未考虑时序图中信息传播的时序性,导致算法最终所得替补节点对原失效种子节点影响范围内的节点的激活率不高。算法GSG与P-S选取替补种子节点的原则是保证网络全局具有较高的影响力,并没有考虑替补节点对特定区域节点的激活性,替补节点与失效种子节点在网络拓扑结构上具有很大的不相关性,故其整体区域节点覆盖率较低。

2) 替补种子节点网络全局影响力

4种算法在2个数据集下所得替补种子节点加入原种子节点集后,所构成的新种子节点集的网络全局影响力实验结果如图4所示。

图4 替补种子节点网络全局影响力Fig.4 Substitute seed node network global influence range

图中R(S)表示原始种子节点集影响到的最多节点数,可以看到在2幅实验结果图中,4种算法所得替补种子节点的网络全局影响力均随着失效种子节点数的增多而下降,这是因为原始种子节点集是网络中可以产生最优传播效果的节点组合,尽管替补节点可以弥补因部分种子节点失效所导致的传播效果方面的损失,但仍不能与原始种子节点的组合效果相媲美,故各算法与原始种子节点集传播效果之间的差距均随着失效种子节点数的增多而增大。其中2个数据集下全局贪心算法GSG均表现出最好效果,这一点是与理论预期相符的。相比于算法GSG,算法TSSM在数据集Digg下对于5个不同数量替补种子节点,新种子节点集的影响范围分别下降了1.4%、1.6%、1.8%、1.7%、2.1%;在数据集Mathoverflow下,算法TSSM相比于GSG所得替补种子节点全局影响范围分别下降了1.5%、1.9%、2.2%、2.9%、3.4%。

可见算法TSSM所得替补种子节点的网络全局影响力已经能够达到与贪心算法GSG十分相近的水平。算法SABS由于构建候选替补节点集的方式不够准确,故导致了最终所得替补种子节点的网络全局影响力下降较大。预选式算法P-S的设计思想是无论任何一个种子节点缺失都会选择预先影响力排名最好的节点,但由于种子节点集是影响力最优组合,其中某一节点缺失都会影响节点的组合效果,此时按预先影响力排名替补选取种子节点已经不是效果最优的节点组合,这是算法P-S所得替补种子节点网络全局影响力下降的原因所在。

3) 算法运行时间对比

4种算法在2个数据集上挖掘获取10个替补种子节点的运行时间如表2所示。

表2 算法运行时间Tab.2 Running time of each algorithms

算法TSSM在设计的过程中,首先将节点可替代度计算的范围由网络全局节点缩小到与失效节点含有公共一阶后继节点的节点集Q,并通过计算启发式地选取可替代度较大的前50个节点构建替补列表,极大地缩小了算法在第二阶段节点边际效应的计算范围,这是算法提高时间效率的主要原因。算法GSG基于贪心算法思想且在算法中并未利用到边际效应的子模特性[5],故其时间复杂度较大。算法SABS为追求新种子节点集在网络全局影响力上具有最优效果,后期采用模拟退火的方法筛选最终替补节点,因此付出了较高的时间代价。相反,预选式算法P-S在运行时间上具有极高的效率,但却导致新种子节点集牺牲了较大影响力。

综上所述,算法GSG所挖掘出的替补种子节点具有较高的网络全局影响力,但其在特定区域节点的激活上表现出的效果较差,同时算法时间复杂度较高,该算法无法高效地适用于大规模网络数据。算法SABS与P-S在区域节点覆盖率与网络全局影响力两方面表现出的效果均一般,而算法TSSM在以上两方面均表现出良好效果,挖掘所得替补种子节点在保证具有较高特定节点激活率的同时,依旧能够在网络全局影响力方面达到较高水平,且算法时间效率可观,可用于解决大规模时序图中替补种子节点挖掘问题。

5 结论

为解决时序图中种子节点失效问题,本文提出了时序图两阶段替补种子节点挖掘算法TSSM。算法在启发式预选阶段从失效种子节点局部入手,定义了节点可替代度概念,并将其作为选点依据为失效种子节点集构建替补列表。在贪心式终选阶段,从网络全局影响力最优化角度出发,通过计算备选替补节点边际效应以确定最终的替补种子节点。通过实验分析验证,算法TSSM挖掘所得替补种子节点可替代性较高,其影响力在保证对特定区域节点高覆盖率的同时,依旧能够维持较高的网络全局影响力,算法表现出更好的准确性与可扩展性。在未来的工作中将会考虑进一步结合节点激活成本、耗费时间、不同信息类型等更多的实际因素,研究如何进行替补种子节点的挖掘。