随机图与小世界：地图之外的疆域

随机图与小世界：地图之外的疆域

最初，Erdős 与 Rényi 只想回答一个朴素到近乎哲学的问题：如果图不是任何人设计的，而是"每条可能的边按固定概率独立出现"，长出来的图会长什么样？答案出乎所有人意料——不是一团乱麻，而是有明确的"发育阶段"：孤立据点先抱团成小簇，某个临界概率上一夜之间涌现出贯通全图的巨型结构，秩序从随机里自己长了出来。地图档案的最后一格留给这类"概率地形"：本节动手复现随机图的相变实验，认识小世界现象，并划清本册与网络科学专题册的分界线——随机图的理论是数学，网络科学的建模是另一个宇宙，那边见。

两个经典模型

** Erdős–Rényi 模型**（边数版与连边概率版，日常用后者）：给定顶点数与连边概率，每对顶点独立地以该概率连边。它像给图装上骰子——期望边数是"顶点对的个数乘概率"，期望度是"顶点数减一乘概率"。这个模型的美德是完全独立、易于分析，缺点是不像任何真实网络（稍后见分晓）。

小世界模型呼应一个著名的实验观察：地球上任意两人之间平均只需短短几次熟人介绍就能相连。规则网格（只认左邻右舍）聚类高但距离远，随机图距离近但聚类稀烂——小世界模型在网格骨架上"改接"少量捷径边，一点随机性就让距离骤降而聚类几乎不损。真实社交网络、神经网络、电网都被测出这种"高聚类加短路径"的指纹。

import networkx as nx
import random

def er_graph(n, p, seed=42):
    """手写连边概率版随机图，与 nx 官方版对照"""
    rng = random.Random(seed)
    G = nx.Graph()
    G.add_nodes_from(range(n))
    for i in range(n):
        for j in range(i + 1, n):
            if rng.random() < p:
                G.add_edge(i, j)
    return G

G = er_graph(60, 0.05)
print("边数:", G.number_of_edges(), "| 期望边数约:", 60 * 59 // 2 * 0.05)
print("平均度:", sum(dict(G.degree()).values()) / 60)

def watts_strogatz_probe(n, k, shortcut):
    """网格骨架 + 少量改接：距离与聚类的同时测量"""
    ring = nx.watts_strogatz_graph(n, k, 0)          # 纯规则：每点连左右各 k/2
    G0 = ring.copy()
    rng = random.Random(7)
    edges = list(G0.edges())
    for _ in range(shortcut):
        u, v = rng.choice(edges)
        w = rng.randrange(n)
        if w not in G0[u] and w != u:
            G0.remove_edge(u, v)
            G0.add_edge(u, w)
    return G0

ring = watts_strogatz_probe(200, 6, 0)
mixed = watts_strogatz_probe(200, 6, 20)
rand = er_graph(200, 0.03)
for name, g in [("纯规则环", ring), ("加捷径后", mixed), ("纯随机", rand)]:
    cl = nx.average_clustering(g)
    giant = g.subgraph(max(nx.connected_components(g), key=len))
    pl = nx.average_shortest_path_length(giant)
    print(f"{name}: 聚类系数 {cl:.3f}, 平均距离 {pl:.2f}")
​

跑完这段对照，小世界的定义便有了数据体温：加捷径后的图聚类系数几乎与纯规则环持平，平均距离却向纯随机图看齐——"既抱团又四通八达"的悖论组合就是小世界。

相变：巨型分量的诞生

随机图最震撼的剧情是相变。固定顶点数，让平均度（等价于连边概率）从零缓慢爬升：起初全是一片片微型碎片；平均度逼近一的过程中，最大分量的规模开始爬坡；越过一的瞬间，它从"小丘"跃升为"山脉"——占据了图中顶点的一个恒定比例，且随着顶点数增长越占越多，而其余分量仍停留在微观尺度。这个统治图面的巨块就是巨型分量；平均度恰为一的两侧，图的连通面貌判若两种物质形态（物理学的"渗流"与之同构）。

def phase_transition(n=300, trials=5):
    """扫描平均度，复现巨型分量的诞生曲线"""
    print("平均度 | 最大分量占比")
    for avg_deg in [0.2, 0.5, 0.8, 1.0, 1.2, 1.5, 2.0, 3.0]:
        p = avg_deg / (n - 1)
        frac = 0
        for t in range(trials):
            G = nx.gnp_random_graph(n, p, seed=100 + t)
            giant = max(len(c) for c in nx.connected_components(G))
            frac += giant / n
        print(f"{avg_deg:5.1f}  | {frac / trials:.3f}")

phase_transition()
​

输出会呈现清晰的"S 形拐点"：平均度低于一时最大分量占比微乎其微，越过一后一路攀升，平均度达到三时大半据点已连成一体。理论给出的精确刻画更漂亮：平均度超过一后，巨型分量占比等于一个方程的解，而图整体的"连通化"还要更晚（平均度达到对数级别才全图连通——孤立顶点是最顽固的钉子户）。

这套"阈值语言"是随机图理论的核心词汇：图的几乎每一种单调性质（含三角形、含巨型分量、连通、直径有界）都有一个临界概率，概率低于它几乎必然不出现、高于它几乎必然出现，且顶点数越大这个开关越陡。"几乎必然"的严格含义是概率随顶点数增长趋于一——数学家把"典型图"研究成了概率论的一个分支。

真实网络与理论的分野

把随机图理论与真实网络并排对照，分野立刻显现。真实社交网、蛋白质网、万维网的度分布普遍呈"重尾"形态——极少数顶点拥有巨量连接（枢纽），大多数顶点度数很小；随机图的度分布却集中在平均值附近（泊松形态），枢纽根本不该出现。解释重尾的活儿交给了"偏好连接"类的增长模型（新边更爱连向已经热门的顶点，富者愈富），那是网络科学的核心剧目。同样，小世界的实证度量、社区结构的挖掘、传播动力学的建模，都已长成独立的学科大树——站内的网络科学专题册在那里等着，本册的使命只是把数学地基（图的语言、随机图的语言）夯实到位。

分野之外也有回馈：随机图作为"零假设"在实战中立功——检测一个网络是否真有社区结构，标准做法是拿同度数的随机图做对照组，真实网络的聚类若不显著高于随机版本，"社区"就是错觉。第 10 章的社交网络分析将直接调用这套对照思路。

⚠️ 常见坑：拿连边概率版的期望度当实际度。期望是"平均而言"，单次采样的波动在顶点数小时相当可观；严谨的说法是"度分布集中在期望附近"，且这是大数定律的赠品，不是保证。

💡 关键直觉：随机图的世界观是"研究典型而非单个"——不再问"这张图如何"，而问"按这个规则长出来的图，几乎必然如何"。概率成了刻画结构的新维度，档案柜到此装下了图论的最后一种基本视角。

地图档案全部归档。下一章远征队整装凯旋，在社交网络、导航路由、编译器与推荐系统的真实战场上，检阅全册兵法的成色。