第10章 凯旋之战：图论的实战检阅

第 10 章 · 凯旋之战：图论的实战检阅

章节摘要：远征队班师回朝，最后一站不是新的疆土，而是检阅场——把全册攒下的兵法拉到真实战场上验收成色。社交网络分析检阅连通性、中心性与社区发现：谁在舆论场里举足轻重、人群沿什么边界抱团；路由与导航检阅最短路的工程形态：亿级路网上的分级加速与互联网的分布式选路；编译器、数据库与推荐系统检阅图数据的全线运用：依赖解析靠拓扑排序、查询优化靠 join 图、推荐召回靠二分匹配与图上的邻居扩散。三章三场，每场都标注"来自第几章的哪支部队在服役"——温故而知新，是收官战的最佳打法。

本章知识点清单

读完本章，下列考核点应当能够通过实战检验：

1. 计算度中心性、接近中心性、介数中心性与特征向量中心性，并说明各自回答的"重要性"问题。
2. 实现 Louvain 思想的多分辨率社区划分演练，并用随机图零假设做显著性对照。
3. 描述分层路网与双向搜索如何配合 Dijkstra 支撑亿级顶点的导航系统。
4. 说明链路状态路由协议与距离向量协议各自对应的图算法谱系。
5. 解释编译器中依赖图的拓扑排序、数据库中查询计划的连接次序、推荐系统中二分匹配的运用方式。
6. 面对"图上机器学习"的需求，能划定经典图论与图神经网络的分界并正确指路。

核心概念速览

金句：经典图论不生产"智能"，它生产的是智能脚下那张可靠的连接地图。

子章节导航

第 1 节"社交网络分析：从连通到社区发现"把人际连接建成图，用中心性度量找出关键人物，用社区发现切开人群边界，并用随机图对照检验社区不是错觉——第 4、6、9 章的兵力在此集结。

第 2 节"路由与导航：最短路的工程落地"追问"亿级路网怎么跑 Dijkstra"，展示分层加速、双向搜索与预处理加速的工程组合拳，再对照互联网两种路由协议的图论谱系。

第 3 节"编译器、数据库与推荐系统：工程图数据检阅"盘点三套系统的图内核：构建系统的依赖解析、数据库的连接次序优化、推荐系统的匹配与扩散——最后划清与图神经网络专题册的边界。

三场检阅的兵力对照

一句话论点：三场实战共享同一批底层兵力——度、路径、连通、排序、匹配——差别只在战场环境与工程包装。

   实战需求            调用部队（章号）
   ─────────────────────────────────
   谁最重要            度与路径 → 中心性家族(1/3/5)
   人群怎么分          连通分量/MST贪心 → 社区发现(4/6)
   分得对不对          随机图零假设(9)
   最快怎么走          Dijkstra + 分层/双向(5)
   任务怎么排          拓扑排序(6)
   怎么配对            二分匹配(7)
​

前置知识与后续延伸

前置：本章是全册的收束与检阅，几乎每一节都调用前九章的成果——连通分量（第 4 章）、最短路（第 5 章）、生成树与贪心（第 6 章）、匹配（第 7 章）、随机图（第 9 章）。若某节感觉吃力，正是回炉对应章节的信号。

后续延伸：图上的深度学习（图神经网络）在本册边界之外，站内有专门的图神经网络专题册承接；网络科学的模型与统计（度分布、传播动力学）另见网络科学专题册。本册交付的是两边的共同地基——图的语言、经典算法与复杂度直觉。