Complex Systems Analysis and Modelling

本文整理 PC5253 Complex Systems Analysis and Modelling 的现有讲义与实践笔记，按“概念 → 条件 → 推导 → 例题 → 检查”的顺序展开。内容覆盖导论、中心极限定理、尺度无关分布、无标度网络、网络基础，以及两份 NetworkX notebook 中的知识主题；结尾附综合自测与六块 helpsheet 速查。

第一次学习建议顺序阅读正文，再独立完成各节例题和综合自测；复习时可通过下方导航定位推导，最后用 helpsheet 核对公式与适用条件。速查不能代替条件： 同一个符号在不同模型中可能有不同含义，使用公式前先确定随机变量、图的类型与归一化约定。

手机上较长的公式与表格可横向滑动查看。

阅读导航与材料范围

内容	对应材料	主要任务
导论	Lecture 0	理解相互作用、涌现与建模思路
中心极限定理	Lecture 1	概率与矩、MGF、完整证明、随机游走
尺度无关分布	Lecture 2	稳定分布、Cauchy、幂律、Pareto、地震与极端事件
无标度网络	Lecture 3	BA 连续推导、离散主方程、ER 与 Poisson 极限
网络基础	Lecture 4	图类型、矩阵、投影、连通性与课堂练习
网络指标与算法	NetworkX_metrics.ipynb	中心性、PageRank、聚类、社群与复杂度
NetworkX 操作	NetworkX_tutorial.ipynb 及 metrics 中的调用	建图、属性、函数选择、可复现例子
综合自测	按以上材料编写	八道综合题、答案与易错点
Helpsheet 速查	以上内容的紧凑索引	六块核心公式与使用条件

这里的“完整”指以上五份讲义及两份 notebook 的知识主题。导论提到但后续材料尚未展开的混沌、元胞自动机、同步与相变等，按导论要求解释其概念，不扩展为未提供的后续章节。具体考试取舍仍以课程公布范围为准。原材料中容易造成误解的公式会在相关位置标为校正；额外推导与练习会说明是补充或自编内容。

符号约定

符号	含义与易混点
$S_n=\sum_{i=1}^{n}X_i$、$\bar X_n=S_n/n$	随机变量的和与样本均值
$\mu$、$\sigma^2$	总体均值与方差；$N(\mu,\sigma^2)$ 第二个参数是方差
$M_X(t)$、$\varphi_X(q)$	矩生成函数 MGF 与特征函数 CF
$\gamma$、$\alpha$	幂律 PDF 指数与 CCDF 指数满足 $\gamma=1+\alpha$；稳定分布的 $\alpha=2$ 是高斯特例
$n$、$M$、$m$	网络节点数、总边数、BA 每个新节点带来的边数；$M_X(t)$ 与总边数 $M$ 由上下文区分
$A_{ij}$	有向图中表示从 $i$ 指向 $j$；因此行和为出度，列和为入度
$p(x)$、$p_k$、$\boldsymbol p$	连续密度、离散度概率、PageRank 概率向量，分别使用

导论：为什么要研究复杂系统

来源：Lecture 0，pp. 1–21、25；pp. 22–24、26 为课程安排与参考信息。

从个体到整体：复杂性出现在哪里

复杂系统（complex system）的核心不是“零件很多”本身，而是大量个体之间的相互作用使整体表现出单个个体没有的结构和行为。讲义第 10 页用四点概括：many-body、autonomous、interaction、emergence，即大量组成单元、分散自主行动、常含非线性相互作用、涌现出的模式或集体行为。它们是本课识别复杂系统的框架，不是每种系统必须严格满足的数学公理。

自主（autonomous）表示整体秩序不必由中央指挥者逐项设计。涌现（emergence）表示群体层面出现新的可观察规律；知道单个组成单元的性质，还不足以直接读出整体行为。

讲义例子	局部机制或个体层次	要说明的集体现象
行军蚁、蚂蚁筏	个体通过邻近接触等局部信息协调	自组织、资源效率、集体能力
鸟群	个体调整运动并相互影响	大尺度同步、集体行为
萤火虫、鼓掌	个体振荡/节奏受他者影响	自发同步、模式形成
人浪	邻近人群响应与参与人数	临界人数、相变式集体响应
交通、城市、疫情	人、道路、接触及反馈网络	拥堵、空间组织与传播

还原论的用途与局限

还原论（reductionism）试图由组成部分及其相互作用理解整体。它提供微观模型的起点；但复杂系统存在关联、反馈及跨尺度行为，不能只把孤立个体的结果线性相加，就认为已经解释整体。

例如，了解一只鸟的飞行能力并不能直接预测鸟群的转向模式；还必须说明它如何响应其他鸟。物理学方法寻求在细节不同的系统中出现的共同规律，即普适性（universality）。这通常需要把问题转化为可测量的宏观量，例如分布尾部、同步程度、网络连通性或聚类程度。

简答题答法： 先指出个体是什么，再说明相互作用是什么，然后指出出现了什么群体现象，最后说明为什么单个个体的性质不足以决定该现象。不要仅写“系统很大、很复杂”。

本课的工具箱与各概念的联系

• Agent-based model（基于主体的模型）： 为个体设定状态与行动/互动规则，观察总体行为。Cellular automaton（元胞自动机） 通常把状态放在离散格点上，并按邻域规则更新。这是导论列出的建模方式，本批材料尚未展开其具体模型。

• 复杂网络： 把个体抽象成节点、相互作用抽象成边。分布描述数据“长什么样”，网络尝试表达“谁与谁发生作用”。同样的局部规则在不同连接结构上可以产生不同宏观结果。

• 非线性动力学与混沌： 非线性使响应不必与输入成比例；混沌研究确定性系统中对初始条件高度敏感的运动。复杂系统可能有序，也可能混沌，不能把“复杂”等同于“随机”或“混沌”。

• 无序、异质性与模式形成： 真实系统的连接、个体属性或耦合强度不同。研究问题是这些差异怎样影响秩序的产生。

• 相变与临界性： 随着控制参数改变，系统的宏观行为可定性改变。统计物理提供从微观互动研究宏观相的工具；复杂系统把这类方法推广到不规则、异质结构。

• 自组织临界性（SOC）： 某些受驱动系统可能通过自身动力学靠近临界状态，沙堆是讲义给出的直观例子。不能由“发现幂律”直接证明一个系统具有 SOC。

• 幂律、厚尾、尺度无关： 大的事件比正态模型预测的更常见，提示正态近似的条件可能不成立。幂律是可检验的统计规律，不自动指定唯一的微观机制。

贯穿全文的一条逻辑线

如果很多影响真的可以近似为独立、同分布、有限方差的加和，CLT 给出正态的基准预测。若数据明显偏离这一预测，应检查独立性、方差是否有限、变量是否是加和、抽样是否混合不同机制等条件。稳定分布与幂律提供另一类可能的统计结构，而增长与优先连接给出产生网络幂律的一种具体机制。网络指标再把复杂的连接图转化为可以比较和计算的量。

自测（概念）： 一群人同时观看同一个外部节拍器而同步，是否已经证明自组织？答： 没有。同步可能来自共同外部驱动；要说明自组织，需要考察群体内部互动怎样使秩序形成。这个区分也说明：相同宏观现象未必只有一种机制。

中心极限定理：为何许多随机贡献之和近似正态

这一章对应讲义 1《Central limit theorem》的第 1–13 页。讲义用落球装置说明随机游走：小球在每一层随机向左或向右偏移，终点位置是许多次随机偏移的总和。下面从分布和矩的基础开始，逐步解释正态近似的条件、矩生成函数证明，以及随机游走的精确结果。

先分清随机变量、分布和矩

随机变量（random variable）$X$ 是随机试验结果的数值表示，$x$ 表示它的某个可能取值。连续型随机变量用概率密度函数（probability density function，PDF）$p_X(x)$ 描述：

$$\begin{aligned} p_X(x)&\geq 0,\\ \int_{-\infty}^{\infty}p_X(x)\,dx&=1,\\ P(a\leq X\leq b)&=\int_a^b p_X(x)\,dx. \end{aligned}$$

密度的高度不是该点的概率；连续分布有 $P(X=x)=0$。离散型随机变量则用概率质量函数（probability mass function，PMF）$p_X(x)=P(X=x)$，积分换成对所有可能取值的求和，例如 $\sum_xp_X(x)=1$。

均值、方差与原点矩

均值（mean）给出位置，方差（variance）描述围绕均值的平方波动，标准差（standard deviation）$\sigma$ 与 $X$ 单位相同：

$$\begin{aligned} \mu&=E[X]=\int_{-\infty}^{\infty}x p_X(x)\,dx,\\ \sigma^2&=\operatorname{Var}(X)=E[(X-\mu)^2]\\ &=E[X^2]-(E[X])^2. \end{aligned}$$

$k$ 阶原点矩（raw moment）是 $m_k=E[X^k]$。因此

$$m_0=1,\qquad \mu=m_1,\qquad \sigma^2=m_2-m_1^2.$$

只有 $\mu=0$ 时，$m_2$ 才等于方差。 原点矩与中心矩 $E[(X-\mu)^k]$ 不要混用。

一般正态与标准正态

一般正态分布（normal/Gaussian distribution）写成 $X\sim\mathcal N(\mu,\sigma^2)$，括号中第二个参数是方差：

$$p_X(x)=\frac{1}{\sigma\sqrt{2\pi}} \exp\!\left[-\frac{(x-\mu)^2}{2\sigma^2}\right],\qquad \sigma>0.$$

标准正态变量 $Z\sim\mathcal N(0,1)$ 的密度为

$$\phi(z)=\frac{1}{\sqrt{2\pi}}e^{-z^2/2},\qquad E[Z]=0,\quad \operatorname{Var}(Z)=1.$$

若 $X\sim\mathcal N(\mu,\sigma^2)$，则 $(X-\mu)/\sigma\sim\mathcal N(0,1)$。定义标准正态分布函数

$$\Phi(z)=\int_{-\infty}^z\phi(u)\,du.$$

区间概率为 $P(a\leq Z\leq b)=\Phi(b)-\Phi(a)$，对称性给出 $\Phi(-z)=1-\Phi(z)$。

CLT 的准确陈述与使用条件

讲义第 3–7 页的核心结论是：设 $X_1,\ldots,X_n$ 独立同分布（independent and identically distributed，i.i.d.），且

$$E[X_i]=\mu\ \text{有限},\qquad 0<\operatorname{Var}(X_i)=\sigma^2<\infty.$$

“同分布”是每个变量遵循同一概率规律，不表示每次抽出的数值相同。独立表示知道某个变量的结果不会改变其他变量的概率分布。定义总和及样本均值

$$S_n=\sum_{i=1}^nX_i,\qquad \overline X_n=\frac{S_n}{n}.$$

中心极限定理（central limit theorem，CLT）的核心是标准化后的总和依分布收敛：

$$\boxed{ \begin{aligned} Z_n&=\frac{S_n-n\mu}{\sigma\sqrt n} =\frac{\sqrt n(\overline X_n-\mu)}{\sigma},\\ Z_n&\xrightarrow{d}\mathcal N(0,1),\qquad n\to\infty. \end{aligned} }$$

这里“依分布收敛”的具体含义是：对每个固定实数 $z$，有 $P(Z_n\leq z)\to\Phi(z)$。它允许原始 $X_i$ 是离散或非正态变量；并不声称有限 $n$ 时分布恰好正态，也不保证任意密度都逐点趋近。

为什么标准化中出现根号 $n$

均值、方差的尺度关系解释了为何出现 $\sqrt n$：

$$\begin{aligned} E[S_n]&=n\mu,\\ \operatorname{Var}(S_n)&=n\sigma^2,\\ E[\overline X_n]&=\mu,\\ \operatorname{Var}(\overline X_n)&=\frac{\sigma^2}{n}. \end{aligned}$$

独立使交叉协方差为零；总和的标准差是 $\sigma\sqrt n$，均值的标准差是 $\sigma/\sqrt n$。所以大 $n$ 时常写成近似

$$\begin{aligned} S_n&\approx\mathcal N(n\mu,n\sigma^2),\\ \overline X_n&\approx\mathcal N\!\left(\mu,\frac{\sigma^2}{n}\right). \end{aligned}$$

讲义采用 $\mu=0,\sigma^2=1$，此时 $Z_n=\sqrt n\,\overline X_n=S_n/\sqrt n$；根号只覆盖 $n$。均值本身的波动缩小到零，趋向常数 $\mu$，不能写成 $\overline X_n\to\mathcal N(0,1)$。 若用密度近似，必须带上正确归一化系数：

$$p_{\overline X_n}(x)\approx\frac{\sqrt n}{\sigma\sqrt{2\pi}} \exp\!\left[-\frac{n(x-\mu)^2}{2\sigma^2}\right].$$

为什么 CLT 有用，又为什么不能滥用

讲义第 5 页举出财富、股票价格、地震、超市销售等“许多因素共同影响”的例子，用来提出正态分布作为初步猜测。应用时必须逐项检查：影响是否相加、是否独立、是否满足相应分布和有限方差条件。例子本身并不是这些量服从正态分布的证明。 相关作用、乘法增长或极端重尾都可能使这一简单论证失效。

这里使用的是有限方差的 i.i.d. 版本；只有“均值与方差相同”并不等于同分布。更一般的 CLT 可以放宽条件，但需要额外定理。也不存在对所有分布都可靠的固定阈值“$n\geq30$”；偏斜和重尾会影响近似速度。

矩生成函数：用一个函数编码矩

讲义第 8–10 页引入矩生成函数（moment generating function，MGF）：

$$M_X(t)=E[e^{tX}] =\int_{-\infty}^{\infty}e^{tx}p_X(x)\,dx.$$

离散型变量改用 $M_X(t)=\sum_x e^{tx}p_X(x)$。

用零点导数生成矩

将 $e^{tX}$ 在 $t=0$ 展开，且在可以交换求和与期望的条件下，有

$$\begin{aligned} e^{tX}&=1+tX+\frac{t^2X^2}{2!}+\frac{t^3X^3}{3!}+\cdots,\\ M_X(t)&=1+m_1t+\frac{m_2t^2}{2!}+\frac{m_3t^3}{3!}+\cdots. \end{aligned}$$

于是

$$\boxed{M_X^{(k)}(0)=m_k=E[X^k].}$$

$M_X^{(k)}$ 表示 $k$ 阶导数，不是 $M_X$ 的 $k$ 次幂。计算时先对 $t$ 求导，再令 $t=0$。直接把 $t=0$ 代入 MGF 只能得到 $M_X(0)=1$。

上述常规 MGF 操作以 $M_X(t)$ 在 $0$ 的某个开邻域内有限为充分条件。并不是每个分布都有这种 MGF，甚至“所有原点矩都有限”也不能自动保证它存在。标准有限方差 CLT 本身不要求 MGF 存在；这里采用的 MGF 证明是一个附加存在性条件下的证明。

平移、缩放与独立相加

后续证明使用两条规则：

$$\begin{aligned} M_{aX+b}(t)&=e^{bt}M_X(at),\\ M_{X+Y}(t)&=M_X(t)M_Y(t)\qquad (X,Y\ \text{独立}). \end{aligned}$$

第一条来自 $e^{t(aX+b)}=e^{bt}e^{atX}$；第二条来自独立性使 $E[e^{tX}e^{tY}]=E[e^{tX}]E[e^{tY}]$。若只是“不相关”，第二条一般不成立。

标准正态的 MGF：配方是关键

令 $Z\sim\mathcal N(0,1)$，则

$$\begin{aligned} M_Z(t) &=\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}}e^{-z^2/2+tz}\,dz\\ &=e^{t^2/2}\int_{-\infty}^{\infty}\frac{1}{\sqrt{2\pi}}e^{-(z-t)^2/2}\,dz\\ &=\boxed{e^{t^2/2}}. \end{aligned}$$

最后一个积分是均值 $t$、方差 $1$ 的正态密度积分，因此等于 $1$。进一步，$X=\mu+\sigma Z$ 给出一般正态 MGF

$$M_X(t)=\exp\!\left(\mu t+\frac{\sigma^2t^2}{2}\right).$$

标准正态的前四阶导数依次为

$$\begin{aligned} M'_Z(t)&=t e^{t^2/2},\\ M''_Z(t)&=(1+t^2)e^{t^2/2},\\ M'''_Z(t)&=(3t+t^3)e^{t^2/2},\\ M^{(4)}_Z(t)&=(3+6t^2+t^4)e^{t^2/2}. \end{aligned}$$

故 $m_0=1,m_1=0,m_2=1,m_3=0,m_4=3$。

原点矩、偏度与峰度不要混淆

一般分布的偏度（skewness）与峰度（kurtosis）定义为

$$\begin{aligned} \gamma_1&=\frac{E[(X-\mu)^3]}{\sigma^3},\\ \beta_2&=\frac{E[(X-\mu)^4]}{\sigma^4},\\ \gamma_2&=\beta_2-3\qquad\text{（超额峰度）}. \end{aligned}$$

只有对已标准化的变量，$m_3=\gamma_1$、$m_4=\beta_2$。正态分布的偏度为 $0$、峰度为 $3$、超额峰度为 $0$；三个数字不要混淆。

CLT 的 MGF 证明：每个假设用在哪里

讲义第 11 页采用简化情形 $E[X_i]=0$、$E[X_i^2]=1$，并假定单个 $X_i$ 的 MGF 在 $0$ 邻域有限。目标是证明 $Z_n=S_n/\sqrt n$ 的 MGF 趋近 $e^{t^2/2}$。

第一步：把和的指数变成指数的乘积

$$\begin{aligned} M_{Z_n}(t) &=E\!\left[\exp\!\left(\frac{t}{\sqrt n}\sum_{i=1}^nX_i\right)\right]\\ &=E\!\left[\prod_{i=1}^n e^{tX_i/\sqrt n}\right]. \end{aligned}$$

第二步：用独立性分解期望，再用同分布性合并为幂

$$\begin{aligned} M_{Z_n}(t)&=\prod_{i=1}^n E[e^{tX_i/\sqrt n}]\\ &=\left[M_X\!\left(\frac{t}{\sqrt n}\right)\right]^n. \end{aligned}$$

这一行就是 independent 与 identically distributed 在证明中的具体位置。

第三步：在零点作二阶泰勒展开

对固定 $t$，令 $u=t/\sqrt n\to0$。因为 $M_X(0)=1$、$M'_X(0)=0$、$M''_X(0)=1$，

$$\begin{aligned} M_X(u)&=M_X(0)+M'_X(0)u+\frac{M''_X(0)}{2}u^2+o(u^2)\\ &=1+\frac{u^2}{2}+o(u^2). \end{aligned}$$

因此

$$M_{Z_n}(t)=\left[1+\frac{t^2}{2n}+o\!\left(\frac1n\right)\right]^n.$$

注意导数必须在展开中心 $0$ 处求值；对有限 $n$ 不能直接丢掉余项后写成严格等号。

第四步：取极限

利用 $\log(1+v)=v+o(v)$，

$$\begin{aligned} \log M_{Z_n}(t) &=n\log\!\left[1+\frac{t^2}{2n}+o\!\left(\frac1n\right)\right]\\ &\longrightarrow\frac{t^2}{2}. \end{aligned}$$

所以 $M_{Z_n}(t)\to e^{t^2/2}$。由 MGF 的连续性定理，得到 $Z_n\xrightarrow{d}\mathcal N(0,1)$。

第五步：还原一般均值与方差

对 $Y_i=(X_i-\mu)/\sigma$ 重复上面的推导，因为 $E[Y_i]=0$、$\operatorname{Var}(Y_i)=1$，故

$$\frac1{\sqrt n}\sum_{i=1}^nY_i =\frac{S_n-n\mu}{\sigma\sqrt n}\xrightarrow{d}\mathcal N(0,1).$$

整条证明链是：标准化 → 指数中的和变乘积 → 独立分解 → 同分布合并 → 零点二阶展开 → $(1+a/n)^n\to e^a$。有限均值确定需要减去什么；有限方差确定缩放尺度。

为什么有限方差 CLT 比这个证明更一般

可以改用总存在的特征函数 $\varphi_X(t)=E[e^{itX}]$。对均值 $0$、方差 $1$ 的变量，有

$$\varphi_X(u)=1-\frac{u^2}{2}+o(u^2),$$

同样得到

$$\left[\varphi_X\!\left(\frac{t}{\sqrt n}\right)\right]^n\to e^{-t^2/2}.$$

这是对 MGF 存在性缺口的说明；前面的主要推导仍采用 MGF 路线。

随机游走：从一步分布到终点分布

讲义第 12–13 页考虑每一步向右 $+1$ 或向左 $-1$，概率各为 $1/2$。各步独立；第 $n$ 步终点为 $S_n=X_1+\cdots+X_n$。落球装置中的多次左右偏移可作直观类比。

一步的分布和矩

这是离散分布，应称为 PMF：

$$P(X=1)=P(X=-1)=\frac12,\qquad M_X(t)=\frac{e^t+e^{-t}}{2}=\cosh t.$$

由 $\cosh' t=\sinh t$、$\sinh' t=\cosh t$，得

$$m_1=0,\quad m_2=1,\quad m_3=0,\quad m_4=1.$$

也可直接观察：$X$ 的奇数次幂仍为 $X$，偶数次幂恒为 $1$。因此一步均值 $0$、方差 $1$；它不是正态分布，因为其第四矩为 $1$，标准正态第四矩为 $3$。

$n$ 步的精确分布

设向右走了 $K$ 次，则 $K\sim\operatorname{Binomial}(n,1/2)$，而 $S_n=K-(n-K)=2K-n$，因此

$$P(S_n=s)=2^{-n}\binom{n}{(n+s)/2},\qquad s=-n,-n+2,\ldots,n.$$

其余 $s$ 的概率为 $0$。终点与 $n$ 的奇偶性相同。$S_n$ 的 MGF 为 $(\cosh t)^n$，有

$$\begin{aligned} E[S_n]&=0,\\ E[S_n^2]&=n,\\ E[S_n^3]&=0,\\ E[S_n^4]&=3n^2-2n. \end{aligned}$$

第四矩的来源也可直接计数：展开 $(\sum_iX_i)^4$ 后，只有同一指标出现四次、或两个指标各出现两次的项期望非零，因此

$$\begin{aligned} E[S_n^4]&=nE[X^4]+6\binom{n}{2}(E[X^2])^2\\ &=n+3n(n-1)\\ &=3n^2-2n. \end{aligned}$$

标准化终点 $Z_n=S_n/\sqrt n$ 的均值为 $0$、方差为 $1$，偏度为 $0$，峰度为

$$E[Z_n^4]=3-\frac2n\longrightarrow3.$$

它的 MGF 为

$$M_{Z_n}(t)=\left[\cosh\!\left(\frac{t}{\sqrt n}\right)\right]^n \longrightarrow e^{t^2/2}.$$

这展示了“每一步只有两个取值”与“很多步的标准化终点趋于正态”如何同时成立。

怎样完成随机游走模拟并解释结果

分别令 $n=5,25,125$，每个 $n$ 独立重复 $1000$ 次，每次生成 $n$ 个等概率 $\pm1$，对每次的所有步求和，得到 $1000$ 个终点。画终点直方图并与 $\mathcal N(0,n)$ 比较；也可画 $S_n/\sqrt n$ 并与 $\mathcal N(0,1)$ 比较。

步数 $n$	$E[S_n]$	$\operatorname{SD}(S_n)$	$Z_n$ 的精确峰度
5	0	$\sqrt5\approx2.236$	$2.600$
25	0	$5$	$2.920$
125	0	$\sqrt{125}\approx11.180$	$2.984$

理解结果时，要分清以下几点：

• $n$ 是每次游走的步数，决定理论近似；$1000$ 是独立重复次数，决定估计直方图的噪声。增加重复次数不会让固定 $5$ 步的真实分布变成连续正态。
• 三个 $n$ 都是奇数，终点相隔 $2$，可用宽度为 $2$、中心在允许终点的直方图区间；与 PDF 叠图时将直方图归一化成密度。若画 PMF 柱高，则应比较正态在相应区间的概率面积，而不是直接比较密度高度。
• 理论参数是 $\mu=0,\sigma=\sqrt n$。用模拟样本拟合时，应报告样本均值及拟合标准差，它们会因抽样波动略有偏离。
• 随 $n$ 增大，标准化终点的整体轮廓通常更接近钟形；有限 $n$ 的真实分布始终离散，有限 $1000$ 次模拟也会保留噪声。

自测与解题模板

下面五道练习将本章的概念和公式串起来，每道题都给出完整答案。

题 1：总和和均值的正态近似

独立同分布 $X_i$ 的均值为 $10$、标准差为 $2$，取 $n=100$。求 $S_n$ 和 $\overline X_n$ 的近似分布，并估计 $P(9.6\leq\overline X_n\leq10.4)$。

解： 先确认 $\sigma^2=4$，所以

$$\begin{aligned} S_{100}&\approx\mathcal N(1000,400),\\ \overline X_{100}&\approx\mathcal N(10,0.04). \end{aligned}$$

均值的标准差为 $0.2$，故所求概率近似为 $\Phi(2)-\Phi(-2)\approx0.9545$。常见错误是把 $0.04$ 当成标准差，或把总和方差误写成 $100^2\times4$。

题 2：由 MGF 读出矩

给定 $M_X(t)=\exp(3t+2t^2)$，求均值、方差、二阶原点矩。

解： 与正态 MGF $\exp(\mu t+\sigma^2t^2/2)$ 对比，得 $\mu=3$、$\sigma^2=4$，所以 $m_2=\sigma^2+\mu^2=13$。亦可用 $M'_X(0)=3$、$M''_X(0)=13$；后者不是方差。

题 3：随机游走的精确概率

走 $5$ 步后到达 $s=1$ 的概率是多少？

解： 需要 $K=(5+1)/2=3$ 次向右，因此

$$P(S_5=1)=\binom{5}{3}2^{-5}=\frac{10}{32}=\frac5{16}.$$

$P(S_5=0)=0$，因为奇数步不可能到达偶数终点。正态近似不能替代这个离散支持条件。

题 4：为何“很多项”还不够

若 $X_1=\cdots=X_n=Y$，其中 $E[Y]=0$、$\operatorname{Var}(Y)=1$，能否按本章的 CLT 得到 $S_n/\sqrt n\to\mathcal N(0,1)$？

解： 不能。这些变量完全相关，$S_n=nY$，故 $\operatorname{Var}(S_n)=n^2$，$\operatorname{Var}(S_n/\sqrt n)=n$；独立性要求不成立。相同分布不等于独立，协方差项不能删去。

题 5：证明中的两处概念判断

“有限方差保证 MGF 在 $0$ 附近存在”“均值的 MGF 是 $[M_X(t/\sqrt n)]^n$”是否正确？

解： 两句均不正确。有限方差 CLT 可成立而 MGF 方法不能直接使用；$\overline X_n$ 的 MGF 是 $[M_X(t/n)]^n$。当 $\mu=0,\sigma=1$ 时，$[M_X(t/\sqrt n)]^n$ 对应 $\sqrt n\,\overline X_n$。

计算题的通用顺序

1. 辨认单个变量分布与独立性。
2. 求 $\mu,\sigma^2$。
3. 写出目标是 $S_n$ 还是 $\overline X_n$。
4. 计算目标的均值和方差。
5. 标准化为 $Z$。
6. 最后用 $\Phi$、精确离散概率或 MGF 回答。

论述时则应同时说明定理、前提与有限样本近似的含义。

尺度无关分布：稳定性、幂律与极端事件

对应资料： 讲义 2，第 1–18 页。主线是：普通中心极限定理为什么产生正态分布；当方差不存在时会怎样；如何从幂律计算概率、矩和尺度；这些结果怎样帮助理解财富、地震和罕见大事件。文中“补充解释”用于填补推导步骤，“校正”用于防止把讲义中的简化说法当成数学定理。

稳定分布与吸引域：相加后保持什么不变？

讲义第 2–3 页。 设 $X_1,\ldots,X_n$ 独立同分布，令

$$S_n=\sum_{i=1}^nX_i,\qquad \bar X_n=\frac{S_n}{n}.$$

分布稳定（stable） 的意思是：相加后，除平移与缩放外，分布形状不变。精确地，对每个 $n$，存在 $a_n>0,b_n\in\mathbb R$，使

$$S_n\overset{d}{=}a_nX+b_n.$$

符号 $\overset{d}{=}$ 表示“同分布”，不表示两边取值逐次相等。若可取 $b_n=0$，称为严格稳定。稳定性是任意有限 $n$ 的精确性质；吸引性是 $n\to\infty$ 的极限性质。 例如，均匀分布不稳定，但其标准化和趋近正态，所以它属于正态分布的吸引域。

正态分布的稳定性

若 $X_i\sim\mathcal N(\mu,\sigma^2)$，则

$$\begin{aligned} M_X(t)&=\mathbb E[e^{tX}] =\exp\!\left(\mu t+\frac{\sigma^2t^2}{2}\right),\\ M_{S_n}(t)&=\prod_{i=1}^nM_{X_i}(t) =\exp\!\left(n\mu t+\frac{n\sigma^2t^2}{2}\right). \end{aligned}$$

独立性允许把乘积的期望拆开。因此

$$\begin{aligned} S_n&\sim\mathcal N(n\mu,n\sigma^2),\\ \bar X_n&\sim\mathcal N\!\left(\mu,\frac{\sigma^2}{n}\right),\\ \frac{S_n-n\mu}{\sigma\sqrt n}&\sim\mathcal N(0,1). \end{aligned}$$

对标准正态 $\mu=0,\sigma=1$，讲义中的 $M_{S_n}(t)=M_X(\sqrt n\,t)$ 成立；这说明和的宽度增加为 $\sqrt n$ 倍。平均值的宽度则缩小为 $1/\sqrt n$ 倍。

自相似（self-similarity）须包含密度的归一化

若 $S_n\overset{d}{=}a_nX$，则

$$f_{S_n}(s)=\frac1{a_n}f_X\!\left(\frac{s}{a_n}\right).$$

前面的 $1/a_n$ 来自变量代换，确保积分仍为 $1$。标准正态的情况为

$$\begin{aligned} f_{S_n}(s)&=\frac{1}{\sqrt{2\pi n}}e^{-s^2/(2n)},\\ f_{\bar X_n}(x)&=\sqrt{\frac n{2\pi}}e^{-nx^2/2}. \end{aligned}$$

易错点： 讲义第 3 页的 $p(\sqrt n\,\bar x)$ 是对函数自变量的示意，不能直接当作 $\bar X_n$ 的密度；那样会漏掉 Jacobian。非正态 $X_i$ 的 $S_n$ 本身通常也不会收敛到固定正态，必须先中心化并缩放。

为什么吸引域重要？

宏观观测经常是许多微小贡献的和。若不同微观分布经同一缩放趋向同一个极限，预测宏观形状便不必知道每个微观细节。这是本课程“普适性”的概率论起点；它始终需要检查独立性、相关性和尾部条件。

怎样放宽中心极限定理的条件？

讲义第 4–5 页。 普通独立同分布版本要求 $\mathbb E[X_i]=\mu$、$0<\operatorname{Var}(X_i)=\sigma^2<\infty$，结论是

$$\frac{S_n-n\mu}{\sigma\sqrt n}\xrightarrow{d}\mathcal N(0,1).$$

下面三种改变要分别判断，不能只凭“加了很多项”便使用 CLT。

分布不相同：Lyapunov CLT

设 $X_i$ 独立，但可有不同均值 $\mu_i$ 和方差 $\sigma_i^2$。定义

$$s_n^2=\sum_{i=1}^n\sigma_i^2.$$

若存在 $\delta>0$，满足 Lyapunov 条件

$$\lim_{n\to\infty}\frac{1}{s_n^{2+\delta}} \sum_{i=1}^n\mathbb E\!\left[|X_i-\mu_i|^{2+\delta}\right]=0,$$

则

$$\frac{\sum_{i=1}^n(X_i-\mu_i)}{s_n}\xrightarrow{d}\mathcal N(0,1).$$

条件的含义是：较高阶的大偏离总量，相对于整体波动尺度越来越小；不允许极少数项完全支配和。$s_n$ 是总和的标准差，不能把它写成各标准差之和。Lyapunov 条件是充分条件，不是所有 CLT 成立的必要条件。

补充例题：独立但不同分布的 Bernoulli 变量

令相互独立的 $X_i\sim\operatorname{Bernoulli}(p_i)$，并假设 $s_n^2\ge cn$，其中 $c>0$。取 $\delta=1$，由于 $|X_i-p_i|\le1$，

$$\frac{\sum_i\mathbb E|X_i-p_i|^3}{s_n^3} \le\frac{n}{(cn)^{3/2}}\longrightarrow0.$$

即使 $p_i$ 各不相同，标准化和仍趋近正态。答题步骤：写出均值、方差与 $s_n$，选 $\delta$，估计该比值，最后写极限分布。

弱依赖：粗粒化的直觉

讲义认为：若依赖只持续很短距离，将很多观测合成一个大块后，相邻远距离块的依赖可变弱，正态极限可能保留。补充限定：“相关很小”或“相关趋于零”单独并不足以保证 CLT，仍需要合适的混合或其他依赖条件；不相关也不等于独立。

对平稳序列，设 $C(k)=\operatorname{Cov}(X_t,X_{t+k})$，则精确地

$$\operatorname{Var}(S_n)=nC(0)+2\sum_{k=1}^{n-1}(n-k)C(k).$$

若协方差绝对可求和且满足适当 CLT 条件，通常

$$\begin{aligned} \operatorname{Var}(S_n)&\sim n\sigma_{\mathrm{LR}}^2,\\ \sigma_{\mathrm{LR}}^2&=C(0)+2\sum_{k=1}^{\infty}C(k)>0. \end{aligned}$$

归一化须使用长期方差 $\sigma_{\mathrm{LR}}^2$。长程依赖可能改变 $\sqrt n$ 缩放甚至改变极限分布。

无穷均值或方差

普通有限方差版 CLT 的假设失效；正态近似不能自动使用。下一节的 Cauchy 给出明确反例。更一般的归一化和可能趋向非高斯稳定分布；“假设失效”并不等价于“任何形式的正态极限都绝对不可能”。

Cauchy / Lorentz：平均越多不一定越准确

讲义第 6 页。 中心在 $0$、尺度为 $\gamma>0$ 的 Cauchy（Lorentz）分布为

$$f_X(x)=\frac{\gamma}{\pi(x^2+\gamma^2)},\qquad -\infty<x<\infty.$$

它的中心是中位数与众数，不是期望。归一化可由
$\int (x^2+\gamma^2)^{-1}\,dx=\gamma^{-1}\arctan(x/\gamma)$ 检查。

为什么 Cauchy 均值不存在？

必须分别检查正、负两侧积分：

$$\int_0^R x f_X(x)\,dx =\frac{\gamma}{2\pi}\log\!\left(\frac{R^2+\gamma^2}{\gamma^2}\right) \xrightarrow{R\to\infty}+\infty.$$

负半轴积分为 $-\infty$，所以普通期望是未定义的 $\infty-\infty$。对称主值
$\lim_{R\to\infty}\int_{-R}^{R}xf_X(x)\,dx=0$，不等于期望存在。另有 $x^2f_X(x)\to\gamma/\pi$，故 $\mathbb E[X^2]=\infty$。校正： 讲义不定积分中的对数系数应为 $\gamma/(2\pi)$，不是 $\gamma/\pi$。

为什么改用特征函数？

矩母函数 $M_X(t)=\mathbb E[e^{tX}]$ 对此分布在任何非零实数 $t$ 都发散；特征函数则总存在，因为 $|e^{iqX}|=1$：

$$\begin{aligned} \varphi_X(q)&=\mathbb E[e^{iqX}] =\int_{-\infty}^{\infty}f_X(x)e^{iqx}\,dx,\\ f_X(x)&=\frac1{2\pi}\int_{-\infty}^{\infty}\varphi_X(q)e^{-iqx}\,dq. \end{aligned}$$

后一反演公式在满足相应可积条件时使用；这里 Cauchy 的特征函数可积，所以没有问题。讲义的 Fourier 约定是一正一负，逆变换有 $1/(2\pi)$。

对于 Cauchy，$\varphi_X(q)=e^{-\gamma|q|}$。补充验证： 不必用复变积分，从逆变换即可计算

$$\begin{aligned} &\frac1{2\pi}\int_{-\infty}^{\infty}e^{-\gamma|q|}e^{-iqx}\,dq\\ &\quad=\frac1\pi\int_0^\infty e^{-\gamma q}\cos(qx)\,dq\\ &\quad=\frac1\pi\operatorname{Re}\frac1{\gamma+ix} =\frac{\gamma}{\pi(\gamma^2+x^2)}. \end{aligned}$$

独立相加的关键计算

$$\begin{aligned} \varphi_{S_n}(q)&=[\varphi_X(q)]^n=e^{-n\gamma|q|},\\ \Longrightarrow\quad f_{S_n}(s)&=\frac{n\gamma}{\pi[s^2+(n\gamma)^2]}. \end{aligned}$$

因此 $S_n\sim\operatorname{Cauchy}(0,n\gamma)$，而

$$\begin{aligned} \varphi_{\bar X_n}(q)&=\varphi_{S_n}(q/n)=e^{-\gamma|q|},\\ &\boxed{\bar X_n\overset{d}{=}X_1}. \end{aligned}$$

均值的分布宽度完全不随样本量缩小。例如，不论 $n$ 多大，$\Pr(|\bar X_n|>\gamma)=1/2$。这不违背通常的大数定律，因为 Cauchy 不满足有限一阶绝对矩这一充分条件。

Lévy 稳定分布、广义 CLT 与尺度指数

讲义第 7–10 页。 本课实际采用对称、中心为零的稳定分布，特征函数为

$$\boxed{\varphi_X(q)=\exp(-\gamma|q|^\alpha)}, \qquad \gamma>0,\quad 0<\alpha\le2.$$

$\alpha$ 是稳定指数或尾指数参数；$\gamma$ 控制尺度，具有与 $X^\alpha$ 相同的量纲。校正： 讲义的“$\mu=0$ mean”应读成位置参数为 $0$，因为 $\alpha\le1$ 时对称分布的均值并不存在。一般稳定分布还可有位置和偏斜参数；讲义中被划去的非对称公式不是本节需要背诵的核心。

由独立性与特征函数唯一性，

$$\varphi_{S_n}(q)=e^{-n\gamma|q|^\alpha} =\varphi_X(n^{1/\alpha}q) \quad\Longrightarrow\quad S_n\overset{d}{=}n^{1/\alpha}X.$$

于是密度与平均值的缩放为

$$\begin{aligned} f_{S_n}(s)&=n^{-1/\alpha}f_X(s/n^{1/\alpha}),\\ \bar X_n&\overset{d}{=}n^{1/\alpha-1}X. \end{aligned}$$

这一推导同时解释三个典型情况：

• $\alpha=2$：正态。由 $e^{-\gamma q^2}$ 与正态特征函数比较，$\sigma^2=2\gamma$；平均宽度按 $n^{-1/2}$ 缩小。
• $\alpha=1$：Cauchy。和的尺度为 $n$，平均尺度不变。
• $1<\alpha<2$：均值存在，平均的波动尺度按 $n^{-(1-1/\alpha)}$ 缩小，比正态慢；$0<\alpha<1$ 时该尺度反而增长。

这里的“宽度”可取分位距等尺度量，不能用不存在的标准差。例如 $\alpha=3/2$ 时，$S_n$ 的尺度是 $n^{2/3}$，$\bar X_n$ 的尺度是 $n^{-1/3}$。

幂律尾与矩

对称非高斯稳定分布满足

$$f_X(x)\sim C_\alpha |x|^{-1-\alpha}\quad (|x|\to\infty), \qquad 0<\alpha<2,$$

且对 $r>0$，$\mathbb E|X|^r<\infty$ 当且仅当 $r<\alpha$。因而所有非高斯稳定分布都有发散的二阶矩；对称情况下只有 $\alpha>1$ 才有有限均值。特别注意：$\alpha=2$ 的尾是高斯尾，不能把它代入幂律式得到 $|x|^{-3}$。正态的各阶绝对矩均有限。

广义 CLT 的课程含义

若独立同分布随机变量的尾部属于相应稳定分布的吸引域，可以选择 $a_n>0,b_n$，使

$$\frac{S_n-b_n}{a_n}\xrightarrow{d}Z_\alpha.$$

补充解释： 对指数为 $\alpha\in(0,2)$ 的规则幂律尾，典型尺度是 $a_n$ 随 $n^{1/\alpha}$ 增长（更一般可能伴随慢变因子）；$\alpha>1$ 时通常中心化 $b_n=n\mathbb E[X]$。精确对称稳定分布才有前述任意 $n$ 都成立的等式。

讲义表述的适用范围

“稳定分布不是正态就是尾部幂律”描述的是稳定分布家族；不能扩大为“所有复杂系统观测只能是正态或幂律”。一般经验分布还可有指数尾、对数正态尾、混合形状和有限截断。也不能反过来说“任何幂律分布都严格稳定”：Pareto 就一般不稳定，但在适当尾指数下可属于稳定吸引域。

幂律的计算工具：指数、尾概率与矩

讲义第 8、10–11 页；本节补齐计算步骤。 为避免指数差一，统一写

$$f_X(x)=C x^{-\tau},\qquad \tau=1+\alpha, \qquad x\ge x_{\min}>0.$$

这是密度的幂律指数 $\tau$；$\alpha$ 是累计尾概率的指数。若 $\tau>1$，归一化给出

$$\begin{aligned} 1&=C\int_{x_{\min}}^\infty x^{-\tau}\,dx =\frac{C x_{\min}^{1-\tau}}{\tau-1},\\ \Longrightarrow\quad C&=(\tau-1)x_{\min}^{\tau-1}. \end{aligned}$$

纯幂律不可能在整个 $(0,\infty)$ 上同时在两端可积，因此下限或其他小尺度修正必不可少。

“尺度无关”是什么意思？

在幂律有效区间内，

$$f_X(cx)=c^{-\tau}f_X(x),\qquad \frac{\Pr(X>cx)}{\Pr(X>x)}=c^{-\alpha}\quad(c\ge1).$$

放大相同倍数所造成的相对概率衰减，与起始值 $x$ 无关；尾部没有像指数分布 $e^{-x/x_0}$ 那样的单一指数衰减尺度。不是说分布没有任何尺度参数，也不是说均值必然不存在。 Pareto 的 $x_{\min}$、稳定分布的尺度参数和分位距都可以存在。

从密度到累计尾概率（CCDF）

$$\begin{aligned} \overline F_X(x)&=\Pr(X>x)=\int_x^\infty Cu^{-\tau}\,du\\ &=\frac{C}{\tau-1}x^{-(\tau-1)}\propto x^{-\alpha}. \end{aligned}$$

因此在双对数图上

$$\begin{aligned} \log f_X(x)&=\log C-\tau\log x,\\ \log\overline F_X(x)&=\mathrm{const}-\alpha\log x. \end{aligned}$$

PDF 斜率为 $-(1+\alpha)$；CCDF 斜率为 $-\alpha$；CDF $F=1-\overline F$ 本身通常不是直线。 先看纵轴是什么，再读指数。若按对数区间分箱，原始箱计数还带有随 $x$ 增长的箱宽，估计密度必须除以箱宽。直线是幂律的诊断线索，有限区间近似直线本身不是严格证明。

矩存在条件从一个积分得出

对 $r>0$，

$$\begin{aligned} \mathbb E[X^r]&=C\int_{x_{\min}}^\infty x^{r-\tau}\,dx<\infty\\ &\Longleftrightarrow r-\tau<-1\\ &\Longleftrightarrow \boxed{r<\tau-1=\alpha}. \end{aligned}$$

$r=\alpha$ 时是 $\int dx/x$，呈对数发散，边界不能算有限。故 $\alpha>1$ 才有有限均值，$\alpha>2$ 才有有限二阶矩与方差。对正变量，$\alpha\le1$ 的期望为 $+\infty$；对两侧对称重尾分布，均值则可能是未定义，二者要区分。

有限系统的截断

若 $x_{\min}\le X\le x_{\max}<\infty$，各正阶矩均有限；但在很大的中间区间仍可呈幂律。对 $f(x)=C x^{-1-\alpha}$，

$$\mathbb E[X^r]= \begin{cases} \displaystyle\frac{C}{r-\alpha}\left(x_{\max}^{r-\alpha}-x_{\min}^{r-\alpha}\right),&r\ne\alpha,\\[4pt] \displaystyle C\log(x_{\max}/x_{\min}),&r=\alpha. \end{cases}$$

这说明截断虽消除数学上的无穷矩，估计值仍可能对上限与极端样本非常敏感。

Pareto 财富分布与微观交换模型

讲义第 11–12 页。 Pareto 模型取 $\alpha>0,x_m>0$：

$$\begin{aligned} f_X(x)&=\begin{cases} \dfrac{\alpha x_m^\alpha}{x^{\alpha+1}},&x\ge x_m,\\ 0,&x<x_m, \end{cases}\\ F_X(x)&=\begin{cases} 1-(x_m/x)^\alpha,&x\ge x_m,\\ 0,&x<x_m. \end{cases} \end{aligned}$$

对 $x\ge x_m$，累计分布是积分 $\int_{x_m}^{x}f_X(u)\,du$ 的结果，尾概率为 $(x_m/x)^\alpha$。任意 $r<\alpha$ 的矩为

$$\mathbb E[X^r]=\frac{\alpha x_m^r}{\alpha-r}.$$

由此得到讲义提出的均值、中位数与离散程度问题：

$$\begin{aligned} \mathbb E[X]&=\frac{\alpha x_m}{\alpha-1}\quad(\alpha>1),\\ \operatorname{Med}(X)&=x_m2^{1/\alpha},\\ Q(u)&=x_m(1-u)^{-1/\alpha}\quad(0<u<1),\\ \operatorname{Var}(X)&=\frac{\alpha x_m^2}{(\alpha-1)^2(\alpha-2)}\quad(\alpha>2). \end{aligned}$$

最后一式由 $\mathbb E[X^2]-(\mathbb E[X])^2$ 化简得到；不要在 $\alpha\le2$ 时代入这个式子，得到负“方差”。$1<\alpha\le2$ 时方差为无穷，$\alpha\le1$ 时有限均值本就不存在。

Gini 与 Lorenz 曲线

补齐讲义练习，要求 $\alpha>1$。 令 $u$ 表示从最穷者开始累计的人口比例，Lorenz 曲线 $L(u)$ 表示这些人持有的财富比例：

$$L(u)=\frac{\int_0^u Q(v)\,dv}{\mathbb E[X]} =1-(1-u)^{(\alpha-1)/\alpha}.$$

完全平等时 $L(u)=u$。Gini 系数是平等线与 Lorenz 曲线间面积的两倍：

$$G=1-2\int_0^1L(u)\,du=\boxed{\frac1{2\alpha-1}}.$$

较小 $\alpha$ 表示较重尾部、较强财富集中。理想 Pareto 且 $\alpha\le1$ 时，不能用有限均值的上述定义直接计算总体 Gini。

完整例题：$\alpha=1.5$ 的 Pareto 分布

取讲义的示例 $\alpha=1.5,x_m=1$，有

$$\begin{aligned} F(x)&=1-x^{-3/2},\\ \Pr(X>4)&=4^{-3/2}=\frac18,\\ \mathbb E[X]&=3,\\ \operatorname{Med}(X)&=2^{2/3}\approx1.587,\\ G&=\frac12. \end{aligned}$$

二阶矩与方差发散；均值仍然有限。密度双对数斜率为 $-2.5$，CCDF 斜率为 $-1.5$。校正经验表述： 讲义的 $\alpha\approx1.5$ 是财富重尾的示例性描述，不能断言所有国家、时期、全部财富区间都精确服从它，也不能从有限样本证明真实财富的总体方差必为无穷。

为什么考虑基于个体的模型（agent-based model）？

财富受许多个人因素影响，但课程转向研究个体之间的交换规则。选中两名个体 $i,j$ 后，

$$x_i'=x_i-\Delta x,\qquad x_j'=x_j+\Delta x, \qquad x_i'+x_j'=x_i+x_j.$$

这种封闭模型守恒总财富，类似分子碰撞时交换能量。实际模拟还要约束交易规则，避免无意产生不允许的负财富。仅凭守恒不能推出幂律；交换与储蓄规则决定最终形状。

讲义用下面的对应关系解释财富交换模型与气体动理论的类比：

气体动理论	财富交换模型
粒子	个体
动能 $K$	财富 $x$
碰撞	交易
几何维数 $D$	有效参数 $D_\lambda$

两者的温度尺度对应为

$$k_BT=\frac{2\langle K\rangle}{D} \quad\leftrightarrow\quad T_\lambda=\frac{2\langle x\rangle}{D_\lambda}.$$

无量纲变量分别为 $K/(k_BT)$ 与 $x/T_\lambda$。讲义原表中的 $\gamma_{D/2}$ 表示 Gamma 分布的形状函数（不是本章稳定分布的参数 $\gamma$）。其作用是说明群体统计可由简单交换规则产生；讲义同时展示了主体近 Gibbs 型、上尾近 Pareto 型的经验形状。

地震与余震：先确定变量，再判断幂律

讲义第 13 页，含必要校正。 该页将震级、振幅、累计计数和概率密度混用，直接影响指数与均值结论。下面保留其“尺度无关现象”的教学目的，并给出可计算的正确形式。

Gutenberg–Richter 定律

对固定区域、时窗和完整性阈值 $m_0$，累计地震数满足

$$\log_{10}N(M\ge m)=a-bm,\qquad b\approx1\text{ 是讲义示例值}.$$

归一化到 $M\ge m_0$ 的事件集，

$$\Pr(M\ge m\mid M\ge m_0)=10^{-b(m-m_0)},\qquad m\ge m_0.$$

所以震级的密度是

$$\begin{aligned} f_M(m)&=b\ln10\,10^{-b(m-m_0)},\\ \mathbb E[M]&=m_0+\frac1{b\ln10}<\infty. \end{aligned}$$

震级 $M$ 的尾是指数尾，并非幂律尾。讲义“earthquake magnitude has infinite mean”不由此定律成立。

若采用讲义简化关系 $M-m_0=\log_{10}(A/A_0)$，则对振幅 $A$，

$$\begin{aligned} \Pr(A>a)&=\left(\frac{A_0}{a}\right)^b,\\ f_A(a)&=bA_0^b a^{-b-1},\qquad a\ge A_0. \end{aligned}$$

也可用 $f_A(a)=f_M(m(a))|dm/da|$，其中 $|dm/da|=1/(a\ln10)$。缺少这个 Jacobian 会使幂律指数差一。 按本章记号，振幅的尾指数是 $\alpha=b$，不是讲义的 $b-1$。理想无截断且 $b=1$ 时，发散的是振幅的均值；震级均值仍有限。真实震级定义还包含仪器、距离等修正，不应把 $M=\log_{10}A$ 当成完整测量公式。

上述累计计数的含义可核对 USGS 的 Gutenberg–Richter 说明；这里的概率变换与均值结论由上式直接推导。

核验来源：USGS：加利福尼亚地震发生率计算；累计计数的明确定义见USGS 第 81-736 号公开报告，报告第 14 页。

Omori 余震定律

讲义写 $N_t\sim t^{-p}$、$p\approx1$；应将它理解成单位时间的事件发生率。常用正则化形式为

$$r(t)=\frac{K}{(t+c)^p},\qquad K>0,\ c>0,$$

其中 $c$ 避免 $t=0$ 的奇点。当 $p=1$，时间区间 $[t_1,t_2]$ 内的期望计数为

$$\mathbb E[N(t_1,t_2)]=\int_{t_1}^{t_2}r(t)\,dt =K\ln\!\frac{t_2+c}{t_1+c}.$$

率不等于归一化概率密度。 不能仅从 $r(t)\propto1/t$ 宣称“平均余震时间无穷，因此余震永远不停止”。若另外定义 $f_T(t)\propto t^{-p}$ 于 $t\ge t_{\min}>0$，必须先有 $p>1$ 才可归一化；其均值仅当 $p>2$ 时有限。$p=1$ 的无限区间模型连归一化都不成立。这也是指数边界需要仔细处理的实例。

核验来源：USGS：余震预报的科学背景，明确将该式定义为余震发生率。

无特征尺度带来的后果与本章自测

St Petersburg 悖论，讲义第 15 页。 采用讲义表格的清晰编号：公平硬币第一次正面出现在第 $n$ 次，$n=1,2,\ldots$，奖金额 $W=2^{n-1}$。于是

$$\begin{aligned} \Pr(N=n)&=2^{-n},\\ \mathbb E[W]&=\sum_{n=1}^{\infty}2^{n-1}2^{-n} =\sum_{n=1}^{\infty}\frac12=\infty. \end{aligned}$$

但 $\Pr(W<\infty)=1$：每次结果几乎必然有限，与期望无穷并不矛盾。 例如 $\Pr(W\le2)=3/4$。仅以风险中性的期望收支平衡定价，得不到有限公平入场费；财富上限、最高赔付、风险偏好或效用函数会改变定价问题。校正： 讲义上方“$n$ 次反面后第一次正面”的文字与其表格错位；按本段 $N$ 的定义，概率、奖金和期望彼此一致。

极端事件不自动是应删除的离群点，讲义第 16–18 页。 重尾分布赋予大事件比高斯模型高得多的概率。若极大值与小事件属于同一机制，仅因数值大就剔除它，会系统性低估尾部风险。讲义以生物灭绝和 1987 年 Black Monday 为讨论例子，并引向期权价格对分布尾部、波动的敏感性。这里应掌握的方法论是：先检查数据质量与生成机制，再判断是否异常；“罕见”不等于“错误数据”。 单幅直方图或单次崩盘不能严格证明整个尾部精确遵循幂律。

金融物理的提示性内容，讲义第 9、17 页。 有效市场假说、布朗运动、收益是否正态、方差是否有限、短记忆与长记忆是彼此不同的问题。有效市场假说本身不推出收益正态。GARCH 是描述随时间变化的条件方差的模型族，可用来表达“大波动之后仍容易出现大波动”的波动聚集。Volatility smile 指由同一基础定价模型反推的隐含波动率随执行价格变化。讲义只将这两者作为提示或进一步阅读，并未给出需要推导的 GARCH 或期权定价公式。

跨尺度结构与建模动机，讲义第 14、18 页。 第 14 页的宇宙超结构是尺度问题的展示例子，没有给出可用于推导的分布公式。第 18 页将地震数据与耦合摆的雪崩分布比较：只保留局部相互作用规则，也可能再现群体层次的幂律。要点是用简单机制解释集体现象和统计规律；这不等于声称幂律足以唯一识别微观机制，也不要求逐个预测每次灾变。

本章自测

检查自己能否独立完成以下题目。

1. $f(x)=Cx^{-5/2}$，$x\ge1$。求 $C$、CCDF、均值与方差是否有限。

   答案：$C=3/2$，$\Pr(X>x)=x^{-3/2}$，$\mathbb E[X]=3$，方差发散。

2. 数据 CCDF 的双对数斜率为 $-0.8$。密度尾指数是多少？正变量的均值存在吗？

   答案：$\alpha=0.8$，$\tau=1.8$；理想无限尾模型下均值为 $+\infty$。

3. $X_i$ 是独立标准 Cauchy，$n=100$。$S_n$ 与 $\bar X_n$ 的尺度是多少？

   答案： 分别为 $100$ 与 $1$；不能套用 $\sigma/\sqrt n$。

4. 对称稳定分布的指数为 $\alpha=1.5$，样本量从 $n$ 增到 $8n$，平均值的典型宽度怎样变化？

   答案： 宽度乘 $8^{1/1.5-1}=8^{-1/3}=1/2$；并不存在可这样缩放的有限标准差。

5. $N(M\ge m)\propto10^{-m}$ 是否说明震级密度为 $M^{-1}$？

   答案： 否。$M$ 是指数分布的平移；若 $M=\log_{10}A+\text{常数}$，则振幅 CCDF 为 $A^{-1}$，密度为 $A^{-2}$。

考试答题顺序： 先写随机变量和取值范围；辨认 PDF、CDF、CCDF 或事件率；统一指数；检查矩和独立性；再决定是否能用 CLT、怎样归一化。只要这五步写清，最常见的“指数差一、无穷矩、缩放漏因子”错误都能被及时发现。

无标度网络与优先连接：从机制推导分布

对应讲义：《3 Scale free networks》PDF 第 1–16 页。先掌握本节的度、度分布和 BA 机制；图的表示与计算在下一节展开。以下用 $n$ 表示节点数，$M$ 表示总边数，$m$ 专指 BA 模型每个新节点带来的边数。

网络描述什么，无标度又指什么？

网络把系统抽象为节点（node/vertex）和边（edge/link）。模型是否合理首先取决于两者的定义。例如互联网以计算机或路由器为节点、通信连接为边；WWW 以网页为节点、超链接为有向边；引用网络以论文为节点、引用为有向边。电网可用发电站/变电站与输电线，友谊网络可用人与友谊，代谢网络可用代谢物与反应，神经网络可用神经元与突触，食物网可用物种与捕食关系。方向、权重及节点粒度由问题决定。（讲义 3，第 2 页）

度与度分布

无向简单图中，节点 $i$ 的度 $k_i$ 是其邻居数。随机等概率选一个节点，其度为 $k$ 的概率为

$$p(k)=\frac{n_k}{n},\qquad \sum_k p(k)=1,\qquad \langle k\rangle=\sum_k k p(k)=\frac{2M}{n},$$

其中 $n_k$ 为度恰好等于 $k$ 的节点数。有向图须分开统计入度和出度分布。无标度网络的核心是度分布尾部近似幂律，并非图形看起来杂乱：

$$p(k)\sim Ck^{-\gamma},\qquad S(k)=\Pr(K\geq k)\sim C'k^{-(\gamma-1)},\qquad \alpha=\gamma-1.$$

离散度的 $p(k)$ 是概率质量函数；连续近似时才称概率密度。$S(k)$ 是互补累积分布（CCDF），而普通 CDF 是 $F(k)=\Pr(K\leq k)$。不要把递减的幂律尾部写成普通 CDF。（讲义 3，第 3 页）

指数的含义

幂律尾部使高度节点比指数/Poisson 尾部中常见，这类高度节点叫 hub。一般幂律无标度性质不要求 $\gamma<3$；课件强调 $1<\gamma<3$，是因为在无上界理想分布中二阶矩发散。条件为 $\langle K^r\rangle<\infty$ 当且仅当 $\gamma>r+1$；等号处通常对数发散。因此 $2<\gamma<3$ 时均值有限、方差无限；$\gamma=3$ 是二阶矩的边界。真实有限网络有最大度，有限样本矩总是有限。

课件第 4 页问题：哪个网络特殊？ 表中性接触网络的 $\gamma\approx3.4$ 明显超过课件强调的区间，因此其理想纯幂律二阶矩有限；引用网络 $\gamma\approx3$ 则在边界上。超出这个区间不等于不是幂律。表格是讲义引用的历史实例，不能据此认定所有现实网络都严格无标度。

第 2 页数图练习

图中有 8 个节点、10 条边，其中 1 个是孤立点。计数时交叉线没有实心节点就不算新节点，文字说明箭头也不算边。将各节点的度相加应得 $20=2\times10$，这是检查边数的办法。

BA 模型：增长与优先连接

从含 $n_0$ 个节点、$M_0$ 条边的种子网络开始，每一步加入一个节点，并把它连接到 $m$ 个已有节点：

$$n(t)=n_0+t,\quad M(t)=M_0+mt,\quad \Pi_i=\frac{k_i}{\sum_j k_j},\quad \sum_i\Pi_i=1.$$

增长（growth）提供不断进入的新节点；优先连接（preferential attachment）使度越高的旧节点越容易得到新边。种子网络应使分母非零，并提供足够的已有节点；通常要求 $m\leq n_0$。课件中 $m_0$ 有时指初始边数，引用文献中又指初始节点数，考试推导时最好像这里分成 $M_0,n_0$。（讲义 3，第 5–6 页）

连续近似：完整推导指数 3

要证明的链条： 优先连接 $\Rightarrow$ 单节点度的增长 $\Rightarrow$ 出生时间与度的对应 $\Rightarrow$ 全网度分布。（讲义 3，第 7–8 页）

第一步：写期望增长率

每步有 $m$ 条新边可以连到旧节点，所以大网络的平均场近似为

$$\frac{\mathrm d k_i}{\mathrm dt}=m\Pi_i =\frac{m k_i}{\sum_jk_j},\qquad \sum_j k_j=2M(t)=2(M_0+mt)\simeq 2mt.$$

因此

$$\frac{\mathrm d k_i}{\mathrm dt}=\frac{k_i}{2t},\qquad k_i(t_i)=m,$$

其中 $t_i$ 是节点 $i$ 的加入时间。分母的 $2$ 来自一条无向边给总度贡献 $2$；前面的 $m$ 来自每步添加 $m$ 条边，两者不可漏掉。

第二步：分离变量并使用初值

$$\int_m^{k_i(t)}\frac{\mathrm dk}{k} =\frac12\int_{t_i}^{t}\frac{\mathrm d\tau}{\tau} \quad\Longrightarrow\quad \ln\frac{k_i(t)}m=\frac12\ln\frac{t}{t_i}.$$

得到

$$\boxed{k_i(t)=m\left(\frac{t}{t_i}\right)^{\beta},\qquad \beta=\frac12.}$$

同一观察时刻，越早出生的节点预期度越大；同一节点的预期度随时间按 $t^{1/2}$ 增加。真实随机实现会有波动，不能把“较老的节点平均更大”理解成任何两个节点都必然严格按年龄排序。若保留种子边数，同一连续方程给出 $k_i(t)=m\sqrt{(M_0+mt)/(M_0+mt_i)}$；大时间时回到上式。

第三步：由出生时间得到 CDF/CCDF

在较大时刻 $T$ 等概率抽取一个节点。每步出生一个节点，忽略占比趋于零的种子节点后，$t_i$ 在 $(0,T]$ 上近似均匀，密度 $f_{t_i}(s)=1/T$。对 $k\geq m$，

$$\begin{aligned} F(k)&=\Pr\!\left[m\left(\frac{T}{t_i}\right)^\beta<k\right] =\Pr\!\left[t_i>T\left(\frac{m}{k}\right)^{1/\beta}\right]\\ &=1-\left(\frac{m}{k}\right)^{1/\beta}, \qquad S(k)=\left(\frac{m}{k}\right)^{1/\beta}. \end{aligned}$$

不等号反向是因为 $k_i$ 随出生时间 $t_i$ 递减。这里均匀分布的是出生时间，不是度。

第四步：求导

$$p_{\rm cont}(k)=\frac{\mathrm dF}{\mathrm dk} =\frac1\beta m^{1/\beta} k^{-(1+1/\beta)}.$$

代入 $\beta=1/2$：

$$\boxed{p_{\rm cont}(k)=\frac{2m^2}{k^3},\quad S_{\rm cont}(k)=\frac{m^2}{k^2},\quad \gamma=1+\frac1\beta=3,\quad\alpha=2.}$$

这里的尾参数 $\alpha=2$ 不表示 BA 度分布是高斯稳定分布；BA 的二阶矩仍处于幂律的对数发散边界。指数不依赖 $m$；$m$ 改变最低度、平均度和分布前因子。连续近似满足归一化条件 $\int_m^\infty p_{\rm cont}(k)\,\mathrm dk=1$，其平均度为 $2m$。不要把这条连续密度公式当成小整数度处的精确离散概率。

主方程：离散度分布与出生边界条件

连续近似容易看出指数；主方程进一步给出离散度概率的前因子。（讲义 3，第 9–11 页）设 $q(k,t_i,t)$ 为出生于 $t_i$ 的节点在 $t$ 时刻度为 $k$ 的概率。在课件的大时间近似中，下一步该节点以 $k/(2t)$ 的概率增加一度，因此

$$q(k,t_i,t+1)=\frac{k-1}{2t}q(k-1,t_i,t) +\left(1-\frac{k}{2t}\right)q(k,t_i,t).$$

第一项是“原来 $k-1$，得到一条边”的流入；第二项是“原来 $k$，没有得到边”的保留。对于 $m>1$，这是标准的大网络主方程近似，不能把有限时间无放回选择 $m$ 个不同目标的过程简单说成精确独立 Bernoulli 试验。

用节点数写，出生项最不容易漏

设 $N_k(t)$ 是度为 $k$ 的节点数的期望，则

$$N_k(t+1)-N_k(t) =\frac{(k-1)N_{k-1}(t)-kN_k(t)}{2t}+\delta_{km},$$

其中 $\delta_{km}=1$ 当 $k=m$，否则为 $0$。最后一项表示每步新出生一个度为 $m$ 的节点。假设稳态比例存在，即 $N_k(t)\simeq t p(k)$，则左边是 $p(k)$，而不是 $0$：网络总节点数仍在增长。

$$p(k)=\frac{k-1}{2}p(k-1)-\frac{k}{2}p(k)+\delta_{km}.$$

整理得统一方程

$$(k+2)p(k)=(k-1)p(k-1)+2\delta_{km}.$$

边界 $k=m$ 与递推 $k>m$

新加入节点的最低度为 $m$，故稳态 $p(m-1)=0$（有限个初始节点不影响极限比例）：

$$\boxed{p(m)=\frac{2}{m+2}},\qquad \boxed{p(k)=\frac{k-1}{k+2}\,p(k-1)\quad(k\geq m+1)}.$$

逐项相乘并约去公共因子：

$$\begin{aligned} p(k)&=\frac{2}{m+2}\prod_{r=m+1}^{k}\frac{r-1}{r+2}\\ &=\frac{2}{m+2}\frac{m(m+1)\cdots(k-1)}{(m+3)(m+4)\cdots(k+2)}\\ &=\boxed{\frac{2m(m+1)}{k(k+1)(k+2)}} \sim 2m(m+1)k^{-3}. \end{aligned}$$

这是标准 BA 模型的渐近离散度分布；尾指数同样是 $3$。课件第 9 页把 $k(k+1)(k+2)$ 换成 $k^3$ 处应理解为 $k\gg1$ 时的渐近近似，不是所有 $k$ 上的恒等式。

快速验算与离散尾概率

利用

$$p(k)=m(m+1)\left[\frac1{k(k+1)}-\frac1{(k+1)(k+2)}\right],$$

相邻项消去得 $\sum_{k=m}^\infty p(k)=1$，并得到整数 $K\geq m$ 时

$$\boxed{\Pr(k_i\geq K)=\frac{m(m+1)}{K(K+1)}},\qquad \sum_{k=m}^{\infty}kp(k)=2m.$$

连续近似的系数 $2m^2$ 和离散结果的 $2m(m+1)$ 不相同，来源是近似层次不同；两者的指数、平均度及大度行为相容。

机制验证与 Erdős–Rényi 随机网络

为何同时需要两个机制？（讲义 3，第 12 页）

在课件所比较的模型中，去掉优先连接而只保留增长，会得到快速衰减的度分布；去掉增长、固定节点集合，也不能保持 BA 的持续增长幂律状态。这说明两项机制共同产生 BA 模型的结果，不能反推“世界上所有幂律都只能来自 BA”。静态图也可以直接按指定幂律度分布构造。

一个直观计算是：若新边在旧节点中均匀选择，则 $\mathrm dk_i/\mathrm dt\simeq m/t$，得到 $k_i(t)\simeq m+m\ln(t/t_i)$。结合均匀出生时间，尾概率约为 $\Pr(K\geq k)\simeq\exp[-(k-m)/m]$，说明增长本身不自动产生幂律。课件的经验图以引用、互联网域、神经科学合作、电影演员网络为例，展示连接倾向随已有度上升，对优先连接机制提供经验支持。

ER 模型定义。（讲义 3，第 14–16 页）

在 $G(n,p)$ 中，固定 $n$ 个节点，每一对不同节点独立以概率 $p$ 连一条无向边；无自环、无重边。共有 $\binom n2$ 个候选边，故

$$M\sim\operatorname{Bin}\!\left(\binom n2,p\right),\qquad \mathrm E[M]=p\frac{n(n-1)}2.$$

课件中 $pn(n-1)/2$ 是期望边数，实际边数是随机变量。 单个节点有 $n-1$ 个可能邻居，因此

$$K\sim\operatorname{Bin}(n-1,p),\qquad \Pr(K=k)=\binom{n-1}{k}p^k(1-p)^{n-1-k},$$

$$c=\mathrm E[K]=(n-1)p,\qquad \operatorname{Var}(K)=(n-1)p(1-p).$$

这里 $c$ 是理论平均度参数；一次实现的实际平均度仍为 $2M/n$。

稀疏大网络的 Poisson 极限

令 $n\to\infty$，同时取 $p=c/(n-1)\to0$、$c$ 固定。对固定 $k$，

$$\binom{n-1}{k}\simeq\frac{(n-1)^k}{k!},\qquad \left(1-\frac{c}{n-1}\right)^{n-1-k}\longrightarrow e^{-c}.$$

代回二项式概率得

$$\boxed{\Pr(K=k)\longrightarrow e^{-c}\frac{c^k}{k!}},\qquad \mathrm E[K]=\operatorname{Var}(K)=c\quad\text{（Poisson 极限）}.$$

特别地，孤立节点概率为 $p(0)=e^{-c}$，预期孤立节点数约为 $ne^{-c}$。这个稀有事件极限不是中央极限定理。若 $c$ 还很大，Poisson 才能再近似为 $\mathcal N(c,c)$；一般二项分布在 $(n-1)p$ 和 $(n-1)(1-p)$ 都足够大时也可用正态近似。不能在“固定 $c$ 的稀疏极限”中直接宣称度分布必然正态。

ER 与 BA 的核心对比

ER 的节点集合固定、所有候选边独立且同概率，度集中在 $c$ 附近、尾部快衰减；BA 节点持续进入、连边概率依赖已有度，$\langle k\rangle\to2m$、$p(k)\sim k^{-3}$，高度节点更突出。ER 也有度高于平均的节点，“无 hub”是相对均匀的示意描述，不是最大度绝不偏离均值的定理。讲义第 13 页把鲁棒性等后果留待后续课程，本次核心是理解度的异质性及其生成机制。

无标度网络常见题：计算、推导与检查

例 1：单节点增长

BA 模型 $m=2$，节点在 $t_i=25$ 时加入，求 $T=400$ 时的预期度。

$$k_i(400)\simeq2\sqrt{400/25}=8.$$

若问达到度 $20$ 所需时间，则 $20=2\sqrt{T/25}$，所以 $T=2500$。这是平均场的预期时间尺度，个体节点真实达到该度的时刻会波动。

例 2：离散概率不能直接拿连续密度代替

$m=2$ 时，由边界和递推式

$$p(2)=\frac12,\qquad p(3)=\frac25p(2)=\frac15, \qquad p(4)=\frac36p(3)=\frac1{10}.$$

若有约 $10^4$ 个节点，稳态预期度恰为 $3$ 的节点数约 $2000$。度至少为 $10$ 的比例为

$$\Pr(K\geq10)=\frac{2\cdot3}{10\cdot11}=\frac3{55}\simeq0.0545.$$

因此节点数约为 $545$。连续近似给 $m^2/10^2=0.04$，它强调尺度规律，不能要求在较小整数阈值处等于离散结果。

例 3：ER 网络参数

取 $n=1000,p=0.004$：

$$c=999\times0.004=3.996,\qquad \mathrm E[M]=\frac{1000\times3.996}{2}=1998.$$

因为 $p$ 很小，可将单节点度近似为 $\operatorname{Poisson}(3.996)$。例如

$$\Pr(K=0)\simeq e^{-3.996}\simeq0.0184, \qquad \mathrm E[n_{\rm isolated}]\simeq18.4.$$

这里 $n_{\rm isolated}$ 指孤立节点数。$18.4$ 是期望数，一次实现中实际观察到的节点数必须为非负整数。

例 4：从图上读指数

若双对数坐标中度概率 $p(k)$ 的直线斜率为 $-2.7$，则 $\gamma=2.7$，CCDF 斜率应约为 $-1.7$。若给的是 CCDF 斜率 $-2$，则 $\gamma=3$，与标准 BA 指数相符；只看这个指数并不能证明机制一定是 BA。

推导题的最短完整答案

连续推导至少写出：$\Pi_i=k_i/\sum_j k_j$，$\sum_jk_j\simeq2mt$，$\dot k_i=k_i/(2t)$，$k_i(t_i)=m$，$k_i(t)=m(t/t_i)^{1/2}$，出生时间均匀，$F(k)=1-m^2/k^2$，$p(k)=2m^2k^{-3}$。主方程推导至少写出：流入、流出、$\delta_{km}$ 出生项，稳态 $N_k(t)\simeq t p(k)$，边界 $p(m)$，递推与乘积约分。

易错点清单

• $\Pi_i$ 是一条新边选中节点的倾向；$m\Pi_i$ 才给每步期望度增量的近似。

• “稳态度分布”表示比例不再变化，不表示节点数或个体度停止增长。

• $\gamma$ 是度概率的指数，$\alpha=\gamma-1$ 是尾概率指数；BA 对应 $\gamma=3,\alpha=2$。

• 连续 $2m^2/k^3$ 与离散 $2m(m+1)/[k(k+1)(k+2)]$ 应标明各自适用层次。

• ER 的 $G(n,p)$ 固定的是连边概率；固定边数的 $G(n,M)$ 是另一种模型，不能混用独立边假设。

网络基础：表示、图类型、连通性与矩阵计算

对应讲义：《4 Network basics》PDF 第 1–14 页。默认讨论有限、无自环、无重边的图；遇到有向或有权网络会明确说明。讲义第 14 页的 NetworkX 实作见本复习资料的编程部分。

基本语言与两种图表示

图写为 $G=(V,E)$，$V$ 是节点集，$E$ 是边集。无向边 $\{i,j\}$ 表示对称关系；有向边 $(i,j)$ 表示 $i\to j$。简单图（simple graph）严格指没有自环和重边，并不等于“结构规则”。复杂网络常用于具有异质度、复杂连接模式的系统，“复杂”本身不是一条唯一的图论判别条件。（讲义 4，第 2–3 页）

邻接矩阵与邻接表

先声明节点顺序，然后定义邻接矩阵。本资料统一采用行是起点、列是终点的约定：

$$A_{ij}=\begin{cases}1,&i\to j\text{ 有边（无向时是 }i\text{ 与 }j\text{ 相连）},\\ 0,&\text{否则。}\end{cases}$$

邻接表逐节点列出邻居。有向图中通常列出出邻居，并在需要时另存入邻居。无向简单图满足 $A=A^{\mathsf T}$、$A_{ii}=0$；边在矩阵中出现两次，在每个端点的邻接表中各出现一次。

讲义第 3 页的四节点例子，其边集为 $\{12,13,23,34\}$，按 $1,2,3,4$ 排序：

$$A=\begin{bmatrix}0&1&1&0\\1&0&1&0\\1&1&0&1\\0&0&1&0\end{bmatrix}, \qquad(k_1,k_2,k_3,k_4)=(2,2,3,1).$$

邻接表是 $1:\{2,3\}$，$2:\{1,3\}$，$3:\{1,2,4\}$，$4:\{3\}$。按行求和即可得到度；总和 $8$，因此 $M=4$。

路径、环、子图

• 游走（walk）：连续经过相邻节点的序列，可以重复节点和边。长度等于经过的边数。

• 路径（path）：通常采用节点不重复的约定；若题目使用更宽的口语定义，应先说明约定。任意相邻两项之间必须有边，有向图还必须方向正确。

• 环（cycle）：从某节点出发回到它自身，除起终点外不重复节点的闭合路径；无向简单图中的环至少含 $3$ 条边。

• 子图（subgraph）：取部分节点和部分允许的边。诱导子图（induced subgraph）选定节点后，保留它们之间原图的全部边。

两节点之间存在路径就称它们相连。连通图的任意两节点间都有路径；连通分量是极大连通子图，不能再加入其他节点仍保持连通。孤立节点自身也是一个分量。最大连通分量指节点数最多的分量；“极大”与“最大”含义不同。

多个分量与分块矩阵。（讲义 4，第 5 页）

把同一个分量的节点排在一起，重排行和列后可写成

$$A'=PAP^{\mathsf T}=\begin{bmatrix}A_1&0&\cdots\\0&A_2&\cdots\\\vdots&\vdots&\ddots\end{bmatrix}.$$

$P$ 只表示节点重新排序；块间没有边，所以非对角块为零。该结论适用于无向分量，亦适用于有向图的不同弱分量。不同强分量之间可能存在单向边，因此不能一概声称按强分量排序就变成块对角矩阵。

讲义第 4 页课堂练习：完整答案

按图中标号，边集为

$$E=\{12,14,15,23,24,34,35,36,46\},\qquad n=6,\quad M=9.$$

这里 $12$ 表示无向边 $\{1,2\}$，不是数字十二。图中 $1$–$4$ 与 $2$–$3$ 的交叉处没有节点。

1. 邻接矩阵与邻接表

按 $1,2,3,4,5,6$ 的顺序：

$$A=\begin{bmatrix} 0&1&0&1&1&0\\ 1&0&1&1&0&0\\ 0&1&0&1&1&1\\ 1&1&1&0&0&1\\ 1&0&1&0&0&0\\ 0&0&1&1&0&0 \end{bmatrix}.$$

$$\begin{array}{lll} 1:\{2,4,5\},&2:\{1,3,4\},&3:\{2,4,5,6\},\\ 4:\{1,2,3,6\},&5:\{1,3\},&6:\{3,4\}. \end{array}$$

2. 节点度

各行求和得 $(k_1,k_2,k_3,k_4,k_5,k_6)=(3,3,4,4,2,2)$。检查 $\sum_i k_i=18=2M$；平均度 $3$，密度为 $9/\binom62=0.6$。

3. 路径或环的判断

• $6$–$3$–$2$–$4$–$5$：都不是，因为 $4$–$5$ 不是边。

• $1$–$4$–$6$–$3$–$2$：路径，相邻节点都有边且没有重复节点，长度为 $4$。

• $5$–$1$–$2$–$3$–$5$：环，四条边均存在，除起终点 $5$ 外没有重复，环长为 $4$。

4. 所有连通的三节点子图

如果按三节点诱导子图理解，检查 $\binom63=20$ 个节点集合：三节点图只要有至少两条边就连通。答案共 14 个，其中三角形为

$$\{1,2,4\},\quad\{2,3,4\},\quad\{3,4,6\};$$

另有 11 个两边路径，顶点集为

$$\begin{aligned} &\{1,2,3\},\ \{1,2,5\},\ \{1,3,4\},\ \{1,3,5\},\ \{1,4,5\},\ \{1,4,6\}, \\ &\{2,3,5\},\ \{2,3,6\},\ \{2,4,6\},\ \{3,4,5\},\ \{3,5,6\}. \end{aligned}$$

若题目允许在同一顶点集合上删去原有边，每个三角形还可删任一条边得到 3 个连通路径，因此共有 $11+3(1+3)=\mathbf{23}$ 个带标号连通子图。若只问不同形状（忽略标号），则只有路径 $P_3$ 和三角形 $K_3$ 两类。考试先说明采用哪一种理解。

5. 同时删除节点 3 和 4

删除节点时也删除所有关联边。剩余节点为 $\{1,2,5,6\}$，剩余边为 $\{12,15\}$，所以连通分量是 $\{1,2,5\}$ 与 $\{6\}$。按顺序 $1,2,5,6$ 写矩阵，得到左上 $3\times3$ 连通块和右下单个零块。

网络类型、判别与现实例子

以下同时回答讲义第 6–7 页的定义与举例题。一个网络可以同时属于多类，例如偶数长度的环既是正则图，又是二部图和平面图。

完全图（complete graph）

任意两个不同节点之间都有边，记为 $K_n$。每个节点的度为 $n-1$，总边数 $M=n(n-1)/2$。例：假设小组内每两名成员都直接互相认识，得到完全友谊图。“所有节点可经路径到达”仅表示连通，不等于任意两点直接相连。

正则图（regular graph）

每个节点度都等于相同的 $k$，称 $k$-正则图。握手定理给出

$$\boxed{M=\frac{nk}{2}}.$$

因此 $nk$ 必须是偶数；简单图还要求 $0\leq k\leq n-1$。例：没有断点的环形通信网络，每个节点连接左右邻居，是 $2$-正则图；$n=10,k=4$ 时 $M=20$。开放边界方格网的边界度通常不同，不能直接称为正则图。

二部图（bipartite graph）

节点可分成不相交的两组 $U,V$，每条边都跨组；组内没有边，并不要求所有跨组节点都相连。例：用户–电影、学生–课程、演员–电影。判别时尝试用两种颜色给节点着色，使每条边两端不同色；存在奇数长度环就不可能是二部图。特别地，三角形不是二部图；树都是二部图。

树（tree）与森林（forest）

树是连通且无环的无向图。讲义将树简写成“无环”省略了连通条件；无环但有多个分量的图叫森林。树有

$$\boxed{M=n-1},\qquad \text{任意两点间存在唯一一条路径。}$$

森林若有 $C$ 个分量则 $M=n-C$。例：不含交叉汇报关系的组织层级、文件目录树；$n=10$ 的树有 $9$ 条边。仅知 $M=n-1$ 还不足以判定是树，必须再保证连通或无环等条件；一个三角形加孤立点就有 $n=4,M=3$，但不是树。

平面图（planar graph）

可以在平面上重新绘制，使边只在共同端点处相遇，不发生边的交叉。例：没有立交跨越、将路口作为节点的理想化道路网络；所有树都可画成平面图。当前画法有交叉，不代表无法重新画成无交叉；因此“看图发现交叉”不是非平面性的证明。

多层网络（multilayer network）

由表示不同节点/关系类型的多个层及层间连接构成。例：电网层与通信网层通过供电依赖、控制依赖相连；各层节点集合可以不同。描述时应交代层内边和层间边分别代表什么。

多重网络（multiplex network）

多层网络的一个特例：各层表示同一批对象，不同层表示不同关系。例：同一群人的朋友关系层、同事关系层、亲属关系层；同一组城市的航空层和铁路层也是一种构造。各层是同一对象的不同表示，multiplex 不等于允许同一节点对之间存在重边的 multigraph。

考试举例的表达模板

写清“节点是什么，边是什么，为什么满足该定义”。例如：“学生–课程网络中，两类节点分别是学生与课程；选课关系仅连接学生与课程，因此是二部图。”仅写“社交网络”不能说明它是否完全、正则或二部。

二部网络的矩阵与投影：讲义第 8 页答案

二部图可用矩形关联矩阵 $B$ 表示：行是第一组对象，列是第二组对象，$B_{u a}=1$ 表示两者关联。按 $U$ 后 $V$ 排序，全体节点的方形邻接矩阵为

$$\boxed{A_{\rm bip}=\begin{bmatrix}0&B\\B^{\mathsf T}&0\end{bmatrix}}.$$

$B$ 是二部图的矩形表示，不要与包含全部节点的方形邻接矩阵混称而不说明。

读出原图

讲义的行节点为 $A,B,C,D$，列节点为 $1,2,3,4,5,6,7$。图中关联为

$$A:\{1,2,3\},\quad B:\{2,3,4,5\},\quad C:\{4,6\},\quad D:\{5,6,7\},$$

所以（矩阵名 $B$ 与节点名 $B$ 要分清）

$$B=\begin{bmatrix} 1&1&1&0&0&0&0\\ 0&1&1&1&1&0&0\\ 0&0&0&1&0&1&0\\ 0&0&0&0&1&1&1 \end{bmatrix}.$$

原二部图有 $11$ 个节点、$12$ 条边；完整 $11\times11$ 邻接矩阵就是将这个 $B$ 代入上述块矩阵。

只保留 $A,B,C,D$ 的投影

两个行节点只要有共同列邻居，就在行投影中相连。矩阵乘法给共同邻居的个数：

$$BB^{\mathsf T}=\begin{bmatrix}3&2&0&0\\2&4&1&1\\0&1&2&1\\0&1&1&3\end{bmatrix}.$$

对角元是各行节点在原图的度，不能直接当作投影自环；去掉对角，再把所有正数变成 $1$，得到讲义上方无权投影图：

$$A_U=\begin{bmatrix}0&1&0&0\\1&0&1&1\\0&1&0&1\\0&1&1&0\end{bmatrix}, \qquad E_U=\{AB,BC,BD,CD\}.$$

如果保留权重，则 $A$ 与 $B$ 的连接权重为 $2$，因为共同关联 $2,3$；其他已有边权重为 $1$。

只保留 $1,\ldots,7$ 的投影

列投影用 $B^{\mathsf T}B$，同样去对角并二值化：

$$A_V=\begin{bmatrix} 0&1&1&0&0&0&0\\ 1&0&1&1&1&0&0\\ 1&1&0&1&1&0&0\\ 0&1&1&0&1&1&0\\ 0&1&1&1&0&1&1\\ 0&0&0&1&1&0&1\\ 0&0&0&0&1&1&0 \end{bmatrix}.$$

例如节点 $2,3$ 共同关联行节点 $A,B$，所以它们的加权投影边权重为 $2$；其余投影边权为 $1$。用户–电影推荐可利用共同看过的电影表示用户相似性，也可利用共同用户表示电影相似性；评分矩阵还能保留数值权重。投影会丢失具体由哪个组产生关联的信息，并可能把一个群组变成完全子图。

有向、有权网络与有向连通分量

对应讲义第 9–10 页。方向与权重是两个独立属性：网络可以无向无权、无向有权、有向无权或有向有权。

有向邻接矩阵

仍用 $A_{ij}=1$ 表示 $i\to j$，通常 $A\ne A^{\mathsf T}$。有向图也可能恰好每条边都成双出现而使矩阵对称，因此不能说“有向矩阵必然不对称”。无自环时

$$\boxed{k_i^{\rm out}=\sum_jA_{ij},\qquad k_i^{\rm in}=\sum_jA_{ji}},$$

$$\sum_i k_i^{\rm out}=\sum_i k_i^{\rm in}=M,\quad \langle k^{\rm out}\rangle=\langle k^{\rm in}\rangle=\frac Mn.$$

节点总度定义为 $k_i^{\rm in}+k_i^{\rm out}$，故全网总度仍为 $2M$。若题目采用转置的邻接约定，行列求和规则相应对换。

有权邻接矩阵

用 $W_{ij}=w_{ij}$ 记录边的强度、距离、容量、流量等；没有边时通常记 $0$，但若零权重本身有效，应另存连接关系。无向权重满足 $W=W^{\mathsf T}$。无权度数的是边数，权重之和称为强度（strength）：

$$s_i^{\rm out}=\sum_jW_{ij},\qquad s_i^{\rm in}=\sum_jW_{ji}.$$

例如 $1\to2$ 权重 $4$、$1\to3$ 权重 $2$，则 $k_1^{\rm out}=2$ 而 $s_1^{\rm out}=6$。若权重表示路程，求最短路时相加有意义；若权重表示相似度或联系强度，数值越大通常不表示路越长，必须先说明怎样解释权重。

强连通与弱连通

强连通分量（SCC）是其中任意两点沿方向互相可达的极大节点集合。弱连通分量（WCC）是忽略所有方向之后的极大连通分量。每个 SCC 都在某一个 WCC 内；反过来不一定成立。没有自环的单独节点也可以构成一个 SCC，因为允许长度为 $0$ 的自达路径。

某节点的入分量、出分量

$$\operatorname{Out}(v)=\{u:v\leadsto u\},\qquad \operatorname{In}(v)=\{u:u\leadsto v\}.$$

两者按课件约定都包含 $v$ 自己。它们通常重叠，也不组成对全图的互斥划分；两者的交集恰为包含 $v$ 的 SCC：

$$\boxed{\operatorname{SCC}(v)=\operatorname{In}(v)\cap\operatorname{Out}(v)}.$$

计算出集合时顺着箭头搜索，计算入集合时反向追踪箭头。

例：区分四种概念

设有边 $1\to2,2\to3,3\to1,3\to4,5\to4$。忽略方向后五个节点全连通，所以只有一个 WCC。SCC 则是 $\{1,2,3\}$、$\{4\}$、$\{5\}$。对节点 $3$，

$$\operatorname{Out}(3)=\{1,2,3,4\},\qquad \operatorname{In}(3)=\{1,2,3\}.$$

节点 $5$ 虽然与 $3$ 弱连通，却既到不了 $3$，也不能从 $3$ 到达。到同一终点 $4$ 并不意味着互相可达。

矩阵求度与二步邻居：讲义第 11 页答案

该页六节点有向图的边为 $1\to3,2\to6,3\to2,4\to1,4\to5,5\to3,6\to4,6\to5$。按 $1,\ldots,6$ 排序：

$$A=\begin{bmatrix} 0&0&1&0&0&0\\0&0&0&0&0&1\\0&1&0&0&0&0\\ 1&0&0&0&1&0\\0&0&1&0&0&0\\0&0&0&1&1&0 \end{bmatrix}.$$

行和与列和分别给出

$$\mathbf k^{\rm out}=(1,1,1,2,1,2),\qquad \mathbf k^{\rm in}=(1,1,2,1,2,1).$$

两者的分量之和均为 $8$，故 $M=8$。若忽略箭头，得到课件左侧无向矩阵，度为 $(2,2,3,3,3,3)$，总度为 $16$。该有向图本身也是强连通的：$1\to3\to2\to6\to4\to1$ 构成包含五点的环，且 $4\to5\to3$ 使节点 $5$ 也与该环互达。

为什么看 $A^2$？

矩阵乘法的定义是

$$(A^2)_{ij}=\sum_\ell A_{i\ell}A_{\ell j}.$$

每个中间节点 $\ell$ 若使 $i\to\ell\to j$ 成立，就贡献 $1$。因此 $(A^2)_{ij}$ 数的是从 $i$ 到 $j$ 长度恰为 $2$ 的游走数；一般 $(A^r)_{ij}$ 数长度恰为 $r$ 的游走数。它不自动排除重复节点，也不直接等于最短距离为 $r$ 的邻居个数。

本例计算得

$$A^2=\begin{bmatrix} 0&1&0&0&0&0\\0&0&0&1&1&0\\0&0&0&0&0&1\\ 0&0&2&0&0&0\\0&1&0&0&0&0\\1&0&1&0&1&0 \end{bmatrix}.$$

例如 $(A^2)_{43}=2$，因为 $4\to1\to3$ 与 $4\to5\to3$ 两条不同二步游走都到达同一个节点 $3$。所以 $4$ 的二步可达节点只有 $3$，不能把行和 $2$ 说成有两个不同的二阶邻居。

严格二阶邻居如何提取？

若定义为最短距离恰好等于 $2$ 的节点，则对无权简单图或同方向的有向可达关系：

$$\boxed{\mathcal N_2(i)=\{j:(A^2)_{ij}>0,\ A_{ij}=0,\ j\ne i\}}.$$

先把正数二值化，再去掉自身及已是一阶邻居的节点。本例 $6\to5$ 是一条直接边，而 $6\to4\to5$ 也是二步游走，故 $5$ 不属于 $6$ 的严格二阶邻居；$\mathcal N_2(6)=\{1,3\}$。课件简单写“二阶邻居：$A^2$”，考试应补上这个区别。

无向图的两个检查

无向简单图中 $(A^2)_{ii}=k_i$，因为每个邻居都提供一条 $i\to\ell\to i$ 的返回游走；$(A^2)_{ij}$（$i\ne j$）是 $i,j$ 的共同邻居数。对带权矩阵 $W$，$(W^2)_{ij}$ 是沿二步路线的权重乘积之和，一般不再是游走条数或最短路长度。

超图、稀疏性与计算表示

超图表示群体关系。（讲义 4，第 12 页）

普通边关联两个节点；超边（hyperedge）可以同时关联多个节点，是节点集合的子集。超图可以同时包含大小为 $2$ 和大于 $2$ 的超边，不要求每条超边都恰好有同一种大小。例如一篇论文的全体作者构成一条超边，一部电影的演员集合构成一条超边，一场活动的参与者构成一条超边。

将每条超边也视为一个新节点，就得到“原节点–超边节点”的二部图：原节点属于某超边，就连一条关联边。其关联矩阵为

$$H_{ie}=\begin{cases}1,&i\text{ 属于超边 }e,\\0,&\text{否则。}\end{cases}$$

行和 $\sum_eH_{ie}$ 是节点参加的超边数，列和 $\sum_iH_{ie}$ 是超边大小。$HH^{\mathsf T}$ 的非对角元数两个节点共同参加的超边数；去对角并二值化就得到普通图投影，但会失去群体结构。

例如“一个三人共同参加的事件”和“三个两人事件”都能投影成三角形，原来的超图却不同。用二部关联表示能保留这个区别。讲义的其他例子包括董事–公司董事会、关键词–出现页面、车站–列车路线、代谢物–反应参与集合，以及用户–共同喜欢的项目。

密度与平均度。（讲义 4，第 13 页）

密度是实际边数占所有允许边数的比例。无向简单图的最大边数是 $\binom n2$，因此

$$\boxed{\rho=\frac{M}{\binom n2}=\frac{2M}{n(n-1)} =\frac{\langle k\rangle}{n-1}\simeq\frac{\langle k\rangle}{n}}.$$

最后一个近似要求 $n$ 很大。有向无自环图有 $n(n-1)$ 个有序候选边，故

$$\rho_{\rm dir}=\frac{M}{n(n-1)}.$$

二部图若两组大小为 $n_U,n_V$，只允许跨组边，若以二部约束内的允许边计密度，则 $\rho_{\rm bip}=M/(n_Un_V)$。密度必须说明允许哪些边，不能把无向公式不加修改地用于有向图、多重图或自环图。

稀疏的尺度含义

若 $M=O(n)$，平均度保持 $O(1)$，则密度 $\rho=O(1/n)\to0$。所以一个大网络虽然含有很多边，仍可能很稀疏。例如 $n=10^6,\langle k\rangle=10$ 时，$M=5\times10^6$，但 $\rho\simeq10^{-5}$。BA 有 $M\simeq mn$，所以 $\rho\simeq2m/n$，可以同时具有 hub 和很低密度。

邻接矩阵与邻接表的代价

普通稠密邻接矩阵需 $O(n^2)$ 存储；邻接表需 $O(n+M)$ 存储。仅当 $M=O(n)$ 时才能进一步说邻接表是 $O(n)$。矩阵查询某条边可为 $O(1)$，但枚举某节点所有邻居通常要扫描一行 $O(n)$；邻接表枚举该节点邻居只需 $O(k_i)$。用邻接表进行广度/深度优先遍历通常为 $O(n+M)$；稀疏矩阵格式也是可用的节省存储方法，并不是所有“矩阵表示”都必须用稠密数组。

最后自测

若能独立回答下列问题，本节核心已掌握：给图写矩阵/邻接表并交叉检查度和边数；区分路径、环、诱导子图与分量；计算完全图、正则图、树的边数；构造二部投影；按行列求入出度；用箭头找 SCC、WCC、In/Out；解释 $A^2$ 并筛出严格二阶邻居；按图类型写密度，判断何时邻接表能节省到线性存储。

网络指标与算法

来源：NetworkX_metrics.ipynb，全部 7 个主题。本节整理 notebook 中的定义、算法及解释，并校正其中的概念与公式。除另有说明，公式针对无自环的简单、无向、无权图，$n$ 为节点数，$M$ 为边数。

距离、偏心率、直径和半径

最短路距离（shortest-path distance）$d_{ij}$ 是从 $i$ 到 $j$ 所有可行路径中最短的长度。无权图按边数计算；加权图若权重表示距离/费用，按沿途权重之和计算。强度越大的边不必是距离越大的边，使用算法前必须解释权重。

$$\begin{aligned} L&=\frac{1}{n(n-1)}\sum_{i\ne j}d_{ij} =\frac{2}{n(n-1)}\sum_{i<j}d_{ij},\\ \varepsilon(i)&=\max_jd_{ij},\qquad D=\max_i\varepsilon(i),\qquad R=\min_i\varepsilon(i). \end{aligned}$$

$L$ 是平均最短路长（characteristic path length）；$\varepsilon$ 为偏心率（eccentricity）；$D$ 是直径（diameter）；$R$ 是半径（radius）。中心集合由 $\varepsilon(i)=R$ 的节点组成，边缘集合由 $\varepsilon(i)=D$ 的节点组成。连通无向图满足 $R\le D\le2R$：任意两点可经一个中心连接，距离最多为 $2R$。

适用条件： 以上全图有限距离公式要求任意相关点对可达。非连通图中存在 $d_{ij}=\infty$；可以对最大连通分量或可达点对另算，但必须写明统计口径。有向图须保留方向，全体点对可达对应强连通。

度、接近与介数中心性：三种不同的“重要”

度中心性（degree centrality）

$$C_D(i)=\frac{k_i}{n-1}.$$

表示直接邻居多少；有向图分别用 $k_i^{\mathrm{in}}$ 或 $k_i^{\mathrm{out}}$。如果边 $i\to j$ 表示“$i$ 关注 $j$”，粉丝多对应入度高，关注别人多对应出度高。不能脱离边的语义记“影响力就是出度”。

接近中心性（closeness centrality）

$$C_C(i)=\frac{n-1}{\sum_{j\ne i}d_{ij}}.$$

是平均距离的倒数，越大代表平均上越靠近其他节点。对有向图，要区分“我到别人”（outward）和“别人到我”（inward）。NetworkX 默认使用到达该节点的距离；要计算向外距离，可对反向图调用。非连通图的默认修正：若可到达 $i$ 的其他节点有 $r_i$ 个，则

$$C_C^{\mathrm{WF}}(i)=\frac{r_i}{n-1}\frac{r_i}{\sum_{j\text{ 可到达 }i}d_{ji}},$$

没有可达其他节点时取 0。见NetworkX 官方 closeness 文档。

介数中心性（betweenness centrality） 令 $\sigma_{st}$ 为 $s$ 到 $t$ 的最短路条数，$\sigma_{st}(i)$ 为其中内部经过 $i$ 的条数。对 $n>2$，归一化无向公式为

$$C_B(i)=\frac{2}{(n-1)(n-2)} \sum_{\substack{s<t\\s,t\ne i}}\frac{\sigma_{st}(i)}{\sigma_{st}}.$$

若按有序点对 $s\ne t$ 求和，前因子改成 $1/[(n-1)(n-2)]$。不可达点对贡献取 0，端点不计入内部经过。介数衡量连接不同区域的桥梁作用；最短路不唯一时要分摊，不能只选其中一条。

选择指标： 直接连接数量用 degree；平均触达距离用 closeness；跨社群交通瓶颈用 betweenness。不同指标可以给出不同排名，没有对所有任务都最好的单一中心性。

特征向量中心性与 Katz 中心性

特征向量中心性（eigenvector centrality） 让重要邻居提供更多分数。无向图定义

$$x_i=\frac1\lambda\sum_jA_{ij}x_j, \qquad A\boldsymbol x=\lambda\boldsymbol x.$$

选取与谱半径 $\rho(A)$ 对应的非负特征向量，再规定归一化。连通、非负邻接矩阵的 Perron–Frobenius 性质保证该方向唯一且分量为正；非连通情形需留意非唯一和零分量。

本文采用 $A_{ij}=1$ 表示 $i\to j$，所以入链重要性为

$$x_i=\frac1\lambda\sum_jA_{ji}x_j, \qquad A^{\mathsf T}\boldsymbol x=\lambda\boldsymbol x.$$

这是 $A$ 的左特征向量（写成列向量时是 $A^{\mathsf T}$ 的右特征向量）。NetworkX 使用这一入链定义。若要由出邻居给分，则改用 $A\boldsymbol x$。见官方 eigenvector 文档。

校正： notebook 中左右特征向量与入出度的解释需跟随邻接矩阵约定。对 DAG，邻接矩阵的全部特征值为 0，普通特征向量中心性退化；不能简单说“所有数学特征向量只能是零向量”。问题是通常的正特征值传播定义不再提供合适的唯一正排名。

Katz 中心性加入每个节点的基础分 $\beta>0$。无向图用 $B=A$，有向入链版用 $B=A^{\mathsf T}$：

$$\boldsymbol x=aB\boldsymbol x+\beta\boldsymbol1, \qquad \boldsymbol x=\beta(I-aB)^{-1}\boldsymbol1, \qquad 0\le a<\frac1{\rho(B)}.$$

由几何级数可得

$$\boldsymbol x=\beta\sum_{\ell=0}^{\infty}a^\ell B^\ell\boldsymbol1.$$

它按 $a^\ell$ 给长度 $\ell$ 的游走计权。$a$ 控制远处路径的影响，$\beta$ 为统一基础分时只改变整体尺度，常设为 1。$a$ 可改变相对得分，进而可能改变排名，不能说只需知道 $a/\beta$。 逆矩阵给出未归一化解；nx.katz_centrality 默认再把欧氏范数归一化为 1。若 $\rho(B)=0$（如 DAG），级数在有限项后停止，不存在有限的 $1/\rho$ 上界。见官方 Katz 文档。

PageRank：沿边传递概率并允许随机跳转

Katz 会让节点把未按出度分摊的重要性传给邻居。PageRank 使用随机游走解释：节点 $j$ 把分数均分给它指向的节点，另以概率 $1-d$ 随机跳转。$0<d<1$ 是阻尼系数，常用 $0.85$；它与 Katz 的 $a<1/\rho(A)$ 是不同条件。

令 $P$ 为行随机矩阵。无权且无 dangling node（出度为 0）时，$P_{ij}=A_{ij}/k_i^{\mathrm{out}}$。若 $k_i^{\mathrm{out}}=0$，把该行设为跳转分布 $\boldsymbol v^{\mathsf T}$；均匀跳转取 $v_i=1/n$。列向量形式是

$$\boxed{\boldsymbol p=dP^{\mathsf T}\boldsymbol p+(1-d)\boldsymbol v}, \qquad p_i\ge0,\quad\sum_i p_i=1.$$

均匀跳转下，每个节点获得的基础概率是 $(1-d)/n$。notebook 的向量式把该项误写成 $(1-d)\boldsymbol x/n$；正确项是 $(1-d)\boldsymbol1/n$（已归一化时）。若用 Google 矩阵，

$$G=dP+(1-d)\boldsymbol1\boldsymbol v^{\mathsf T},\qquad G^{\mathsf T}\boldsymbol p=\boldsymbol p.$$

检查公式的快速办法是对分量求和：左右两边都应为 1。官方实现对无出边节点的处理见NetworkX PageRank 文档。

自编例题： 只有 $1\to2$，取均匀跳转。第 2 行补成 $(1/2,1/2)$，因此

$$p_1=\frac d2p_2+\frac{1-d}{2},\quad p_1+p_2=1 \quad\Longrightarrow\quad p_1=\frac1{2+d},\quad p_2=\frac{1+d}{2+d}.$$

$d=0.85$ 时约为 $(0.350877,0.649123)$。节点 2 无出边也不会“吞掉”总概率。

核、局部聚类与全局传递性

$k$-core 是通过不断剔除当前度小于 $k$ 的节点后留下的最大诱导子图，其内部每个节点度至少为 $k$。节点的 core number 是它所属的最大 $k$ 值。度要在剩余子图内反复更新。高原始度节点若只连着叶子，仍可能仅属于 1-core，例如星形图中心。notebook “至少连着 $k$ 个同 coreness 节点”不够准确，应为该 $k$-core 内的节点，其 core number 可以更高；$k$-core 也不只指最内层。官方定义与此一致。

局部聚类系数设 $t_i$ 为包含节点 $i$ 的三角形数，也等于其邻居之间的边数，则

$$C_i=\frac{t_i}{\binom{k_i}{2}}=\frac{2t_i}{k_i(k_i-1)},\quad k_i\ge2; \qquad C_i=0\ (k_i<2).$$

网络的平均局部聚类 $\bar C=\frac1n\sum_iC_i$，按节点等权平均。无向简单图还可用 $(A^3)_{ii}=2t_i$、全网三角形数 $T=\operatorname{tr}(A^3)/6$ 检验。

全局传递性（transitivity）

$$C_{\mathrm{trans}}=\frac{3T}{\sum_i\binom{k_i}{2}} =\frac{\sum_i\binom{k_i}{2}C_i}{\sum_i\binom{k_i}{2}}.$$

若没有任何连通三元组，NetworkX 约定传递性为 0。分母是以某节点为中心的连通三元组数；每个三角形贡献三个闭合三元组。它按邻居对数加权，故不等于 $\bar C$，也没有普遍的谁大谁小关系。当大度节点局部聚类较低时，传递性可能比平均局部聚类小。

同配性、社群与模块度

同配性（assortativity） 是边两端节点属性的相关程度。令每条有向边端点的属性为 $u_e=f(i)$、$v_e=f(j)$；无向边要计两个方向，以消除端点选取的不对称。记沿边端点的平均为 $\bar u,\bar v$，则

$$r=\frac{\sum_e(u_e-\bar u)(v_e-\bar v)} {\sqrt{\sum_e(u_e-\bar u)^2\sum_e(v_e-\bar v)^2}}.$$

这就是 Pearson 相关。$r>0$ 表示相似属性相连（同配），$r<0$ 表示不同属性相连（异配），$r=0$ 表示无此线性相关；端点属性方差为零时未定义。无向度同配性取 $f(i)=k_i$；有向图须指定端点的度类型，NetworkX 默认相关的是源节点出度与目标节点入度（x="out", y="in"）。这里按边端点抽样，不能替换成所有节点等权抽样。

BA 增长时新节点初始度低，且优先连高度节点，有限样本可能呈弱负度相关；一次模拟的符号不构成所有 BA 参数和规模下的定理。笔记中的政治网络图展示群体间连接分化的经验趋势。

社群（community） 通常指内部连接比外部更密的一组节点。社群划分可由领域标签给出，也可用算法推断；Louvain 是笔记展示的划分方法，属于无监督的社群检测，不需要已有正确标签。

模块度（modularity） 比较实际内部边数与保留度信息的随机基准。对 $M>0$ 的无向无权图的一项不重叠划分 $c_i$，

$$\begin{aligned} Q&=\frac1{2M}\sum_{i,j}\left(A_{ij}-\frac{k_ik_j}{2M}\right)\delta(c_i,c_j)\\ &=\sum_C\left[\frac{l_C}{M}-\left(\frac{K_C}{2M}\right)^2\right]. \end{aligned}$$

$l_C$ 为社群内部边数，$K_C=\sum_{i\in C}k_i$ 为该社群在原图中的度之和。这个基准不是任意“纯随机图”，而是用度给出预期连边数的模型。$Q$ 较高表示该划分比基准有更多内部边，但不保证发现唯一真实社群；把所有节点作为一组得到 $Q=0$。见官方 modularity 文档（本文采用默认 resolution $=1$）。

巨分量、小世界和真实网络的读表方法

最大连通分量的比例是 $S=|C_{\max}|/n$。严格地说，巨分量（giant component）指网络增大时仍占非零比例、规模为 $O(n)$ 的分量，有限图的“最大分量”不自动证明此渐近性质。

笔记用 $G(n,p)$ 的图示说明提高连边概率后，许多小分量合并成大分量；此处重点是识别现象，完整渗流证明未在这两份 notebook 展开。

小世界（small world）表示典型最短路很短、常随规模缓慢增长。度分布幂律、短路径、高聚类是三个不同性质，不能互相替代；“六度分隔”是社会网络的经验叙述，不是任意两个现实人必恰好六步相连的定理。

原 notebook 的真实网络表依次给出 $n,M,c,S,L$、幂律指数、transitivity、平均局部聚类、$r$。解读重点：社会网络样本常有短距离、高聚类和正同配；信息/生物网络样本可有幂律及负同配，但表中也有例外，不能背成所有网络的定律。“幂律必无方差”也应改为：无上界理想尾部 $1<\gamma\le3$ 没有有限二阶矩，$\gamma>3$ 可以有有限方差；有限观测样本的样本方差总是可计算的。

BFS 与计算复杂度：说明采用什么表示法

邻接表空间为 $O(n+M)$，邻接矩阵为 $O(n^2)$。在稀疏网络 $M=O(n)$ 时，邻接表近似线性存储；若存在 hub，单个节点的度仍可能很大，不能把所有节点邻居枚举都当常数时间。

广度优先搜索（breadth-first search, BFS） 适用于无权图：把起点 $s$ 的距离设为 0 入队；每次取出队首 $u$，对每个未访问邻居 $v$，设 $d(v)=d(u)+1$ 并入队。因为先探索第 $d$ 层再探索第 $d+1$ 层，首次到达就是最短距离。原笔记缺失的更新值应为 $d+1$。

任务	邻接表典型复杂度	理由与条件
枚举节点 $i$ 的邻居	$O(k_i)$	必须看每个邻居
取未加权度	可为 $O(1)$	若容器/缓存保存邻居数；扫描计数则 $O(k_i)$
平均度 $2M/n$	$O(1)$ 或 $O(n)$	已知 $M,n$ 为常数；逐节点取度后求和为 $O(n)$；若再扫描边则 $O(n+M)$
单源 BFS、两点最短路	最坏 $O(n+M)$	每节点和边最多访问常数次；两点可提前停但最坏阶数相同
单节点偏心率	$O(n+M)$	单源 BFS 后取最大距离
所有点对距离、全图精确 $D,R,L$	$O(n(n+M))$	从每个节点分别 BFS

上述最后一行在稀疏图变成 $O(n^2)$。使用邻接矩阵时，一次 BFS 检查每个节点整行，通常为 $O(n^2)$。加权距离不能直接用逐层 BFS；非负距离权重常用 Dijkstra。

贯穿例题：一个三角形加一片叶子（自编）

取 $V=\{1,2,3,4\}$，$E=\{(1,2),(1,3),(2,3),(3,4)\}$。

1 ----- 2
 \     /
  \   /
    3 ----- 4

$$(d_{ij})=\begin{pmatrix}0&1&1&2\\1&0&1&2\\1&1&0&1\\2&2&1&0\end{pmatrix}.$$

共有 4 条边，度为 $(2,2,3,1)$，平均度 2，密度 $2/3$。六个无序点对的距离和为 8，故 $L=4/3$；$D=2,R=1$，中心为 $\{3\}$，边缘为 $\{1,2,4\}$。

节点	$C_D$	$C_C$	$C_B$	$C_i$	core number
1	$2/3$	$3/4$	0	1	2
2	$2/3$	$3/4$	0	1	2
3	1	1	$2/3$	$1/3$	2
4	$1/3$	$3/5$	0	0	1

节点 3 位于点对 $(1,4)$、$(2,4)$ 的最短路，故归一化介数 $=2/3$。全网一个三角形，三元组总数 $1+1+3=5$，所以 $\bar C=7/12$，$C_{\mathrm{trans}}=3/5$。

对划分 $\{1,2,3\},\{4\}$，$l_1=3,K_1=7,l_2=0,K_2=1,M=4$，

$$Q=\frac34-\left(\frac78\right)^2-\left(\frac18\right)^2=-\frac1{32}.$$

度同配性还可验得 $r=-5/7$：沿边端点的平均度为 $9/4$，协方差为 $-5/16$，两端方差均为 $7/16$。这说明本例高度端点较倾向连接低度端点。

上述 $Q<0$ 说明单独把叶子分成社群，并未产生优于该随机基准的划分。所有结果可用下一节的代码逐项核验。

NetworkX 操作与代码题

来源：NetworkX_tutorial.ipynb（95 个单元）及 NetworkX_metrics.ipynb 中的函数调用。下面按学习用途合并重复操作，保留所有知识主题。代码使用 NetworkX 3.x 常用接口，独立示例已实际核验。

字典、图类型与节点边的创建

Python 字典保存 key:value。例如 tel['jack'] 查询值，tel['john']=4127 添加或更新；list(tel) 或 tel.keys() 取键，tel.values() 取值，len(tel) 取条目数，sorted(tel) 返回排序后的键。NetworkX 的邻接与属性以字典式结构组织。

nx.Graph() 表示无向图，nx.DiGraph() 表示有向图；这两个类允许自环、不允许平行边，反复添加同一边不会产生额外边。本文示例不添加自环，因此按简单图讨论。需要平行边时使用 MultiGraph 或 MultiDiGraph。节点标识须可哈希，如整数、字符串、元组。见 NetworkX Graph 官方说明。

import networkx as nx
G = nx.Graph()
G.add_node(1)
G.add_nodes_from([2, 3])
G.add_nodes_from([(4, {"color": "red"})])
G.add_edge(1, 2)  # creates missing endpoints automatically
e = (2, 3)
G.add_edge(*e)    # unpack tuple into two arguments
G.add_edges_from([(1, 3), (3, 4)])
G.add_weighted_edges_from([(1, 4, 0.5)])

字符串陷阱：add_node("spam") 添加一个节点 "spam"；add_nodes_from("spam") 遍历字符串，添加 's','p','a','m' 四个节点。边列表应是二元组或带属性的三元组。

可以直接构造图：nx.Graph([(0,1),(1,2)])；邻接字典也可传给构造器。nx.DiGraph(G) 把无向边转换为两条相反有向边；DG.to_undirected() 或 nx.Graph(DG) 忽略方向形成无向图。转换会改变问题语义，解释题中应说明方向为何可忽略。

查看、属性与删除：读懂对象返回什么

写法	意义
G.number_of_nodes() / G.number_of_edges()	节点数、边数
list(G.nodes), list(G.edges)	节点、边；不转换时通常为动态 view
list(G.neighbors(i)) / list(G.adj[i])	邻居；有向图为 successors
G.degree[i] / dict(G.degree())	一个节点的度 / 度字典
G.graph['day']='Monday'	整张图的属性
G.nodes[i]['color']='red'	节点属性，节点必须已经存在
G[i][j]['weight']=2	已存在边的属性；等价于访问 G.edges[i,j]
G.edges.data('weight')	迭代 (u,v,weight)
G.adj.items()	节点及其邻接字典，无向边会被看见两次
G.remove_node(i), G.remove_edge(i,j)	单个删除；删节点同时删除关联边
G.remove_nodes_from([...])	批量删节点；边有对应批量函数
G.clear()	清空图的节点、边和属性

属性可在添加时写入，例如 G.add_edge(1,2,weight=4.7)；重复添加同一边可以更新属性。查看图的 view 与创建独立数据副本不同：图变化时 view 会反映变化，若要固定快照可转成 list 或 dict。遍历同时删除时先取列表快照可避免迭代对象变化。

有向与加权例子：

DG = nx.DiGraph()
DG.add_weighted_edges_from([(1, 2, 0.5), (3, 1, 0.75)])
DG.out_degree(1)                   # 1
DG.in_degree(1)                    # 1
DG.degree(1)                       # 2 (in + out)
DG.out_degree(1, weight="weight")  # 0.5
DG.degree(1, weight="weight")      # 1.25
list(DG.successors(1))             # [2]
list(DG.neighbors(1))              # [2]
list(DG.predecessors(1))           # [3]

不传 weight 时“度”数边；传入时计算相应边权和（strength）。degree 在有向图是入度加出度，不等于 neighbors 的个数。

生成图、作图与随机性

K5 = nx.complete_graph(5)
K35 = nx.complete_bipartite_graph(3, 5)
B = nx.barbell_graph(10, 10)
L = nx.lollipop_graph(10, 20)
ER = nx.erdos_renyi_graph(100, 0.15, seed=1)
WS = nx.watts_strogatz_graph(30, 4, 0.1, seed=1)
BA = nx.barabasi_albert_graph(100, 5, seed=1)
lobster = nx.random_lobster(100, 0.9, 0.9, seed=1)

ER 的第二参数是每对节点连边概率；BA 的第二参数是每个新节点带来的边数；WS 先构造局部规则环再重连，第二参数是初始邻域参数，例子选偶数 4 便于解释。barbell 是两个完全图用路径相连；lollipop 是完全图与路径相连；random lobster 是随机树状结构的生成器。不同模型的参数含义不能互换。随机 seed 用于复现一次样本，不代表该样本等于模型平均值。

import matplotlib.pyplot as plt
G = nx.petersen_graph()
pos = nx.spring_layout(G, seed=1)
nx.draw(G, pos, with_labels=True, node_size=300)
plt.savefig("network.png", dpi=200)
plt.close()

笔记还展示 random、circular、spectral、shell 布局及 shell 的 nlist 分层。布局改变可视化坐标，不会改变邻接关系和图指标。图中两点画得近不保证最短路近，画得交叉也不代表交点是节点。Gephi 是笔记介绍的独立网络可视化工具；新加坡 Twitter/X 图展示了真实网络规模及异质性，不需要记住绘图坐标。

指标函数速查与常见前提

# Components and paths
list(nx.connected_components(G))  # undirected
list(nx.strongly_connected_components(DG))
list(nx.weakly_connected_components(DG))
nx.shortest_path(G, source=1, target=4)
nx.shortest_path_length(G, source=1, target=4)
nx.average_shortest_path_length(G)
nx.eccentricity(G)
nx.diameter(G); nx.radius(G)
nx.center(G); nx.periphery(G)

# Centrality (returns dictionaries keyed by node)
nx.degree_centrality(G)
nx.closeness_centrality(G)
nx.betweenness_centrality(G)
nx.eigenvector_centrality(G, max_iter=1000)
nx.katz_centrality(G, alpha=0.1, beta=1.0)
nx.pagerank(G, alpha=0.85, weight=None)

# Cohesion and communities
nx.core_number(G)
nx.k_core(G, k=2)
nx.clustering(G); nx.average_clustering(G)
nx.transitivity(G)
nx.degree_assortativity_coefficient(G)
groups = nx.community.louvain_communities(G, seed=1, weight=None)
nx.community.modularity(G, groups, weight=None)

这里 PageRank、Louvain 和模块度显式设 weight=None，以对应无权公式；笔记使用的 karate-club 图自带权重，省略此参数时这些函数通常会使用权重。

这些是接口示意，不要求对任意输入图全部调用成功。计算全图距离先检查连通性；有向图用合适的强/弱分量函数。特征向量、Katz、PageRank 采用迭代时可能需调整迭代次数与收敛容差，Katz 还须先满足谱半径条件。nx.k_core(G) 不指定 $k$ 时返回最大 core number 对应的核心。无权距离是默认口径；加权路径要显式传 weight='weight'，加权 closeness 的参数名是 distance。

完整可复现的检验例子

以下代码使用上一节“三角形加一片叶子”的同一张图，展示从输入到结果的完整路径。

import networkx as nx
G = nx.Graph([(1, 2), (1, 3), (2, 3), (3, 4)])
n = G.number_of_nodes()
M = G.number_of_edges()
print(dict(G.degree()))       # {1: 2, 2: 2, 3: 3, 4: 1}
print(2 * M / n)              # 2.0
print(nx.density(G))          # 2/3
print(nx.average_shortest_path_length(G))  # 4/3
print(nx.center(G), nx.periphery(G))      # [3], [1,2,4]
print(nx.betweenness_centrality(G))        # node 3: 2/3
print(nx.average_clustering(G))           # 7/12
print(nx.transitivity(G))                 # 3/5
print(nx.core_number(G))      # {1: 2, 2: 2, 3: 2, 4: 1}
print(nx.community.modularity(G, [{1, 2, 3}, {4}]))
# -0.03125 = -1/32

H = G.copy()
H.remove_node(3)
print(list(nx.connected_components(H)))   # [{1,2}, {4}]

输出中集合、字典的显示顺序不是数学结果的一部分。取最大连通分量并建立独立子图可写成：

nodes = max(nx.connected_components(G), key=len)
largest = G.subgraph(nodes).copy()

代码题检查顺序： 图是有向还是无向 $\to$ 节点是否被字符串拆开 $\to$ 边是否重复/带权 $\to$ degree 是否加权 $\to$ 算法是否要求连通 $\to$ 输出是标量、路径、集合还是字典。按此顺序通常能定位笔记练习中的主要陷阱。

综合自测与考前核对

以下均为依据现有材料编写的自测题，不是往年试题或老师预测题。先独立作答，再对照答案。各章还保留了原讲义练习和对应解答。

八道综合题

1. $X_i$ 独立同分布，均值 2、方差 9。$n=100$ 时 $S_n$ 和 $\bar X_n$ 的近似分布是什么？$P(\bar X_n>2.6)$ 怎样计算？

2. 在 $x\ge2$ 上 $p(x)=Cx^{-5/2}$。求 $C$、$P(X>8)$、均值与方差是否有限。

3. 若 log-log 图上 CCDF 的斜率为 $-1.6$，PDF 的尾部指数是多少？普通有限方差 CLT 能直接用吗？

4. 对称标准 Cauchy 的独立样本均值会不会随样本量增大集中到 0？解释标准化尺度与有限均值条件。

5. BA 模型每步添加一个带 3 条边的节点。若节点在 $t_i=100$ 出生，$t=2500$ 时连续近似期望度是多少？尾部 PDF 与 CCDF 指数分别是多少？

6. 有向图 $E=\{1\to2,2\to1,2\to3,3\to4,4\to3\}$。写邻接矩阵、入出度、强分量、弱分量及节点 2 的 in/out component。

7. 一张图有 1 个中心和 5 片叶子（星形图）。求中心与叶子的 degree/closeness/betweenness、core number，及全图 $L,D,R$。

8. 用邻接表表示一个 $n$ 节点稀疏无权网络。求从一个节点到所有节点的距离需要什么算法和时间复杂度？对全部节点重复的复杂度是多少？

答案与得分所需步骤

第 1 题

$S_{100}\approx N(200,900)$，$\bar X_{100}\approx N(2,0.09)$。标准差为 $0.3$，故 $P(\bar X>2.6)\approx1-\Phi(2)\approx0.0228$。这是假设满足 CLT 后的近似，不是对任意原分布的有限样本精确值。

第 2 题

$C=(\gamma-1)x_{\min}^{\gamma-1}=(3/2)2^{3/2}$；尾概率 $(8/2)^{-3/2}=1/8$。$\gamma=2.5>2$ 所以均值为 $\frac{\gamma-1}{\gamma-2}x_{\min}=6$；$\gamma\le3$ 所以没有有限方差。

第 3 题

CCDF 指数 $\alpha=1.6$，PDF 指数 $\gamma=2.6$；均值有限、二阶矩无穷，不能直接使用普通有限方差 CLT。指数关系来自对 PDF 从 $x$ 积到无穷，不是同一条斜率。

第 4 题

不会。$S_n\overset d=nX$，$\bar X_n\overset d=X$。Cauchy 的均值未定义，样本均值的分布保持宽度；大数定律所需的可积性不成立。

第 5 题

$k_i(t)\approx m\sqrt{t/t_i}=3\sqrt{25}=15$。BA 渐近 PDF 指数为 3，CCDF 指数为 2；$m$ 改变平均度与幅度，不改变基本 BA 的指数 3。

第 6 题

$$A=\begin{pmatrix}0&1&0&0\\1&0&1&0\\0&0&0&1\\0&0&1&0\end{pmatrix},\quad k^{\mathrm{out}}=(1,2,1,1),\quad k^{\mathrm{in}}=(1,1,2,1).$$

强分量为 $\{1,2\},\{3,4\}$，弱分量为全体。含节点自身时，$\mathrm{IN}(2)=\{1,2\}$，$\mathrm{OUT}(2)=\{1,2,3,4\}$。入度、出度总和都等于 5 条有向边。

第 7 题

$n=6,M=5$。中心的 $C_D=C_C=C_B=1$；叶子的 $C_D=1/5$、$C_C=5/9$、$C_B=0$。中心的距离和为 5，叶子的为 $1+4\times2=9$。15 个无序点对中 5 个距离1、10个距离2，故 $L=25/15=5/3$；$D=2,R=1$。所有节点 core number 都为1，局部聚类为0；中心原始度高不意味着高 coreness。

第 8 题

BFS；邻接表一次为 $O(n+M)=O(n)$（稀疏条件下），全部单源距离为 $O(n(n+M))=O(n^2)$。写答案时不能省略“邻接表、无权、稀疏”这些决定阶数的前提。

必须能够不看答案复现的内容

• 用 $S_n$ 的期望与方差得到 CLT 标准化；说明 MGF 泰勒展开中常数项、一次项、二次项分别来自哪里。

• 从归一化积分推出幂律常数，再用 $\int x^{q-\gamma}\,dx$ 判断矩；分清边界值 $\gamma=2,3$ 的对数发散。

• 从 BA 的连接概率推 $dk_i/dt$、初始条件、年龄变换与 $p(k)$；用离散主方程复现 $p_k$。

• 从图得到矩阵、邻接表、度及分量；解释 $A^\ell$ 计数的是游走，不是“距离恰好为 $\ell$”的邻居。

• 对网络指标先写语义与适用条件，再代入公式；尤其检查矩阵转置、介数二倍因子、三角形三倍因子和 PageRank 总概率。

最终易错点清单

1. i.i.d. 的 identical 指同分布，不是每次取到同一个数；独立是联合分布可分解，不只是零相关。

2. CLT 描述标准化的和/均值趋于正态，不说原始单个观测变成正态。

3. 有限样本有方差估计，不代表背后的无界理论分布有有限方差；Cauchy 对称不代表均值为0。

4. PDF 与 CCDF 的 log-log 斜率差1；震级、振幅和能量是不同变量，变量变换必须带 Jacobian。

5. 幂律数据不自动证明优先连接或 SOC；Poisson 稀疏极限与 CLT 正态近似是不同极限。

6. tree 必须连通且无环；一般无环图是 forest。平面图取决于能否重新画成无交叉，并非当前图上是否有交叉。

7. 固定 $A_{ij}=i\to j$ 后，出度看行，入度看列；入链传播用 $A^{\mathsf T}$。

8. $\bar C$ 按节点平均，transitivity 按邻居对加权；同配性沿边端点取相关。

9. 度、特征向量、Katz、PageRank、core number 衡量不同性质，不可仅凭节点画在中央就判断数值。

Helpsheet：六块核心速查

下面集中列出六组核心定义、公式与适用条件，便于在读完正文后回查。相同字母在不同模块中可能有不同含义，以各模块的定义为准。

1. 概率、CLT 与 MGF

记 $S_n=\sum_{i=1}^nX_i$、$\overline X=S_n/n$。$N(\mu,\sigma^2)$ 的第二个参数是方差。

$$\begin{aligned} \int p(x)\,dx&=1,\\ \mu&=E[X],\\ \sigma^2&=E[X^2]-\mu^2,\\ p_N(x)&=\frac{e^{-(x-\mu)^2/(2\sigma^2)}}{\sigma\sqrt{2\pi}}. \end{aligned}$$

CLT：$X_i$ 独立同分布，且 $0<\sigma^2<\infty$ 时，

$$\begin{aligned} Z_n&=\frac{S_n-n\mu}{\sigma\sqrt n} =\frac{\sqrt n(\overline X-\mu)}{\sigma},\\ Z_n&\xrightarrow{d}N(0,1),\qquad n\to\infty,\\ S_n&\approx N(n\mu,n\sigma^2),\\ \overline X&\approx N(\mu,\sigma^2/n). \end{aligned}$$

MGF 与原点矩：

$$\begin{aligned} M_X(t)&=E[e^{tX}],\\ M_X^{(r)}(0)&=E[X^r],\\ M_{aX+b}(t)&=e^{bt}M_X(at),\\ M_{\sum_iX_i}(t)&=\prod_iM_{X_i}(t)\qquad\text{（独立时）},\\ M_N(t)&=e^{\mu t+\sigma^2t^2/2}. \end{aligned}$$

标准正态的原点矩为 $(m_0,m_1,m_2,m_3,m_4)=(1,0,1,0,3)$。令 $Y=(X-\mu)/\sigma$，证明链为

$$\begin{aligned} \left[M_Y\!\left(\frac{t}{\sqrt n}\right)\right]^n &=\left[1+\frac{t^2}{2n}+o(n^{-1})\right]^n\\ &\longrightarrow e^{t^2/2}. \end{aligned}$$

MGF 证明额外要求它在 $0$ 的邻域内有限；泰勒导数在 $0$ 处取值。独立才可把和的 MGF 写成乘积。

$$\begin{aligned} \text{偏度}&=\frac{E[(X-\mu)^3]}{\sigma^3},\\ \text{峰度}&=\frac{E[(X-\mu)^4]}{\sigma^4},\\ \text{超额峰度}&=\text{峰度}-3. \end{aligned}$$

对称随机游走：$P(X=1)=P(X=-1)=1/2$，各步独立，

$$\begin{aligned} M_X(t)&=\cosh t,\\ S_n&\approx N(0,n),\\ P(S_n=s)&=2^{-n}\binom{n}{(n+s)/2},\\ s&=-n,-n+2,\ldots,n. \end{aligned}$$

2. 稳定分布、幂律与 Pareto

稳定性与特征函数： 对独立同分布变量的和，稳定性写成 $S_n\overset{d}{=}a_nX+b_n$。特征函数（CF）$\varphi_X(q)=E[e^{iqX}]$ 总存在。

对称、中心为 $0$ 的稳定族满足 $c>0$、$0<\alpha\le2$：

$$\begin{aligned} \varphi_X(q)&=e^{-c|q|^\alpha},\\ S_n&\overset{d}{=}n^{1/\alpha}X,\\ \overline X&\overset{d}{=}n^{1/\alpha-1}X. \end{aligned}$$

$\alpha=2$ 是 Gaussian，方差为 $2c$；$\alpha=1$ 是 Cauchy：

$$\begin{aligned} p_C(x)&=\frac{c}{\pi(x^2+c^2)},\\ \varphi_C(q)&=e^{-c|q|},\\ \overline X&\overset{d}{=}X. \end{aligned}$$

Cauchy 的均值未定义，对称主值 $0$ 不等于期望存在；样本均值不会随样本量增加而集中。

幂律尾与矩：

$$\begin{aligned} p(x)&\propto x^{-\gamma}=x^{-(1+\alpha)},\\ \overline F(x)&\propto x^{-\alpha},\\ \gamma&=1+\alpha,\\ E|X|^r<\infty &\iff r<\alpha\iff\gamma>r+1,\qquad r>0. \end{aligned}$$

PDF、CCDF 在 log-log 图上的斜率分别为 $-\gamma$、$-\alpha$。等号边界发散；幂律尾指数 $\alpha=2$ 的二阶矩仍发散。用于稳定族时，幂律尾及上述矩判据限于 $0<\alpha<2$；稳定指数 $\alpha=2$ 是高斯特例，各阶矩有限。

Pareto：$x\ge x_m>0$、$\alpha>0$，

$$\begin{aligned} p(x)&=\frac{\alpha x_m^\alpha}{x^{1+\alpha}},\\ \overline F(x)&=(x_m/x)^\alpha,\\ E[X^r]&=\frac{\alpha x_m^r}{\alpha-r},\qquad r<\alpha,\\ E[X]&=\frac{\alpha x_m}{\alpha-1},\qquad\alpha>1,\\ \operatorname{Med}(X)&=x_m2^{1/\alpha},\\ \operatorname{Var}(X)&=\frac{\alpha x_m^2}{(\alpha-1)^2(\alpha-2)},\qquad\alpha>2,\\ G&=\frac1{2\alpha-1},\qquad\alpha>1. \end{aligned}$$

尺度无关表现为幂律有效区间内 $p(ax)/p(x)=a^{-\gamma}$。有限截断使各正阶矩有限。

3. 放宽 CLT 与应用提醒

独立但非同分布的 Lyapunov 条件： 记 $s_n^2=\sum_{i=1}^n\sigma_i^2$。若存在 $\delta>0$，使

$$\frac{\sum_{i=1}^nE|X_i-\mu_i|^{2+\delta}}{s_n^{2+\delta}}\longrightarrow0,$$

则

$$\frac{\sum_{i=1}^n(X_i-\mu_i)}{s_n}\xrightarrow{d}N(0,1).$$

Gutenberg–Richter：

$$\log_{10}N(M_{\mathrm{mag}}\ge u)=a-bu.$$

由 $M_{\mathrm{mag}}=\log_{10}A+\mathrm{const}$，得到

$$\overline F_A(A)\propto A^{-b},\qquad p_A(A)\propto A^{-b-1}.$$

Omori：$r(t)=K/(t+c)^p$ 描述事件率，不能直接当作概率密度。

St Petersburg：

$$P(N=j)=2^{-j},\qquad W=2^{j-1},\qquad j=1,2,\ldots,$$

由此 $E[W]=\infty$。

复杂系统关键词： 多体、自主、非线性互动、涌现。发现幂律不能单独证明其生成机制。

4. BA 与 ER 网络

记 $n$ 为节点数，$M$ 为总边数，$m$ 为 BA 模型每个新节点带来的边数。

BA：增长加线性优先连接。

$$\begin{aligned} n&=n_0+t,\\ M&=M_0+mt,\\ \Pi_i&=\frac{k_i}{\sum_jk_j},\\ \sum_jk_j&\simeq2mt. \end{aligned}$$

连续近似中，

$$\begin{aligned} \dot k_i&=m\Pi_i=\frac{k_i}{2t},\\ k_i(t_i)&=m,\\ k_i(t)&=m\sqrt{t/t_i}. \end{aligned}$$

出生时间近似均匀；对 $k\ge m$，反解得 $t_i=t(m/k)^2$，因此

$$\begin{aligned} F(k)&=1-(m/k)^2,\\ p_{\mathrm{cont}}(k)&=2m^2k^{-3},\\ \gamma&=3. \end{aligned}$$

主方程：$N_k$ 为度等于 $k$ 的节点数，$\delta_{km}$ 为新节点出生项。

$$\begin{aligned} \Delta N_k&=\frac{(k-1)N_{k-1}-kN_k}{2t}+\delta_{km},\\ N_k&\simeq tp_k. \end{aligned}$$

边界、递推与闭式分别为

$$\begin{aligned} p_m&=\frac2{m+2},\\ p_k&=\frac{k-1}{k+2}p_{k-1},\qquad k>m,\\ p_k&=\frac{2m(m+1)}{k(k+1)(k+2)},\qquad k\ge m,\\ P(K\ge q)&=\frac{m(m+1)}{q(q+1)},\qquad q\in\mathbb Z,\ q\ge m,\\ \langle k\rangle&\longrightarrow2m. \end{aligned}$$

ER 随机图 $G(n,p)$： 每对节点独立连边，

$$\begin{aligned} E[M]&=\frac{pn(n-1)}2,\\ P(K=k)&=\binom{n-1}{k}p^k(1-p)^{n-1-k},\\ c&=(n-1)p. \end{aligned}$$

固定 $c$，令 $p=c/(n-1)$、$n\to\infty$，得到 Poisson 极限：

$$p_k\longrightarrow\frac{e^{-c}c^k}{k!}.$$

在该极限分布中，$E[K]=\operatorname{Var}(K)=c$。Poisson 极限不是 CLT；只有进一步取较大 $c$，才可近似正态。ER 尾部衰减快，BA 则会形成 hub。

5. 图论、矩阵与分量

采用 $A_{ij}=1$ 表示 $i\to j$；无向图有 $A=A^{\mathsf T}$。对无自环简单图，

$$\begin{aligned} k_i^{\mathrm{out}}&=\sum_jA_{ij},\\ k_i^{\mathrm{in}}&=\sum_jA_{ji}. \end{aligned}$$

无向图的度和及平均度为

$$\sum_i k_i=2M,\qquad \langle k\rangle=2M/n.$$

有向图有 $\sum_i k_i^{\mathrm{in}}=\sum_i k_i^{\mathrm{out}}=M$。无向与有向密度分别为

$$\rho_u=\frac{2M}{n(n-1)},\qquad \rho_d=\frac{M}{n(n-1)}.$$

矩阵幂与距离：$(A^\ell)_{ij}$ 计数长度为 $\ell$ 的 walk。严格距离为 $2$ 的节点须满足

$$(A^2)_{ij}>0,\qquad A_{ij}=0,\qquad j\ne i.$$

无向简单图还满足 $(A^2)_{ii}=k_i$。

图的计数与结构：

• 树是连通且无环的图，$M=n-1$。
• 含 $C$ 个分量的森林满足 $M=n-C$。
• $k$-正则图有 $M=nk/2$。
• 完全图有 $M=n(n-1)/2$。
• 二分图没有奇环，邻接矩阵可写成

$$A_{\mathrm{bip}}=\begin{pmatrix}0&B\\B^{\mathsf T}&0\end{pmatrix}.$$

$BB^{\mathsf T}$、$B^{\mathsf T}B$ 给出两侧各自的共邻居投影；去掉对角线，再将正值置为 $1$，得到无权投影。

连通性与其他网络类型： SCC 要求双向可达；WCC 忽略方向。将自身也计入时，

$$\mathrm{IN}(v)\cap\mathrm{OUT}(v)=\mathrm{SCC}(v).$$

超边可以同时连接多个对象；multiplex 用多层关系描述同一组节点。平面图可以重新画成边不交叉的形式。

存储与搜索复杂度： 邻接矩阵空间为 $O(n^2)$；邻接表空间为 $O(n+M)$。一次 BFS 为 $O(n+M)$；从所有节点分别执行 BFS 为 $O(n(n+M))$。

6. 网络指标

以下距离公式先假设图连通、无向、无权，$d_{ij}$ 是最短距离。

$$\begin{aligned} L&=\frac{\sum_{i\ne j}d_{ij}}{n(n-1)},\\ \varepsilon_i&=\max_jd_{ij},\\ D&=\max_i\varepsilon_i,\\ R&=\min_i\varepsilon_i. \end{aligned}$$

度、接近与介数中心性：

$$\begin{aligned} C_D(i)&=\frac{k_i}{n-1},\\ C_C(i)&=\frac{n-1}{\sum_{j\ne i}d_{ij}},\\ C_B(i)&=\frac{2}{(n-1)(n-2)} \sum_{\substack{s<t\\s,t\ne i}}\frac{\sigma_{st}(i)}{\sigma_{st}}. \end{aligned}$$

这里 $\sigma_{st}$ 为最短路条数，$\sigma_{st}(i)$ 为其中内部经过 $i$ 的条数；介数公式要求 $n>2$。

谱中心性与 Katz： 入链中心性取 $B=A^{\mathsf T}$，无向图取 $B=A$。

$$\begin{aligned} B\boldsymbol x&=\rho(B)\boldsymbol x,\\ \boldsymbol x&=aB\boldsymbol x+\beta\boldsymbol 1,\\ \boldsymbol x&=\beta(I-aB)^{-1}\boldsymbol 1,\\ a&\ge0,\qquad a\rho(B)<1,\qquad\beta>0. \end{aligned}$$

PageRank：$0<d<1$，取行随机矩阵 $P_{ij}=A_{ij}/k_i^{\mathrm{out}}$；无出边节点的整行设为 $\boldsymbol v^{\mathsf T}$。

$$\begin{aligned} \boldsymbol p&=dP^{\mathsf T}\boldsymbol p+(1-d)\boldsymbol v,\\ \sum_i p_i&=1,\qquad v_i=1/n. \end{aligned}$$

聚类与传递性：$t_i$ 是经过节点 $i$ 的三角形数，$T$ 是全网三角形数。

$$\begin{aligned} C_i&=\frac{2t_i}{k_i(k_i-1)},\qquad k_i\ge2,\\ C_i&=0,\qquad k_i<2,\\ \overline C&=\frac1n\sum_iC_i,\\ C_{\mathrm{trans}}&=\frac{3T}{\sum_i\binom{k_i}{2}}. \end{aligned}$$

无连通三元组时，传递性约定为 $0$。$k$-core 通过反复剔除当前度小于 $k$ 的节点得到。

同配性：$r=\operatorname{Corr}_{\mathrm{edge}}(k_i,k_j)$；正值为同配，负值为异配。相关系数沿边端点统计，无向边计两个方向。

模块度与巨分量比例：

$$\begin{aligned} Q&=\sum_C\left[\frac{l_C}{M}-\left(\frac{K_C}{2M}\right)^2\right],\\ K_C&=\sum_{i\in C}k_i,\\ S&=|C_{\max}|/n. \end{aligned}$$

$l_C$ 为社群内部边数，$K_C$ 是该社群节点在原图中的度之和；模块度要求 $M>0$。$S$ 是最大分量占全部节点的比例。