节点特征
一个图包含两个主要元素:节点和边。节点和边上都可以有属性，边可以是有向的也可以是无向的。图的建模可以包括结构特征和聚集特征。特征表示的粒度可以是节点、边、子图等。
本文从最常见的情况入手:以节点为粒度的结构特征。具有节点粒度的结构特征往往同时作为图嵌入(图？嵌入)算法，从而得到描述节点局部结构的向量。例如，三角形的度数和数量可以用作Role2vec[5]或Graphage [6]的输入。这些将在后面详细讨论。
节点粒度最简单的结构特征是度，即与一个节点相关联的相邻节点的数量。在很多应用中，大家肯定都有意无意地用过这个功能。
节点的重要性
一般来说，描述节点重要性的特征有两种:一种是基于一定定义直接描述的特征，如度、介数、紧密度等。另一类是互联网链接分析衍生的算法，如HITS算法、PageRank算法等。
由定义直接描述的节点重要性
介数描述了一个节点作为中枢节点的重要性。还有其他方式来描述一个节点作为枢纽的重要性(比如HITS，下面会提到)。介数的定义是最粗糙的:节点的介数是通过该节点的最短路径数与所有最短路径数的比值。因为定义简单粗暴，所以计算起来也比较麻烦。如果要进行分布式计算，需要设计专门的算法。更好的实现来自于sparkling？图表:
/sparkling-graph/sparkling-graph/tree/master/operators/src/main/Scala/ml/sparkling/graph/operators/measures/顶点/介数
这里betweeness使用了两个实现，即Edmonds[1]和Hua[2]。亲测华的执行效率比较高，但是题目太冷，很少有人引用论文。
紧密中心性(紧密性？中心性)描述了图中一个节点相对于其他节点的难度。取图中从这个节点到其他节点的平均距离的倒数。如果这个值很大，说明从这个节点到其他节点的大部分节点都经过了几步，整个图结构比较紧凑。对于这个指标，闪闪？Graph也有更好的实现。
三角形计数(三角形？算)？是一个系数，用来描述图中顶点之间的聚集密度。节点所在的局部结构越密集，三角形就越多。对于这个指标，火花？Graphx有更好的实现。
基于链接分析的节点重要性特征
HITS算法和PageRank算法最初是为了衡量网页在Web图模型中的重要性而提出的。它们基于不同的假设。
随机游走模型(Random？冲浪者？型号)
随机游走模型(Random？冲浪者？Model)假设用户随机浏览由两部分组成的网页:
(1)直接跳转:用户进入一个网页A，以等概率访问该网页的链接(假设该网页有D个链接，则为1/d)。
(2)瞬移:浏览到一定程度后，用户决定不再进一步，而是进入另一个网站再次浏览。
PageRank算法
假设:
(1)数量假设:一个页面节点收到的链接越多，越重要。
(2)质量假设:如果指向某个页面节点的页面节点重要，则该页面越重要。
基于这种假设和随机？冲浪者？模型可以得到PageRank的迭代公式。首先，一个页面节点A可能有两种访问方式:一种是远程跳转，另一种是直接跳转。
假设图中有n个节点，用户有1-p的概率，那么远程跳转的概率为:
进入远程跳跃的概率有多大？x？选择这个节点的概率=(1-p)x(1/N)
第二种方式是从其他节点等概率跳转。假设节点A的邻居B有自己的度(B)邻居，B有自己的页面？Rank得分是PR(b)，那么B能给A的得分就是PR(b)/degree(b)。a的邻居都能给一页吗？排名分数相加，乘以用户进入直接跳转的概率p，就是节点A通过这种方式可以得到的页面。排名得分。
远程跳转和直接跳转的分数相加，就是大家平时在博客里看到的页面。秩迭代公式。
HITS算法
HITS算法认为一个节点有两个特征:一个是节点本身的重要性，也就是权限。二是一个节点作为枢纽节点通向一个重要节点的重要性，即枢纽度。
假设:
(1)一个权限值高的节点应该有很多Hub值高的节点。
(2)一个Hub值高的节点应该指向很多权限值高的节点。
HITS的迭代方式是这样的:权威价值和枢纽价值是迭代的、相互促进的；
(1)一个节点的权限值是指向他的节点的hub值之和(对应于1的假设)。
(2)节点的Hub值是他所指向的节点的权限值之和(对应于假设2)
执行1，2直到收敛。
如果没有种子集，对于所有节点的权限和中心值，HITS的初始值可以设置为1。如果有种子集，合成方法是扩展种子集，所有与种子集中的节点有直接指向关系的节点都被扩展，然后使用上述迭代步骤。
应用场景
PageRank仅通过链接就可以指向判断图中的重要节点。点击量和页面？等级值本身也可以作为节点特征输入到分类模型中。比如在企业违约风险的预测中，[3]提到可以基于企业之间的担保关系构造一个有向图。本文以不同的图特征作为输入，发现HITS得到的权威和枢纽值的特征权重比较大。笔者的解释是:风险高的企业需要找很多公司担保，这样权威值高，最终违约率高。低风险、稳健的企业往往担保企业多，枢纽价值会高。其实从这个角度来说，也可以直接用节点的出度和入度作为特征。HITS的好处是可以实现枢纽和权威评分的相互提升。
HITS和PageRank在应用场景上的一个重要区别是，HITS可以从一个带标签的种子集扩展到其他同样相关的重要节点。[4]使用HITS扩展由专家标记的与“时尚”相关的网页地址的种子集，并自动排列外部相关网页与“时尚”的相关性。重要的一点是作者提到了PageRank和HITS在使用场景上的重要区别:
(1)PageRank只有在你拥有相对完整的链接信息时才有效，而HITS在链接信息不完整时也能发挥作用。
(2)HITS可以使用人工标注的样本进行挖掘，而PageRank不能(除非个性化？佩奇？排名，不过那是后话了)
引用
[1]埃德蒙兹？n？,?霍夫勒？t？,?卢斯汀？答？。？答？节省空间？平行？算法？为了什么？计算？介于之间？中心性？在？分布式？内存[C]//？2010?国际？会议？开？高？性能？计算，？HiPC？2010,?多娜？宝拉。果阿，？印度，？十二月？19-22,?2010.？IEEE，？2010.
[2]?华？q？s？,?范？h？,?Ai？m？,?et？艾尔。？差不多？最优？分布式？算法？为了什么？计算？介于之间？中心性[C]//？IEEE？国际？会议？开？分布式？计算？系统。？IEEE，？2016.
[3]?牛？z，？程？d，？颜？j，et？艾尔。？答？混血儿？接近？为了什么？风险评估？的？贷款？保证？网络[J]。？论文？2017.
[4]https://www . confluent . io/blog/ranking-websites-real-time-Apache-kafkas-streams-API/
[5]艾哈迈德？n？k？,?罗西。r？,?李？j？b？,?et？艾尔。？学习？基于角色？图表？嵌入[J].？2018.
[6]汉密尔顿？w？l？,?英？r？,?莱斯科维奇？j？。？归纳？代表权？学习？开？大号的？图表[J]。？2017.