基于加权PageRank的异质网络影响力最大化

韩 婷，周丽华*，黄亚群，姜懿庭

(1.云南大学 信息学院，云南 昆明 650504；

2.云南师范大学 信息学院，云南 昆明 650500)

0 引 言

随着各种各样社交网络的出现，人与人之间的联系越来越紧密，人们的学习、工作和生活正在不断地被改变。社交网络中信息的传播和影响力无处不在，通过社交网络，具有高影响力的名人可以影响他人的看法和行为。准确度量不同对象之间的影响力，有助于识别社交网络中最具影响力的对象并促进信息的快速传播，对谣言传播、流行病传播、产品营销以及推荐系统等工作起着至关重要的作用[1-3]，因此影响力最大化研究受到了研究人员的极大关注。

影响力最大化问题被认为是对病毒营销的一个直接数学刻画。其目的就是希望利用病毒式营销手段，在社交网络找到少数重要的节点作为种子集，利用这些种子集进行信息的传播从而达到在社交网络中影响力的最大化[4]。目前，传统的影响力最大化方法有基于中心度、PageRank、特征向量和启发式算法等，其中PageRank[5]是一种重要的算法，该算法最初是Google公司为了衡量网页等级和重要性而提出的，它从网页数量和质量综合考虑了页面的重要性，能较好地刻画页面的性质，并描述对象之间的关系。这些传统的算法在同质信息网络中取得了较好的结果，但是同质信息网络中的节点和链接关系类型单一，没有区分对象及其关系的异质性[6]，这与实际的现实网络不符。现实中的网络大多是异质信息网络，包含了多种类型的对象及多种关联类型的链接关系[7-8]，网络中的一个实体对象的影响力不仅受到同种类型对象的影响，还与其他类型对象有关。由此关于影响力最大化问题的研究正逐步从同质信息网络转向异质信息网络。

异质信息网络包含了多种类型的对象及链接关系，相对于同质信息网络，节点和链接类型、语义关系更为丰富[8]，这些丰富的信息可以更全面地评价节点的影响力。如图1所示的文献信息网络DBLP就是典型的异质信息网络，它包含了四种类型的节点：A(作者)、P(文章)、C(会议)和T(主题)，六种关系：A-P(编写/被编写),P-C(发表/被发表),P-T(包含/被包含)。评价一个作者的影响力不仅要从作者发表的文章数量和质量来衡量，还要从他撰写的文章的内容主题、所属会议以及与他合作的作者等方面考虑，通过融合这些丰富的信息能更好地刻画现实网络中不同节点对象之间的影响力情况。

图1 DBLP网络

由于异质信息网络包含了多种类型的对象及链接关系，并且网络结构复杂，各节点之间不是相互独立的，他们通过各种关系相互影响。如何有效地利用不同类型对象间的关系成为异质信息网络分析的一个难点。Zhao等人[9]对异质信息网络中两种不同类型的节点使用PageRank，保留了节点间的连接关系，更好地考虑到不同类型节点彼此间的影响。但是他们只考虑了直接相连的两种类型节点，忽略了异质网络中同种类型节点和其他非直接相连的不同类型节点的影响，同时他们还将所有节点之间的初始连接关系的权重视为相同。然而，现实中并非所有节点间的连接关系都是同等重要的，为了能进一步区分连接关系的重要性并考虑到所有类型节点间的影响，该文针对异质信息网络提出了一种基于加权PageRank的影响力最大化算法(Comprehensive Weighted PageRank，CWPR)。CWPR根据不同节点之间的连接关系赋予对应的权重，这样可以更全面地考虑节点的重要性。

主要工作如下：

(1)将异质信息网络分解为若干个只含一种连接类型的网络，再根据各节点之间连接关系的次数分配对应的权重。网络的分解简化了复杂的网络结构，权重的分配区分了节点间连接关系的重要性，有助于准确度量不同节点之间的影响力。

(2)提出了一种基于加权PageRank的影响力最大化算法CWPR，其中影响力的度量考虑了不同类型节点的直接影响和间接影响，从而更好地描述了节点影响力的复杂性和异质性，全面保留了异质信息网络中的信息，使找到的种子节点具有较高的影响力。

(3)在DBLP和Yelp两个数据集上进行了实验，通过与其他同质和异质影响力最大化算法的对比，验证了CWPR的合理性和准确性。同时讨论了参数和边权重对于算法性能的影响。

1 相关工作

Kempe等人[10]首次将影响力最大化问题表示成离散的优化问题，证明了该问题是一个NP-hard问题，并基于单调次模性提出了有效的贪心算法。该算法能得到最优解，但是不能改进算法的时间复杂度。后来Leskovec等人[11]提出了CELF算法，CELF算法在实验中的效率得到了很大的提升。随着对影响力最大化问题研究的进一步深入，相关工作也越来越多，Goyal等人[12]又进一步改进了CELF算法，提出CELF++算法。当问题规模较大时，CELF++算法并不适用，于是Chen等人[13-15]又提出了DegreeDiscount、PMIA、LDAG等算法，大大提高了运算速度。周明洋等人[16]从多节点的综合影响力角度出发,基于Rayleigh熵机制,提出了一种指标刻画多节点的综合影响力算法。曹玖新等人[17]基于用户交互的主题偏好计算不同类别信息下节点间的影响概率,并结合扩展的传播模型和信息扩散的特点,提出基于节点子图的影响力计算算法。杨书新等人[18]基于三度影响力原则,综合考虑局部度量的适宜层次及大规模网络的可扩展性,提出一种基于3级邻居的节点影响力度量算法。Oriedi等人[19]提出选择性广度优先遍历算法，对来自社交网络成员之间实际社交行为进行影响力建模，有效地生成影响最大化的最佳种子集。目前从运算效率、网络结构等方面对影响力最大化问题的研究工作越来越多，影响力最大化问题也正逐步从同质信息网络转向异质信息网络。

在异质信息网络中，Deng等人[20]设计了一个基于互动记录、社交友谊、标签和话题的MIF模型来衡量用户之间的社交影响力，还有基于同元路径考虑信息熵[21-22]来定位有影响力的节点等。Keikhar和Rahgoza等人[23]利用深度学习技术获得异质信息网络节点的特征，根据节点的本地和全局结构特性得到最具影响力的节点。然而，由于异质信息网络相对于同质信息网络的网络结构、性质更为复杂，目前对于异质信息网络影响力最大化的研究还未足够成熟，因此在异质信息网络中对于影响力最大化的研究还存在很大的进步空间。

2 相关概念及问题定义

该文的主要目的是利用加权PageRank综合考虑各种类型节点之间的影响关系，从而挖掘出异质信息网络中影响力最大的节点。本节主要介绍所涉及到的一些相关概念及问题定义。

2.1 相关概念

定义1 异质信息网络[7,24]：信息网络由一个带有对象类型的映射函数τ:V→A和关系类型映射函数φ:E→R的有向图G=(V,E,τ,φ)组成，其中V={v1,v2,…,vn}是对象集合，它属于对象类型集合A的某一个特定对象类型集合，E={e1,e2,…,en}是对象之间的链接集合，属于关系类型集合R的某一个特定关系类型集合，当信息网络中的对象类型数|A|或者关系类型数|R|大于1时，称这个信息网络为异质信息网络。

定义2 网络模式[7,24]：网络模式是定义在对象类型A上的有向图，它的边为R中的关系，记为TG=(A,R)，表示信息网络的元模式。

定义4 加权PageRank[25]：根据信息网络中对象的连接结构及连接频次对每个对象的质量进行排名，进而利用链接和对象质量排名来衡量整个网络对象的重要性。其重要性的表示如下。

(1)

2.2 问题定义

S*=argmaxS0σ(S0)

(2)

3 CWPR算法

该文提出了一种基于加权PageRank的影响力最大化算法(CWPR)，用于解决异质信息网络中的影响力最大化问题。该算法包含两个步骤。第一，首先将原始异质信息网络分解成若干个只含一种连接类型的网络，并根据节点间的连接关系分配对应的边权重。第二，利用加权PageRank来衡量节点的直接和间接影响力，最终融合所有影响力得到节点的最终影响力，并筛选出影响力最大的前k个节点。

3.1 边权重的分配

由于异质信息网络结构复杂，每个节点都能通过不同的元路径与其他类型节点相连得到不同类型的连接边并产生不同的影响关系，其中每条连接边的权重都不尽相同，这与连接边的两个节点间的交互程度密切关联，若两节点间交互次数过多，则对应的边权重也大。为了能减少不同类型边的差异性，简化整个复杂的异质信息网络，同时保留网络的异质性和不同类型节点之间的影响关系，并为影响关系分配相应的权重，该文将包含多种连接关系的异质信息网络分解成若干个只含一种连接类型的网络。如图1中的DBLP网络，APTC四种类型节点，直接相连关系A-P/P-A,P-T/T-P,P-C/C-P，故可以分解成只含有AP,PT,PC类型的三个异质信息网络，使每条边的权重分别为对应的连接次数，如图2所示。

(a) (b) (c)

一个节点的影响力除了与它直接相连的邻居有关，还与它邻居的邻居有关，因此可以基于单中介元路径获得节点的间接相连关系，若一个节点到达另一个间接相连的节点的路径数越多，则说明它们之间的联系越紧密，因此根据路径数为节点的间接相连关系分配对应的权重。对图1中的DBLP网络而言，A能通过P与A、C、T间接相连，则对应的间接相连关系有A-A,A-C/C-A,A-T/T-A,将图1中的间接相连关系提取出来，例如A1和C2只能通过元路径A1P2C2相连，路径数为1，而A4和C2可以通过元路径A4P2C2,A4P3C2相连，路径数为2，则A1和C2的边权重为1，A4和C2的边权重为2，如图3所示。

(a) (b) (c)

3.2 影响力度量

加权PageRank延续了PageRank的优点，能够通过节点间的连接数量和质量来综合描述节点的重要性，同时又根据节点之间的交互程度分配对应的权重。该文利用加权PageRank来度量节点对不同类型节点的影响力，其综合影响力主要由直接影响力和间接影响力组成。

3.2.1 直接影响力

为给定的若干个直接相连两种不同类型节点，只包含一种类型边的异质信息网络G构建一个加权有向图，i,j是两种不同类型A,B的节点，若j指向i，则j到i有边，边的权重等于j到i边的个数k，即wj,i=k，否则wi,j=0，使用加权PageRank计算得到j对i贡献的PR值，即i对j的重要性为：

(3)

(4)

其中,N(i)为与i直接相连的不同类型节点的集合，故得i对所有与它相连的B类型节点的直接影响力为：

(5)

3.2.2 间接影响力

IIi1,t1=Pi1,t1PRt1

(6)

那么i1对所有与它相连的类型C的节点的间接影响力为：

(7)

其中，ii(i)为与i1间接相连的节点类型的集合。

图4 间接相连关系图

3.2.3 综合影响力

异质信息网络中，节点类型丰富，它们之间的影响力是通过直接或间接关系相连去传播的。该文将融合节点的直接影响力和间接影响力，作为节点的最终综合影响力Ii，Ii的表示如下：

(8)

3.2.4 筛选种子节点

通过融合节点的直接影响力和间接影响力得到节点的最终影响力，因此可以对所有节点的最终影响力进行排序。为了避免种子节点影响力重合，该文采用边际增益策略筛选种子节点。先选择一个影响力最大的节点作为种子节点，然后去除其余节点与其影响重叠的部分，再选择剩余节点中影响力最大作为种子节点，不断重复此过程，直到筛选出给定数量的节点作为种子集为止。

CWPR是基于加权PageRank迭代计算获得节点的影响力，因此使用邻接矩阵对节点间的关系进行表示存储，需要的空间复杂度为O(n2)，其中n为节点数，而PR值的计算是一个迭代过程，向量与矩阵相乘所需要的时间复杂度为O(n2)，经过若干次迭代达到收敛所需的时间复杂度为O(cn2)，其中c为迭代次数。

4 实验评估

4.1 实验准备

数据集：使用了两个最常见的文献网络数据集DBLP和Yelp，数据集的情况分别如表1和表2所示。

表1 DBLP数据集详细信息

表2 Yelp数据集详细信息

对比算法：为了验证CWPR方法的有效性，该文将与已有的同质信息网络影响力度量方法Degree(DC)、PageRank(PR)以及异质的方法APR和CWPR的变种方法CWPR-II进行实验对比。由于目前对于网络中关键节点的度量方法大多都是针对同质信息网络的，而本实验是利用异质信息网络的关键节点进行影响力最大化研究，为了进行对比实验，故将常用的同质信息网络关键节点的度量方法直接运用于异质信息网络，在使用这些方法时，忽略不同类型节点之间关系的差异，根据度量方法计算得到每个节点对应的度量值。在选取种子集时，由于不同类型节点在信息扩散中扮演的角色不同，为了减少实验的差异性，种子集类型固定，本实验以人作为目标类型，选取度量值最大的目标类型节点作为种子集。对比算法描述如下。

Degree centrality(DC)：一个节点v与它直接相连的邻居节点的个数，称为度，一个节点度越大，就意味着这个节点越重要。

PageRank(PR)：网页重要性度量方法，如果一个网页被很多网页链接，或者被知名度很高的网页链接，则这个网页的重要性就越大，也可以用于社交网络节点分析。

APR：一种在异质的文献网络中的节点重要性度量方法，利用PageRank度量的异质信息网络中作者和文章两种类型节点之间的影响力，对于DBLP、Yelp则分别考虑了作者和文章，用户和商业之间的影响力。

CWPR-II：该文提出的CWPR的变体，在异质网络中只考虑人与人之间的影响力。

CWPR：该文提出的异质信息网络影响力的度量算法，基于异质信息网络的连接结构，考虑了不同类型节点之间的影响力。

扩散模型：采用线性阈值模型LT作为传播模型，将每一节点的入度边的度数归一化，作为每个节点被自己入邻居节点激活的概率，使它们和为1，每个非激活节点都有一个[0,1]的激活阈值，当非激活节点的已激活邻居节点对其影响总和超过该阈值，则此节点被激活。该文的扩散指标分别为在k个有影响力的作者和用户作为种子集时被影响的作者和用户的个数，影响的人越多说明实验效果越好。为了减小实验的偶然性，进行了10 000次蒙特卡洛仿真来估计影响扩散结果

4.2 实验结果

4.2.1 算法参数的影响

图5 算法参数的影响

对以上实验结果分析可知，在数据集DBLP中，当λAP=0.4,ηAA=0.2,ηAC=0.2,ηAT=0.2时，影响范围的值达到最大，这表明在信息扩散过程中作者对论文的影响力是作者的综合影响力的重要组成部分。而对于数据集Yelp，当λUB=0.3,ηUU=0.3,ηBC=0.3,ηBCat=0.1时，影响范围的值达到最大，此时在信息扩散过程中，用户和领域的之间的影响力在用户的综合影响力所占的比重最小。用户和用户、商业、城市之间的影响力则是用户综合影响力的重要组成部分。

4.2.2 边权重参数的影响

在异质信息网络中，包含了多种类型的边，每种类型的边在信息扩散中同不同类型的节点一样也是扮演着不同的角色。同不同类型节点一样，该文也假设异质信息网络中不同类型边的权重等于1，则数据集DBLP中有WAP+WPC+WPT=1,数据集Yelp中有WUB+WBC+WBCat=1。通过设置多种不同的权重并选出k=50个种子所得到的影响范围大小进行结果对比，从而获得一组合理的边权值。实验结果如图6所示。

图6 边权重的影响

由实验结果可知，在数据集DBLP中，当WAP=0.5,WPC=0.4,WPT=0.1时，影响范围的值达到最大，此时作者与论文之间的边权值是三个中间最大的，这说明在信息扩散过程中作者与论文之间的关系起着重要作用，同时发现对于每一组权重，若是论文与主题之间的边权重是三者中最大的一个，则影响范围的值将会下降，则可以认为在信息扩散中，论文与主题之间的关系影响作用较小。在数据集Yelp中，当WUB=0.5,WBC=0.25,WBCat=0.25，影响范围的值达到最大，此时用户和商业之间的关系在信息扩散过程中起着重要的作用。通过对这两个数据集的边权重分析发现，均是人和与人直接相连的类型节点的边权重在所有边权重所占的比重是最大的，这也表明了直接的影响会比间接影响更有力。

通过对算法参数和边权重设置不同值，分别选取了各自最好的结果，作为该算法有效性验证的参数。

4.2.3 有效性验证

对于数据集DBLP和Yelp，本实验的种子集的类型分别设为作者和用户，由于本实验基于不同元路径考虑了不同类型的节点直接的影响，在数据集DBLP中，对不同类型的边权重设为WAP=0.5,WPC=0.4,WPT=0.1。在数据集Yelp中，设各类型的边权重为WUB=0.5,WBC=0.25,WBCat=0.25，实验对比方法中的同质方法DC和PageRank不区分边的类型，权重都为0.5。实验效果如图7所示。

图7 影响范围

由这些实验对比结果可知，保留各种类型节点信息的三种异质方法要明显优于其他两种同质方法，在DBLP中该文所提出的CWPR方法明显优于其他两种异质方法CWPR-II、APR，而在Yelp中CWPR也同样优于其他两种异质方法，但是差距并不如DBLP明显。该文给出的三种异质方法都区分了不同类型的边的权重，但CWPR考虑了不同类型节点之间的影响，而APR,CWPR-II只考虑了部分的类型节点的影响。通过以上实验结果可以表明，在异质信息网络中，保留节点与其他类型节点之间的语义信息比只保留部分信息能更全面地评价节点的特征，得到更好的实验效果，从而可以借助这种方法得到最有影响力的节点。

5 结束语

该文提出了一种基于加权PageRank的异质信息网络影响力最大化算法CWPR，该算法将包含多种类型节点的异质信息网络分解成若干个只含一种连接类型的网络，然后通过节点之间的连接方式考虑了所有不同类型节点之间的影响关系，去获得影响力最大的节点作为信息扩散的种子节点，从而实现异质信息网络影响力的最大化。通过在两个真实数据集的实验结果表明，在异质信息网络中，保留节点与其他节点之间的信息越多，筛选出的种子节点得到的影响效果越好。但是该算法的不足在于对异质信息网络中不同类型的边权重的设置是基于先验知识设定的，在未来的研究中，可以通过机器学习去自主获得不同类型的边权重，使得边权重结果更加真实可靠。