想象你手里摊开一张城市地铁图：密密麻麻的站点像洒落的棋子，铁轨像蛛网一样把它们连起来。你每天上下班，其实都在不自觉地和“图”打交道——找最快换乘路线、判断哪个站是枢纽、观察这座城市天然形成了几个生活圈。图算法，就是教你从这张巨大的关系网里“抄近道、找圈子、认大佬”的本事。最短路径负责帮你在千万条路里挑最快那条；社区发现能自动圈出彼此紧密联络的人群；中心性分析则一眼锁定那些“一呼百应”的关键节点。AI 从业者掌握了这三板斧，就能在社交网络、金融风控、智能推荐等场景里，把一堆枯燥的关系数据变成真正值钱的洞见。这篇文章，我们就用一座虚拟城市的交通系统，把这三大经典应用讲透。

岗位关联

对 AI 从业者来说，图算法是理解复杂关系数据的核心工具。学完你就能为社交、风控、推荐等真实业务选对算法，也能看懂图数据库背后的计算逻辑，是数据科学家和算法工程师的必备技能。

目录
  1. 可视化演示
  2. 图的本质
  3. 最短路径
  4. 社区发现
  5. 中心性分析
  6. 对比选型
  7. 业务实战
  8. 图数据库
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

展示Dijkstra最短路径贪心搜索、Louvain社区发现模块度优化与PageRank中心性迭代计算，切换模式掌握图算法核心原理与工程应用。

本节配有交互动效（进入视口后自动加载，约 3KB）。

Dijkstra最短路径算法与堆优化实现 贪心策略维护已确定最短路径集合，每次选最近节点加入并松弛邻居，优先队列优化至O(ElogV) 适用于非负权重图的单源最短路径，金融风控中用于交易路径追踪和资金流向分析 Dijkstra: dist[v] = min(dist[v], dist[u]+w(u,v)), priority_queue O(ElogV) Dijkstra是图算法中最基础且应用最广的路径搜索算法

图的本质

拿起一张地铁线路图，你会发现它其实是一张“网的画像”：每个地铁站是一个点，两条站之间的铁轨是一条线，站与站之间的行驶时间则写在线的旁边。数学家把这种“点 + 线 + 数字”的结构叫做图。点叫节点，线叫边，数字叫权重。如果铁轨只能单向走，那就是有向边，好比单行道；如果双向都能走，就是无向边。整座城市的交通网络，就这样被压缩成了一张简洁的图。

在计算机眼里，这张图不能画在纸上，得存进内存里。最直观的存法是邻接矩阵：把每个站编号，然后画一张表格，第 i 行第 j 列填的数字，就是从 i 站到 j 站的耗时。没有直达铁轨就填 0。这种“表格式”存储让计算机能瞬间回答“A 到 B 到底通不通”，代价是空间占得多——站越多，表格越庞大。另一种存法是邻接表：每个站只记一份“邻居名单”，谁离得近就记谁，省空间也更贴近真实的地铁网络。

无论城市地图画得多么眼花缭乱，落到计算机里无非就是一张表格或一串邻居名单。理解了这个“长相”，后面所有算法都像在地图上做游戏一样自然。

G=(V,E),Wij={w(i,j),(i,j)∈E0,otherwiseG = (V, E), \qquad W_{ij} = \begin{cases} w(i,j), & (i,j) \in E \\ 0, & \text{otherwise} \end{cases}
这个公式是说：图由顶点集合 V 和边集合 E 组成，而权重矩阵 W 里存着每对节点之间的“距离数字”。
  1. 顶点集合V 代表所有地铁站的集合，每个站点就是一个节点，它们是整个图的“点主角”。
    V={家站,公园站,公司站,… }V = \{\text{家站}, \text{公园站}, \text{公司站}, \dots\}
  2. 边集合E 代表所有铁轨的集合，每条边连接两个站点，边存在说明“这两个站之间有路”。
    E={(u,v)∣u,v∈V}E = \{(u, v) \mid u, v \in V\}
  3. 权重矩阵取值W_ij 是 i 站到 j 站的耗时；如果 i、j 之间没有铁轨，就记为 0，表示不可直达。
    Wij=w(i,j) if (i,j)∈E, else 0W_{ij} = w(i,j) \ \text{if} \ (i,j) \in E, \ \text{else} \ 0

最短路径

早上八点，你从家站出发要去公司站，手机地图给你推荐了三条换乘方案。你真正关心的其实是同一个问题：哪条路最快？在地铁图里，每条边的权重就是两站之间的耗时，最短路径算法就是那个帮你把“总耗时最小”的方案找出来的智能导航员。其中最著名的选手叫 Dijkstra，它的思路听起来像生活里的常识：先盯着离自己最近的站，把能确定最短时间的站一个个“定下来”，再从这个站继续往外扩展。

Dijkstra 是个典型的贪心算法。它维护一张“当前已知最快耗时表”，一开始除了起点是 0，其他站都记为正无穷。然后每次从未确定的站里挑一个当前耗时最小的，把它正式确定下来，再顺着它的铁轨看看：如果绕道这个新确定的站，能让某个邻居的耗时变短，就更新那个邻居的耗时，这个动作叫“松弛”。如此反复，直到目标站被确定为止。在无权图（每条边耗时都一样）里，更简单的 BFS 广度优先搜索就够用了——它像水波一样一圈一圈往外扩散，第一次碰到目标站时的圈数就是最少步数。

所以下次打车时，导航 App 其实就是在后台反复执行这个“比大小 + 更新”的动作。对 Dijkstra 来说，只要知道每条路的耗时，它就能像经验丰富的老司机一样，笃定地告诉你：走这条路，最快。

d[v]=min⁡(d[v], d[u]+w(u,v))d[v] = \min\big(d[v],\, d[u] + w(u,v)\big)
意思是：到 v 站的最短耗时，要么维持原来记录，要么等于“先到 u 站，再从 u 走到 v”的总耗时，取其中更小的那个。
  1. 当前最短耗时d[v] 表示目前记录的“起点到 v 站的最快耗时”，一开始只有起点为 0，其余都是无穷大。
    d[s]=0,d[v]=+∞ (v≠s)d[s] = 0, \quad d[v] = +\infty \ (v \neq s)
  2. 候选新路线d[u] + w(u,v) 表示“起点先走最快路线到 u 站，再从 u 坐 w 分钟地铁到 v 站”的总耗时。
    d[u]+w(u,v)d[u] + w(u,v)
  3. 取最小值把新候选路线和旧记录比一比，谁小就留下谁，这就是松弛操作的核心。
    d[v]=min⁡(d[v], d[u]+w(u,v))d[v] = \min(d[v],\, d[u] + w(u,v))

社区发现

现在把目光从早高峰挪到整座城市。交通部门发现一个有趣的现象：东边的人总是在东边的几个站之间换乘，西边的人几乎从不跨到东边去。换句话说，地铁网络天然地分裂成了几个“生活圈”。社区发现算法要做的，就是不看任何人的居住证，只靠乘车记录自动把这些圈子找出来。最常用的算法叫 Louvain，它的工作方式很像班级里的小团体形成过程：一开始每个人各玩各的，然后慢慢靠近聊得来的人，最后形成几个稳定的小圈子。

Louvain 的核心是优化一个叫“模块度”的指标 Q。模块度回答的问题是：假如把地铁图随机打乱，现实中的“生活圈”还能不能这么明显？如果社区内部的铁轨数量远大于随机期望值，Q 就高，说明圈子划分得漂亮。Louvain 会反复尝试把每个站挪到邻居的圈子里，看 Q 是否上升，直到怎么挪都不再提升为止。整个过程像揉面团：先在小范围聚出小团，再把小团看作新节点，重新揉一遍，越揉圈子越清晰。

社区发现就像给城市做“体检”，自动圈出生活圈、商圈、学区。产品经理看到这些圈子，就能知道该往哪个圈子里投广告、推服务，因为圈子里的人往往有着相似的出行习惯和消费偏好。

Q=12m∑ij[Aij−kikj2m]δ(ci,cj)Q = \frac{1}{2m} \sum_{ij} \left[ A_{ij} - \frac{k_i k_j}{2m} \right] \delta(c_i, c_j)
模块度 Q 是“社区划分质量分”：实际连边数比随机连边数多多少。分数越高，说明划分出的生活圈越真实、越有结构。
  1. 总边数归一化m 是图中边的总数，2m 是所有节点的度数之和，用来把分数标准化。
    m=∣E∣,2m=∑ikim = |E|, \quad 2m = \sum_i k_i
  2. 实际连边数A_ij 表示 i 站和 j 站之间是否有真实铁轨，有则为 1，没有则为 0。
    Aij=1 if (i,j)∈E, else 0A_{ij} = 1 \ \text{if} \ (i,j) \in E, \ \text{else} \ 0
  3. 随机期望连边数k_i k_j / (2m) 是如果铁轨完全随机铺设，i 和 j 之间期望的连边数，这是衡量“巧合程度”的基线。
    kikj2m\frac{k_i k_j}{2m}
  4. 是否同圈δ(c_i, c_j) 是一个判断开关：只有 i 和 j 被分进同一社区时才算数，否则这一项为 0。
    δ(ci,cj)={1,ci=cj0,ci≠cj\delta(c_i, c_j) = \begin{cases} 1, & c_i = c_j \\ 0, & c_i \neq c_j \end{cases}

中心性分析

如果你在北京生活过，一定知道西直门桥——无数条车流、地铁线在这里交汇，一旦堵住，半个城市都要窒息。在图论里，这种“关键节点”可以用中心性来衡量。中心性分析要回答三个递进的问题：谁的朋友最多？谁是最重要的桥梁？谁被大佬们抬举？对应三种指标：度中心性、介数中心性和 PageRank。

度中心性最直白：一个节点的邻居数量就是它的度数，朋友越多中心性越高。但光看朋友数量会被人钻空子——买几百万僵尸粉也能装大佬。介数中心性则看重“桥梁作用”：统计在所有节点对的最短路径中，有多少条必须经过你。就像一座桥，平时不起眼，一旦断掉整个城市的东西交通就瘫痪了。PageRank 则更聪明，它来自谷歌搜索排序：一个节点的权重，由指向它的那些节点的权重共同决定——被高质量的大佬推荐，比被一万个路人点赞更有分量。

回到地铁场景：度中心性告诉你哪个站换乘线路最多，介数中心性告诉你哪座桥断了会全城瘫痪，PageRank 则告诉你哪个站在整个网络的“口碑传播”中话语权最大。三个指标合在一起，就能完整刻画一个节点在这个关系网里的真实地位。

PR(v)=1−dN+d∑u∈N−(v)PR(u)C(u)PR(v) = \frac{1-d}{N} + d \sum_{u \in N^{-}(v)} \frac{PR(u)}{C(u)}
PageRank 的递归公式：v 的重要性 = 随机跳转的基础概率 + 所有指向 v 的节点，把它们的 PageRank 平分给各自粉丝后的总和。
  1. 阻尼因子d 是阻尼因子，通常取 0.85，模拟“用户 85% 的时间顺着链接点击，15% 的时间随手跳到一个随机页面”。
    d=0.85d = 0.85
  2. 全网节点数N 是图中节点总数，基础概率 (1-d)/N 保证每个节点哪怕没人推荐，也至少有一点初始权重。
    1−dN\frac{1-d}{N}
  3. 入链贡献对每一个指向 v 的节点 u，把 u 的 PageRank 值除以它的出链数 C(u)，再累加起来。
    ∑u∈N−(v)PR(u)C(u)\sum_{u \in N^{-}(v)} \frac{PR(u)}{C(u)}
  4. 迭代计算所有节点同时套用这个公式反复计算，直到数值收敛，最终得到的 PR 值就是节点的重要性排名。
    PRt+1(v)=1−dN+d∑u∈N−(v)PRt(u)C(u)PR_{t+1}(v) = \frac{1-d}{N} + d \sum_{u \in N^{-}(v)} \frac{PR_t(u)}{C(u)}

对比选型

去公司上班，你可以走路、骑车、打车、坐地铁；去陌生城市旅游，你又会换一套出行方案。图算法也一样——没有“万能算法”，只有“最合适的算法”。选型的第一把尺子是时间复杂度。Dijkstra 在有 n 个节点、m 条边的图上的复杂度是 O((n+m)logn)，听起来有点吓人，翻译过来就是：站点越多、铁轨越多，计算时间增长得越慢越好。而 BFS 在无权图上的复杂度是 O(n+m)，更快，但它完全用不了边的权重信息。

第二把尺子是场景。如果你只知道“有没有路”，不在乎“路有多长”，BFS 是最优选——比如计算最少换乘次数。如果每条路的耗时千差万别，Dijkstra 就是标配。如果你想找“关系紧密的圈子”，Louvain 这类社区发现算法登场。如果你想找“最有影响力的人”，就要用中心性三件套。第三把尺子是数据规模：几万节点的图，单机算法轻松搞定；上亿节点的大图，就得靠分布式图计算引擎了。

选算法就像选交通工具：先看你要解决什么问题（导航、找圈、找大佬），再看数据长什么样（有没有权重、规模多大），最后才决定选哪位“司机”。把问题定义清楚，算法往往就自己浮出水面了。

TDijkstra=O((∣V∣+∣E∣)log⁡∣V∣)T_{\text{Dijkstra}} = O\big((|V| + |E|) \log |V|\big)
这个复杂度告诉你：Dijkstra 在大型稀疏图上依然高效，因为 log 项增长非常缓慢，边数 m 才是主要成本来源。
  1. 顶点贡献|V| 是节点数，每个节点都要被取出来处理一次，这是算法的基本工作量。
    ∣V∣|V|
  2. 边贡献|E| 是边数，每条边在松弛操作中都要被检查一遍，所以也要计入总成本。
    ∣E∣|E|
  3. 优先队列代价log|V| 来自每次从候选站中挑“当前最小耗时”所用堆操作的开销。
    log⁡∣V∣\log |V|

业务实战

前面所有算法，最终都要落到真实世界的钱和效率上。想象城市大脑里有三个部门同时运作：社交部门想让大家多交朋友，风控部门想抓到诈骗团伙，配送部门想让外卖更快送达。三个部门用的工具，恰好就是我们讲的三大类算法。

社交网络的好友推荐是社区发现的经典舞台。微信的“可能认识的人”、LinkedIn 的“二度人脉”，本质都是在做同一件事：把你和某个圈子里的其他人关联起来。你和好友在同一个社区里，你的好友的好友大概率也值得认识。金融风控则把中心性和社区发现结合起来：诈骗分子往往不是单兵作战，而是一个有组织的团伙。把转账记录织成一张交易图，社区发现能揪出异常抱团的账号集群，介数中心性则能定位那些专门负责“过账洗钱”的中转账号。配送领域则是最短路径的主场——外卖骑手同时接多单，算法要在几分钟内算出途经所有商家和客户的最短路线。

最短路径、社区发现、中心性就像三个配合默契的部门：一个负责“怎么走最近”，一个负责“谁和谁是一伙”，一个负责“谁是关键人物”。当它们一起运转时，就能支撑起推荐、风控、调度这些真实世界里的复杂决策。

Score(u,v)=α⋅PathLen(u,v)+β⋅CommSim(u,v)+γ⋅Central(v)\text{Score}(u,v) = \alpha \cdot \text{PathLen}(u,v) + \beta \cdot \text{CommSim}(u,v) + \gamma \cdot \text{Central}(v)
一个典型的综合决策评分：系统给“是否向 u 推荐 v”打分，综合考虑路径远近、社区相似度和对方影响力，三项按权重相加。
  1. 三个权重系数α、β、γ 是业务方调节的旋钮，告诉模型“距离、圈子、影响力”哪个更重要。
    α+β+γ=1\alpha + \beta + \gamma = 1
  2. 路径长度项PathLen(u,v) 反映 u 和 v 在图上的距离，越近越容易产生信任和连接。
    PathLen(u,v)\text{PathLen}(u,v)
  3. 社区相似项CommSim(u,v) 表示两人是否属于同一社区、共同好友比例有多高，是推荐系统的重要信号。
    CommSim(u,v)\text{CommSim}(u,v)
  4. 中心性项Central(v) 衡量目标节点 v 在全局的重要性，优先推荐那些有影响力的人。
    Central(v)\text{Central}(v)

图数据库

当一座城市大到千万级站点，内存里的那张地铁图就不只是一张表那么简单了——你需要一个专门为“关系”而生的仓库：图数据库。传统关系型数据库存关系，靠的是多张表之间反复执行代价昂贵的 JOIN 操作；图数据库则用“邻接表”式的物理存储，每个节点旁边直接挂着它的邻居指针，从 A 找 B 的“朋友的朋友”，就像在真实的城市地图上连续拐两个弯那么快。

图数据库配套的查询语言也很有意思。以 Neo4j 的 Cypher 为例，它的查询语句长得像英文句子：MATCH (a:Person)-[:FRIEND]->(b:Person) RETURN b。翻译过来就是“找出所有 a 的朋友 b”，非常接近人类思维。计算引擎则在底层做优化：多跳遍历、路径匹配、社区聚合，全部在存储层就近完成，不需要把数据搬来搬去。配合可视化工具，分析师能直接在屏幕上看到一个个“团伙”或者“关键枢纽”浮现出来。

图数据库就是这座城市的“数字孪生地图”：把存储结构、查询语言、计算引擎和可视化能力打包在一起。当你需要反复追问“谁和谁之间有什么关系”时，它比任何传统数据库都更懂这张关系网的价值。

Tmulti-hop=O(d⋅kˉ)T_{\text{multi-hop}} = O(d \cdot \bar{k})
多跳查询的代价：走 d 步路，每一步要访问当前节点的平均邻居数 k̄，总成本是两者相乘。这就是图数据库“以遍历为中心”的复杂度模型。
  1. 跳数d 是查询的路径长度，朋友的朋友是 2 跳，朋友的同事的邻居是 3 跳。
    d=路径跳数d = \text{路径跳数}
  2. 平均度k̄（均值为 k-bar）是每个节点平均有多少邻居，决定每一步要“看几个方向”。
    kˉ=1n∑i=1nki\bar{k} = \frac{1}{n}\sum_{i=1}^{n} k_i
  3. 总成本d 和 k̄ 相乘，就是整条路径遍历需要访问的节点和边的数量级。
    O(d⋅kˉ)O(d \cdot \bar{k})

AI 应用场景

社交网络好友推荐

阶段：召回阶段 / 特征工程

解决的问题：传统协同过滤只看“用户-物品”评分矩阵，完全浪费了社交关系。图上的社区发现能把用户按真实关系圈成一个个生活圈，圈内人互相推荐，召回精准度大幅提升。

具体案例：微信“可能认识的人”功能，本质就是把你的社交关系织成一张大图，用 Louvain 算法找到你所在的圈子，再把圈子里你还没加过的联系人推荐给你。LinkedIn 的“二度人脉”也是同样的原理，先找社区，再找社区内未连接的高中心性节点。

金融风控反欺诈团伙识别

阶段：模型训练 / 实时推理

解决的问题：单笔交易的特征再异常，也看不出团伙结构。把每笔转账看成一条边，收款人、付款人看成节点，社区发现能挖出异常抱团的小群体，介数中心性则能锁定负责“洗钱中转”的关键账号。

具体案例：银行反洗钱系统中，算法自动构建交易大图，用 LPA 标签传播或 Louvain 识别出资金往来异常紧密的账户集群，再用介数中心性找出连接多个集群的“过桥账户”，从而斩断整个洗钱链路。

智能配送与路径规划

阶段：决策优化 / 路径规划

解决的问题：外卖骑手一次接 5 单，要在几十个路口、同一时段的多条路线里选出总耗时最短的组合。Dijkstra 及其变体（如 A*）就是实时算路的核心引擎，配合道路图的动态权重（拥堵、红绿灯）持续更新路线。

具体案例：美团、饿了么的骑手调度系统，把城市道路建模为权重图，每几分钟重新计算一次最优路径，同时考虑商家出餐时间、用户期望送达时间等多重约束，让骑手跑得更快、用户等得更短。

Python 演示

python84 行
"""城市交通网络上的三类经典图算法演示"""import heapqfrom collections import deque # 地铁网络：站点(节点) + 换乘耗时(权重)METRO = {    "家": [("公园", 4), ("超市", 2)],    "公园": [("家", 4), ("公司", 3), ("医院", 5)],    "超市": [("家", 2), ("医院", 2), ("学校", 2)],    "公司": [("公园", 3), ("医院", 3), ("体育馆", 2)],    "医院": [("公园", 5), ("公司", 3), ("超市", 2), ("学校", 1)],    "学校": [("超市", 2), ("医院", 1), ("体育馆", 4)],    "体育馆": [("公司", 2), ("学校", 4)],} def dijkstra(graph, start, end):    """Dijkstra 最短路径：贪心 + 优先队列"""    dist = {node: float("inf") for node in graph}    prev = {}    dist[start] = 0    pq = [(0, start)]    while pq:        d, u = heapq.heappop(pq)        if d > dist[u]:            continue        for v, w in graph[u]:            nd = d + w            if nd < dist[v]:                dist[v] = nd                prev[v] = u                heapq.heappush(pq, (nd, v))    path = []    node = end    while node != start:        path.append(node)        node = prev[node]    path.append(start)    path.reverse()    return path, dist[end] def degree_centrality(graph):    """度中心性：朋友的个数"""    return {node: len(neighbors) for node, neighbors in graph.items()} def pagerank(graph, iterations=20, d=0.85):    """PageRank：被高质量邻居投票决定影响力"""    nodes = list(graph)    pr = {node: 1.0 / len(nodes) for node in nodes}    for _ in range(iterations):        new_pr = {}        for node in nodes:            incoming = 0.0            for u, neighbors in graph.items():                out_links = len(neighbors)                if u != node and any(v == node for v, _ in neighbors):                    incoming += pr[u] / out_links            new_pr[node] = (1 - d) / len(nodes) + d * incoming        pr = new_pr    return pr def lpa_community(graph, iterations=5):    """标签传播社区发现：邻居们互相投票选圈"""    labels = {node: i for i, node in enumerate(graph)}    for _ in range(iterations):        for node in graph:            votes = {}            for neighbor, _ in graph[node]:                lbl = labels[neighbor]                votes[lbl] = votes.get(lbl, 0) + 1            if votes:                labels[node] = max(votes, key=votes.get)    groups = {}    for node, label in labels.items():        groups.setdefault(label, []).append(node)    return list(groups.values()) if __name__ == "__main__":    start, end = "家", "公司"    path, cost = dijkstra(METRO, start, end)    print(f"最短路径 {start} -> {end}: {' -> '.join(path)}，耗时 {cost} 分钟")    print("度中心性:", degree_centrality(METRO))    pr = pagerank(METRO)    print("PageRank 排名:", sorted(pr.items(), key=lambda x: -x[1])[:3])    print("社区发现:", lpa_community(METRO))
目的：用一座小型“城市地铁网”演示三类核心图算法——Dijkstra 求最快路线、度中心性与 PageRank 找关键站点、标签传播找生活圈。
  1. def dijkstra(graph, start, end):定义求两点最快路线的核心函数，用堆优化贪心选择。
  2. dist = {node: float("inf") for node in graph}所有站点的耗时先记成正无穷，表示“还不知道怎么走”。
  3. nd = d + w新候选耗时 = 当前站耗时 + 到邻居的铁轨耗时，是松弛操作的核心计算。
  4. if nd < dist[v]:只有绕道更快时才会更新记录，这就是贪心里的“比大小”环节。
  5. def pagerank(graph, iterations=20, d=0.85):阻尼因子 0.85 模拟“85% 概率顺着关系继续点击”的用户行为。
  6. incoming += pr[u] / out_links上游节点把自己的影响力平均分给所有出链邻居，再累加到当前节点。
  7. labels = {node: i for i, node in enumerate(graph)}标签传播的第一步：每个站点先自成一个生活圈。
  8. labels[node] = max(votes, key=votes.get)核心更新规则：跟“投自己最多票”的邻居加入同一个圈子。

常见误区

误区Dijkstra 看起来每一步都在取最小值，那负权边应该也能算吧？只要不断更新，总能找到最短路径。

正解不能。Dijkstra 的贪心核心是“已确定节点的最短路径不再变化”，这个假设在负权边存在时会被击穿。想象一条“越走越短的魔法传送带”，走一圈路径反而更短，贪心就陷入了死循环般的反复更新。处理负权边要用 Bellman-Ford 算法，它会老老实实地迭代多轮直到收敛。

为何常见：因为日常路网里几乎没有负权边，初学者很容易忽略这个前提，把 Dijkstra 当作“万能最短路算法”。

误区一个节点朋友最多，它肯定就是全网最重要的节点，推荐它准没错。

正解度中心性只看“数量”，不看“质量”。一个人可以买大量僵尸粉，好友数量虚高但毫无真实影响力。真实业务里，度中心性要结合介数中心性和 PageRank 一起看：一个节点朋友多、还总出现在别人之间的最短路径上、又被高质量节点推荐，那才是真的重要。就像地铁站，换乘线路多（度高）不一定最核心，还要看它是不是多条关键线路的必经枢纽。

为何常见：度中心性最容易计算和理解，直觉上“朋友多 = 人脉广”也符合日常经验，所以容易被误用为唯一指标。

误区社区发现不也是聚类吗？直接把节点的坐标特征丢进 KMeans，不就能分出圈子了？

正解KMeans 聚类的是“向量距离”，需要先把节点变成向量特征，还要求用户预先指定分成几个圈。社区发现直接利用图的拓扑结构，Louvain 通过最大化模块度自动决定圈数和成员，不需要任何特征工程。就像判断城市的生活圈，KMeans 会问“你打算分几个区”，而 Louvain 直接看铁轨的疏密自己把圈子画出来。

为何常见：初学者刚学完聚类算法，容易把所有“分组任务”都往 KMeans 上套，忽略了图结构本身的连接信息。

误区PageRank 就是数一数谁被链接的次数多，被链最多的人排名最高。

正解PageRank 不是简单计数，而是“带权重的投票”。每张选票的权重，取决于投票者自己的 PageRank 和它的出链数。被一个高质量的大 V 转发，胜过被一万个营销号转发。这也是它能抵抗“刷量”的原因——刷出来的低质量节点本身的 PR 值很低，投出去的票也就没有分量。

为何常见：很多人把 PageRank 和“入链计数”混为一谈，因为它俩在简单例子里的排序结果常常相似，让人误以为原理也相同。

误区图也能用关系型数据库的表存，无非是多写几个 JOIN 查询，图数据库没什么特别的。

正解关系型数据库的 JOIN 代价随表规模急剧上升，多跳查询尤其痛苦。图数据库用邻接表物理存储，每个节点直接持有邻居的指针，从 A 查 B 的“朋友的朋友”只需沿着指针走两步，复杂度几乎是常数级。它从存储、查询语言到计算引擎都是围绕“遍历关系”设计的，不是普通的表加索引能替代的。

为何常见：大家对关系型数据库最熟悉，遇到任何数据都本能地想“建表”，低估了关系遍历在大规模图数据上的性能瓶颈。

面试题

Q1. Dijkstra 算法的核心思想是什么？

单选题 · easy

  • A.动态规划
  • B.贪心策略← 正确答案
  • C.分治思想
  • D.随机采样

答案：B。Dijkstra 每次从未确定的节点中挑“当前耗时最小”的节点，把它确定下来，这就是典型的贪心策略。动态规划需要保存所有子问题状态，分治需要把问题拆成子问题，随机采样更不是它的特征。就像导航每次都先选当下最近的车站，一步步逼近目标。

Q2. 在无权图中求最少换乘次数，最合适的搜索方式是？

单选题 · easy

  • A.DFS 深度优先
  • B.BFS 广度优先← 正确答案
  • C.随机游走
  • D.暴力枚举

答案：B。BFS 按“圈”逐层扩散，第一次碰到目标节点时走过的层数就是最少边数，天然适合无权图最短路径。DFS 会一条道走到黑，第一次找到的路径不一定最短；随机游走和暴力枚举更不合适。就像水波一圈圈往外推，最先触岸的那圈就是最近的。

Q3. PageRank 中阻尼因子 d 的常用取值是多少？

单选题 · mid

  • A.0.70
  • B.0.85← 正确答案
  • C.0.95
  • D.0.50

答案：B。PageRank 的标准实现里阻尼因子默认取 0.85，模拟用户有 85% 的概率顺着链接继续浏览，15% 的概率随机跳到任意页面。0.70 和 0.50 偏低，0.95 偏高，都会改变随机跳转的基础概率和收敛行为。就像大多数乘客会顺着换乘通道走，只有少数人会随机出站。

Q4. Louvain 算法的模块度 Q 值越大，说明什么？

单选题 · mid

  • A.社区内部连接紧密← 正确答案
  • B.节点度数整体偏高
  • C.图中边的总数量多
  • D.最短路径长度很短

答案：A。模块度衡量的是“社区内部实际连边数”相对“随机连边期望数”的超出程度。Q 越大说明社区内部连接越紧密、社区之间连接越稀疏，划分质量越高。节点度数和总边数只是图的基本属性，最短路径长度与模块度没有直接关系。

Q5. 一个节点介数中心性最高，通常意味着它是什么角色？

单选题 · hard

  • A.连接两个社区的桥梁← 正确答案
  • B.粉丝数量最多的明星
  • C.节点总数最大的群
  • D.路径长度最长的边

答案：A。介数中心性统计“所有节点对最短路径中有多少条经过该节点”。这个值最高的节点往往是不同社区之间的必经之路，像一座桥，断了会导致很多节点对的最短路径大幅变长。粉丝多对应度中心性，群大小和路径长度都不是介数中心性的定义。

Q6. 下列哪种情况下，Dijkstra 算法会失效？

单选题 · easy

  • A.图数据量非常庞大时
  • B.图中存在负权边时← 正确答案
  • C.图中存在孤立节点时
  • D.边权全部相同时

答案：B。Dijkstra 的贪心假设是“已确定节点的最短路径以后不再改变”，负权边会让这条路径不断变短，破坏这个假设。数据量大只是性能问题，孤立节点会被跳过，边权相同反而退化成 BFS，这些都不会导致算法失效。就像现实路网里不会有“越走越省时间”的魔法通道。

Q7. Louvain 算法每一步迭代都在尝试优化什么？

单选题 · mid

  • A.提升社区内部连接密度← 正确答案
  • B.扩大图中节点总数量
  • C.控制算法迭代次数
  • D.提高边的平均权重

答案：A。Louvain 通过把节点移动到邻居社区来最大化模块度 Q，而 Q 的本质是衡量社区内部连接是否比随机期望更紧密，所以每一步优化都在提升社区内部的连接密度。节点数量是业务决定的，迭代次数是训练超参，边权重是输入数据，都不是优化目标。就像揉面团是为了让面粉和水抱得更紧，而不是改变面团大小。

Q8. 以下哪些属于中心性指标？

多选题 · mid

  • A.度中心性与介数中心性← 正确答案
  • B.PageRank 迭代影响力← 正确答案
  • C.余弦相似度聚类指标
  • D.信息熵与条件概率测度

答案：AB。中心性指标用来衡量节点在图中的重要性，经典的三件套是度中心性、介数中心性和 PageRank。余弦相似度属于向量空间度量，信息熵属于信息论，它们不是图上的中心性指标。就像衡量地铁站地位看换乘线路数和必经程度，而不是看车站名字的长度。

Q9. 图算法在金融风控中常用于哪些任务？

多选题 · hard

  • A.识别异常交易团伙网络← 正确答案
  • B.追踪多步资金流转链路← 正确答案
  • C.推荐相似商品给新用户
  • D.生成新闻标题与摘要文本

答案：AB。金融风控把交易关系建模成图，用社区发现识别抱团作案的团伙，用中心性算法锁定洗钱中转账号，还能用最短路径追踪资金在多个账户间的流转链路。推荐相似商品是推荐系统的任务，生成新闻摘要属于自然语言处理，均不属于风控场景。就像反诈警察查关系网里的“团伙”和“中间人”，而不是做商品营销。

Q10. 相比关系型数据库，图数据库的优势体现在哪些方面？

多选题 · mid

  • A.多跳关系查询响应更快← 正确答案
  • B.原生邻接表结构存储← 正确答案
  • C.JOIN 操作依赖索引优化
  • D.遍历邻居开销近似常数← 正确答案

答案：ABD。图数据库用邻接表存储，每个节点直接持有邻居指针，多跳遍历时每跳访问邻居的开销接近常数，所以“朋友的朋友”这类查询比关系型数据库层层 JOIN 快得多。C 描述的是关系型数据库的做法，恰恰是它的瓶颈而非优势。就像顺着地铁图直接看下一站，而不是翻遍整本电话簿去查。