图的重要性计算必读：节点重要性与节点间相关性计算中的中心度和PersonalRank算法总结与实现

在前面的文章《KG-Embedding前沿：引入节点位置特征的注意力神经网络表示模型GFA-NN剖析与总结》以及《大规模知识图谱表示必读：从Bert中的wordpiece到KG中的nodepiece》中，我们都说到，当前引入节点拓扑结构信息到知识表示中的重要性。

其中有个重要的点，就是重要节点的选择问题，如nodepeice中的锚点anchor选择。

因此，本文主要介绍节点重要性以及节点间相关性的计算方法，这在当前图表示中有着十分重要的应用场景。

本文中参考和引用了参考文献的内容，在此对前人的工作表示感谢。

一、基于PageRank与中心度的节点重要性计算

在一张大图中，如何衡量图中节点的重要性，是当前图算法的重要应用场景，下面介绍几种方法。

1、基于PageRank的节点重要性算法

PageRank算法，又称网页排名算法，是一种由搜索引擎根据网页（节点）之间相互的超链接进行计算的技术，用来体现网页（节点）的相关性和重要性。

如果一个网页被很多其他网页链接到，说明这个网页比较重要，也就是其PageRank值会相对较高。

如果一个PageRank值很高的网页链接到其他网页，那么被链接到的网页的PageRank值会相应地提高。

2、基于中心性的节点重要性算法

对于节点重要性的解释有很多种，当前最主要的度量指标为点度中心性（Degree Centrality）、接近中心性/亲密中心性（Closeness Centrality）、中介中心性/中间中心性(Between Centrality) 、特征向量中心性（Eigenvector Centrality） 四种。

1）点度中心性Degree Centrality

度中心性（Degree Centrality）是在网络分析中刻画节点中心性（Centrality）的最直接度量指标。一个节点的节点度越大就意味着这个节点的度中心性越高，该节点在网络中就越重要。

在无向图（Undirected Graph）中，度中心性测量网络中一个节点与所有其它节点相联系的程度。对于一个拥有g个节点的无向图，节点i的度中心性是i与其它g-1个节点的直接联系总数：

其中CD（Ni)表示节点i的度中心度， 用于计算节点i与其它g-1个j节点（i≠j，排除i与自身的联系；也就是说，主对角线的值可以忽略）之间的直接联系的数量。CD（Ni）的计算就是简单地将节点i在网络矩阵中对应的行或列所在的单元格值加总。

也可以进行归一化，即：

其中，n表示节点的数量.

2）紧密中心度Closeness Centrality

紧密中心度算法（Closeness Centrality）计算一个节点到所有其他可达节点的最短距离的倒数，进行累积后归一化的值，反映在网络中某一节点与其他节点之间的接近程度，衡量了某个顶点与其它顶点的平均距离，其值越高说明该顶点与其它顶点的距离越短。

紧密中心度可以用来衡量信息从该节点传输到其他节点的时间长短。节点的“Closeness Centrality”越大，其在所在图中的位置越靠近中心，适用于社交网络中关键节点发掘等场景。

计算公式为：

其中：l(vi,vj)表示顶点vi与顶点vj 之间的最短路径长度。公式同时适用于加权图。

类似度中心度，紧密中心度对有向图也可以使用入度或者出度作为紧密中心度，例如：

其中 l(vi,vj)in表示顶点vj到顶点vi的最短路径长度；l(vi,vj)out表示顶点vi到顶点 vj的最短路径长度。

使用入度时，紧密中心度衡量了信息到达顶点的能力，表示突出性；使用出度时，紧密中心度衡量了信息流出顶点的能力。

3）中介中心性/中间中心性Between Centrality

中介中心性/中间中心性(Between Centrality) 以经过某个节点的最短路径数目来刻画节点重要性的指标。

计算公式为：

知乎文章《度中心性、特征向量中心性、中介中心性、连接中心性》地址：https://zhuanlan.zhihu.com/p/403076024，对该计算方式进行了讲解，如下：

其中dst表示s到t的最短路径数量，dst()表示从s到t的最短路径中经过节点的数量。若需要进行标准化，在如上公式基础上，除以（n-1)(n-2)，n为节点数量。

例如：

4）特征向量中心性Eigenvector Centrality

特征向量中心性（Eigenvector Centrality）认为，一个节点的重要性既取决于其邻居节点的数量（即该节点的度），也取决于其邻居节点的重要性，与之相连的邻居节点越重要，则该节点就越重要。

知乎文章《度中心性、特征向量中心性、中介中心性、连接中心性》地址：https://zhuanlan.zhihu.com/p/403076024，对该计算方式进行了讲解，如下：

如图，先求出该图所表示的邻接矩阵的特征值。选最大的一个特征值2.48，求出对应的特征向量。将其乘以-1，是没有影响的。于是得到了图中所示的特征向量中心性：

{1：0.53，2：0.358, 3:0.358 , 4:0.427 ,5:0.53}

可以看到，1和5节点的特征向量中心性是比较大的，因为其本身的度就比较大。

其次是2，3，4节点，它们自身的度都是2，但是特征向量中心性不一样。2连接了1，3连接了5，但是4连接了1和5，特征向量中心性与该节点的邻居节点重要性相关，所以4的特征向量中心性比2和3的大。

二、基于personalrank的节点相关性计算

除计算节点重要性之外，计算节点之间的相关性也是当前图算法的一大应用场景，其需要考虑图中节点之间的交互关系，而计算两个个顶点的相关性。

上面的二部图表示user A对item a和c感兴趣，B对a b c d都感兴趣，C对c和d感兴趣。本文假设每条边代表的感兴趣程度是一样的。

现在要为user A推荐item，实际上就是计算A对所有item的感兴趣程度。在personal rank算法中不区分user节点和item节点，这样一来问题就转化成：对节点A来说，节点A B C a b c d的重要度各是多少，重要度用PR来表示。

但进一步的，我们可以看到，为了计算ABC与abcd之间的相关性，一般可以从三个方面进行考虑，即：

两个顶点之间的路径数、两个顶点之间路径的长度以及两个顶点之间的路径经过的顶点。而且，

相关性较高的一对顶点一般两个顶点之间有很多路径相连，连接两个顶点之间的路径长度都比较短，连接两个顶点之间的路径不会经过出度比较大的顶点

下面，我们选用personalrank算法来进行说明。

1、主要思想

PersonalRank算法又称Personalized PageRank算法。该算法继承了经典PageRank算法的思想，利用图链接结构来递归计算各节点的重要性，适用于商品推荐、好友推荐和网页推荐等场景。

与PageRank算法不同的是，为了保证随机行走中各节点的访问概率能够反映出用户的偏好，PersonalRank算法在随机行走中的每次跳转会以（1-alpha）的概率返回到source节点，因此可以基于source节点个性化地计算网络节点的相关性和重要性。

一般而言，PersonalRank值越高，source节点的相关性/重要性越高。

文章《PersonalRank：一种基于图的推荐算法》地址：https://www.cnblogs.com/zhangchaoyang/articles/5470763.html，对该原理进行了形象概述，计算公式如下：

如上图所示，步骤如下：

1）初始赋予𝑃𝑅(𝐴)=1,𝑃𝑅(𝐵)=𝑃𝑅(𝐶)=𝑃𝑅(𝑎)=𝑃𝑅(𝑏)=𝑃𝑅(𝑐)=𝑃𝑅(𝑑)=0，即对于A来说，他自身的重要度为满分，其他节点的重要度均为0。

2）开始在图上游走。每次都是从PR不为0的节点开始游走，往前走一步。继续游走的概率是𝛼 ，停留在当前节点的概率是1−𝛼第一次游走，从A节点以各自50%的概率走到了a和c，这样a和c就分得了A的部分重要度，𝑃𝑅(𝑎)=𝑃𝑅(𝑐)=𝛼∗𝑃𝑅(𝐴)∗0.5。最后𝑃𝑅(𝐴)变为1−𝛼。第一次游走结束后PR不为0的节点有A a c。

3）第二次游走，分别从节点A a c开始，往前走一步。这样节点a分得A 1/2∗𝛼的重要度，节点c分得A 1/2∗𝛼的重要度，节点A分得a 1/2∗𝛼的重要度，节点A分得c 1/3∗𝛼的重要度，节点B分得a 1/2∗𝛼的重要度，节点B分得c 1/3∗𝛼的重要度，节点C分得c 1/3∗𝛼的重要度。最后𝑃𝑅(𝐴)要加上1−𝛼。

2、关键参数

下图列举了personalrank的几个重要参数：

其中：
alpha决定跳转概率系数，也称为阻尼系数，是算法内的计算控制变量；

convergence定义每次迭代各个点相较于上次迭代变化的绝对值累加和上限，当小于这个值时认为计算收敛，算法停止，收敛精度（convergence）设置较大值时，迭代会较快停止。

2、代码实现

#coding=utf-8
import time
def PersonalRank(G, alpha, root, max_step):
    rank = dict()
    rank = {x:0 for x in G.keys()}
    rank[root] = 1
    #开始迭代
    begin=time.time()
    for k in range(max_step):
        tmp = {x:0 for x in G.keys()}
#取节点i和它的出边尾节点集合ri        
        for i, ri in G.items():
#取节点i的出边的尾节点j以及边E(i,j)的权重wij, 边的权重都为1，归一化之后就上1/len(ri)
            for j, wij in ri.items():
#i是j的其中一条入边的首节点，因此需要遍历图找到j的入边的首节点，
#这个遍历过程就是此处的2层for循环，一次遍历就是一次游走
                tmp[j] += alpha * rank[i] / (1.0 * len(ri))
#我们每次游走都是从root节点出发，因此root节点的权重需要加上(1 - alpha)
        tmp[root] += (1 - alpha)
        rank = tmp
    end=time.time()
    print('use time', end - begin)
    rank = sorted(rank.items(), key=lambda asd:asd[1], reverse=True)
    print(root, rank)
    return rank
def test_rank():
    alpha = 0.8
    G = {'A' : {'a' : 1, 'c' : 1},
        'B' : {'a' : 1, 'b' : 1, 'c':1, 'd':1},
        'C' : {'c' : 1, 'd' : 1},
        'a' : {'A' : 1, 'B' : 1},
        'b' : {'B' : 1},
        'c' : {'A' : 1, 'B' : 1, 'C':1},
        'd' : {'B' : 1, 'C' : 1}}
PersonalRank(G, alpha, 'b', 50) #从'b'节点开始游走
return

结果:

b [('B', 0.311771289366653),
('b', 0.26235568512102325),
('c', 0.11542526431829382),
('a', 0.08889047471965857),
('d', 0.08889047471965857),
('A', 0.06633340587735637), 
('C', 0.06633340587735637)]

总结

本文主要介绍节点重要性以及节点间相关性的计算方法，其中关于节点中心度的方法和personanlrank的思路值得我们一起深入思考。

如何将图算法和知识图谱表示进行融合是知识图谱技术的一个方向，利用好拓扑结构，期待有更好的工作出现。

参考文献

1、https://www.imooc.com/article/39459

2、https://baike.baidu.com/item/度中心性/17510724?fr=aladdin

3、https://blog.csdn.net/qq_39918677/article/details/123452926

4、https://support.huaweicloud.com/usermanual-ges/ges_01_0033.html

关于我们

老刘，刘焕勇，NLP开源爱好者与践行者，主页：https://liuhuanyong.github.io。

就职于360人工智能研究院、曾就职于中国科学院软件研究所。

老刘说NLP，将定期发布语言资源、工程实践、技术总结等内容，欢迎关注。

对于想加入更优质的知识图谱、事件图谱实践、相关分享的，可关注公众号，在后台菜单栏中点击会员社区->会员入群加入。

本月底，我们将开展一次面向知识图谱的实体标注、实体关系标注、事件标注的线上分享， 欢迎加入社区，一起实践。