覃 俊，易金莉

(中南民族大学 计算机科学学院，武汉 430074)

基于前驱后继节点的社会网络影响最大化算法

覃 俊，易金莉

(中南民族大学 计算机科学学院，武汉 430074)

针对社会网络影响最大化问题，基于挖掘“潜在影响力”节点的策略并结合贪心算法可有效降低问题复杂度，综合考虑了节点与其前驱后继节点的相互影响，对“潜在影响力”进行了重新定义，基于线性阈值模型提出了基于前驱及后继节点的影响最大化算法．实验结果表明：与目前的同类算法相比，该算法具有更好的信息扩散范围．

影响最大化；潜在影响力；前驱后继节点

社会网络是关于社会实体如个人、团体或组织之间关系的网络．随着对社会网络中大规模数据宏观和微观扩散的可用性认知的不断增强，信息、产品等如何在社会网络中传播方面的研究受到越来越多的关注[1]．信息在社会网络中通过节点之间的影响从一个节点传播到另一个节点，查找社会网络中最具影响力的节点，对于研究社会学和“病毒式营销”[2]等而言是一个重要的课题．

结合上述“潜在影响力”一类方法，本文根据信息在网络中扩散的动态性，基于LT模型，综合考虑节点与其前驱和后继节点之间的相互影响，优化“潜在影响力”节点的选取策略，结合贪心策略提出了基于前驱后继节点的社会网络影响最大化算法(PSH)，并选取多个真实的社会网络数据集对本方法进行了验证．

1 背景知识

1.1 LT模型

LT模型中，对于一个表示社会网络的有向图，任一节点v初始时分配[0,1]范围内的阈值θv，边(w,v)分配权重bwv，对应节点w对节点v的影响力，且所有指向v的边的权重满足：

(1)

其中pre(v)表示节点v的直接前驱节点集合．若所有已激活邻节点对v的影响力之和大于或等于阈值，即：

(2)

则节点v被激活．其中aPre(v)表示节点v已激活的直接前驱节点．LT模型下，对于给定的初始节点集合，最终的扩散范围是确定的．

1.2 相关工作

基于挖掘“潜在影响力”节点的方法通常都是结合贪心策略的混合式算法，即首先启发式地选择一部分具有潜在影响力的节点，然后使用贪心策略选取当前最具影响力的节点，在前一阶段的基础上，网络图中部分节点已被激活，因此本阶段计算规模显著降低，效率和效果都大大提升．相关工作如下：

1)爬山贪心算法[5].每一步选择使得当前影响范围最大的节点，定义：

m(v|Si-1)=|I(Si-1∪{v})|-|I(Si-1)|.

(3)

其中I(Si-1)表示Si-1节点集合能激活的节点个数，m(v|Si-1)表示节点v相对于Si-1产生的影响范围增量．

2)混合式影响最大化算法(HPG).田家堂等人[9]首次提出基于挖据“潜在影响力”节点的方法，利用节点的度数和节点对其未激活直接后继节点的影响力之和来选取潜在影响力节点，结合HCG提出了HPG算法．

3)基于阈值的影响最大化算法(TBH).陈浩等人[10]基于HPG，考虑节点阈值的变化和节点之间的影响共同决定节点的潜在影响力．定义：

(4)

p(u,v)为u对v的影响，值为1表示u能激活v，其中θvt表示u在t时刻的阈值.

(5)

2 基于前驱后继节点的影响最大化算法

2.1 现有问题分析

前期研究者在选取潜在影响力节点时仅考虑节点对其直接后继节点的影响，忽略了该节点对更多层级后继节点可能存在的影响．此外，前驱节点的累积影响决定着该节点自身是否更易被激活，这种情形也未见讨论．虽然基于局部结构的方案复杂度较低，但潜在影响力的辐射范围有局限．本文针对以上缺陷，对“潜在影响力”的度量方法进行改进，在选取种子节点时，同时考虑节点与其前驱后继节点间的相互影响，即自身不易被激活，但激活后对其后继节点能产生更大影响的节点，据此提出了基于前驱后继节点影响最大化算法．

本文提出的方法对有向图和无向图均适用，下面主要针对有向图进行分析，无向图的处理方式见3.3节．

2.2 潜在影响力分析

2.2.1 对多级后继节点的影响

潜在影响力旨在积累更多的潜在影响，即对更多的节点产生影响(激活或使其阈值减小)．若某节点在t时刻被激活，则该节点会直接或间接地影响其后继节点，这种间接的影响同样应该在该节点的影响范围内，即潜在影响力为节点对其后继节点产生的直接或间接影响力的累加：

(6)

(6)式的解释需考虑以下两种情况：

1) 计算u的潜在影响力时，不仅需要计算u对其直接后继节点v的影响，同时需要考虑这些v节点的潜在影响力，以此类推．如图1(a)(深色圆圈表示已激活节点，下同)，在计算节点u的潜在影响力时，若有buv3≥θv3t，则若在当前时刻激活节点u，节点v3会在下一时刻受u的影响而被激活，v3继而影响其自身的未激活的后继节点．

(a) 多级后继传播 (b) 不同路径传播图1 对直接和间接后继节点的影响Fig.1 Influence on direct and indirect successor nodes

2) 计算u的潜在影响力时，需要考虑其经不同路径对同一后继节点的影响．如图1(b)，若θu=θv1=θv2=0.5，buv1=0.2，buv2=0.5，bv2v1=0.3，则在当前时刻节点u对节点v1的影响不足以将其激活，而u可以将v2激活，之后v2对v1的影响与u之前对v1的影响两者累加后能够将v1激活，v1继续对自身的后继节点产生影响．

2.2.2 受前驱节点的影响

节点受其前驱节点的累积影响越大，该节点被激活的概率越大，而在初始节点选取时，应考虑自身不易被激活的节点．因此基于(6)式，将前驱节点对自身的影响考虑在内，根据前驱节点的影响力大小，对PI“打折”，消除前驱节点的影响：

(7)

其中aPre(u)表示节点u已激活的直接前驱节点．

(7)式相关解释如图2，根据(6)式若有PI(u1)=PI(u2)且PI(u2)=PI(u3)，节点u1存在已激活的直接前驱节点w2．LT模型下w2对u1的影响持续保留直至u1被激活．因此可以认为，相较于u2、u3而言，u1更易受其他节点的影响而被激活．

图2 直接前驱节点激活状态对比Fig.2 Comparison of direct previous nodes′ active status

综上，同时考虑节点对其后继节点产生的直接或间接影响，以及前驱节点对节点本身影响的积累，结合(6)、 (7)式提出节点潜在影响力计算方法为：

(8)

环路的考虑：由PI的定义可以看出，网络图中存在环时，可能会出现PI值循环迭代相加的情况．为避免这种问题，可标记节点是否受到影响而激活，若是，则接下来的计算过程中若再次访问到该节点，不再对其PI值进行累加．

2.3 算法框架

根据以上分析，参考文献[9,10]基于潜在影响力一类方法的框架，这里给出PSH的算法描述．首先启发式选择PI值大的一部分节点，再用贪心策略选取剩余部分节点，其中仅PI值计算发生变化．为增强可比性，启发因子c∈[0,1]含义不变，1-c表示通过潜在影响力选取节点所占的比例．

输入：图G=(V,E)，初始节点集合大小k，启发因子c.

输出：初始节点集S(|S|=k)，激活节点个数.

1) 根据(8)式计算所有节点的PI值；

2) 选择PI值最大的节点放入S，基于S进行一轮激活并计数，更新未激活节点的PI值，重复此步骤k-「ck⎤次；

3) 根据(3)式计算每个未激活节点的影响范围增量，选择当前能产生最大影响范围增量的节点放入S，基于S进行一轮激活并计数，重复此步骤「ck⎤次．

2.4 算法复杂度分析

对于图G=(V,E)，记节点个数|V|，启发阶段PI值的计算为常数时间，选取PI值最大的节点的时间复杂度为O(|V|)．相较于TBH，时间差主要在PI值的计算上．实际传播过程中，节点对其后继节点的直接或间接影响级数较小，因此PSH相较于TBH时间复杂度略高．考虑离线状态下时间性能要求不高，因此可以接受．

3 实验

3.1 实验设计

在同一平台下进行实验验证，选取LT模型作为信息扩散模型．θv均取0.5[5]，权值bwv的处理参考文献[9,10]．

1-c表示通过潜在影响力选取的节点个数占目标节点个数k的比例．c=0即仅考虑潜在影响力对结果的影响；c=1时初始节点全都由贪心策略选取，此时PSH与TBH退化为HCG；c∈(0,1)时，通过潜在影响力选取k-「ck⎤个节点，通过贪心策略选取「ck⎤个节点．实验设计如下：①仅考虑潜在影响力因素，即c=0时，与TBH比较，对比两种潜在影响量化标准，与HCG比较，分析潜在影响力因素下的最终扩散效果；②潜在影响力所占比例c∈(0,1)对结果的影响，同样与TBH、HCG比较，分别对比潜在影响的累积效果和对最终扩散结果的影响．

3.2 实验数据集

本方法选取3个常用的真实数据集进行实验验证，数据集分别来源于Stanford大学大型网络数据集和Geom lib基础几何数据库[9]，如表1.

表1 数据集基本信息

Wiki_vote数据集是Wikepedia的投票历史网络，有向无权图．节点代表Wikipedia的用户，有向边(u,v)表示u给v投票．

Facebook数据集记录了Facebook应用用户的社交信息，节点代表该应用用户，无向边(u,v)表示用户u、v为好友关系，无向无权图．

Geom数据集代表计算几何合著社会网络，记录作者之间合作关系的无向带权图．节点代表作者，无向边(u,v)代表作者u与v之间的合作，边的权值表示合作次数．

3.3 无向图的处理

对于无向图，若节点u、v之间存在边，则认为u、v之间存在相互影响，加入由u指向v的有向边(u,v)和由v指向u的有向边(v,u)，分别表示u对v的影响和v对u的影响．

3.4 实验结果

3.4.1 无向无权图上的实验结果

仅考虑潜在影响力对结果的影响．选取无向无权网络数据集2验证PSH的性能，见表2．

表2 Facebook数据集上影响范围对比

1)比较两种潜在影响力的影响范围．k取不同值时PSH相较于TBH均具有更好的激活范围．这是因为在计算潜在影响力时，PSH相对于TBH而言考虑了节点更多层级之间的结构关系，而非单层的局部结构，即PSH选取的是对更多节点具有潜在影响的节点．

2)仅用潜在影响力选取节点的扩散结果．与HCG相比，k≤40时，PSN扩散效果较差，k≥50时，PSH激活范围显著提升，这是因为PSH需要一个潜在影响的累积过程，才能使后续扩散过程中更多的节点更易被激活．

3.4.2 有向无权图上的实验结果

考虑潜在影响力所占比例对结果的影响，选取数据集1验证PSH在有向无权图上的性能．

1)比较不同潜在影响的积累产生的不同结果．考虑c的大小，k取定值80，PSH与TBH扩散效果对比如表3，PSH均表现出较TBH更好的激活效果，验证了3.4.1的实验结论，即PSH的潜在影响力量化标准较TBH更优．随着c值增大，通过潜在影响力选取的节点所占比例减小而贪心策略选取的节点较多，两者激活范围差距随之减小．

表3 k=80时，Wiki_vote数据集上不同c值下的比较Tab.3 Comparison based on dataset Wiki_vote under different c when k=80

2)讨论潜在影响所占比例对结果的影响．同时考虑c,k，PSH与HCG扩散效果如表4.c=0.4时PSH相较于HCG(即c=1)具有更好的激活范围，也就是说当潜在影响力比重较大而贪心策略比重较小时，PI的潜在影响积累使得更多的节点更易被激活，PSH可以达到比HCG更好的结果，且随着k增大，优势越明显．另外，PSH每一步只需更新受影响节点的PI值，而HCG则需要计算所有未激活节点的影响范围增量，因此PSH运行时间更短．

表 4 Wiki_vote数据集上不同k和c的影响范围对比

3.4.3 无向带权图上的实验结果

为了验证PSH算法在带权网络上的有效性，选取数据集3进行同样的实验．同时考虑k、c的变化，验证不同潜在影响力的积累对结果的影响．如表5，k≥40，c取不同值，随着k值的增大，PSH均表现出较TBH更优的扩散效果．PSH相较于TBH考虑的是范围更广的邻节点结构，因此需要更多的节点来累积潜在影响，如k≤30时，扩散效果会出现较TBH差的情况，此时k值较小，但随着k值的增大，PSH优势越明显．

表 5 Geom数据集上不同k和c的影响范围对比

同样，c=0.4即c较小时，PSH激活范围超过HCG，验证了3.4.2的结论．

综上，PSH中改进的潜在影响力量化标准在大多数情况下的扩散效果都较TBH好，仅当k值较小时，由于PSH需要更多的节点来累积潜在影响，可能出现扩散效果较差的结果；此外，c值较小时，PSH就能达到较HCG更好的扩散效果且运行时间更短，k值越大，优势越显著．

4 结语

本文基于线性阈值模型，提出了基于前驱后继节点的影响最大化算法，实验结果表明：相较于基于阈值的影响最大化算法，我们的算法在大部分情况下具有更好的扩散范围；通过潜在影响力选取的节点比例较大时，我们的算法能达到比爬山贪心算法更好的扩散效果，运行时间也更优．

本文对社会网络影响最大化问题进行了探究，提出的算法虽然在时间复杂度上比同类算法略高，但扩散效果明显较好．另外，本算法存在进一步改进的空间，如初始节点集要求较小时，由于潜在影响的累积较少，本算法扩散效果可能较差；还有，节点阈值不同的情况下，算法的适用性研究等，这些工作有待后期深入研究．

[1] Rodriguez M G, Song L. Diffusion in social and information networks: research problems, probabilistic models and machine learning methods[C]//ACM. Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2015: 2315-2316.

[2] Chen W, Wang C, Wang Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]//ACM. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2010: 1029-1038.

[3] Richardson M, Domingos P. Mining knowledge-sharing sites for viral marketing[C]// ACM. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2002: 61-70.

[4] Kemple D, Kleinberg J, Tardos E. Maximizing the spread of influence in a social network[C]// ACM. Proceeding of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2003: 137-146.

[5] Kemple D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network[J]. Theory of Computing, 2015, 11(4): 105-147.

[6] Leskovec J, Krause A, Guestrin C, et al. Cost-effective outbreak detection in networks[C]// ACM. Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2007: 420-429.

[7] Goyal A, Lu W, Lakshmanan L V S. Celf++: optimizing the greedy algorithm for influence maximization in social networks[C]// ACM. Proceedings of the 20th International Conference Companion on World Wide Web. New York: ACM, 2011: 47-48.

[8] Chen W,Wang Y,Yang S. Efficient influence maximization in social networks[C]// ACM. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM,2009: 199-208.

[9] 田家堂,王轶彤,冯小军. 一种新型的社会网络影响最大化算法[J]. 计算机学报，2011,34(10): 1956-1965.

[10] 陈 浩 王轶彤. 基于阈值的社交网络影响力最大化算法[J]. 计算机研究与发展，2012,49(10): 2181-2188.

Previous and Successor Nodes-Based Heuristic Algorithm for Influence Maximization

Qin Jun, Yi Jinli

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

Strategies based on mining “potential influence” nodes combined with Greedy Algorithm could effectively reduce the complexity of the influence maximization problem for social networks. In this paper, we redefined “potential influence” by considering the interaction influence between nodes and their previous and successor nodes, and proposed the Previous and Successor Nodes-Based Heuristic Algorithm for Influence Maximization based on linear threshold model. Experimental results demonstrate that our algorithm significantly outperforms the similar algorithms in information diffusion.

influence maximization; potential influence; previous and successor node

2016-09-05

覃 俊(1968-)，女，教授，博士，研究方向：智能优化、数据挖掘，E-mail：498011695@qq.com

国家民委基金资助项目(2015BAD29B00)

TP311

A

1672-4321(2016)04-0095-06