图论基础回顾：金融关系网络的数学基石
各位同学，今天咱们来聊聊图论。说实话，我刚开始接触金融关系网络时，第一反应是「这不就是一张大网吗？」后来才发现，图论才是真正理解这张网的数学语言。没有图论，你看到的只是一堆乱麻；有了图论，你才能看清资金流向、风险传导和关联交易。
我个人习惯把图论比作金融网络的「解剖学」。你想想看，每一笔交易、每一个持股关系、每一份担保合同，本质上都是在图上画了一条边。所以，搞懂图的基本概念，是咱们做动态更新的第一步。
一、图的基本概念：有向图、无向图、加权图
先说说最基础的东西。图由两部分组成：顶点（Vertex）和边（Edge）。在金融场景里，顶点可以是公司、个人、账户，边就是它们之间的关系。
- 无向图：边没有方向。比如两家公司互相持股，或者两个账户之间有共同联系人。这种关系是对称的，A和B有关系，B和A也有同样的关系。
- 有向图：边有方向。比如A公司向B公司转账，或者A股东持有B公司的股份。方向很重要，资金流向就是典型的单向关系。
- 加权图：边上带权重。比如转账金额、持股比例、担保额度。权重可以表示关系的「强度」或「成本」。
重要提醒：金融关系网络几乎都是有向加权图。我在项目中遇到过有人把持股关系当成无向图处理，结果分析关联交易时漏掉了控制链条的方向性，差点出大问题。
举个例子：A公司持有B公司30%股份，B公司持有C公司20%股份。如果画成无向图，你只能看到「A-B-C」连在一起；但画成有向加权图，你就能算出A对C的实际控制力是30%×20%=6%。这就是方向性的价值。
二、图的表示方法：邻接矩阵 vs 邻接表
图怎么存到计算机里？两种主流方式：邻接矩阵和邻接表。我建议你根据图的稀疏程度来选择。
| 特性 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 存储方式 | 二维数组，matrix[i][j]表示边 | 每个顶点维护一个链表/数组 |
| 空间复杂度 | O(V²)，V是顶点数 | O(V+E)，E是边数 |
| 查询边是否存在 | O(1)，直接索引 | O(degree)，需要遍历链表 |
| 适合场景 | 稠密图（边多） | 稀疏图（边少） |
金融关系网络通常很稀疏。你想想看，一家公司可能和几十家、几百家公司有关联，但整个市场有上万家主体。用邻接矩阵存，大部分空间都是0，浪费内存。所以我个人习惯用邻接表，尤其是处理上百万节点的金融网络时，内存开销能差好几个数量级。
// 邻接表的简单实现（Python风格伪代码）
graph = {
'A': [('B', 100), ('C', 200)], // A向B转账100万，向C转账200万
'B': [('C', 50)], // B向C转账50万
'C': [] // C没有出边
}我的小技巧：如果边数超过顶点数的10倍，可以考虑用邻接矩阵。否则，邻接表更香。我曾经用邻接矩阵存一个10万节点的图，内存直接爆了——嗯，从那以后我再也不敢乱用矩阵了。
三、图的遍历：BFS 与 DFS
遍历就是「走一遍图」。两种经典方式：广度优先（BFS）和深度优先（DFS）。
- BFS（广度优先）：一层一层往外走。适合找最短路径、计算距离。比如从某个账户出发，找出所有3跳以内的交易对手。
- DFS（深度优先）：一条路走到黑，再回头。适合检测环路、拓扑排序。比如找资金循环、识别循环担保链。
为什么会这样？BFS用队列，先进先出，保证先访问距离近的节点；DFS用栈（或递归），后进先出，优先深入探索。
// BFS 伪代码
def bfs(graph, start):
visited = set()
queue = [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
queue.append(neighbor)
// DFS 伪代码
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)避坑指南：我曾经在分析担保圈时用了DFS，结果因为图里有环，递归深度太大导致栈溢出。后来改用迭代式DFS（手动维护栈），才搞定。记住：金融网络里环特别多，递归DFS要小心。
四、图的连通性与强连通分量
连通性解决一个核心问题：图是不是「一块」？
- 连通图：无向图中，任意两个顶点都有路径相连。比如一个集团内部的所有子公司，通常构成连通图。
- 强连通分量（SCC）：有向图中，顶点之间可以互相到达的最大子图。比如一个资金闭环里的所有账户，它们之间资金可以循环流转。
强连通分量在金融风控里特别有用。你想想看，如果一组公司构成强连通分量，意味着它们之间可以互相担保、循环出资。这种结构风险极高——一家出问题，整个分量里的公司都会连锁反应。
核心观点：金融关系网络中的强连通分量，往往对应着「风险共同体」。我在做企业关联图谱分析时，第一步就是找出所有SCC，然后重点监控这些子图。因为一旦某个SCC内部出现违约，风险会像多米诺骨牌一样传导。
检测SCC的经典算法是Kosaraju算法或Tarjan算法。Tarjan算法只需要一次DFS，效率更高。我建议你掌握Tarjan，因为它在动态更新场景下也能用——嗯，这个咱们后面章节会细讲。
// Tarjan算法核心思路（伪代码）
def tarjan_scc(graph):
index = 0
stack = []
indices = {}
lowlink = {}
on_stack = set()
sccs = []
def strongconnect(v):
nonlocal index
indices[v] = index
lowlink[v] = index
index += 1
stack.append(v)
on_stack.add(v)
for w in graph[v]:
if w not in indices:
strongconnect(w)
lowlink[v] = min(lowlink[v], lowlink[w])
elif w in on_stack:
lowlink[v] = min(lowlink[v], indices[w])
if lowlink[v] == indices[v]:
scc = []
while True:
w = stack.pop()
on_stack.remove(w)
scc.append(w)
if w == v:
break
sccs.append(scc)
for v in graph:
if v not in indices:
strongconnect(v)
return sccs我的经验：实际金融网络中，SCC的规模通常不大。大多数SCC只有2-5个节点，但偶尔会出现几十个节点的巨型SCC。这种巨型SCC一旦出现，基本就是风险预警信号——我曾经在一个担保链分析中，发现一个42家公司的SCC，结果半年后其中3家同时暴雷。
知识体系总览
下面这张图帮你梳理本章的核心逻辑。从图的基本概念出发，到表示方法、遍历算法，再到连通性分析，每一步都是为后续的动态更新策略打基础。
好了，这一章的内容就到这里。图论基础是后续所有章节的「地基」，尤其是邻接表的选择和SCC的识别，在动态更新场景下会反复用到。下一章咱们会深入讨论动态图的增量更新策略——说白了，就是图变了，怎么只改受影响的部分，而不是全量重算。