技术科普｜图算法是什么？何时用、怎么用？

导读：图数据库的核心价值在于揭示数据之间隐藏的复杂关系。NebulaGraph 支持丰富的图算法，将隐秘关系高效转化为 actionable 的洞见。 本期技术科普将带你了解图算法与 NebulaGraph Algorithm，看看 NebulaGraph 社区用户如何将这些图算法用于生产环境以及如何上手。

一、 图数据库与图算法

（一）什么是“图”？

想象一下你有一张关系网：

1. 点：代表独立的实体。比如：

• 你微信里的所有好友。

• 城市地图上的所有十字路口。

• 一个项目里的所有任务。

2.线：代表这些实体之间的关系。比如：

• 微信里，你和某个好友是“好友关系”（一条线连着你俩）。

• 城市地图上，两个十字路口之间有一条“道路”（一条线连着两个路口）。

• 项目里，任务 A 必须在任务 B 开始之前完成（一条线从 A 指向 B，表示依赖）。

这种由“点”（图数据库中的顶点或节点）和连接它们的“线”（图数据库中的边）组成的结构，就叫做“图”。

（用 NebulaGraph Studio 进行某公司股权穿透）

（二）什么是图算法？

图算法就是一套聪明的“解题思路”或“工具包”，专门用来分析这种“点”和“线”组成的关系网，计算关于这个网络的问题。

为什么需要专门的“图算法”？

• 超越简单查询：传统查询能找到直接邻居，但图算法能分析整个网络的结构和动态。

• 量化关系价值：把模糊的“关联”变成可计算的指标（如重要性、紧密度、相似度）。

• 发现隐藏模式：自动识别传统关系数据库难以查询的社群、关键枢纽、传播路径。

图算法的应用

找最短路径：

• 问题：从家（点A）导航到公司（点B），导航如何规划最快/综合成本最低的路线？

• 图算法：经典的最短路径算法（如 Dijkstra 算法），能快速计算出从 A 到 B 的所有可能路线中，总权重（通常代表路程长度、通行时间或综合成本）最小的那条路径。

好友推荐：

• 问题：微信/微博/Facebook 怎么知道你可能认识谁，从而给你推荐好友？

• 图算法：基于共同邻居的链路预测算法（如 Jaccard 算法）会分析你的社交网络图：关注你的直接好友（一度邻居），然后考察他们的好友（你的二度邻居）。那些与你拥有大量共同好友（即共同的一度邻居） 但尚未与你建立连接的人，就很可能被推荐给你。

网页排名：

• 问题：搜索引擎怎么决定当你搜索“图算法”时，哪个网页应该排在前面？

• 图算法：PageRank 算法。它的核心思想是：

• 被很多其他网页链接指向的网页（点），通常比较重要（票数多）。

• 被一个重要网页链接指向的网页，也会获得更高的重要性（重要的一票更有分量）。

• 算法会不断计算每个网页的“重要性得分”，得分高的排名就靠前。

二、图算法类型及应用场景

图算法大致可分为以下几种类型：

三、NebulaGraph Algorithm

NebulaGraph Algorithm 是一款基于 GraphX 的 Spark 应用程序，通过提交 Spark 任务的形式使用完整的算法工具对 NebulaGraph 数据库中的数据执行图计算，也可以通过编程形式调用 lib 库下的算法针对 DataFrame 执行图计算。

（一）NebulaGraph 支持的图算法

上图为社区版支持的基础图算法，企业版支持更多高性能算法（如 InfoMap、APSP、DegreeWithTime、HyperANF 等）及基于 ISO-GQL 的自定义图算法。

（二）NebulaGraph 用户这么用

NebulaGraph 用户们如何用图算法解锁业务价值？

1、中心性分析-PageRank

• 何时用：当你需要找出整个网络中“影响力大”或“被广泛引用/连接”的节点时。

• 场景举例：识别社交媒体上的关键意见领袖；在金融交易网络中定位核心中转账户。

• 社区用户：Boss 直聘整合链路追踪（Trace）、系统指标（Metrics）、日志（Logs）三大数据源，构建统一的全链路异常拓扑图，发现多个真子图分散出现在图结构中，每个子图都有“风暴中心”，故采用 PageRank 算法动态计算节点故障权重（Rank 值由节点出入度、链路错误数、事件进行加权计算），得出 Rank 值最高的 TopN 故障节点（即 “风景眼”），从而快速实现根因定位，平均收敛时间仅 20s.

2、 社区发现-Louvain、Hanp

• 何时用？需要在大规模网络中发现层次化的社区结构时。

• 场景举例：社交网络中的兴趣社群划分；电商用户群体细分（购买模式相似）；城市交通流量分区。

• 社区用户：中国移动首先基于所有移动用户构建一个关系网络，采用 Louvain、Hanp 算法进行社区发现与挖掘，如个人的信用评分以及个人之间的关系，然后对这个社区进行打分，识别出这个社区是否为一个欺诈社区或者是一个低信用的社区，从而进行风险管理。

3、社区发现-LabelPropagation

• 何时用？需要快速发现社区，或者网络结构清晰、社区边界明显时。

• 场景举例：实时推荐系统中的用户兴趣圈识别；新闻/信息传播路径上的群体划分。

• 社区用户：在众安保险，LabelPropagation 应用于贷中环节。LabelPropagation 主要是通过一个确定的点 Y 去传播、衍生出它相关点。比如，贷中用户名单中某个用户是严重逾期人员，这个人员便是打上逾期标签的确定点 Y，结合既定的风控规则查看点 Y 关联延伸的点中哪些点出现相似逾期行为，从而判断这些点是否属于严重逾期的社群。

4、ConnectedComponent/StronglyConnectedComponent

• 何时用？ CC (弱连通分量)关心是否可以通过路径（忽略边方向）连通。用于发现孤岛。SCC (强连通分量)：关心是否可以通过有向路径互相到达。用于分析紧密循环依赖。

• 场景举例：分析社交网络中的孤立用户群体 (CC)；研究论文引用网络中的研究学派 (SCC)；分析系统模块间的循环依赖 (SCC)。

• 社区用户：众安保险使用 ConnectedComponent 计算出用户关系图谱。当发现一个手机号被异常数量（如五六十人）标记为“家庭联系人”时，该手机号及其关联用户即构成一个潜在风险社群。处于此类异常社群是用户风险的强信号（充分不必要条件），用户也可能是因亲属涉黑产而被牵连。众安据此对社群内用户进行初步风控标记和深入核查。

四、NebulaGraph AI Suite

除了 NebulaGraph Algorithm, @wey 在 2023 年为社区提供了一个名为 NebulaGraph AI Suite 的项目，它是在 NebulaGraph 之上跑算法的 Python 套件，能给用户一个自然、简洁的高级 API。简单来说，用很少的代码量就可以执行图上的算法相关的任务。

在《手把手教你用 NebulaGraph AI 全家桶跑图算法》中，@wey 给出了详细的上手教程。该项目完全开源，如果你有新的 idea, 欢迎共建～

五、行动起来～

NebulaGraph Algorithm，提供了一套强大的“关系显微镜”。那些困扰你的问题（谁最重要？哪些人是一伙的？最优路径怎么走？）是否能用图算法来解决？访问 NebulaGraph 官方文档，深入了解 NebulaGraph Algorithm 的配置细节，开始你的图算法探索之旅吧！

文档🔍⬇️

https://docs.nebula-graph.com.cn/3.8.0/graph-computing/nebula-algorithm

---

香港 nMeetUp 报名中🔥

进一步探索 NebulaGraph 在#知识图谱、#Web3、#金融风控 的最新应用