特征向量中心度（eigenvector centrality）算法原理与源码解析

前言

随着图谱应用的普及，图深度学习技术也逐渐被越来越多的数据挖掘团队所青睐。传统机器学习主要是对独立同分布个体的统计学习，而图深度学习则是在此基础上扩展到了非欧式空间的图数据之上，通过借鉴NLP和CV方向的模型思想，衍生了很多对图谱这种非序列化数据的建模分析手段，帮助分析人员洞察数据之间隐含的复杂关系特征。

在深度学习技术没有普及之前，已经存在大量的图谱数据分析工作，而这些工作的主要思路是通过抽取图中节点的统计信息作为特征，并用作分类模型的输入。今天，在这里介绍的其中一个经典的图分析算法叫做特征向量中心度（eigenvector centrality），它的作用是衡量节点在整个网络中的重要性。图数据一个最常用的数据结构就是邻接矩阵，而这个算法的主要思想就是用到了矩阵分解的思想，经典的图深度学习算法GCN也是基于拉普拉斯矩阵的谱分解和傅立叶变换实现的。所以对于新人来说，特征向量中心度可以做为图数据挖掘的经典入门算法之一。

参考资料

[1] William L. Hamilton. Graph Representation Learning. Morgan and Claypool publishers, 2020
[2] Xinyu Chen. 幂迭代法[OL]. https://zhuanlan.zhihu.com/p/336250805
[3] Power method for approximating eigenvalues, https://ergodic.ugr.es/cphys/lecciones/fortran/power_method.pdf
[4] 柴静. 线性代数-山东大学. https://www.bilibili.com/video/av370427050/?p=42&vd_source=9ca707c71dee64c77d2f5f3d824e1c19

定义问题

图片引用自 ：《交网络舆情中意见领袖主题图谱构建及关系路径研究_基于网络谣言话题的分析》

我们首先来定义特征向量中心度算法所要解决的问题。如上图所示，这是微博谣言话题中意见领袖节点关系图谱的一部分。如果用最简单直观的图统计方法来分析这个图谱，那就是使用节点的出入度的大小（有多少邻节点）来衡量这个节点在图谱中的重要性。我们可以看到”天涯历知幸“、“来去之间”和“开水族馆的XX”三位博主的出入度最高，是重要的意见领袖。但是，如果仅仅是通过博主周围的邻居节点的数量来衡量其影响力又是有失偏颇的，因为这些转发和关注的微博用户有可能是僵尸粉（现在僵尸粉都很智能的）。所以，我们还需要找到一种方式，不仅仅是通过当前节点关联的邻居节点数量来横量其重要性，还要将邻居节点本身的重要性也一起考虑进去。回到上图，“鸟窝里的猫妖”和“筆木鱼_”这两个节点虽然它的邻居节点数量很少，但是它们都关注转发了”天涯历知幸“、“来去之间”和“开水族馆的XX”三位重要博主的博文，所以他们也应该是重要的谣言传播者。

算法原理

我们先定义$e_u$ 节点的特征向量中心度由下面的递归等式表示：

$e_u=\frac{1}{\lambda }{\sum }_{v\in \nu }A[u,v]e_v\forall u\in \nu$,                 (1),

这个等式的意思是$e_u$ 节点的中心度是其周围邻节点$e_v$ 中心度总和的$\frac{1}{\lambda }$, 其中$\lambda$是一个常量。$\nu$是图上所有节点的集合。$A$是邻接矩阵，$A\in {\mathbb{R}}^{|\nu |\times |\nu |}$, $A[u,v]=1$ 代表节点$u$和节点$v$之间相连（节点之间存在边关系），$A[u,v]=0$ 代表节点$u$和节点$v$之间不相连。
从上面的式子来看，如果在一个很大的图谱上做递归运算，且图谱的度数很深，甚至存在环路，则需要非常大的栈内存，同时计算效率也不高。

那么我们再对公式进行转换，假设$e$是图谱上所有节点中心度的集合，也就是

$e=\{e_1,e_2,e_3,\dots \dots ,e_v{\}}^T$                 (2),

那么将式子(2) 代入式子 (1), 得我们可以得到下面的式子(3)：

$\lambda e=Ae$                 (3),

我们可以发现，式子(3)就是一个典型的特征值方程，其中$e$是邻接矩阵$A$的特征向量，$\lambda$是邻接矩阵的特征值。

定义：设A是n阶矩阵，$\lambda$为一个数，若存在非零向量X，使得$\lambda X=AX$, 则称数$\lambda$为矩阵A的特征值，非零向量X为矩阵A的对应于特征值$\lambda$的特征向量。

则我们可以将图谱领接矩阵A的特征向量$e$做为其每个节点的中心度度量值。同时，我们也希望衡量节点中心度的值为正数，那么通过Perron-Frobenius定理，我们可以证明特征向量$e$中的每一个分量都是正值，满足节点中心度的度量值的要求。

Perron–Frobenius定理证明了存在一个方阵，如果其行列的元素为正值，则存在最大的特征值${\lambda }_{pf}$，并且该特征值所对应的特征向量的每个元素都是正数。

由上面的公式和定理可以得知，一个矩阵如果存在最大的特征值，那么这个特征值就是该矩阵的主特征值，其对应的特征向量则是主特征向量，并且主特征向量里面的每一个元素都是正数。我们可以将邻接矩阵A的主特征向量$e$的每一个分量值，作为其节点所对应的中心度度量值，它体现了节点所连接的邻节点的数量以及所连接邻节点的重要性。

那么我们来看看特征向量的一般求法，以公式(3)为例，A是n阶邻接矩阵，移项后公式(3)可以写成
$(A-\lambda E)e=0$                (4),
其中$E$是n阶单位矩阵。又因为$e$是非零向量，那么可以进一步得出
$｜A-\lambda E｜=0$                (5),
解此行列式，即公式(5)，获得的值${\lambda }_i$即为矩阵A的特征值 ，再将${\lambda }_i$值代入公式(4)中，就可以求出对应的特征向量。

例如：$A=\left|\begin{array}{ccc}1& -2& 2\\ -2& -2& 4\\ 2& 4& -2\end{array}\right|$
那么 $｜A-\lambda E｜=\left|\begin{array}{ccc}1-\lambda & -2& 2\\ -2& -2-\lambda & 4\\ 2& 4& -2-\lambda \end{array}\right|=0$
$=(1-\lambda )(2+\lambda {)}^2-16-16+4(2+\lambda )-16(1-\lambda )+4(2+\lambda )=0$
$=-{\lambda }^3-3{\lambda }^2+24\lambda -28=0$
我们看见一个3阶矩阵的行列式方程就有3个根${\lambda }_1,{\lambda }_2,{\lambda }_3$。那么如果图谱是100万的节点，那么就会组成一个100万阶的邻接矩阵，它的行列式方程将有100万个根。由此可见，我们需要找到一个更加合理的办法去求出大图的特征向量。

这时候我们要引入幂迭代 (power iteration) 法。

幂迭代 (power iteration) 法是线性代数中一种非常重要的方法，可对特征值分解和奇异值分解等问题进行求解。比较特别的是，当我们要对来自真实世界的大规模数据进行奇异值分解时，基于幂迭代法的奇异值分解在保证精度的同时可以极大提高计算效率。^[2]

类似于Jacobi和Gauss-Seidel两个迭代算法，幂迭代 (power iteration) 法也是采取迭代计算的方式去得到一个近似值逼近主特征向量。假设我们有一个具有主特征值的邻接矩阵$A$，我们选取一个非零向量$x_0$作为矩阵$A$的主特征向量的初始向量，那么幂迭代的计算方法如下：
$x_1=A{x}_0$
$x_2=A{x}_1=A(A{x}_0)=A^2{x}_0$
$x_3=A{x}_2=A(A^2{x}_0)=A^3{x}_0$
…………
$x_k=A{x}_{k-1}=A(A^{k-1}{x}_0)=A^k{x}_0$
当k足够大的时候，也就是迭代次数足够多时，我们就能逼近矩阵$A$的主特征向量。

例如：有一个矩阵$A=\left[\begin{array}{cc}2& -12\\ 1& -5\end{array}\right]$，且假设一个初始化的非零特征向量为$x_0=\left[\begin{array}{c}1\\ 1\end{array}\right]$
使用幂迭代法，我们可以得到以下计算过程

$x_1=A{x}_0=\left[\begin{array}{cc}2& -12\\ 1& -5\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]=\left[\begin{array}{c}-10\\ -4\end{array}\right]=-4\left[\begin{array}{c}2.50\\ 1.00\end{array}\right]$
$x_2=A{x}_1=\left[\begin{array}{cc}2& -12\\ 1& -5\end{array}\right]\left[\begin{array}{c}-10\\ -4\end{array}\right]=\left[\begin{array}{c}28\\ 10\end{array}\right]=10\left[\begin{array}{c}2.80\\ 1.00\end{array}\right]$
$x_3=A{x}_2=\left[\begin{array}{cc}2& -12\\ 1& -5\end{array}\right]\left[\begin{array}{c}28\\ 10\end{array}\right]=\left[\begin{array}{c}-64\\ -22\end{array}\right]=-22\left[\begin{array}{c}2.91\\ 1.00\end{array}\right]$
…………
$x_6=A{x}_5=\left[\begin{array}{cc}2& -12\\ 1& -5\end{array}\right]\left[\begin{array}{c}-280\\ -94\end{array}\right]=\left[\begin{array}{c}568\\ 190\end{array}\right]=190\left[\begin{array}{c}2.99\\ 1.00\end{array}\right]$

经过第6次的迭代，我们发现向量$x_6$的单位向量$\left[\begin{array}{c}2.99\\ 1.00\end{array}\right]$已经十分接近矩阵$A$真实的主特征向量$\left[\begin{array}{c}3\\ 1\end{array}\right]$.

当然，随着迭代次数的增大，矩阵计算中的各分量元素在计算过程中可能会出现数值溢出，所以我们需要对每个元素进行归一化处理，幂迭代法的一般性算法可以写为：
step1: $x_k=A{x}_{k-1}$
step2: $x_k=x_k/\Vert x_k{\Vert }_2$
其中，$\Vert x_k{\Vert }_2$是特征向量的${\ell }_2$范数，意思是特征向量中所有元素的平方和再开方。

有一种观点认为，特征向量中心度是在图中进行无限长度的随机游走时，一个节点被访问到的可能性的排序，从上述的幂迭代法就可以看出这个观点依据。^[1]

以上就是特征向量中心度算法的基本实现原理。大家有时间也可以学习一下Rayleigh quotient表达式，它是在知道矩阵特征向量的前提下，计算矩阵对应特征值近似解的方法。

源码解析

接下来，我们将从一个开源框架SparklingGraph去学习如何用代码实现中心度的计算。因为我们平时在处理工业界的图数据时，都是上亿的节点和边，所以这也是为什么去选择一个分布式的图计算框架来讲解。

GitHub : https://github.com/sparkling-graph/sparkling-graph

因为该开源框架是基于Spark Graphx去实现的图计算方法，所以其开发语言是100%的Scala。这里建议大家具备一些Spark和Scala的基础知识，不然下面的源码解读比较难以理解。

Spark Graphx的官网： https://spark.apache.org/docs/latest/graphx-programming-guide.html

我们直接解读核心单例对象EigenvectorCentrality中的computeEigenvector方法

/*** Created by Roman Bartusiak ([e-mail] http://riomus.github.io).*/
object EigenvectorCentrality extends VertexMeasure[Double]{/*** Generic Eigenvector Centrality computation method, should be used for extensions, computations are done until @continuePredicate gives true* @param graph - computation graph* @param vertexMeasureConfiguration - configuration of computation* @param continuePredicate - convergence predicate* @param num - numeric for @ED* @tparam VD - vertex data type* @tparam ED - edge data type* @return graph where each vertex is associated with its eigenvector*/
1  def computeEigenvector[VD:ClassTag,ED:ClassTag](graph:Graph[VD,ED],vertexMeasureConfiguration: VertexMeasureConfiguration[VD,ED],continuePredicate:ContinuePredicate=convergenceAndIterationPredicate(1e-6))(implicit num:Numeric[ED])={
2    val numberOfNodes=graph.numVertices
3    val startingValue=1.0/numberOfNodes
4    var computationGraph=graph.mapVertices((_,_)=>startingValue)
5    var iteration=0
6    var oldValue=0d
7    var newValue=0d8    while(continuePredicate(iteration,oldValue,newValue)||iteration==0){
9      val iterationRDD=computationGraph.aggregateMessages[Double](
10      sendMsg = context=>{
11        context.sendToDst(num.toDouble(context.attr)*context.srcAttr)
12        context.sendToSrc(0d)
13        if(vertexMeasureConfiguration.treatAsUndirected){
14          context.sendToSrc(num.toDouble(context.attr)*context.dstAttr)
15          context.sendToDst(0d)
16        }
17      },
18      mergeMsg = (a,b)=>a+b)
19      val normalizationValue=Math.sqrt(iterationRDD.map{case (_,e)=>Math.pow(e,2)}.sum())
20      computationGraph=computationGraph.outerJoinVertices(iterationRDD)((_,_,newValue)=>if(normalizationValue==0) 0 else newValue.getOrElse(0d)/normalizationValue)
21      oldValue=newValue
22      newValue=computationGraph.vertices.map{case (_,e)=>e}.sum()/numberOfNodes
23      iterationRDD.unpersist()
24      iteration+=1
25    }
26    val out=computationGraph
27    out.unpersist(false)
28    out
29  }

需要注意的是第1行代码中computeEigenvector方法中有一个隐式变量(implicit num:Numeric[ED])，这里其实是指GraphX对象中边上的属性是要可计算的，这里相当于是边的权重值。
这个方法的输入主要是GraphX对象，它是由VertexRDD和EdgeRDD组成，由用户自己从数据源读取图数据生成。另外输入的就是封装了算法参数的VertexMeasureConfiguration对象。

第2-3行，表示计算全图的节点，所有节点的初始值为1.0/总节点数。这里相当于幂迭代法中初始化的主特征向量值。
第4行，表示用一个map方法将节点的属性都统一成我们之前的初始化值，且节点只包含这一个属性值，并以此形成后续迭代所用的计算图。
第8行到第24行就是我们之前说的幂迭代法的循环体，它的循环控制是由convergenceAndIterationPredicate这个函数实现的。

/*** Created by Roman Bartusiak ([e-mail] http://riomus.github.io).*/
object EigenvectorUtils {type ContinuePredicate=(Long,Double,Double)=>Booleandef convergenceAndIterationPredicate(delta:Double, maxIter:Long=100)(iteration:Long, oldValue:Double, newValue:Double)={Math.abs(newValue-oldValue)>delta && iteration<maxIter}
}

这个函数是用来控制循环体什么时候停止，当迭代循环的次数大于100时，或者前一次迭代计算的值和当前迭代计算的值的差的绝对值小于一个极小值，那么循环就停止。从上面的代码可以看出这个极小值默认为1e-6.

第9-18行，则是使用Graphx的消息发送算子aggregateMessages，定义了图上每个节点向邻居节点所发送的消息，以及节点收到消息后的合并方法。我们从上面可以看到第11行就代表着将每一条边上的开始(source vertex)节点的值乘以当前边的权重，然后发送到结束节点（target vertex）。每个节点的初始值就是我们在第2-3行代码里定义的初始化的值。第18行就是节点对消息的聚合函数，这里看到就是全部相加。
这段代码本质就是将当前节点的所有邻居节点的中心度值发送过来，并进行聚合相加当做当前节点的中心度值。让我们回顾一下邻接矩阵，$A[u,v]=1$ 代表节点$u$和节点$v$之间相连，为0则不相连；所以这个聚合相加操作本质上就等于我们幂迭代法中邻接矩阵和主特征向量的矩阵相乘。这就是整个代码的核心，比较抽象，大家可以多花些时间思考和理解。

第19-20行实际上就是主特征向量的${\ell }_2$范数计算，也就是归一化。

最终输出的也是一个Graphx对象，其中的VertexRDD由一个二元组（节点ID，节点的特征向量中心度）组成。

以上就是特征向量中心度的算法原理与源码解析，希望对大家有帮助。文章中有写得不正确的地方希望大家帮忙指出并给我留言，谢谢各位读者。