引入信任度传递机制的影响力最大化节点挖掘

王栋志 张 晖 杨春明 赵旭剑 李 波

(1. 西南科技大学计算机科学与技术学院 四川绵阳 621010； 2. 西南科技大学理学院 四川绵阳 621010)

影响力分析是社交网络分析的重要内容，其中影响力最大化节点挖掘是影响力分析的基础工作，其目的是从网络中识别K个节点，使得通过这K个节点在某种影响力传播机制下产生的影响传播范围最大。影响力分析在舆情分析、精准广告等领域有着广泛应用，近年来大量学者从不同角度提出了不同算法进行影响力分析。由于现实社交网络涉及节点数量巨大且网络稀疏，实际社交网络下的最大化影响力挖掘仍然面临着巨大的挑战。

为提高算法执行效率，不少学者采用启发式算法识别影响力最大化节点。文献[1-3]提出度中心性(High-Degree, HD)衡量节点重要性程度，即按照节点度值的大小定义节点影响力强度，文献[4-5]证明了在具有“富人俱乐部”特性网络中，策略性的移除度值最高节点作为影响力节点能够最快地将影响力扩散至整个网络。在此基础上，Cohen[3]提出适应性度中心性(High Degree Adaptive, HDA)，即不断从网络中移除度值最高的节点及其连边作为影响力节点，同时更新计算所有节点的度排序。Bavelas[6]提出利用接近度中心性(Closeness Centrality, CC)反映节点在网络中居于中心的程度，即表示节点i到其他所有节点最短距离之和的倒数乘以其他节点的个数。节点的接近度越大，表明节点越居于该节点的局部网络中心，它在网络中就越重要。一个网络的K-核是指反复移除度值小于K的节点及其连边后所剩余的子图，该子图的节点数就是该核的大小。Kitsak M[7]论证K-核算法适用于最大影响力节点相互独立的社交网络，而当最大影响力节点相互联合传播的情况下K-核算法效率极低。也就是说在影响力节点相互独立假设下，若影响力最大的节点处于核中，那么下一个被挖掘的影响力节点有很大概率不存在于该核中，因为该核中的节点已被影响力最大节点感染激活。若将影响力节点之间的交互因素考虑进K-核算法，则为NP难问题[8]，故K-核算法在联合传播的社交网络下是非最优的。文献[9-10]由谷歌提出用来衡量网页重要度，该算法的核心为网页网络连接的特征向量中心性，以该算法计算节点影响力有一个很明显的缺陷：若一个非影响力节点和影响力最大节点相连，则该节点能获得较高的影响力“得分”，从而很大概率被挖掘为下一个伪影响力最大化节点。启发式算法存在以下两个缺陷：启发式算法起初被提出的目的并非衡量节点影响力，而是从拓扑结构的角度考虑节点重要性程度，而节点重要度并不等于影响力扩散程度；启发式算法未考虑影响力最大节点集之间的联合传播影响因素。

由于启发式算法本身的局限性，学者们也从信息传播建模的角度挖掘影响力最大节点集合。Kempe[8]将影响力传播建模为时间离散的传播过程，将问题形式化为一个离散最优化问题，例如线型阈值模型[11](Linear Threshold Model, LTM)与独立级联模型[12](Independent Cascade Model)，后续有大量工作对以上两种模型进行了改进。针对规模庞大的在线社交网络，Chen[13]证明了在社交网络中计算每个用户的影响力的期望值是NP难的，即并不存在多项式时间内可以计算节点增益影响力的方法,使得其效率上存在瓶颈。另一方面该模型需要人为定义信息扩散阈值，这使得模型对于输入参数极其敏感，选择不同的参数将导致不同的信息扩散结果，不能客观有效地衡量信息在网络中的传播影响力大小。

Morone等[18]从渗流理论着手考虑影响力最大化问题，为该问题的求解提供了全新的思路。在传统启发式算法的基础上提出了全局影响力优化指标，同时考虑到影响力节点之间的联合传播影响因素，但其工作没有考虑影响力在节点间传播的信任度传递机制。本论文在其工作基础上，引入信任度传递函数，考虑影响力在传播过程中“信任度递减，不信任度递增”现象对影响力最大化的影响，采用人工网络数据与真实网络数据集对算法的影响力进行评估分析，通过与常用启发式算法比较所挖掘影响力最大化节点集合的影响力扩散率来验证本文所提算法的合理性与有效性。

1 基于渗流理论的最大影响力节点挖掘模型

本论文主要从3个角度构建最大影响力节点挖掘模型：(1)使用非回退矩阵构建满足信息(影响力)传播条件的社交网络图模型；(2)将信任度传递函数引入信息传播模型构建符合实际的影响力传播机制；(3)通过渗流理论得到快速的最大影响力挖掘算法。

1.1 基于非回退矩阵的社交网络表示图模型

近年来，非回退矩阵(non-tracking matrix)在复杂网络建模受到关注。该矩阵从网络连通性的角度考虑影响力在网络中的传播，不仅突破了最大影响力节点挖掘算法使用传统邻接矩阵在稀疏网络上的局限性，并且研究表明基于非回退矩阵的谱方法在社团发现等社交网络研究上相较于拉普拉斯(Laplacian)矩阵与邻接矩阵有更好的效率。

非回退矩阵的构造流程如下：给定具有N个节点M条边的无向社交网络，为了构建在该社交网络的非回退矩阵，首先将无向图转为有向图，具体操作为：针对两个具有直接关联的节点i,j∈N且(i,j)∈E，E为边集，将无向边代替为两条相反指向的有向边，即分别用i→j与j→i来表示两条有向边，故M条无向边共构成2M条有向边。下面给出非回退矩阵的元素定义。

定义1[14-15]设网络具有N个节点，M条边，则非回退矩阵B为2M×2M的非对称矩阵，其元素取值为：

(1)

非回退矩阵刻画了非回溯游走的可行路径，即影响力传播路径。“非回退”指的是一种简单游走策略，游走路径不允许沿着已经走过的路径返回，也就是说类似于1→2→1的访问路径是不被允许的。其次，非回退矩阵的子图为包含诸多“非回退”路径的树状网络，若从网络中移除该树状网络将不影响非回退矩阵的谱，需要注意的是由于非回退矩阵为非对称矩阵，故其特征值除最大特征值为实数外均为复数。

非回退矩阵的上述两种性质，一方面刻画了影响力在实际社交网络中的传播为源节点到边缘节点、从上至下的传播路径，另一方面描述了影响力在局部网络的传递呈树状结构。从整个网络中移除该树状子图不影响非回退矩阵的谱，说明以非回退矩阵表示社交网络相较其他无向对称邻接矩阵更具稳定性，当考虑某个节点在网络中的影响力时，可以客观地比较移除以该节点为中心的影响力传播树状子图前后的信息传播情况。

以图1所示的某个社交网络子图为例，该网络具有N=6个节点，同时具有M=6条边，先将这6条无向边转为2M=12条有向边，并根据定义1所确定非回退矩阵元素取值，构建2M×2M大小的非回退矩阵。非回退矩阵可以表明影响力能够传播的路径，以节点2为例，若节点1为影响力传播源节点，影响力传达3节点与5节点，必须经过节点2，故形成以节点2为中心的两条非回溯路径1→2→3与1→2→5，根据非回退矩阵元素定义即B1→2,2→3=1，B1→2,2→5=1。

图1 社交网络

1.2 基于信任度的影响力传播机制

传统研究影响力在社交网络中的传播问题采用信息级联技术，信息级联在社交网络中是十分常见的一种现象，当信息级联形成后，处于影响力传播底层的个体节点容易受其上层影响力节点的影响，作出与前面个体相同的选择而忽略自身观点。如微博平台中很多人转发某条微博并不是出于对内容的兴趣而是基于从众心理。

在信息级联模型中，每个初始激活节点会产生自身独立的扩散级联，级联之间相互独立、互不干扰。将社交网络抽象为加权无向图后，任何一条边(u,v)∈E都被分配一个属于[0,1]之间的特定值Pu,v，这个值代表激活态节点在t时刻是否将信息传递给该激活态节点邻近的某个非激活态节点的影响力扩散概率。

初始时，选择合适的影响力扩散种子节点，影响力从这些节点开始扩散。在时刻t，每个当前激活的节点u都会以扩散概率Pu,v去激活它的每个邻居节点v。如果节点v在该时刻被成功激活，那么在t+1时刻，节点v作为激活态节点会去影响该节点的邻居节点。

图2展示了具有3个节点{A,B,C}⊂N的独立级联模型，其中包含两个一阶信息级联扩散，分别为A→B与B→C，激活态节点A通过影响力传播机制于t时刻将信息传递给节点B，若节点B被成功激活，则在t+1时刻，依扩散概率PB,C尝试激活C节点。

图2 独立级联模型

在独立级联模型中，每个激活节点与其邻居节点形成的扩散级联相互独立，如图2中显示的两个独立一阶级联扩散，节点A与节点C不存在扩散级联。根据信息扩散理论，影响力随社交链逐层递减，处于影响扩散链底层节点不仅受与其直接相连的上级朋友节点的影响，同时与高层节点之间存在间接的影响力传递。影响力扩散模型不能真实刻画影响力在社交网络中的传递，以该模型模拟影响力在网络中的传播存在一定误差，故本文引入信任度传递函数[17]，以便能够更加真实地对社交网络中的影响力传播进行仿真模拟。

定义2 节点信任度函数。每个节点的信任度函数用二元组λ=(t,d)表示，其中t,d∈[0,1]，信任传递函数二元组的第一部分为节点信任度，第二部分为节点不信任度。社交网络上的信任度函数集合用Λ={λ=(t,d)│t,d∈[0,1] }≡[0,1]2表示。

节点信任度函数二元组为衡量节点的局部属性，其第一部分表示以该节点为中心与其直接连接节点构成的最小连通子图的相对信任度，节点信任度越高表明该节点在其最小连通子图中能够以较大概率影响(激活)其邻居节点。由于间接影响力传递机制的存在，也会促使邻居节点的朋友继续将影响力传递下去；第二部分相反，则是衡量的节点在最小连通子图中的相对不信任度。在影响力传播过程中，即使激活态节点将影响力传递给了社交链中下一级的非激活态节点(即成功激活其邻居)，如激活态节点具有较高的不信任度，其邻居节点会抗拒将影响力传播给该邻居节点的朋友。

影响力在社交网络中的传播机制的实质是节点间信任度的交互，信任度较高的节点们更容易达成共识从而达到影响力最大化的效果。为了刻画影响力传播过程中节点间信任传递机制，本文引用三角模(Triangularnorms)与三角余模(Triangularconorms)的概念[16]。若函数T∶[0,1]2→[0,1]当且仅当满足交换性、结合律、单调性并且同时对∀x满足边界条件T(x,1)=x，则T函数成为三角模。若函数S∶[0,1]2→[0,1]当且仅当满足交换性、结合律、单调性并且同时对∀x满足边界条件S(x,0)=x，则S函数成为三角余模。在本文中采用Einstein乘积⊗ε作为三角模，采用Einstein求和⊕ε作为三角余模，本文使用上述两种函数作为信任传递函数，对于∀(a,b)∈[0,1]2，有如下计算公式：

(2)

(3)

三角模为最小化算子，而三角余模为最大化算子，上述两种运算具有如下性质：

E⊗(x1,x2)≤min{x1,x2}

(4)

max{x1,x2}≤E⊕(x1,x2)

(5)

现有影响力传播模型中的信任传递机制并未考虑到不信任度在具有3个节点及以上构成的影响传播链中的传播。更重要的一点，并未考虑到影响力在社交网络中传播时的信任度衰减问题。考虑影响力在现实社交网络中的传递存在信任度减少而不信任度增加的现象，为了实现信任度衰减、不信任度增加机制，本文利用Einstein乘积⊗ε与Einstein求和⊕ε作为双向信任传递算子。

定义3 信任度传递指数。令Λ为节点信任度函数集合。构造信任双向传递算子PD∶Λ×Λ→Λ，信任双向传递算子连接两个具有直接连接的投票节点，其信任度函数分别为λ1=(t1,d1)，λ2=(t2,d2)，则信任传递指数为：

PD(λ1,λ2)=(E⊗(t1,t2) ,E⊕(d1,d2))=

(6)

定义2利用Einstein乘积⊗ε与Einstein求和⊕ε构建双向信任传递算子，由于满足E⊗(t1,t2)≤min{t1,t2}与max{d1,d2}≤E⊕(d1,d2)性质，该算子PD分别实现了影响力传播过程中的信任度减少而不信任度增加的信任度传递机制。信任传递算子PD具有以下性质：

(1)交换性：

PD(λ2,λ1)=(E⊗(t1,t2) ,E⊕(d1,d2))=

PD(λ1,λ2)

(7)

(2)结合律：

PD(PD(λ1,λ2),λ3)=

PD[(E⊗(t1,t2) ,E⊕(d1,d2)),(t3,d3) ]=

(E⊗(E⊗(t1,t2),t3),E⊗(E⊗(d1,d2),d3))=

(E⊗(t1,E⊗(t2,t3)),E⊗(d1,E⊗(d2,d3)))=

PD(λ1,PD(λ2,λ3))

(8)

(4)边界条件：对于信任传递算子PD的边界条件，对信任度与不信任度分别讨论。

全信任传递：当λ1=(1,0)时，有PD((1,0),λ2)=(t2,d2)=λ2。当λ2=(1,0)时，根据交换律有PD(λ1,(1,0))=(t1,d1)=λ1。在一个具有3个节点{A,B,C}的影响力传播链中，当A节点对B节点具有完全信任度时，则B节点对C节点的影响力程度完全以A节点为主导。

全不信任传递：当λ1=(0,1)时，有PD((0,1),λ2)=(0,1)；根据交换性，当λ2=(0,1)时，有PD(λ1,(0,1))=(0,1)；在具有全不信任度的节点为中心构成的最小连通子图中，该节点将不受任何具有直接连接朋友的影响。

图3展示了具有3个节点的影响力传播过程中的信任传递链，图3(a)中为3个节点的完全连通图，每个节点之间都具有实际的社交链接，则节点之间的信任传递根据上述信任传递算子直接可计算节点之间的信任度与不信任度；若影响力以线性链式传播，如图3(b)所示，构造了一条从B→A→C的影响力传播链，实际上节点B与节点C之间不仅存在实际的相互影响同时存在间接的信任传递，故B与C之间通过虚线进行相连来代表C节点收到B节点具有的二阶扩散级联的影响。

图3 影响力传播中的信任传播链

(9)

通过节点间的信任度传递机制，可计算两个节点间的影响力扩散系数，该系数衡量了两个具有直接连接的节点中激活态节点不能够激活邻居节点的概率。

1.3 信任度传递下最大影响力节点挖掘

影响力最大化旨在从网络中识别k个节点，使得通过这k个节点在某种影响力传播机制下产生的影响传播范围最大。前两节说明了基于非回退矩阵的社交网络表示图模型与影响力在社交网络的传播机制。在此基础上，采用渗流理论的思想针对最大影响力节点进行挖掘。传统的识别k个影响力传播节点算法中，并未提出一个全局的明确的影响力最大化函数，其次均假设节点重要性程度与节点的影响力成正相关，故忽略了节点之间的影响力联合传播。基于渗流理论的k个影响力最大化节点挖掘一定程度上避免了传统挖掘算法的缺点，不仅考虑节点重要性程度，同时引入联合影响强度的概念，将节点之间的联合影响因素考虑在内。

设向量n=(n1,n2,…,nN)代表网络中节点是否为影响力节点的标记向量，其中：

(10)

则影响力节点在网络中所占比例为：

(11)

渗流理论将影响力最大化节点挖掘过程看做不断从网络节点中移除qc个“超级影响力”节点及其连边，使得影响力不能在网络中扩散，其中qc为从网络中移除节点的比例，即“超级影响力”节点的比例。设G(q)为在具有q个“超级影响力”节点的网络中当影响力扩散行为结束后网络中未曾受到影响节点的平均概率。设v=(v1,v2,…,vN)，其中vi为节点i最终不受影响概率，即在当t→∞时节点i为非激活态的概率，G(q)的表达式为：

(12)

故可将影响力最大化节点挖掘转化为最优渗流问题，寻找最优qc比例的“超级影响力”节点(移除节点)使得最终网络中为受影响力节点的概率G(qc)最小，问题的数学形式化表达如下：

qc=min{q∈[0,1]:minG(q)}

(13)

当q≥qc时，社交网络存在一系列影响力联合扩散节点集合，使得影响力由这一系列节点扩散至整个网络。当q≤qc时，说明社交网络存在小型孤立局域世界使得影响力不能扩散至整个网络。

为了衡量某个节点在网络中的实际影响力，考虑虚拟地移除该节点，并考察移除该节点前后影响力传递的情况。设两个具有直接关联的节点i与j，引入标记vi→j表示当虚拟移除j节点时，节点i最终不被影响的概率。以节点i为中心的局部影响力扩散树的数学形式化表达如下：

(14)

(15)

当节点i本身为影响力节点，即ni=0，显而易见vi→j=0；当节点i为非影响力节点，即ni=1时，该节点最终是否被激活的概率与周边节点有关。其中wk→i为当节点w的邻居节点i被虚拟移除时，节点k的局部平均影响力扩散系数；∂ij为虚拟的移除节点j后的节点i的邻居节点集合。

上述局部影响力扩散模型中，可以验证对于所有i→j,i,j∈N，{vi→j=0}是全局稳定解。依据非回退矩阵，上述模型可构建2M×2M个可闭合的方程组，为了求解全局最优n，引入线型操作算子：

(16)

(17)

1→22→12→32→53→23→43→54→35→25→35→66→51→200n2w1→2n2 w1→2000000002→10000000000002→300000n3w2→3n3w2→3000002→5000000000n5w5→3n5w2→503→20n2w3→20n2w3→2000000003→40000000000003→500000000n5w3→50n5w3→504→30000n3w4→30n3w4→3000005→20n2w5→2n2w5→20000000005→30000n3w5→3n3w5→30000005→60000000000006→500000000n5w6→5n5w6→500

(18)

最优“超级影响力”节点比例qc满足以下等式：

(19)

(20)

(21)

上式中，Zi=∑t∈∂iwi→t，|w0(n)|2=2∑i,jIS(λi,λj)，Ball(i,)为以i节点为中心、影响力阶数为半径的朋友圈边界节点，P(i,j)为节点i到阶数的朋友圈边界节点j的所经路径节点。影响力阶数衡量了两个社交节点之间联合传播的平均可达条件，具体表现为其中一个影响力节点需经过条路径才与另一影响力节点联合传播。

为了求解上述最小化最大特征值问题，即最大化节点影响力，考虑两个“超级影响力”节点i与j之间能够联合传播，则这两个节点之间应满足距离可达，则nk=1,k∈P(i,j)，故可定义节点在影响力阶数下的联合影响强度。

定义5 节点联合影响强度。给定节点影响力阶数，则节点i的联合影响力强度如下：

(22)

为了更快地挖掘“超级影响力”节点，本文采取贪婪算法的思想：总是移除网络中节点联合强度更大的节点及其连边，直至挖掘qc比例的影响力节点。具体算法流程如下：

Step 1:初始化节点是否为影响力节点标记向量n=(n1,n2,…,nN)=0；给定影响力阶数；

CI算法通过移除有限比例的节点，算法的时间复杂度为O(NlogN)。针对大规模复杂社交网络的影响力分析，CI算法能够快速搜索影响力节点。

2 数值实验

本文采用的两种数据集如表1所示。

表1 数据集网络参数

图4所示人造网络生成节点的数量参数为50，边连接概率为0.2。图5所示Netscience数据集为现实网络，该网络用于描述科学家合作关系，其度分布存在明显的幂率特性。本文将节点信任度二元组引入影响力最大化节点挖掘算法，由于节点信任度测度不是本文研究的重点，故利用线性同余发生器生成[0,1]内均匀分布的随机数作为信息在网络传播过程中的节点初始信任度与不信任度。

图4 人造均匀网络

图5 Netscience网络

2.1 影响力最大化节点实验

根据2.3节对基于渗流理论的最大化节点挖掘算法的描述，不同网络的节点挖掘特征值阈值如表2所示。

表2 各网络下特征值阈值及挖掘节点比例

图6与图7展示了随着联合影响力强度最大节点被移除网络后，带权非回退矩阵的最大特征值的变化情况。对于均匀网络，选择不同的影响力阶数对于特征值阈值的变化与挖掘节点比例无显著变化；而对于Netscience幂率网络，根据选择影响力阶数的不同导致特征值阈值的变化区间非常大，同时挖掘节点比例也不一致，数据表明2阶影响力阶数的影响力挖掘能够极大地减少挖掘影响力节点的个数，同时根据图中2阶的特征值变化曲线情况，在挖掘到满足特征值阈值的节点后，特征值以指数速度递减为0，说明信息能够更快传播到整个网络。

图6 特征值变化曲线(Netscience)

图7 特征值变化曲线(均匀网络)

2.2 影响力最大化算法比较试验

本文选择基于渗流影响力理论的影响力最大化算法、节点度、节点特征向量中心性、接近度中心性作为选择影响力最大化节点挖掘算法，来挖掘人造均匀网络与Netscience网络下的影响力节点。用来衡量每个节点的影响力强度指标分别为：联合影响力强度、度、特征值、接近度中心值。表3展示了人工均匀网络下的指标强度前3的节点数据，表4展示了Netscience网络下的前3指标强度的节点数据。

表3 均匀网络前3影响力强度指标

表4 Netscience网络前3影响力强度指标

为了比较不同影响力最大化算法的性能，以不同算法选择的影响力最大化节点作为线型阈值模型的种子节点，考察当模型收敛后影响力的扩散率。图8与图9分别展示了Netscience网络与人造均匀网络下的影响力扩散率，结果显示在均匀网络下的扩散率的大小程度为：改进渗流理论影响力挖掘算法≥传统渗流理论的影响力节点挖掘算法≥度中心性≥特征向量中心性≥接近度中心性。故在均匀网络下使用本文所提影响力挖掘算法与度中心性、特征向量中心性的扩散效用相近，但显著高于接近度中心性；而在Netscience幂率网络下，基于渗流理论的影响力挖掘算法在线型阈值模型迭代收敛后的扩散率显著高于其他影响力算法，同时能够在极小的迭代次数内使算法达到收敛，即网络中已不存在能够被激活的节点。

图8 Netscience网络下的扩散率

图9 人造均匀网络下的扩散率

引入信任度传递机制下的渗流理论挖掘算法略优于传统基于渗流理论影响力最大化算法，虽影响扩散速率相近，但能提升最终影响力扩散率上限。其次渗流理论下的影响力挖掘对于均匀网络下影响阶数对扩散率及扩散速率影响不大，而对于真实网络中选择合适的联合影响阶数能够略微提升影响力最大化性能，Netscience网络下选择1阶联合指数能够极大提升影响力扩散率上限。

3 结论

本文利用非回退矩阵构建社交网络图模型，突破了最大影响力节点挖掘算法在传统邻接矩阵稀疏网络上的局限性，同时用信任度传递函数刻画影响力传播过程中“信任度减少不信任度增加”现象，在此基础上采用渗流理论对影响力节点进行挖掘，并提出节点联合影响传播强度指数刻画节点影响力大小。利用本文所提算法与传统启发式算法(度中心性、接近度中心性、特征向量中心性)挖掘出的影响力最大节点集合作为线型阈值模型的种子节点，考察其扩散率与扩散速度，结果表明本文算法扩散率与扩散速度均普遍高于其他启发式算法。