方法选型决策指南：网络 / 图结构问题怎么选（深度版）

面对节点+关系（社交、路网、供应链），用图论/网络科学方法：最短路径、中心性、社区发现、传播。

分类：⚙ 优化类　适用：路由/物流网络、社群/影响力分析、依赖关系与脆弱性

一、这个指南适合谁（适用场景）

路由/物流网络
社群/影响力分析
依赖关系与脆弱性

二、选型决策要素

建图：节点、边、权重、有向/无向
目标：路径/中心性/聚类/传播
规模与稀疏性
匹配算法
结果解释与可视化

三、选型的底层逻辑

网络问题的本质是关系数据——样本不是独立个体，而是"节点 + 边"的拓扑结构。这彻底改变了选型逻辑：传统统计假设样本独立同分布，而图里节点的属性通过边相互依赖（同配性、传播）。选算法 = 先正确定义图（有向/无向、加权/二值、静态/动态），再据"要回答什么图论问题"选对应算子：可达性与最优路由用最短路径，关键节点用中心性，社群结构用模块度优化，扩散用传染病模型。最致命的坑是图建模错误——把有向边当无向（如关注≠互关、上游≠下游），会让"谁是关键节点""路径怎么走"全部反向。所以网络选型的第一步永远是"把现实关系正确翻译成图"。

四、决策模型与推导

图表示：邻接矩阵 $A\in\{0,1\}^{n\times n}$ ， $A_{ij}=1$ 表示 $i\to j$ 有边。节点 $i$ 的度 $k_i=\sum_j A_{ij}$ （入/出度在有向图分开）。

中心性算子：

度中心： $C_D(i)=k_i$ （直接连接数）；
介数： $C_B(i)=\sum_{s\neq t}\frac{\sigma_{st}(i)}{\sigma_{st}}$ ， $\sigma_{st}$ 为 $s\to t$ 最短路径数，衡量"控制信息流"的能力；
PageRank： $r_i=\frac{1-d}{n}+d\sum_{j\to i}\frac{r_j}{k_j^{out}}$ ，随机游走稳态分布，对"影响力/重要性"排序鲁棒。

最短路径：Dijkstra 在非负权图求单源最短路，复杂度 $O((V+E)\log V)$ ；Floyd 求全源最短路 $O(V^3)$ 。选哪个取决于"要单点还是全对"。

社群发现（模块度）：Louvain 最大化模块度

$Q=\frac1{2m}\sum_{ij}\Bigl[A_{ij}-\frac{k_i k_j}{2m}\Bigr]\delta(c_i,c_j)$

$m$ 为边数， $\delta$ 指示同社群。社区结构是"关系数据"相较"独立样本"独有的可挖掘结构。

传播模型：SIR 用状态转移刻画扩散速率 $\beta$ （感染）、 $\gamma$ （恢复），基本再生数 $R_0=\beta/\gamma$ 决定能否流行——用于"脆弱性/关键节点"分析。

五、选型流程（怎么选）

求最短/最优路径 → Dijkstra / Floyd / 最小生成树。
找关键节点 → 度中心性/介数/PageRank。
发现社群 → Louvain / 谱聚类。
传播/扩散 → SIR/SIS 模型。
用 Gephi/networkx 可视化并解释结构特征。

六、问题 → 方法映射

Dijkstra/Floyd：路径优化基础；Floyd 求全源最短路。
Louvain：大规模社区发现快且稳。
PageRank：影响力/重要性排序。

七、常见误选与对策

图建错（有向当无向）→ 结论反。
忽略权重语义 → 路径无意义。
只算不画 → 评委看不到结构。

八、选型自检清单

图模型正确（有/无向、权重）
算法匹配目标
关键节点/社区已识别
有网络图可视化

九、配套资源与搭配

算法速成手册（图/网络）
Gephi 工具入门手册
图表选择可视化指南

本指南由 MCM520 资料站自动生成（深度版），配套算法速成手册可在资源页下载。

10、实战案例

案例：网络问题选题

常见类型：社交网络、交通网络、传播路径
推荐模型：图论、复杂网络、PageRank

实战案例

网络/图结构问题选型实战

场景：问题涉及节点与关系（传播、路由、社群）。
任务：根据目标选图算法。

完整代码（text）

按目标选型：
| 目标 | 方法 |
|------|------|
| 最短路径 | Dijkstra / Floyd |
| 最大流 | Ford-Fulkerson |
| 关键节点 | 度中心性 / PageRank |
| 社群发现 | Louvain / GN |
| 传播模拟 | SIR / 渗流模型 |
| 网络构建 | 相关系数阈值 / kNN |

工具：NetworkX(Python)、Gephi(可视化)。

运行效果

选型案例：

物流配送路径 → Dijkstra
社交意见领袖 → PageRank
疫情传播 → SIR 微分方程
社团结构 → Louvain(modularity)
坑：边权定义不清→结果无意义，先定相似度度量。