算法一览表 为满足用户各种场景需求，图引擎服务提供了丰富的基础图算法、图分析算法和图指标算法。算法简介如下表所示。 表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） 用于解决图论研究中的一个经典算法问题，旨在寻找图中两节点之间的所有最短路径。 带一般过滤条件最短路径算法（Filtered Shortest Path） 寻找两点间满足过滤条件的最短路径，如有多条，返回任意一条最短路径。 单源最短路（SSSP） 图论中的经典问题，给定一个节点（称为源），该算法给出从该源节点出发到其余各节点的最短路径长度。 点集最短路（Shortest Path of Vertex Sets） 用于发现两个点集之间的最短路径。适用于互联网社交、金融风控、路网交通、物流配送等场景下的区块之间关系分析。 关联路径（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 Coefficient） 聚类系数是表示一个图中节点聚集程度的系数，证据显示，在现实的网络中，尤其是在特定的网络中，由于相对高密度连接点的关系，节点总是趋向于建立一组严密的组织关系。 中介中心度算法（Betweenness Centrality） 中介中心度算法（Betweenness Centrality）以经过某个节点的最短路径数目来刻画节点重要性的指标。 边中介中心度（Edge-betweenness Centrality） 边中介中心度算法（Edge-betweenness Centrality）以经过某条边的最短路径数目来刻画边重要性的指标。 OD中介中心度（OD-betweenness Centrality） OD中介中心度算法（OD-betweenness Centrality）在已知一系列OD出行计划前提下，以经过某个点/某条边的最短路径数目来刻画边重要性的指标。 单点环路检测（Single-Vertex-Circles-Detection） 单点环路检测是一个经典的图问题，意在寻找图中的环路。环路上的点较好地体现了该点的重要性，适用于交通运输、金融风控等场景。 点集共同邻居（Common Neighbors of Vertex Sets） 可以得到两个点集合（群体集合）所共有的邻居（即两个群体临域的交集），直观的发现与两个群体共同联系的对象，如发现社交场合中的共同好友、消费领域共同感兴趣的商品、社区群体共同接触过的人，进一步推测两点集合之间的潜在关系和联系程度。 点集全最短路（All Shortest Paths of Vertex Sets） 点集最短路算法用于发现两个点集之间的所有最短路径，可应用于互联网社交、金融风控、路网交通、物流配送等场景下的区块之间关系的分析。 带一般过滤条件环路检测（Filtered Circle Detection） 目的是寻找图中所有满足过滤条件的环路。适用于金融风控中循环转账检测、反洗钱，网络路由中异常链接检测，企业担保圈贷款风险识别等场景。 子图匹配（Subgraph Matching） 子图匹配（subgraph matching）算法的目的是在一个给定的大图里面找到与一个给定小图同构的子图，这是一种基本的图查询操作，意在发掘图重要的子结构。 带过滤全对最短路径（Filtered All Pairs Shortest Paths） 带过滤全对最短路径（Filtered All Pairs Shortest Paths）是寻找图中任意两点之间满足条件的最短路径。当前，考虑到实际应用场景，此算法需要用户指定起点集（sources）和终点集（targets），本算法将返回起点集合到终点集合之间满足条件的两两全最短路径。 带过滤全最短路径（Filtered All Shortest Paths） 带过滤全最短路径（Filtered All Shortest Paths）是在最短路径算法（Shortest Path）基础上支持条件过滤，寻找图中两节点之间满足条件的全最短路径。 TopicRank算法 TopicRank算法12345热线多维度话题排序算法之一，适用于政务12345热线投诉话题排序。 带过滤的n_paths算法（filtered_n_paths） 带过滤的n_paths算法是给定起始点source、目的点target、跳数k、路径数n、过滤条件filters，找出source和target间不多于n条的k跳无环路径。 时序路径分析算法（Temporal Paths） 时序路径分析算法区别于静态图上的路径分析，结合了动态图上信息传播的有序性，路径上后一条边的经过时间要晚于或等于前一条边，呈现时间递增（或非减）性。 父主题： 算法参考