图与网络基础：节点、边、度、连通分量、图表示方法
好，我们开始讲图。说白了，图就是用来描述“谁和谁有关系”的数学模型。我在工业界做过社交网络分析，也处理过分子的结构式，本质上它们都是用图来建模的。你先想清楚图是什么，后面Louvain和Leiden聚类的原理就顺了。
节点与边 —— 图的基本构件
图由两部分组成：节点（也叫顶点）和边（也叫链接）。节点是你关心的实体，边表示实体间的关系。我记得第一次处理电商用户-商品图时，节点是用户和商品，边是“购买”行为。这很直观。
- 无向边：关系是对称的，比如好友关系。
- 有向边：关系有方向，比如关注（A→B，但B不一定关注A）。
- 带权边：边上有个数值，表示关系的强度或代价。在聚类里，权重常表示相似度。
度 —— 节点的热度
一个节点的度就是它连接的边数。对于有向图，还分出度、入度。我在分析社交网络时，经常用度的分布判断网络是否“幂律”——少数节点连接了大量边，多数节点只有几条边。
举个例子，一个微信群里有100人，群主一个人加了99个好友（度99），其他人平均只有2-3个好友。这种“富者愈富”的结构在现实网络里非常多。你想想看，Leiden算法在做社区发现时，也会优先考虑高度节点。
连通分量 —— 图的“孤岛”
如果图里某些节点之间可以通过边互相到达，而和之外的节点完全没连接，那就形成一个连通分量（有向图里叫强连通分量）。我早年踩过一个坑：处理欧洲航空网络数据时，忘了检查连通分量，结果把不同大陆的机场强行聚类到一起……跑出来的社区全是乱的。
图的表示方法 —— 怎么把图装进计算机
我们总得把图存起来。常用的两种方式：邻接矩阵和邻接列表。我简单对比一下：
| 表示方法 | 存储结构 | 时间复杂度（判断边是否存在） | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| 邻接矩阵 | 二维数组 A[i][j] | O(1) | O(V²) | 稠密图、需要快速随机访问 |
| 邻接列表 | 每个节点一个列表存邻居 | O(degree(v)) | O(V+E) | 稀疏图、遍历邻居频繁 |
我个人更常用邻接列表——因为现实图都是稀疏图，邻居比节点数少太多了。你看社交网络里一个人平均几百个好友，但总用户上亿，邻接矩阵根本存不下。
实际代码怎么写？
我们用Python的NetworkX库来演示。你可以在自己电脑上跑跑看：
import networkx as nx
# 创建一个简单的无向图
G = nx.Graph()
G.add_edge('A', 'B')
G.add_edge('B', 'C')
G.add_edge('C', 'D')
G.add_edge('E', 'F') # 单独的一个分量
# 度
print("节点度：", dict(G.degree()))
# 输出：{'A': 1, 'B': 2, 'C': 2, 'D': 1, 'E': 1, 'F': 1}
# 连通分量
components = list(nx.connected_components(G))
print("连通分量：", components)
# 输出：[{'A', 'B', 'C', 'D'}, {'E', 'F'}]
# 邻接列表表示
for node in G.nodes():
print(f"{node}: {list(G.neighbors(node))}")注意：上面代码中连通分量返回的是节点集合的列表。如果你要做聚类，需要对每个分量分别运行Louvain或Leiden，而不是把整个图丢进去。
SVG里我画了两个连通分量。一个分量里有四个节点，B和C是中间枢纽，度=2；A和D是叶子，度=1。另一个分量只有小节点E和F。你看到了吧？这两个分量之间没有任何边，在聚类时就应该分别处理。
一点个人经验
我记得多年前做一个蛋白质相互作用网络的聚类，数据集有几十万节点。一开始我用邻接矩阵存储，结果内存直接爆了。后来换成邻接列表才跑起来。再后来发现图里有很多孤立的“单节点分量”，它们没有边，度为零。这种节点在Louvain算法里会自己成一个社区，但Leiden的处理方式稍有不同——嗯，这个我们后面会讲到。
另外，关于度的归一化——如果你处理的是加权图，度要换成强度（边权之和）。Louvain和Leiden在计算模块度时，用的就是节点的强度，这一点必须提前搞对。