Node Ranking in Complex Networks Based on LeaderRank and Modes Similaritya

LeaderRank通过在原网络中加入一个与网络中其他节点双向连接的背景节点，增强网络的连通性，从而提高了算法的收敛速度。

定义1   LR_i定义为节点v_i的全局重要度。LR_i(k) 为经过k步后系统到达稳态，节点v_i的初步重要度。稳态后，背景节点将其影响力平均分配给网络中的其他节点，从而获得网络中节点的全局重要度。因此节点v_i的最终的全局重要度LR_i值为：

式中，n为网络节点总数 (不包括背景节点)；LR_g(k) 为第k步背景节点v_g的重要度；a_ji为基本Google矩阵中的元素，如下：

式中，k_i^out为节点v_i的岀度。

PageRank算法和LeaderRank算法中，每个节点跳转到邻居节点的概率是相等的，但是现实生活中，人们更信任那些和自己关系更为相似的人。在有向社会网络中，节点的出边代表该节点的兴趣所向，入边代表了其他节点对其兴趣的一种认可。可以认为，若两个节点共同指向的节点数越多，其兴趣越相似，相似度值越高；指向两个节点的其他节点数越多，代表其他人认为这两个节点的兴趣越相似，其相似度值越高。因此，两个节点的相似度，不仅和其共同指向的节点数有关，也和共同指向其的节点数有关。

对于一个简单有向网络如图 1a所示，考虑节点4不存在的情况，节点1、2、3的影响力是相同的，可得两两节点之间的相似度一致。节点4加入后，直接提高了节点1、2的影响力，对节点3的贡献低，间接削弱了节点3的影响力，即节点对1、2相似度要高于节点对1、3和节点对2、3，符合拓扑结构。因此，节点间相似度和共同指向其的节点数有关，即两个节点受其他节点共同指向的个数越多，其相似度越高。对与图 1b来说，由于节点1、2同时指向节点4，提高了节点4的影响力，节点4的影响力提高，也会提高节点1、2的影响力，因而节点1、2的相似度会高于图 1a中的相似度。因此，节点间相似度和其共同指向的节点数有关。两个节点共同指向的节点数越多，其相似度越高。

定义2  节点相似度矩阵Sim。节点v_i和其邻居节点节点v_j的相似度为Sim_ij：

式中，α_i为节点v_j的邻居节点；0 < γ < 1；k_{i, j}^out表示节点v_i和节点v_j共同指向的节点个数；k_{i, j}ⁱⁿ表示共同指向节点v_i和节点v_j的节点个数。

定义3   SRank矩阵SR。节点v_i的SR_i值如下：

式 (4) 表明：1) 与节点连接的邻居节点个数越多，节点的重要度越高，这与直观判断相符。2) 节点的邻居节点重要度越高，节点的重要性越高。3) 节点对之间的相互影响力不同，邻居节点数多的一方对另一方的影响力更大。符合现实网络中，当两个人的共同好友数一致时，好友数少的一方对认为另一方和其的关系会比好友数多的一方认为对方和其的关系更为亲密。4) 节点对的相似度为0时，节点之间仍然有相互作用。

SRank算法步骤：

1) 使用LeaderRank算法，即使用式 (1) 得到每个节点的LR值；2) 使用式 (3) 计算节点对之间的相似度；3) 使用式 (4) 得到节点的SR值。

本文选取了4种真实网络，Zachary空手道网络、海豚社会网络 (Dolphins)、线性虫神经网络 (Neural) 及美国政治家博客网络 (Polblogs)，其网络参数如表 1所示。本文节点相似度计算时选取参数γ=0.5。

Zachary空手道网络和海豚网络如图 2所示，分别用度中心性、接近中心性、PageRank算法、LeaderRank算法、SRank算法进行节点重要性排序，所得排序结果如表 2、表 3所示。

由表 2可知，相较于其他算法排名，SRank算法认为节点1比节点34更为重要。节点1和节点34的共同邻居节点为节点9、14、20、32，其重要性不同是因为两节点特有的邻居节点。对于节点1而言，其邻居节点中节点2、3、4的重要性在其他算法中排名靠前，而节点34的邻居节点中只有节点33的重要性在其他算法中比较高，因此，本文算法认为节点34重要性低于节点1更为合理。本文算法认为节点8的重要性比节点32高，因为节点8的邻居节点为节点1、2、3、4，这些节点重要性在其他算法中也比较高，而节点32的邻居节点为节点1、25、26、29、33、34，虽然节点32的部分邻居节点在网络中的重要性比较高，但由于节点32的邻居节点个数比较多，弱化了重要性较强的邻居节点如节点33、34对其的作用。因此，本文算法认为节点32重要性低于节点8更接近事实。

由表 3可知，SRank算法选出的10个节点和其他算法结果相似，区别在于节点的重要性排序不同，说明本文算法具有一定合理性。本文算法和度中心性都认为节点46比节点38重要。从网络结构中可以看出两个节点相互连接，其影响力不同在于其存在不同的邻居节点，节点46的邻居节点为节点16、19、24、25、30、51、52、60，节点38的邻居节点为节点15、17、34、35、37、41、44、62，可以看出，节点46的邻居节点的影响力在其他算法中没有节点38的邻居节点高。但在网络结构上，节点46与其邻居节点的相似性比节点38的高，例如节点16与节点46有3个共同邻居节点而节点17与节点38只有两个。因此，本文算法认为节点38重要性低于节点46更为合理。

通常采用传染病模型评价节点重要性排序方法，本文采用SIR模型^{[1-2, 11]}。SIR模型中，一个节点的传播能力被定义为该节点的平均传播范围，如果一个排序方法的结果使得网络流传播又快又广，则说明该重要节点排序方法优于其他方法。

定义4   节点的传播重要度矩阵S_IR定义为多次传播仿真网络中I状态和R状态的节点占整个网络的比例的平均值。分别对网络中每一个节点进行传播仿真，即每一次仿真只有一个节点处于I状态，其他节点都为S状态，选取传播时间步为10，对每个节点进行100次传播仿真，因此节点v_i的传播重要度为：

式中，n_{j_i_s_}表示初始传播节点为节点v_i的第j次传播仿真中经过10步传播后网络中S状态的节点个数。

首先，选取Nerual网络对其进行仿真，将本文算法和度中心性、接近中心性、PageRank和LeaderRank进行对比，得到每个算法的节点重要度和传播重要度关系如图 3所示。由图 3明显看出，PageRank、LeaderRank和SRank节点重要度和传播重要度的线性程度表现更好。换而言之，本文算法在重要节点排序上要优于度中心性和接近中心性。图 3c、3d、3e图中圆圈标注的部分中，LeaderRank、PageRank算法排名值高的其S_IR值低，而本文算法线性程度好，可知本文算法发现重要性低的节点，比另外两种算法优秀；此外，图 3中椭圆标注中，本文算法在节点重要性高的部分其离散程度低于其他两种算法，可知本文算法在发现网络重要节点更为有效。

其次选取Polblogs网络进行仿真，将本文算法和度中心性、接近中心性、PageRank算法和LeaderRank算法进行对比，得到每个算法的节点重要度和传播重要度关系如图 4所示，PageRank、LeaderRank和SRank节点重要度和传播重要度的线性程度比其他算法表现更好。换而言之，本文算法在重要节点排序上要优于度中心性和接近中心性。

定义5相关性系数ρ定义为节点重要度排序和传播重要度的相关性关系。ρ的绝对值越接近1，两者的相关性越强，节点重要度排序算法越好。ρ由斯皮尔曼等级相关系数^[12]计算，定义为：

式中，x_i、y_i分别为节点v_i在重要性排序算法中的排名和传播重要度中的排名。分别选取Nerual网络、Polblogs网络进行相关性分析。

为了分析不同排名节点段的重要性排序结果，本文分别选择PageRank、LeaderRank和SRank算法的重要性排序并对每个重要性排序算法的排名前10%、前20%以及所有节点分别进行考虑。相关性系数ρ对比结果如表 4所示。由表 4可知，无论是整个网络的重要度排序还是节点重要性排名比较高的排序结果，本文算法的相似性程度更高，表明本文算法更优秀。

对各算法在线性虫神经网络、美国政治家博客网络的重要节点排序结果进行传播仿真。选取传播时间步为50，观察网络中I状态节点个数S_I占网络的比例随时间的变化。针对本文算法所得排名前10%节点，选取其中节点排名高于PageRank的节点作为传播节点；同理，针对PageRank所得排名前10%节点，选取其中节点排名结果高于本文算法的节点作为传播节点。为了保证算法对比时，不同方式选择传播节点个数相同，传播节点个数较多的去除排名低的部分节点。其次，分别选取本文算法排名前20%和全部节点进一步验证本文算法对比PageRank的有效性。本文算法与LeaderRank的对比亦如是。线性虫神经网络、美国政治家博客网络的传播仿真结果分别如图 5、图 6所示。

图 5a~图 5c为本文算法与PageRank的对比结果。图 5a、图 5b中，本文算法的I状态比例S_I最大值超过0.5，高于PageRank算法，且前者增长时后者已经下降了，表明本文算法的传播深度高于后者，也证明了本文算法选取该网络的核心节点上表现比PageRank优越。图 5c中，两者的相差比例更加明显，本文算法的斜率高于后者，表明本文算法传播速度高于后者，说明了本文算法在整个网络节点重要度排序要优于PageRank。同理，由图 5d~图 5f本文算法与LeaderRank的对比结果可知，本文算法I状态的最大值和斜率都高于后者，说明本文算法无论是在发现该网络的核心节点上还是整个网络节点重要度排序上，都要优于LeaderRank。由图 6a~图 6c本文算法与PageRank的对比结果可得，本文算法的I状态比例的最大值超过后者，且增长时其斜率高于后者，表明本文算法的传播深度、深度高于后者，本文算法无论是在发现该网络的核心节点上还是整个网络节点重要度排序上，都要优于PageRank。同理，由图 6d~图 6f本文算法与LeaderRank的对比结果可得，本文算法要优于LeaderRank。

本文主要工作是在LeaderRank算法的基础上引入了节点相似度的概念，综合考虑节点的局部特征和全局特征，提出了SRank节点重要性排序算法。对四种真实网络进行重要性排序，在通过分析网络结构来说明本文算法在无向网络的节点重要度排序的合理性同时，利用传播仿真成功验证了本文算法在有向网络节点重要度排序的有效性。

本文研究工作还存在一些不足。提出的算法主要针对于连通网络，对不连通网络还存在一定的不确定性。今后的工作需要更全面、科学地考虑不连通网络节点重要性的排序和验证方法。