图算法实践之k-hop

k-hop是什么

      k-hop中文译名是k-跳，或者为k-邻。所谓的k-hop算法，指的是从某个起点出发，寻找所有与其最短路径不超过k的顶点的集合（或者：寻找所有与其最短路径为k的顶点的集合）。k为正整数。当k=1时，结果即为起点的所有邻点（包括起点）。

k-hop怎么计算

      k-hop算法采用的是宽度优先搜索（BFS）的方式。

Step1:记k-跳以内的所有顶点的集合为A_k(包括起点)，第k-跳的顶点的集合为B_k，特殊地，令A_0=B_0={起点};

Step2:获取起点的所有邻点(不包括起点)，记为C_1，得到A_1=A_0∪C_1，B_1=C_1；

Step3：判断是否已经达到k-跳，如果未达到第k-跳，判断集合B_i是否为空，若为空，则直接返回，若不为空，执行Step4,若已经到达第k-跳，返回结果;

Step4: 获取B_i中所有顶点的邻点，要求这些邻点不包含在A_i中，记为C_{i+1}，令A_{i+1}=A_i∪C_{i+1}，B_{i+1}=C_{i+1},执行Step3。

k-hop实践之Erdos数

      Erdos作为一名伟大的数学家，其发表的论文数约有1500篇，超过了任何一位数学家，而且他有很多的合作者----超过了500人，这与早期的数学家更倾向于独立研究的工作方式有很大不同，另外，有超过6000人尽管没有和Erdos合作过论文，但是他们和Erdos的合作者合作过论文，这种现象促使了Erdos数（Erdos number）的诞生。只有Erdos的Erdos数为0，与Erdos有过合作的数学家的Erdos数为1，除Erdos外，与Erdos数为1的数学家合作过但没有与Erdos合作过的数学家的Erdos数为2，以此类推。

      从图的角度来看，可以通过构造合作图（collaboration graph）来表示。合作图G以所有的数学家作为顶点，两个数学家如果合作过论文，则在表示其顶点的顶点对之间连一条边。一个数学家的Erdos数就是该顶点在图G上与Erdos顶点之间的最短路径的长度！

      下面是合作图的一个子图。

      设置k=1, 运行k-hop算法，可以得到Erdos数不超过1的数学家的集合。

      如果想知道Welis的Erdos数，设置相应参数，运行最短路径算法，如下图所示

      得到Erdos顶点和Welis顶点之间的最短路径的长度为3，据此可知Welis的Erdos数为3。

      注：以上的计算和展示都是基于华为云图引擎服务GES平台。GES提供标准的k-hop算法，并且支持带过滤条件的k-hop算法，使之更灵活和实用，具体可参考GES k-hop算法。

      关于Erdos数有很多的研究和变种，具体可参考网站https://en.wikipedia.org/wiki/Erd%C5%91s_number和https://oakland.edu/enp/，相对完整的合作图数据可通过网站https://oakland.edu/enp/或者http://vlado.fmf.uni-lj.si/pub/networks/data/获取。

关于k-hop的说明

      根据六度分离理论，理想状态下，任何一个人都可以通过最多五个人与另外一个人产生联系，也就是说，任何一个人6-跳范围内可覆盖所有人。

      由于k值越大，覆盖的点越多，实际用的时候一般会限制返回结果的数量，或者对搜索过程中的点边加上限制条件。

k-hop的应用场景

      k-hop适用于关系发现、影响力预测、好友推荐等场景。