我的微信公众号是“黄泓图计算分享”，很多朋友反映公众号上看文章不方便，就在简书上同步一份

图包含两大要素：节点和边。节点和边上都可以有属性，边既可以有方向也可以无向。对于图的建模，可以包含结构上的特征和聚集的特征。特征表征的粒度，可以是节点，边，子图等等。

本文先从最常见的情况讲起：以节点为粒度的结构特征。以节点为粒度的结构特征，往往同时会作为图嵌入（Graph Embedding）算法的输入，从而得到描述节点所在的局部结构的向量。例如度以及三角形的个数，可以作为Role2vec[5]或者GraphSage[6]的输入。这些后面再详谈。

以节点为粒度的结构特征，最简单的是度（degree），也就是一个节点关联的邻居节点的个数。在很多应用中，想必大家都有意无意用过这个特征。

节点的重要性

描述节点重要性的特征，一般有两类：一类是基于一定的定义直接描述的特征，如度，介数中心性和紧密中心性等等。另外一类是源于互联网链接分析的算法，如HITS算法和PageRank算法。

根据定义直接描述的节点重要性

介数中心性（betweeness）描述的是一个节点作为枢纽节点的重要程度。描述一个节点作为枢纽的重要程度还有别的方法（如HITS，下面会提到），介数中心性采用的是最粗暴的定义方法：一个节点的介数中心性是经过这个节点的最短路径条数与所有最短路径条数的比值。因为定义简单粗暴，所以计算起来也比较麻烦。如果要进行分布式计算的话需要设计特殊的算法。比较好的一个实现来自sparkling graph：

https://github.com/sparkling-graph/sparkling-graph/tree/master/operators/src/main/scala/ml/sparkling/graph/operators/measures/vertex/betweenness

这里betweeness使用了两个实现，分别是Edmonds[1]和Hua[2]。亲测Hua的实现效率更加高一些，奈何话题太冷，论文没什么人引用。

紧密中心性（closeness centrality）描述一个节点到图中其他节点的难易程度。取的是这个节点到图中其他节点的距离平均数的倒数。如果这个值比较大，那么说明这个节点到其他节点大部分都是经过很少的几步就行，整个图结构比较紧密。对于这个指标，sparkling graph也有比较好的实现。

三角形计数（triangle count） 是用来描述一个图中的顶点之间聚集密集程度的系数。节点所在的局部结构越密集，三角形个数越多。对于这个指标，spark graphx有比较好的实现。

基于链接分析的节点重要性特征

HITS算法和PageRank算法最初的提出都是用于衡量Web图模型中页面的重要程度。他们基于不同的假设。

用户浏览网页的随机游走模型(Random Surfer Model)

用户浏览网页的随机游走模型(Random Surfer Model)假设用户随机游走网页由两部分构成：

（1）直接跳转：用户进入一个网页a，并且以等概率访问这个网页的链接（假设这个网页有d个链接，则为1/d）

（2）远程跳转（teleporting）：用户浏览到某个程度之后决定不再继续深入，而是输入另外一个网址重新浏览。

PageRank算法

假设：

（1）数量假设：一个页面节点接收到的入链数量越多，他就越重要

（2）质量假设：如果指向一个页面节点的页面节点重要，这个页面就越重要

基于这样的假设以及random surfer model可以得到PageRank的迭代公式。首先一个页面节点a可能以两者方式受到访问：一种是远程跳转，一种是直接跳转。

假设图中有N个节点，用户有概率1-p会进行远程跳转，则远程跳转的概率是：

进入远程跳转的概率 x 选中这个节点的概率=(1-p)x(1/N)

第二种方式是有其他节点等概率跳转而来。假设节点a的一个邻居b，b自己有degree(b)个邻居，b自己的page rank分数为PR(b)，则b能够给a的分数为PR(b)/degree(b)。a的所有邻居能分给a的page rank分数加起来，再乘以用户进入直接跳转的概率p，就是在直接跳转这种方式下节点a能够得到的page rank分数。

远程跳转和直接跳转两部分分数结合起来，也就是大家一般在博客里看到的page rank迭代公式。

HITS算法

HITS算法认为节点有两个特性：一是节点本身的重要程度，即权威度（Authority）。二是节点作为引向重要节点的枢纽节点的重要程度，即枢纽度（Hub）。

假设：

（1）一个Authority值高的节点应该有很多Hub值高的节点指向

（2）一个Hub值高的节点应该指向很多Authority值高的节点

HITS的迭代方式就是这样Authority值和Hub值迭代相互增强：

（1）一个节点的Authority值是指向他的节点的hub值之和（对应假设1）

（2）一个节点的Hub值是他指向的节点的Authority值之和（对应假设2）

执行1，2直到收敛

如果没有种子集合，HITS的初始值可以所有节点的authority和hub值都设置为1。如果有种子集合，则构图方式为对种子集合进行扩充，凡是和种子集合里面的节点有直接指向关系的节点都扩充进来，然后使用上述的迭代步骤。

应用场景

PageRank可以用于仅仅依靠链接指向判断图中的重要节点。HITS和page rank值本身也可以作为节点特征输入分类模型。例如对于企业违约风险的预测当中，[3]提到基于企业之间的担保关系可以构建一个有向图。这个论文使用了不同的图特征作为输入，发现HITS得到的authority和hub值的特征权重比较大。作者对此的解释是：风险大的企业，需要找很多公司担保，从而authority值高，最后违约率高。风险低，稳健的企业，倾向于担保很多企业，Hub值就会很高。其实单纯从这个角度来讲，直接用节点的出度和入度做特征也是可以的。HITS得到的好处在于可以实现Hub和Authority分值的相互增强。

HITS与PageRank在应用场景上的一个重要区别是HITS可以从一个有标注的种子集合向外扩充得到其他同样相关的节点中的重要节点。[4]使用HITS从一个专家标注的与“时尚”有关的网页地址的种子集合进行扩充，自动对外部关联的网页与“时尚”的相关性进行排序。重要的一点是作者提到PageRank和HITS在使用场景上的重要区别：

（1）PageRank在你有比较完整的链接信息的时候才有效，而HITS可以在链接信息不完整的时候也发挥作用

（2）HITS可以利用人工标注的样本进行挖掘，PageRank不行（除非personalized page rank，不过那是另一个故事了）

引用

[1]Edmonds N , Hoefler T , Lumsdaine A . A space-efficient parallel algorithm for computing betweenness centrality in distributed memory[C]// 2010 International Conference on High Performance Computing, HiPC 2010, Dona Paula, Goa, India, December 19-22, 2010. IEEE, 2010.

[2] Hua Q S , Fan H , Ai M , et al. Nearly Optimal Distributed Algorithm for Computing Betweenness Centrality[C]// IEEE International Conference on Distributed Computing Systems. IEEE, 2016.

[3] Niu Z, Cheng D, Yan J,et al. A hybrid approach for riskassessment of loan guarantee network[J]. Papers, 2017.

[4]https://www.confluent.io/blog/ranking-websites-real-time-apache-kafkas-streams-api/

[5]Ahmed N K , Rossi R , Lee J B , et al. Learning Role-based Graph Embeddings[J]. 2018.

[6]Hamilton W L , Ying R , Leskovec J . Inductive Representation Learning on Large Graphs[J]. 2017.