图算法实践之k-hop

举报
你好_TT 发表于 2021/05/12 15:16:47 2021/05/12
【摘要】 k-hop中文译名是k-跳,或者为k-邻。所谓的k-hop算法,指的是从某个起点出发,寻找所有与其最短路径不超过k的顶点的集合(或者:寻找所有与其最短路径为k的顶点的集合)。k为正整数。当k=1时,结果即为起点的所有邻点。

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_1B_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)的诞生。只有ErdosErdos数为0,与Erdos有过合作的数学家的Erdos数为1,除Erdos外,与Erdos数为1的数学家合作过但没有与Erdos合作过的数学家的Erdos数为2,以此类推。

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

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

合作图.PNG

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

k-hop.PNG               Erdos为1.PNG

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

2.PNG                 1.PNG

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

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

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

关于k-hop的说明

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

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

k-hop的应用场景

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

【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200