文档首页 > > 用户指南> 算法参考> 算法一览表

算法一览表

分享
更新时间:2020/05/25 GMT+08:00

为满足用户各种场景需求,图引擎服务提供了丰富的基础图算法、图挖掘算法和图指标算法。算法简介如下表所示。

表1 算法一览表

算法

介绍

PageRank算法

又称网页排名,是一种由搜索引擎根据网页(节点)之间相互的超链接计算的技术,用来体现网页(节点)的相关性和重要性。

PersonalRank算法

PersonalRank算法又称Personalized PageRank算法。该算法继承了经典PageRank算法的思想,利用图链接结构来递归地计算各节点的重要性。与PageRank算法不同的是,为了保证随机行走中各节点的访问概率能够反映出用户的偏好,PersonalRank算法在随机行走中的每次跳转会以(1-alpha)的概率返回到source节点,因此可以基于source节点个性化地计算网络节点的相关性和重要性(PersonalRank值越高,对source节点的相关性/重要性越高)。

k核算法(k-core)

k-core是图算法中的一个经典算法,用以计算每个节点的核数。其计算结果是判断节点重要性最常用的参考值之一,较好的刻画了节点的传播能力。

k跳算法(k-hop)

从起点出发,通过宽度优先搜索(BFS),找出k层与之关联的所有节点。找到的子图称为起点的ego-net。k跳算法会返回ego-net中节点的个数。

最短路径(Shortest Path)

用于解决图论研究中的一个经典算法问题,旨在寻找图中两节点之间的最短路径。

全最短路(All Shortest Paths)

用于解决图论研究中的一个经典算法问题,旨在寻找图中两节点之间的所有最短路径。

单源最短路(SSSP)

图论中的经典问题,给定一个节点(称为源),该算法给出从该源节点出发到其余各节点的最短路径长度。

关联路径(n-Paths)

该算法用于寻找图中两节点之间在k层关系内的n条路径。适用于关系分析、路径规划、网络规划等场景。

紧密中心度(Closeness Centrality)

紧密中心度是一个节点到所有其他可达节点的最短距离的平均,该指标可以用来衡量信息从该节点传输到其他节点的时间长短。节点的“Closeness Centrality”越小,其所在图中的位置越中心。

标签传播(Label Propagation)

一种基于图的半监督学习方法,其基本思路是用已标记节点的标签信息去预测未标记节点的标签信息。利用样本间的关系建图,节点包括已标注和未标注数据,其边表示两个节点的相似度,节点的标签按相似度传递给其他节点。标签数据就像是一个源头,可以对无标签数据进行标注,节点的相似度越大,标签越容易传播。

Louvain算法

基于模块度的社区发现算法,该算法在效率和效果上都表现较好,并且能够发现层次性的社区结构,其优化目标是最大化整个社区网络的模块度。

关联预测(Link Prediction)

给定两个节点,根据Jaccard度量方法计算两个节点的相似程度,预测他们之间的紧密关系。

Node2vec算法

通过调用word2vec算法,把网络中的节点映射到欧式空间,用向量表示节点的特征。Node2vec通过回退参数P和前进参数Q来生成从每个节点出发的随机步,它带有BFS和DFS的混合,回退概率正比于1/P,前进概率正比于1/Q,每个节点出发生成多个随机步,反映出网络的结构信息。

实时推荐(Real-time Recommendation)

一种基于随机游走模型的实时推荐算法,能够推荐与输入节点相近程度高、关系或喜好相近的节点。该算法可以基于历史购买或浏览数据进行相近商品推荐,也可以针对人进行相近喜好的潜在好友推荐。

共同邻居(Common Neighbors)

是一种常用的基本图分析算法,可以得到两个节点所共有的邻居节点,直观地发现社交场合中的共同好友、消费领域共同感兴趣的商品,进一步推测两个节点之间的潜在关系和相近程度。

联通分量(Connected Component)

联通分量代表图中的一个子图,当中所有节点都相互连接。考虑路径方向的为强联通分量(strongly connected component),不考虑路径方向的为弱联通分量(weakly connected component)。

说明:

本算法计算得到的是弱联通分量。

度数关联度(Degree Correlation)

度数关联度算法计算所有边上起点和终点度数之间的Pearson关联系数,常用来表征图中高度数节点是否和高度数节点相连。

三角计数(Triangle Count)

不考虑边的方向,统计图中三角形个数。三角形越多,代表图中节点关联程度越高,组织关系越严密。

聚类系数(Cluster Coeffcient)

聚类系数是表示一个图中节点聚集程度的系数,证据显示,在现实的网络中,尤其是在特定的网络中,由于相对高密度连接点的关系,节点总是趋向于建立一组严密的组织关系。

分享:

    相关文档

    相关产品

文档是否有解决您的问题?

提交成功!

非常感谢您的反馈,我们会继续努力做到更好!

反馈提交失败,请稍后再试!

*必选

请至少选择或填写一项反馈信息

字符长度不能超过200

提交反馈 取消

如您有其它疑问,您也可以通过华为云社区问答频道来与我们联系探讨

智能客服提问云社区提问