谢世娜，李川

（四川大学计算机学院，成都 610065）

基于用户复杂联系的最大影响力节点发现算法

谢世娜，李川

（四川大学计算机学院，成都 610065）

提出基于用户联系的信息网络中最具影响力用户的发现算法，基于现实社会网络启示得到的假定“与越多易受影响用户有联系的这类用户的影响力越大”，且给出无向网络和有向网络中节点影响力的度量模型。实验表明，该方案优于求解影响力最大化的贪心算法达到的影响范围，能够较准确地刻画社会网络中节点影响力。

影响力；有影响力的节点；贪心算法

0 引言

社会网络（Social Network）通常指实体与实体间联系构成的复杂信息网络（Information Network），即由节点和边组成的，反映一定社会结构关系的网络或图。其中，节点可表示个人或组织等实体，节点之间的链接或边表示实体之间的联系，例如合作关系、朋友关系、认同关系等。当我们考察信息传播时，发现：社会网络的结构担当着非常重要的作用。当一用户接受某新事物之后，会向其邻居、好友推荐该事物，其中一部分人就会受其影响接受该新事物，且进一步向他们的邻居、朋友推荐。在这样一个传播过程中，一个人的社会关系及其朋友的行为会影响到他的决策[1]。社会网络中节点影响力的研究由来已久[2～7]。近年来，随着各大社交网站的兴起，如Facebook、Twitter等，使得该研究再次成为热点。而这些社交网站的庞大用户数量以及用户间的复杂联系等特点也给相关研究带来巨大的挑战。一个基础的问题是：如何在这些庞大的用户网络中找到最具影响力的小部分用户使得信息通过他们能够传播或扩散的范围更广[2～4]？通过对影响力分析还可以发现意见领袖，改进个性化推荐等[5～8]。

直观来讲，网络中度越大的节点影响力应该越大，这是许多其他相关研究的基础假设。其他常用的影响力度量为紧密度中心性（Closeness Centrality），介数中心性（Betweenness Centrality）等[9]。有研究[10]表明：大众思想的大规模改变也即新事物的传播，是由容易被影响的用户去影响其他容易被影响的用户推动，从而促进信息的广泛传播。

1 相关工作

1.1 独立级联模型

常用的信息传播模型为独立级联模型[4]。它借鉴交互粒子系统和概率论的理念[1]。在独立级联模型中，若节点u在第t步被激活，则它只有一次机会去激活其邻居节点；而其邻居节点v被u激活的概率为p，也被称为信息转移概率，换句话说，若节点v的邻居中有l个节点处于活动状态，则v以1-（1-p）l的概率被激活。如果节点v被成功激活，v将成为t+1步被激活的节点；在以后的激活过程中节点u就失去激活其他节点的机会。若v有多个已激活的邻居节点，则他们激活v的顺序是随机的。与线性阈值模型类似，独立级联模型下的激活过程也是从一个初始激活的节点集合开始直到网络中没有节点可以激活为止。具体激活过程如图1所示。

图1中灰色表示活动状态，绿色表示新被激活状态，红色表示第t步激活失败的节点，空白表示不活动状态。初始活动节点为1、2，第一步成功激活节点3、5，节点4激活失败；第二步，节点3、5有能力激活其他节点，继续以p概率影响其他邻居，此时成功激活节点4、6；第三步，以节点4、6为给定活动节点，此时成功激活节点7。节点9激活失败。

图1 独立级联激活过程

1.2 传统方案的不足

随着社交网站的兴起，社会网络等信息网络已成为学术界的研究热点，研究者从不同的角度对社会网络中节点的影响力的进行研究[6～8]。

传统的研究节点影响力的度量方式有度中心性、介数中心性、接近中心性等，但这些指标并不适用于所有场合[9]。度虽易计算但并不能很好地刻画节点的影响力，而介数、接近性等在大规模网络中则很难计算。Chen等人[11]提出考虑两阶邻居的局部中心性指标来描述节点的传播影响力。近年来，也有对Kempe等人[4]提出的贪心算法的改进算法，虽然提高了贪心算法的计算效率，但因其计算复杂度过高很难适用于大规模社会网络中。Leskovec等[12]利用集函数子模块性提出CELF算法。子模块性是指，在向初始节点集合S中添加一个节点v时，若该集合S越大，则v对影响范围的增量就越小，即满足收益递减原则。CELF算法去掉了大量重复计算，提高了贪心算法的计算速度，但并没有扩大贪心算法的影响范围。本文在实验部分用到的贪心算法即CELF算法。但是这些算法也很难达到理想的效果，即使是贪心算法也只是找到最有影响力的节点集合，并未给出刻画节点影响力的度量。

2 基于易受影响的节点影响力度量

本文提出挖掘信息网络中最具影响力节点的新思想：一个用户周围有越多的容易受影响的用户，则该用户发布一条消息或者推广某新事物就越容易被扩散，进而影响网络中更多的其他用户。本文认为与越多容易受影响用户有联系的这类用户的影响力越大。同时，本文提出用节点间的相似性来度量节点的易受影响程度。

信息网络可表示为一无向（有向）图，其中用户用节点表示，用户之间的关系用节点间的边表示，设G（V，E）为一个无向（有向）图，V表示节点的集合，E表示节点间连边的集合。

2.1 无向网络影响力度量方案

得益于社会网络分析中经典的“越相似的用户就越容易相互影响”这一结论[9]，本文提出了基于节点相似性来度量节点容易受影响的程度。具体如下：

定义1易受影响程度。设Sv，u表示节点v与u之间的相似性，Nv表示节点v的邻居节点集合，则节点v易受影响程度Ev定义为：

定义2节点v受节点u的影响程度。设ev，u为节点v受节点u的影响程度，Ev表示节点v易受影响程度，Sv，u表示节点v与u之间的相似性，则节点v受节点u的影响程度为：

易知：一个用户与越多的容易受影响的用户有联系，则这个用户的影响力就越大。

定义3节点v的影响力。设eu，v表示节点u受节点v的影响程度，即v的邻居节点受v的影响程度；Nv表示节点v的邻居节点集合，则节点v的影响力Iv定义为：

2.2 有向网络影响力度量方案

本文对无向网络中度量节点影响力方案进行扩展，考虑了影响传播的方向性，提出了针对有向网络中节点影响力的度量方案，具体如下：

定义4有向网络中节点v与u之间的相似性。设Sv，uOUT表示出度方向的相似性，代表用户间共同投票的用户，表示共同感兴趣的用户越多越相似；Sv，uIN表示入度方向的相似性，表示共同投票给他们的用户越多则这两个用户越相似，则有向网络节点v与u之间的相似性Sv，u定义为：

2.3 算法框架

本文实现了2.1、2.2节提出的节点影响力度量方案，用到的算法伪代码见算法1。该算法用到了节点间的相似度，1～7行为按网络是否向有计算网络中节点v易受影响的程度；第8～12行为计算节点v受节点u的影响程度。13～15行为按网络关系计算网络中节点v的影响力。

算法1算法框架

3 实验分析

本文实验使用常用于社会网络研究领域中各项试验分析的真实数据集（Ca-HepTh），代表的社会语义为合作关系。本文使用独立级联模型来验证本文方案提出的节点影响力度量方法的有效性，并与贪心的算法比较其在网络中的影响范围。本文选取的为p=0.01，每次模拟传播过程100次。在计算节点影响力的时候，本文选取了6种节点局部相似性[13]，计算了其相应的节点影响力，分别是Sorenson指标、Salton指标、CN、Jaccard指标、HPI、HDI。实验结果如图2所示。横坐标均表示初始活动节点的规模，纵坐标均表示影响范围，即初始活动节点集对应的平均激活节点数。从图中可以看到，（a）和（b）为在数据集Ca-HepTh上的实验结果。从中可以看到本文方案优于贪心算法的影响范围，且可以给出节点影响力的具体大小，这是贪心算法不能实现的。由此，说明本文提出影响力度量方案是可行且有效的，能较准确刻画社会网络中节点影响力。因本文方案是基于网络自身结构，不需加入更多的额外信息，因此也具有普适性。

4 结语

本研究通过考察社会网络中节点影响力的传播机制，提出基于节点相似性的度量影响力的新的模型，进一步研究探讨无向网络与有向网络的度量方法。实验表明，本文方法优于贪心算法的影响范围，验证了新方案的有效性。

图2 本文方案与CELFgreedy实验结果对比

[1] Tang L,Liu H.Community Detection and Mining in Social Media[J].Synthesis Lectures on Data Mining and Knowledge Discovery, 2010,2（1）:1～137

[2] Serrat O.Social Network Analysis[J]，2009

[3] Chen W,Wang C,Wang Y.Scalable Influence Maximization for Prevalent Viral Marketing in Large-Scale Social Networks[C].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2010:1029～1038

[4] Kempe D,Kleinberg J,Tardos.Maximizing the Spread of Influence Through a Social Network[C].Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2003:137～146

[5] Song X,Chi Y,Hino K,et al.Identifying Opinion Leaders in the Blogosphere[C].Proceedings of the Sixteenth ACM Conference on Conference on Information and Knowledge Management.ACM,2007:971～974

[6] Centola D.The Spread of Behavior in an Online Social Network Experiment[J].Science,2010,329（5996）:1194～1197

[7] Kimura M,Saito K,Nakano R.Extracting Influential Nodes for Information Diffusion on a Social Network[C].AAAI.2007,7:1371～ 1376.

[8] Guille A.Information Diffusion in Online Social Networks[C].Proceedings of the 2013 Sigmod/PODS PhD.Symposium on PhD Symposium.ACM,2013:31～36

[9] 汪小帆，李翔，陈关荣.网络科学导论[M].北京：高等教育出版社，2012

[10] Watts D J,Dodds P S.Influentials,Networks,and Public Opinion Formation[J].Journal of Consumer Research,2007,34（4）:441～ 458

[11] Chen D,Lü L,Shang M S,et al.Identifying Influential Nodes in Complex Networks[J].Physica A:Statistical Mechanics and Its Applications,2012,391（4）:1777～1787

[12] Leskovec J,Krause A,Guestrin C,et al.Cost-Effective Outbreak Detection in Networks[C].Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2007:420～429

[13] Lin-yuan L.Link Prediction on Complex Networks[J].Journal of University of Electronic Science and Technology of China,2010,9: 5～39

The Most Influential Nodes Finding Algorithm Based on User Complex Relationships

XIE Shi-na，LI Chuan
（School of Computer Science,Sichuan University,Chengdu 610065）

Proposes a most influential node finding algorithm based on complex user relationship,which is based on such hypothesis that the nodes with more easily affected neighborhood users have more chances to be affected.Gives the measurement method of undirected and directed network.Experiments show that the method exceeds the greedy algorithm of influence maximization on the spread influence and is more likely to depict the influence in social network accurately.

Influence;Influential Node;Greedy Algorithm

1007-1423（2015）03-0006-04

10.3969/j.issn.1007-1423.2015.03.002

谢世娜（1990-），女，四川达州人，研究生，研究方向为信息网络、图数据挖掘

李川（1977-），男，河南郑州人，博士，副教授，硕士生导师，研究方向为数据库、数据挖掘

2014-12-25

2015-01-14