第 06 章学习笔记：时序网络社区检测
第 06 章学习笔记：时序网络社区检测
配套译文：
内部译文（已落盘；proof-check 锚点与译文一致）。 本章把第 4 章的社区检测推广到时序网络：数据是 $T$ 个快照组成的邻接张量 $(A^1,\ldots,A^T)$，社区结构可以静态、也可以随时间马尔可夫演化。全章沿两条轴组织——成员结构（静态 vs 马尔可夫演化）与相互作用结构（时间独立 vs 马尔可夫）——6.1 建统一框架，6.2 处理"静态成员 + 马尔可夫交互"（恢复阈值、在线似然、谱方法、长时间跨度），6.3 处理"马尔可夫成员 + 时间独立交互"（VEM、时空图信念传播、在线半监督推断）。语义对象 9 个（1 定理 / 3 命题 / 2 引理 / 3 例 / 3 评注；Theorem 与 Lemma 共享计数器）、编号公式 (6.1)–(6.23)、算法块 5 个（Algorithm 15–19）、7 图 1 表；章末为"进一步阅读"（Further Notes，印刷页 170）与一条未来工作声明，本书无习题。第 1 章的高中互动数据集（Table 1.1、Figure 1.4/1.5）在 6.2.3 被正式处理，完成全书首个"现象 → 方法"回环。
1. 一句话定位
本章回答"社区随时间演化、或交互随时间相关时，第 4 章的静态方法哪里失效、怎么修"——统一框架（6.1：成员结构 $Z$ + 相互作用结构 $B$）先把文献中杂乱的时序模型归并成两轴四象限；随后沿"静态成员"轴（6.2）证明马尔可夫交互相对静态 SBM 带来信息增益（Proposition 6.1：恢复阈值由 $\rho$ 降为 $\rho T$ 量级），并把这一增益工程化为在线似然算法（Algorithm 15/16）、持久边加权谱聚类（Algorithm 17，由 Proposition 6.2 的 MLE 经 Lemma 6.1 的正则化模块度近似推出）与长时间跨度的经验转移率聚类（Algorithm 18，Theorem 6.2 保证 $T\to\infty$ 完全恢复）；再沿"马尔可夫成员"轴（6.3）处理标签漂移——后验不可分解逼出变分 EM（Lemma 6.3）与时空图信念传播，滞后问题（lagging problem）把每步在线推断化为"以前一步预测为噪声预言机"的半监督问题（Proposition 6.3，式 (6.21)–(6.23)，Algorithm 19），直接接上第 5 章 §5.4 的框架。
2. 本章导读
- 6.1 一般模型（印刷页 141–143）：成员结构 $Z\in[K]^{n\times T}$（行 $Z_{i\cdot}$ = 节点 $i$ 的标签演化，列 $Z_{\cdot t}$ = 时刻 $t$ 的全图标签）+ 相互作用结构 $B$（社区模式对之间交互模式 $x^{1:T}\in\{0,1\}^T$ 的分布族，式 (6.1)–(6.2)）。完全一般的模型参数爆炸，故 6.1.2 给出三条特化路线：静态成员（$B$ 退化为交互核 $f=(f_{k\ell})$，式 (6.3)）、时间独立交互（式 (6.4)）、马尔可夫成员（$\mathscr P$ 取马尔可夫链形式）。Example 6.1–6.3 是三个基准特例：独立交互 = $T$ 个独立静态 SBM；马尔可夫交互；均匀保持型马尔可夫成员（以概率 $r$ 保持、$1-r$ 均匀重选）。
- 6.2 静态成员（印刷页 143–160）：马尔可夫随机分块模型（成员静态 + 交互马尔可夫，式 (6.5) 的 $f_{\mathrm{in}}/f_{\mathrm{out}}$）。 - 6.2.1 理论：稀疏 regime（式 (6.6)–(6.7)，$\rho T$ 是"总信号量"）下的恢复阈值 Proposition 6.1——一致恢复的相变在 $\rho T\asymp 1/n$，强一致在 $\rho T\asymp\log n/n$，临界常数由含几何分布 Hellinger 散度的 $\tilde I$ 决定。与 Ch4 Example 4.1/4.2 对照：$T$ 个快照相当于把信号强度放大 $T$ 倍（Remark 6.1/6.2）。 - 6.2.2 方法：对数似然比矩阵 $M^t$（式 (6.8)）在马尔可夫交互下可递推 $M^t=M^{t-1}+\Delta^t$（$\Delta^t$ 只取 4 个值），得在线 Algorithm 15（参数已知）；参数未知时用经验转移率 (6.10)–(6.13) 在线估计 $P,Q$，得 Algorithm 16。Figure 6.1–6.3：似然法能纠正糟糕的谱初始化，且在每层期望度 $<1$ 的极稀疏 regime 仍可用。 - 6.2.3 谱方法：朴素时间聚合 $\sum_t\mathrm{Cut}(A^t,z)=\mathrm{Cut}(\sum_t A^t,z)$ 丢掉时间相关（$x_1=(0,1,0,0,0,0,1,0,0,1)$ vs $x_2=(0,0,1,1,1,0,0,0,0,0)$ 之例）；修正 = 计入持久边（$\mathrm{PerCut}$ = 割中持久边数）。理论化：DC 马尔可夫 SBM（式 (6.14)–(6.15)）的 MLE（Proposition 6.2）在稀疏极限下近似"新生边权 $\alpha$ + 持久边权 $\beta$"的正则化模块度最大化（Lemma 6.1，式 (6.16)–(6.17)），连续松弛即 Algorithm 17。数值：合成数据验证 $\beta$ 的方向（Figure 6.4）；高中数据集用 2011 年估计 $\hat P,\hat Q$ 预测 2012/2013 的 $\hat\alpha=2.9,\hat\beta=0.18$（Figure 6.5、Table 6.1）。 - 6.2.4 长时间跨度：$n$ 固定、$T\to\infty$ 时经验转移率 $\widehat P_{ab}(i,j)$ 一致收敛，把"同社区判别"化为相似图连通分量（Algorithm 18），不需预知 $K$ 且作为副产品估计它（Theorem 6.2；$P,Q$ 未知时对 $\widehat P(i,j)$ 二聚类，Remark 6.3）。
- 6.3 马尔可夫成员（印刷页 160–170）：成员按马尔可夫链漂移（式 (6.20)）、交互时间独立（$A^t_{ij}\sim\mathrm{Ber}(p_{z_{it}z_{jt}})$）。 - 6.3.1 推断：$Z$ 的后验因边依赖不可按节点分解，变分近似把它限制在节点级非齐次马尔可夫链族 $\mathbb Q_\tau$ 内，最大化 $J(\theta,\tau)=\mathbb E_{\mathbb Q}\log\mathbb P(A^{1:T},Z)+\mathcal H(\mathbb Q)$；VE 步与 M 步更新均有显式表达（Lemma 6.3）。 - 6.3.2 时空图信念传播：在"空间边 + 时间边"的时空图上同时传空间消息 $\psi^{i\to j}_k(t)$ 与时间消息 $\psi^{i(t)\to i(t+1)}_k$，$i\to j$ 更新不用 $j\to i$ 的消息以避免回声室效应；收敛后取边际最大标签。 - 6.3.3–6.3.4 在线推断：滞后问题——节点换社区后其历史交互污染当前标签，时间聚合方法必然失效；解法是把每步推断化为以前一步预测 $\hat z_{\cdot t-1}$ 为噪声预言机的半监督问题（呼应 Ch5 §5.4）。度校正模型下 MAP 估计量有显式形式（Proposition 6.3），连续松弛后化为约束线性系统 (6.22) + secular equation (6.23)，即 Algorithm 19（online-ssl）。Figure 6.6：$\eta=1$（静态）时 Algorithm 17 最优；$\eta<1$ 时 Algorithm 17 因滞后迅速退化而 Algorithm 19 保持高精度。Figure 6.7：$\lambda$ 在 $[0.1,1]$ 内稳健，过大则过度相信预言机；$\lambda_t$ 随 $t$ 自适应是章末声明的未来工作。
- 进一步阅读（印刷页 170）：BP 文献线（含"边持久反而使恢复更困难"的反例 Barucca et al. 2018）与交互参数随时间演化模型（含可辨识性警告），解读见本页 §16。
3. 本页使用方式
按你在正文中最可能卡住的位置直接跳转：
- Proposition 6.1 (i) 的条件在 OCR 里读不通（下标 $_pT$、游离的 $\gamma$） → 已按 PDF 订正：一致恢复"不存在"的条件是 $\rho T\lesssim 1/n$、"存在"的条件是 $\rho T\gg 1/n$（OCR 把 $\rho T$ 误读为下标 $p$ + 游离 $\gamma$）。订正后的完整陈述见 §9 卡片 T1。
- 找不到 Theorem 6.1 或 Lemma 6.2 → 本章 Theorem 与 Lemma 共享计数器（Lemma 6.1 → Theorem 6.2 → Lemma 6.3），是原书编号体系而非缺漏，见 §14 易混点 第 1 条。
- Lemma 6.1 的 $\gamma$ 公式代回验证对不上 → 你读得没错：原书陈述（无 $T-1$ 因子）与证明末尾（含 $T-1$）的两个 $\gamma$ 公式彼此不一致，且 $\bar m$ 漏掉了求和中的 $(T-1)$。按原书模块度定义和其自身 $\bar d_i$ 公式，局部代数唯一闭合为 $\gamma=(P_{01}-Q_{01})K/((T-1)S)$（$S$ 见证明卡）；辨析与按推导值进行的证明见 proof-lemma-6-1 的校勘提示。译文保留源文显示，不把该值冒充原书原式。
- $x_1$ 与 $x_2$ 的例子到底说明什么 → 两条交互序列都有 3 个 1（时间聚合无差别），但 $x_1$ 的 1 是孤立尖峰、$x_2$ 的 1 是连续段（2 次 $1\to1$ 转移）——转移结构携带社区信息，聚合把它抹掉。这是全章方法论的总动机，见 §14 第 2 条与 §15 公式卡片 F6。
- 6.2 与 6.3 的分界到底是哪条轴 → 6.2 = 成员静态 + 交互马尔可夫；6.3 = 成员马尔可夫 + 交互时间独立。"成员"与"交互"是两条独立的轴，组合关系见 §14 第 3 条与 §5 概念地图。
- VEM（6.3.1）和 BP（6.3.2）都在逼近同一个后验，区别是什么 → VEM 是优化：在变分族 $\mathbb Q_\tau$ 内最大化下界 $J$；BP 是消息传递：直接在时空图上迭代逼近边际 $\psi^i_k(t)$。见 §14 第 6 条。
- Lemma 6.3 只证了一个坐标的导数 → 其余坐标（M 步 $\hat\pi,\hat p$、初始分布 $\tau(i,k)$）的完整求导见 §11 补证卡；VE 步本身的完整推导见 proof-lemma-6-3。
- $\alpha$、$\rho$、$P$、$Q$ 在 6.2 和 6.3 里含义不同 → 本章符号复用严重（$\alpha$：谱权重 vs 成员初始分布；$\rho$：稀疏参数 vs 预言机错误率；$P$：边转移矩阵 vs 连边概率矩阵），对照表见 §14 第 4 条。
- Figure 6.7 图注的 $\alpha_{22}=2$ 是什么 → 交互权重下标只取 $\{0,1\}$，所以 $\alpha_{22}$ 越界；结合 Figure 6.6 的同一参数，可确定校勘读法为 $\alpha_{11}=2$。同一图注的 $\mu_2=0.02$ 只由相邻图注的 $\nu_1=0.02$ 支持为候选修正，源图注仍保留，见 §14 第 8 条。
4. 本章主线
| 推进层 | 要解决的问题 | 关键转折 | 后续用途 |
|---|---|---|---|
| 6.1 统一框架 | 时序社区模型术语爆炸，如何归并 | 成员结构 $Z$ × 相互作用结构 $B$ 两条轴；完全一般的 $B$ 有 $(KT)^2/2$ 个测度 ⇒ 必须特化（Example 6.1–6.3） | 6.2/6.3 按轴分治；快照张量记号 $A^{1:T}$ 服务全章 |
| 6.2.1–6.2.2 阈值与在线似然 | 静态成员下，$T$ 个相关快照比 1 个静态图多多少信息 | 信号量从 $\rho$ 变 $\rho T$（Prop 6.1，承接 Ch4 §4.4.3 的恢复分级）；对数似然比矩阵在马尔可夫交互下可递推 ⇒ 在线更新 $O(Kn^2T)$（Alg 15/16） | Alg 15/16 是 6.3.4 在线算法的雏形；极稀疏实验（Fig 6.3）验证 Remark 6.1 的"$\rho=1/n$ 也可恢复" |
| 6.2.3 谱方法 | 时间聚合丢失时间相关，谱方法如何用上马尔可夫结构 | $x_1$ vs $x_2$ 反例 ⇒ 持久边；DC 马尔可夫 SBM 的 MLE（Prop 6.2）≈ 新生/持久边加权的正则化模块度（Lemma 6.1）⇒ Alg 17 | 高中数据集回环（Fig 6.5、Table 6.1：$P_{11}-Q_{11}$ 大 ⇒ 持久边有信息）；权重机制被 6.3.4 的 (6.21) 继承 |
| 6.2.4 长时间跨度 | $T\to\infty$、$n$ 固定时能否免调参、免 $K$ | 遍历性 ⇒ 经验转移率一致收敛（式 (6.10)）；"同社区判别"= 相似图连通分量（Alg 18），$K$ 作为副产品输出 | Theorem 6.2 给出全章唯一的完全恢复定理；Remark 6.3 处理 $P,Q$ 未知 |
| 6.3 马尔可夫成员 | 标签随时间漂移时如何推断 | 后验不可按节点分解 ⇒ 变分 EM（Lemma 6.3）或时空图 BP；滞后问题 ⇒ 每步在线推断 = 噪声预言机 SSL（Prop 6.3 → (6.21)–(6.23) → Alg 19） | 直接调用 Ch5 §5.4 的松弛与 secular equation；Fig 6.6 展示 $\eta<1$ 时 Alg 17 失效、Alg 19 存活 |
5. 本章学习路线 / 概念地图
因果结构读法：两轴框架把问题分成两半；静态成员半边沿"理论阈值 → 在线似然 → 谱方法 → 长时间跨度"递进，每一步都在把马尔可夫交互的信息兑现成算法；马尔可夫成员半边先撞上后验不可分解（逼出 VEM/BP），再撞上滞后问题（逼出在线 SSL）。
① 框架（6.1）
成员结构 $Z\in[K]^{n\times T}$ × 相互作用结构 $B$
两轴：成员 静态/马尔可夫 × 交互 独立/马尔可夫（Ex 6.1–6.3）
成员结构 $Z\in[K]^{n\times T}$ × 相互作用结构 $B$
两轴：成员 静态/马尔可夫 × 交互 独立/马尔可夫（Ex 6.1–6.3）
→
② 静态成员（6.2）= Markov SBM
$f_{\mathrm{in}},f_{\mathrm{out}}$ 为马尔可夫链分布（式 (6.5)）
信号量 = $\rho T$：快照数放大信息（Prop 6.1，承接 Ch4 阈值语言）
$f_{\mathrm{in}},f_{\mathrm{out}}$ 为马尔可夫链分布（式 (6.5)）
信号量 = $\rho T$：快照数放大信息（Prop 6.1，承接 Ch4 阈值语言）
→
③ 兑现信息增益（6.2.2–6.2.4）
在线似然递推 $M^t=M^{t-1}+\Delta^t$（Alg 15/16）
持久边加权模块度（Prop 6.2 → Lemma 6.1 → Alg 17）
经验转移率 + 连通分量（Alg 18，Thm 6.2）
高中数据集：2011 估计权重 → 2012/2013 聚类（Fig 6.5）
在线似然递推 $M^t=M^{t-1}+\Delta^t$（Alg 15/16）
持久边加权模块度（Prop 6.2 → Lemma 6.1 → Alg 17）
经验转移率 + 连通分量（Alg 18，Thm 6.2）
高中数据集：2011 估计权重 → 2012/2013 聚类（Fig 6.5）
⇓
④ 马尔可夫成员（6.3）
标签漂移 $z_{i\cdot}\sim$ Markov 链（式 (6.20)），交互时间独立
后验 $\mathbb P(Z|A^{1:T})$ 因边依赖不可按节点分解
标签漂移 $z_{i\cdot}\sim$ Markov 链（式 (6.20)），交互时间独立
后验 $\mathbb P(Z|A^{1:T})$ 因边依赖不可按节点分解
⑤a 批量推断：VEM / 时空图 BP
变分族 $\mathbb Q_\tau$（节点级非齐次马尔可夫链），最大化 $J(\theta,\tau)$（Lemma 6.3）
BP：空间消息 + 时间消息，去回声室；收敛后取边际 argmax
变分族 $\mathbb Q_\tau$（节点级非齐次马尔可夫链），最大化 $J(\theta,\tau)$（Lemma 6.3）
BP：空间消息 + 时间消息，去回声室；收敛后取边际 argmax
⑤b 在线推断 = 半监督（6.3.3–6.3.4）
滞后问题 ⇒ 时间聚合失效；上一步预测 $\hat z_{\cdot t-1}$ = 噪声预言机
Prop 6.3 MAP → 松弛 (6.21) → 线性系统 (6.22) + secular (6.23) → Alg 19；接 Ch5 §5.4
滞后问题 ⇒ 时间聚合失效；上一步预测 $\hat z_{\cdot t-1}$ = 噪声预言机
Prop 6.3 MAP → 松弛 (6.21) → 线性系统 (6.22) + secular (6.23) → Alg 19；接 Ch5 §5.4
⑥ 全书位置：Ch4 提供恢复分级语言（一致/强一致，§4.4.3）、SBM 阈值基准（Example 4.1/4.2）与模块度-谱松弛工具（§4.4.2）；Ch5 §5.4 提供噪声预言机 SSL 的完整松弛技术；Ch1 的高中数据集在 6.2.3 被正式处理。章末 Further Notes 指出反方向结果：边持久也可能使恢复更困难（Barucca et al., 2018）。
6. 分层阅读路线
- 第一遍（主线，约 1.5 小时）：章首两段（时间信息为何不能被聚合掉）→ 6.1.1 的 $Z$/$B$ 定义 + 6.1.2 三个例子 → 6.2.1 Prop 6.1 陈述与 Remark 6.1/6.2（只记"$\rho T$ 替代 $\rho$"）→ 6.2.2 的 $M^t$ 递推与 Algorithm 15 框 → 6.2.3 的 $x_1$/$x_2$ 例子、持久边定义、Algorithm 17 框 → 6.3.3 滞后问题一段 → Figure 6.6 两 panel 对比。目标：能画出 §5 的因果图，说清两条轴和"信息增益"的兑现路线。
- 第二遍（证明精读，约 3 小时）：按依赖序读五组：① Prop 6.2（似然按 $\delta(z_i,z_j)$ 拆项 + §11 示性展开补证）；② Lemma 6.1（Taylor 近似 + 平稳分布算期望 + 模块度匹配，含 $\gamma$ 校勘）；③ Thm 6.2（马尔可夫链 CLT + 并集界，全章最短的完整证明）；④ Lemma 6.3（VEM 目标 $J$ 的结构 + VE 步求导）+ §11 其余坐标补证；⑤ Prop 6.3（Bayes + 复用 Prop 6.2 的拆项 + 因子 2 的来源）。Prop 6.1 书内无证明，读 §11 定位卡 即可。
- 第三遍（应用与实验逻辑）：按 Algorithm 15–19 的实现视角重读（$\Delta^t$ 四值预计算、$L=M^0Z$ 矩阵化、稀疏存储；Alg 16 的参数在线更新频率；Alg 17 的 $\alpha,\beta\ge0$ 限制；Alg 19 的 $\gamma_*$ 求根）；细读三段数值实验的设计逻辑：Fig 6.1（初始化敏感性）、Fig 6.4（$\beta$ 的方向与 $P_{11}\gtrless Q_{11}$ 的关系）、Table 6.1（用 2012 年 $P_{11}\approx Q_{11}$ 解释 Fig 6.5(a) 改进不明显）。
- 专题回看：学 Ch4 §4.4.3 时对照 Prop 6.1 与 Remark 6.1/6.2（§9 卡片 T1）；学 Ch4 §4.4.2 模块度-谱等价时回看 Lemma 6.1 的近似链；学 Ch5 §5.4 时对照 Prop 6.3 与 (6.21)–(6.23)（同样的二次型 + 预言机贴合项 + secular equation）；读 Ch1 §1.1 高中数据集时回看 6.2.3 数值节完成回环。
7. 初学者背景补充
本章默认的数学背景集中在六处，按首次出现顺序：
- 有限状态马尔可夫链（6.1.2 起）：$\{0,1\}$ 状态链由初始分布 $\mu$ 与 $2\times2$ 转移矩阵 $P$ 刻画，$P_{ab}=\mathbb P(x_{t+1}=b|x_t=a)$；序列概率 = $\mu_{x_1}\prod_t P_{x_{t-1}x_t}$。平稳分布 $\mu$ 满足 $\mu=\mu P$（Lemma 6.1 的"$\mu,\nu$ 是平稳分布"假设服务期望计算）；不可约非周期链的遍历性给出经验频率的 LLN 与 CLT（Theorem 6.2 引用 Billingsley 1961 的标准结果：$\sqrt{n_a}(\widehat P_{ab}-P_{ab})$ 渐近正态）。
- Hellinger / Rényi 散度（Prop 6.1）：$H^2(f,g)=1-\int\sqrt{fg}$；Ch4 Definition 4.3 的 Rényi 散度 $D_{1/2}=-2\log(1-H^2)$（见第 4 章笔记与术语表）。Prop 6.1 的 $\tilde I$ 是两个马尔可夫链分布间 Rényi 散度 Taylor 展开的主项；其中 $H_{11}^2=1-\frac{\sqrt{(1-P_{11})(1-Q_{11})}}{1-\sqrt{P_{11}Q_{11}}}$ 是参数 $P_{11},Q_{11}$ 的两个几何分布间的 Hellinger 散度（几何分布来自"边保持活跃时长"）。
- EM 与变分推断（6.3.1）：含潜变量 $Z$ 的似然最大化用 EM：E 步求 $\mathbb P(Z|A)$、M 步更新参数；E 步不可算时把后验限制在易处理的分布族 $\mathcal Q$ 内，等价于最大化证据下界 $J(\theta,\tau)=\mathbb E_{\mathbb Q}\log\mathbb P(A,Z)+\mathcal H(\mathbb Q)$（= ELBO；$J=\log\mathbb P(A)-\mathrm{KL}(\mathbb Q\|\mathbb P(Z|A))$，故最大化 $J$ 同时逼近似然与后验）。本章取 $\mathcal Q$ 为节点级非齐次马尔可夫链族。
- 信念传播（6.3.2）：树上精确、一般图上近似的边际推断消息传递；关键是"排除回送"原则——$i\to j$ 的消息不使用 $j\to i$ 的消息（去回声室）。只需算法层面理解，理论背景见 Further Notes 的综述（Decelle et al., 2011；Moore, 2017）。
- 模块度与谱松弛（6.2.3）：正则化模块度 $\mathcal M(W,z,\gamma)=\sum_{i,j}\delta(z_i,z_j)(W_{ij}-\gamma\frac{d_id_j}{2m})$（式 (4.21)）的最大化是 NP-hard，连续松弛后化为归一化谱聚类（Ch4 §4.4.2，见第 4 章笔记）。本章 Lemma 6.1 把时序 MLE 近似成这个标准形式，从而直接调用 Ch4 的机器（Algorithm 17）。
- 噪声预言机半监督框架（6.3.3–6.3.4）：Ch5 §5.4 的 DC-SBM + 噪声 oracle 设定（$\eta_1/\eta_0$、MAP → 二次型松弛 → 约束线性系统 → secular equation，见第 5 章笔记）。本章 (6.21)–(6.23) 是同一套推导在"上一步预测 = oracle"下的复用，原书明确说 "mimicking the reasoning of Section 5.4.2"。
8. 核心对象与符号表
| 符号 | 含义 | 本章出处 | 在推导中的角色 |
|---|---|---|---|
| $A^t$，$A^{1:T}$ | 时刻 $t$ 的快照邻接矩阵；观测张量 | 6.1.1 | 全章数据形式；$A^t\in\{0,1\}^{n\times n}$ |
| $T$，$n$，$K$ | 快照数、节点数、社区数 | 6.1.1 | 6.2 的渐近是 $n,T\to\infty$；6.2.4 是 $n$ 固定 $T\to\infty$ |
| $Z\in[K]^{n\times T}$，$Z_{i\cdot}$，$Z_{\cdot t}$ | 成员结构矩阵；节点 $i$ 的标签演化；时刻 $t$ 的全图标签 | 6.1.1 | 两轴划分的载体：静态 = 各列相同 |
| $B_{k^{1:T},\ell^{1:T}}(x^{1:T})$ | 社区模式对间交互模式的概率测度（式 (6.2)） | 6.1.1 | 最一般相互作用结构；特化为核 $f_{k\ell}$（式 (6.3)） |
| $f_{\mathrm{in}},f_{\mathrm{out}}$ | 同质模型的同/异社区交互分布（式 (6.5)） | 6.2.1 | 马尔可夫链分布 $\mu_{x_1}\prod P_{x_{t-1}x_t}$ / $\nu_{x_1}\prod Q_{x_{t-1}x_t}$ |
| $\mu,\nu$；$P,Q$ | 同/异社区的初始分布与 $\{0,1\}$ 转移矩阵 | 6.2.1 | 6.2 全部公式的主角；$P_{11}$ = 同社区边保持概率 |
| $\rho$；$u,\upsilon,p_{01},q_{01}$ | 稀疏参数（式 (6.6)）；$\rho$ 的常数因子（式 (6.7)） | 6.2.1 | 信号量 = $\rho T$；Prop 6.1 阈值用它表述 |
| $\tilde I$，$H_{11}^2$ | Rényi 散度展开主项；几何分布间 Hellinger 散度 | Prop 6.1 | 临界 regime 相变常数：$\tau\tilde I>K$ 可强一致恢复 |
| $M^t_{ij}$，$\Delta^t_{ij}$ | 累积对数似然比 $\log f_{\mathrm{in}}/f_{\mathrm{out}}$（式 (6.8)）；单步增量 $\log P/Q$ | 6.2.2 | 在线递推 $M^t=M^{t-1}+\Delta^t$；$\Delta^t$ 只取 4 值 |
| $L^t_{i,k}$ | 节点 $i$ 划入社区 $k$ 的得分（式 (6.9)） | 6.2.2 | $\hat z_i=\arg\max_k L_{i,k}$；可矩阵化 $L=M^0Z$ |
| $n_{ab}(i,j)$，$\widehat P_{ab}(i,j)$ | $a\to b$ 转移计数；经验转移率（式 (6.10)） | 6.2.2/6.2.4 | 遍历性 ⇒ $T\to\infty$ 一致估计 $P(i,j)$；Alg 16/18 的输入 |
| $A_{\mathrm{pers}}^t=A^{t-1}\odot A^t$；$A_{\mathrm{new}}^t$；$A_{\mathrm{old}}^t$ | 持久边 / 新生边 / 消失边邻接矩阵 | 6.2.3/6.3.4 | 加权谱方法的三个成分（$\odot$ = 逐元乘积） |
| $W$；$\alpha,\beta$；$\gamma$ | 时序加权图（式 (6.16)）；新生/持久边权重（式 (6.17)）；模块度分辨率参数 | 6.2.3 | Alg 17 的输入；$\alpha=\log\frac{P_{01}}{Q_{01}}+\log\frac{1-P_{11}}{1-Q_{11}}$，$\beta=\log\frac{P_{11}}{Q_{11}}$ |
| $\theta_i$ | 度校正参数（$\sum_{z_i=k}\theta_i=|\{z_i=k\}|$ 归一化） | 6.2.3/6.3.4 | 只乘在"发起"概率上（$\mu_1,\nu_1,P_{01},Q_{01}$），不乘 $P_{11},Q_{11}$ |
| $\rho_a^{\theta_i\theta_j}$，$\ell_{ab}^{\theta_i\theta_j}$，$R_{ab}^{\theta_i\theta_j}$ | MLE 拆项系数：$\rho_a=\log\mu_a$ 型；$\ell_{ab}=R_{ab}-R_{00}$，$R_{ab}=\log(P_{ab}/Q_{ab})$ | Prop 6.2/Lemma 6.1 | 似然分解的代数载体；稀疏极限下 $\ell_{01}\approx\log\frac{P_{01}}{Q_{01}}$ 等 |
| $\pi$；$\alpha$（6.3） | 成员标签的 $K\times K$ 转移矩阵与初始分布（式 (6.20)） | 6.3 | 与 6.2 的谱权重 $\alpha$ 同名不同义（§14 第 4 条） |
| $\eta$ | 标签保持概率：$\pi=\eta I_K+\frac{1-\eta}{K}1_K1_K^{\top}$ | 6.3.4 | $\eta=1$ 退化为静态成员（Fig 6.6 两 panel 的分界） |
| $\tau(i,k)$，$\tau(t,i,k,\ell)$，$\tau_{\mathrm{marg}}(t,i,k)$ | 变分参数：初始分布、转移概率、边际 | 6.3.1 | $\mathbb Q_\tau$ 族的坐标；Lemma 6.3 给出其 argmax 显式值 |
| $J(\theta,\tau)$，$\mathcal H(\mathbb Q)$ | VEM 目标 = 期望对数联合 + 熵 | 6.3.1 | ELBO；VE 步对 $\tau$、M 步对 $\theta=(\pi,P)$ 交替最大化 |
| $\psi_k^i(t)$，$\psi_k^{i\to j}(t)$，$\psi^{i(t)\to i(t+1)}$ | BP 边际与空间/时间消息 | 6.3.2 | $\hat z_{it}=\arg\max_k\psi_k^i(t)$ |
| $s$；$\rho$（6.3.4）；$\lambda$ | 噪声预言机；错误率 $\mathbb P(s_i\ne z_{it})$；$\lambda=\log\frac{1-\rho}{\rho}$ | 6.3.4 | $\rho$ 与 6.2 的稀疏参数同名不同义；$\lambda$ 控制贴合预言机的强度（Fig 6.7） |
9. 关键定理卡片
本章 6 个编号定理类对象：Prop 6.1（阈值，书内无证明）、Prop 6.2 与 Lemma 6.1（MLE → 模块度）、Thm 6.2（长时间跨度完全恢复）、Lemma 6.3（VEM 更新）、Prop 6.3（在线 MAP）。
卡片 T1：Proposition 6.1（稀疏 Markov SBM 的恢复阈值）
- 条件：同质 Markov SBM（$n\gg1$，$K\asymp1$，$T\gg1$），$f_{\mathrm{in}},f_{\mathrm{out}}$ 为式 (6.5) 的马尔可夫链分布且满足稀疏参数化 (6.7)（$\rho T\ll1$）；$P_{11},Q_{11}$ 为常数、$(P_{11},Q_{11})\ne(1,1)$、$(p_{01},P_{11})\ne(q_{01},Q_{11})$。记 $\tilde I=(\sqrt{p_{01}}-\sqrt{q_{01}})^2+2\sqrt{p_{01}q_{01}}\,H_{11}^2$，$H_{11}^2=1-\dfrac{\sqrt{(1-P_{11})(1-Q_{11})}}{1-\sqrt{P_{11}Q_{11}}}$（两个几何分布间的 Hellinger 散度）。
- 结论（(i) 已按 PDF 订正 OCR 误读）：(i) 一致估计量在 $\rho T\lesssim 1/n$ 时不存在、在 $\rho T\gg 1/n$ 时存在；(ii) 强一致估计量在 $\rho T\ll\log n/n$ 时不存在、在 $\rho T\gg\log n/n$ 时存在；(iii) 临界 regime $\rho T=(1+o(1))\tau\log n/n$ 下，$\tau\tilde I<K$ 不可强一致恢复、$\tau\tilde I>K$ 可以。
- 用途：本章理论基准——与 Ch4 Example 4.1/4.2（静态 SBM 阈值 $\rho\gg 1/n$、$\rho\asymp\log n/n$）对照，$T$ 个快照把信号从 $\rho$ 放大到 $\rho T$（Remark 6.1：$\rho=1/n$ 时 $T=\omega(1)$ 即可一致恢复；Remark 6.2：临界 regime 与静态 SBM 完全同构）。Figure 6.1 的 $T^*_{\mathrm{theo}}$ 即由 (iii) 解出。
- 证明入口：原书明确外包（Avrachenkov et al., 2022），书内无证明 → §11 定位卡。
卡片 T2：Proposition 6.2（DC Markov SBM 的 MLE）
- 条件：度校正马尔可夫 SBM（式 (6.14)–(6.15)）：标签均匀、交互核 $F^{\theta_i\theta_j}_{z_iz_j}$ 为 $\mu^{\theta_i\theta_j}$/$\nu^{\theta_i\theta_j}$ 初始 + $P^{\theta_i\theta_j}$/$Q^{\theta_i\theta_j}$ 转移（度校正只乘发起概率）；$\max_{i,j}\theta_i\theta_j\delta\le1$，$\delta=\max\{\mu_1,\nu_1,P_{01},Q_{01}\}$。
- 结论：MLE 是最大化一个按 $\delta(z_i,z_j)$ 拆项的显式目标——同社区对的贡献含初值项 $A^1_{ij}(\rho_1-\rho_0)+\rho_0$、边界修正 $(A^1_{ij}-A^T_{ij})\ell_{10}$，与逐快照项 $(\ell_{01}+\ell_{10})(A^t_{ij}-A^{t-1}_{ij}A^t_{ij})+\ell_{11}A^{t-1}_{ij}A^t_{ij}-\log\frac{Q_{00}}{P_{00}}$（系数均带 $\theta_i\theta_j$ 上标）。
- 用途：6.2.3 的方法论枢纽——目标中的 $A^{t-1}_{ij}A^t_{ij}$ 项即持久边，$A^t_{ij}-A^{t-1}_{ij}A^t_{ij}$ 即新生边；$T$ 大时忽略边界项， Lemma 6.1 把它近似成正则化模块度，Algorithm 17 由此而来。
- 证明入口：proof-proposition-6-2；其中 "Simple calculations" 一步由 §11 补证卡 展开。
卡片 T3：Lemma 6.1（MLE ≈ 正则化模块度）
- 条件：$P^{\theta_i\theta_j},Q^{\theta_i\theta_j}$ 非退化，$\mu^{\theta_i\theta_j},\nu^{\theta_i\theta_j}$ 为各自平稳分布；稀疏设定 $P_{01},Q_{01}=o(1)$。
- 结论：MLE 近似最大化 $\mathcal M(W,z,\gamma)$，其中 $W=\sum_{t=2}^T(\alpha A_{\mathrm{new}}^t+\beta A_{\mathrm{pers}}^t)$（式 (6.16)），$\alpha=\log\frac{P_{01}}{Q_{01}}+\log\frac{1-P_{11}}{1-Q_{11}}$、$\beta=\log\frac{P_{11}}{Q_{11}}$（式 (6.17)），$\gamma$ 为显式常数；原书两处 $\gamma$ 与 $\bar m$ 的印刷不一致，按定义和求和唯一闭合为 $\gamma=(P_{01}-Q_{01})K/((T-1)S)$，见证明卡校勘提示。
- 用途：把时序聚类接入 Ch4 §4.4.2 的"模块度最大化 ⇔ 谱松弛"机器 ⇒ Algorithm 17；解释为何 $\beta$ 的符号方向应跟 $P_{11}-Q_{11}$ 一致（Figure 6.4 的实验事实）；高中数据集正文/图例采用 $\hat\alpha=2.9,\hat\beta=0.18$，但 Table 6.1 的 2011 行印作 $0.58$（可由比值列与正文确定为排印错误），2013 行的 $4.5,0.07$ 又与表内概率代入 (6.17) 的约 $4.16,0.47$ 冲突；后者因缺少未四舍五入数据而采用双分支复现，不作唯一修正。
- 证明入口：proof-lemma-6-1。
卡片 T4：Theorem 6.2（Algorithm 18 的完全恢复）
- 条件：同质 Markov SBM；$n$ 固定、$T\to\infty$；$P,Q$ 已知；演化非静态；$P\ne Q$。
- 结论：$T\to\infty$ 时 Algorithm 18 以趋于 1 的概率把每个节点分类正确（完全恢复），同时正确输出 $\widehat K=K$。
- 用途：全章唯一的完全恢复定理；与 Prop 6.1（$n,T$ 同发散的阈值）互补——这里是"$n$ 固定、时间无限"的遍历性 regime；算法免谱分解、免 $K$，Remark 6.3 处理 $P,Q$ 未知（对 $\widehat P(i,j)$ 二聚类）。
- 证明入口：proof-theorem-6-2。
卡片 T5：Lemma 6.3（VEM 更新的显式形式）
- 条件：马尔可夫成员模型（式 (6.20)），$K$ 已知，$\alpha$ 为 $\pi$ 的平稳分布；变分族 $\mathbb Q_\tau$ = 节点级非齐次马尔可夫链。
- 结论：$\arg\max_\tau J$ 给出 $\widehat\tau(t,i,k,\ell)\propto\pi_{k\ell}\prod_j\prod_{k'}\mathrm{Ber}(p_{\ell k'})(A^t_{ij})^{\widehat\tau_{\mathrm{marg}}(t,j,k')}$；$\arg\max_\theta J$ 给出 $\widehat\pi_{k\ell}\propto\sum_{t,i}\tau_{\mathrm{marg}}(t-1,i,k)\tau(t,i,k,\ell)$ 与 $\widehat p_{k\ell}$ = 期望意义下的同/异社区连边频率之比（经验二值加权比）。
- 用途：6.3.1 的算法内核——VE/M 两步都有闭式更新，使 VEM 可实际迭代；$\widehat p_{k\ell}$ 的形式就是"软标签加权的有向连边率"。
- 证明入口：proof-lemma-6-3（VE 步）+ §11 补证卡（M 步与 $\tau(i,k)$）。
卡片 T6：Proposition 6.3（在线学习的 MAP 估计量）
- 条件：6.3.4 的度校正马尔可夫成员模型；$s\in[K]^n$ 为时刻 $t$ 标签的噪声预言机，与观测 $A$ 独立，错误率 $\rho=\mathbb P(s_i\ne z_{it})$ 对所有节点相同；先验均匀（$\alpha=\frac1K1_K$，$\pi=\eta I_K+\frac{1-\eta}{K}1_K1_K^{\top}$）。
- 结论：MAP 估计 $\hat z_{\cdot t}=\arg\max_z\mathbb P(z|A^t,A^{t-1},s)$ 等价于最大化"同社区对的马尔可夫转移对数似然比项（新生/消失/持久三类边，系数 $\ell_{01},\ell_{10},\ell_{11}$）+ $2\lambda\sum_i1(z_i=s_i)$"，$\lambda=\log\frac{1-\rho}{\rho}$。
- 用途：把 6.3.3 的"上一步预测 = 噪声预言机"思想变成显式目标；与 Ch5 Prop 5.1 同构（图项 + 预言机贴合项），其连续松弛即 (6.21)–(6.23) ⇒ Algorithm 19。
- 证明入口：proof-proposition-6-3。
10. 关键定理完整证明
本章书内带证明的对象共 5 个，按原书顺序给出完整证明（原书跳步直接并入）；Proposition 6.1 书内无证明，见 §11 定位卡。
完整证明Proposition 6.2（DC Markov SBM 的 MLE，式 (6.14)–(6.15)）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：设 $\rho_a^{\theta_i\theta_j}=\log\dfrac{\mu_a^{\theta_i\theta_j}}{\nu_a^{\theta_i\theta_j}}$、$R_{ab}^{\theta_i\theta_j}=\log\dfrac{P_{ab}^{\theta_i\theta_j}}{Q_{ab}^{\theta_i\theta_j}}$、$\ell_{ab}^{\theta_i\theta_j}=R_{ab}^{\theta_i\theta_j}-R_{00}^{\theta_i\theta_j}$（$a,b\in\{0,1\}$）。则模型 (6.14)–(6.15) 的 MLE 是使下式最大的社区指派 $\hat z$：
$$\sum_{\substack{i,j\\z_i=z_j}}\Big\{A^1_{ij}\big(\rho_1^{\theta_i\theta_j}-\rho_0^{\theta_i\theta_j}\big)+\rho_0^{\theta_i\theta_j}+\big(A^1_{ij}-A^T_{ij}\big)\ell_{10}^{\theta_i\theta_j}\Big\}+\sum_{\substack{i,j\\z_i=z_j}}\sum_{t=2}^T\Big\{\big(\ell_{01}^{\theta_i\theta_j}+\ell_{10}^{\theta_i\theta_j}\big)\big(A^t_{ij}-A^{t-1}_{ij}A^t_{ij}\big)+\ell_{11}^{\theta_i\theta_j}A^{t-1}_{ij}A^t_{ij}-\log\frac{Q_{00}^{\theta_i\theta_j}}{P_{00}^{\theta_i\theta_j}}\Big\}.$$
**依赖工具**：时间马尔可夫性（似然 = 初值 × 逐转移，式 (6.5)/(6.15) 的结构）；示性函数恒等式 $\delta(z_i,z_j)$ 拆项（与 Ch4 Prop 4.4 同款代数）；两个初等展开（[§11 补证卡](#proof-check-6-2-3-mle-indicator-expansion)）。
**证明思路**：对数似然按时间马尔可夫性拆成"初值项 + 逐转移项"；每项再把 $z_i=z_j$（核为 $\mu/P$）与 $z_i\ne z_j$（核为 $\nu/Q$）分开——后者不含 $z$，吸收进常数 $c(A)$；最后用两个示性展开把"$\sum_a\delta(A^1,a)\rho_a$"与"$\sum_{a,b}\delta\delta R_{ab}$"写成 $A^1,A^{t-1},A^t,A^{t-1}A^t$ 的线性式，按 $A^{t-1}A^t$（持久）、$A^t-A^{t-1}A^t$（新生）归并即得。
**完整证明**：
1. **时间分解**：由 (6.14)–(6.15) 的马尔可夫结构，
$$\log\mathbb P(A|z,\theta)=\log\mathbb P(A^1|z,\theta)+\sum_{t=2}^T\log\mathbb P(A^t|A^{t-1},z,\theta).$$
2. **初值项按社区关系拆项**：$z_i=z_j$ 时交互分布为 $\mu^{\theta_i\theta_j}$，否则为 $\nu^{\theta_i\theta_j}$，故
$$\log\mathbb P(A^1|z,\theta)=\frac12\sum_{i,j}\sum_a\delta(A^1_{ij},a)\Big(\delta(z_i,z_j)\rho_a^{\theta_i\theta_j}+\log\nu_a^{\theta_i\theta_j}\Big)=\frac12\sum_{i,j}\delta(z_i,z_j)\sum_a\delta(A^1_{ij},a)\rho_a^{\theta_i\theta_j}+c_1(A),$$
其中 $c_1(A)=\frac12\sum_{i,j}\log\nu_{A^1_{ij}}^{\theta_i\theta_j}$ 与 $z$ 无关。
3. **转移项同理**：以 $R_{ab}$ 记对数似然比，
$$\log\mathbb P(A^t|A^{t-1},z,\theta)=\frac12\sum_{i,j}\delta(z_i,z_j)\sum_{a,b}\delta(A^{t-1}_{ij},a)\delta(A^t_{ij},b)R_{ab}^{\theta_i\theta_j}+c_t(A),$$
$c_t(A)$ 与 $z$ 无关；记 $c(A)=\sum_tc_t(A)$。
4. **初等展开**（原书 "Simple calculations"，完整验证见 [§11 补证卡](#proof-check-6-2-3-mle-indicator-expansion)）：
$$\sum_a\delta(A^1_{ij},a)\rho_a=A^1_{ij}(\rho_1-\rho_0)+\rho_0;$$
$$\sum_{a,b}\delta(A^{t-1}_{ij},a)\delta(A^t_{ij},b)R_{ab}=R_{00}+A^{t-1}_{ij}\ell_{10}+A^t_{ij}\ell_{01}+A^{t-1}_{ij}A^t_{ij}(\ell_{11}-\ell_{01}-\ell_{10}),$$
其中用到 $\ell_{ab}=R_{ab}-R_{00}$（故 $R_{10}-R_{00}=\ell_{10}$，$R_{11}-R_{01}-R_{10}+R_{00}=\ell_{11}-\ell_{01}-\ell_{10}$；系数上标 $\theta_i\theta_j$ 省略未写）。
5. **归并成持久/新生边形式**：把第 4 步第二式对 $t=2,\dots,T$ 求和。注意 $A^{t-1}_{ij}\ell_{10}$ 与 $A^t_{ij}\ell_{10}$ 的指标平移关系：
$$\sum_{t=2}^T A^{t-1}_{ij}\ell_{10}=\sum_{t=2}^T A^t_{ij}\ell_{10}+A^1_{ij}\ell_{10}-A^T_{ij}\ell_{10}.$$
于是对每个同社区对 $(i,j)$，转移部分贡献
$$\sum_{t=2}^T\Big\{\ell_{10}A^t_{ij}+\ell_{01}A^t_{ij}+(\ell_{11}-\ell_{01}-\ell_{10})A^{t-1}_{ij}A^t_{ij}+R_{00}\Big\}+\big(A^1_{ij}-A^T_{ij}\big)\ell_{10},$$
而 $\ell_{10}A^t+\ell_{01}A^t+(\ell_{11}-\ell_{01}-\ell_{10})A^{t-1}A^t=(\ell_{01}+\ell_{10})(A^t-A^{t-1}A^t)+\ell_{11}A^{t-1}A^t$（拆出新生边 $A^t-A^{t-1}A^t$ 与持久边 $A^{t-1}A^t$），且 $R_{00}=-\log\frac{Q_{00}}{P_{00}}$。
6. **合并初值项**：把第 4 步第一式（初值）与第 5 步的边界修正 $(A^1-A^T)\ell_{10}$ 合写，再对同社区对求和、补上与 $z$ 无关的 $c(A)$，即得目标式（原书陈述中把 $\frac12$ 吸收为对有序对 $i,j$ 求和）。$\square$
**闭合检查**：最大化目标只含 $z_i=z_j$ 的示性项与数据量（$A^1,A^{t-1}A^t,A^t-A^{t-1}A^t$），其余全部吸收进 $c(A)$——$z$ 只通过"哪些对算同社区"进入目标，这正是模块度型目标的形状，也是 Lemma 6.1 近似的起点。常见误用：忘记 $\ell_{ab}=R_{ab}-R_{00}$ 的**相对**定义（第 5 步归并时 $R_{00}$ 项不能丢，它给出 $-\log\frac{Q_{00}}{P_{00}}$）。
完整证明Lemma 6.1（稀疏极限下 MLE ≈ 正则化模块度，式 (6.16)–(6.18)）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：在 $P^{\theta_i\theta_j},Q^{\theta_i\theta_j}$ 非退化、$\mu^{\theta_i\theta_j},\nu^{\theta_i\theta_j}$ 为各自平稳分布、且 $P_{01},Q_{01}=o(1)$ 的条件下，Prop 6.2 的 MLE（忽略边界项后）近似等价于最大化正则化模块度 $\mathcal M(W,z,\gamma)=\sum_{i,j}\delta(z_i,z_j)\big(W_{ij}-\gamma\frac{d_id_j}{2m}\big)$，其中
$$W=\sum_{t=2}^T\big(\alpha A_{\mathrm{new}}^t+\beta A_{\mathrm{pers}}^t\big),\qquad \alpha=\log\frac{P_{01}}{Q_{01}}+\log\frac{1-P_{11}}{1-Q_{11}},\qquad \beta=\log\frac{P_{11}}{Q_{11}}.$$
**依赖工具**：一阶 Taylor $\log(1-x)=-x+o(x)$（$x=o(1)$）；平稳分布定义（$\mu_1$ 同时是"边出现"的稳态概率）；标签均匀 + $\theta$ 归一化（每社区 $\sum\theta_i=$ 社区大小）下的期望计数；Ch4 式 (4.21) 的正则化模块度定义。
**证明思路**：稀疏性使所有 $\theta_i\theta_j$ 上标的对数似然比塌缩为不带 $\theta$ 的常数（$\ell_{01}\approx\log\frac{P_{01}}{Q_{01}}$ 等），$-\log\frac{Q_{00}^{\theta_i\theta_j}}{P_{00}^{\theta_i\theta_j}}$ 一阶展开成 $\theta_i\theta_j(P_{01}-Q_{01})$；目标于是变成 (6.18)：逐对贡献 = 加权邻接 $\tilde a^t_{ij}$ 减去 $\theta_i\theta_j(P_{01}-Q_{01})$。再用平稳分布算 $W$ 的期望度 $\bar d_i$ 与总权 $\bar m$，把 $\theta_i\theta_j(P_{01}-Q_{01})$ 匹配成模块度零模型项 $\gamma\frac{\bar d_i\bar d_j}{2\bar m}$。
**完整证明**：
1. **稀疏 Taylor 近似**：$P_{01},Q_{01}=o(1)$ 时
$$\log\frac{1-\theta_i\theta_jQ_{01}}{1-\theta_i\theta_jP_{01}}=\theta_i\theta_j(P_{01}-Q_{01})+o(P_{01}^2+Q_{01}^2),$$
且 $\ell_{01}^{\theta_i\theta_j}=\log\frac{\theta_i\theta_jP_{01}}{\theta_i\theta_jQ_{01}}-\log\frac{1-\theta_i\theta_jP_{01}}{1-\theta_i\theta_jQ_{01}}\approx\log\frac{P_{01}}{Q_{01}}$（第二项为 $O(\theta_i\theta_j(P_{01}-Q_{01}))$，被主导项 $\log\frac{P_{01}}{Q_{01}}$ 吸收）；同理 $\ell_{10}^{\theta_i\theta_j}\approx\log\frac{1-P_{11}}{1-Q_{11}}$（注意 $P_{10}=1-P_{11}$ 且 $P_{11}$ 不带度校正），$\ell_{11}^{\theta_i\theta_j}\approx\log\frac{P_{11}}{Q_{11}}$。
2. **目标化简为 (6.18)**：把第 1 步代入 Prop 6.2 的目标（$T$ 大忽略边界项）：$(\ell_{01}+\ell_{10})\approx\alpha$、$\ell_{11}\approx\beta$，常数项 $-\log\frac{Q_{00}^{\theta_i\theta_j}}{P_{00}^{\theta_i\theta_j}}\approx-\theta_i\theta_j(P_{01}-Q_{01})$，得最大化
$$\sum_{t=2}^T\sum_{i,j}\delta(z_i,z_j)\Big(\tilde a^t_{ij}-\theta_i\theta_j(P_{01}-Q_{01})\Big),\qquad \tilde a^t_{ij}=\alpha\,(A_{\mathrm{new}}^t)_{ij}+\beta\,(A_{\mathrm{pers}}^t)_{ij}.$$
3. **期望权重（平稳性）**：$\mu$ 是 $P$ 的平稳分布 ⇒ 任意时刻 $\mathbb P(A^t_{ij}=1)=\theta_i\theta_j\mu_1$（同社区）；新生边要求"上一时刻 0、这一时刻 1"，稳态下概率 $\theta_i\theta_j\mu_1(1-P_{11})$；持久边要求两时刻皆 1，概率 $\theta_i\theta_j\mu_1P_{11}$。异社区把 $\mu_1,P_{11}$ 换成 $\nu_1,Q_{11}$。故
$$\mathbb E W_{ij}=\begin{cases}(T-1)\,\theta_i\theta_j\mu_1\big(\alpha(1-P_{11})+\beta P_{11}\big),&z_i=z_j,\\ (T-1)\,\theta_i\theta_j\nu_1\big(\alpha(1-Q_{11})+\beta Q_{11}\big),&z_i\ne z_j.\end{cases}$$
4. **期望度与总权**：标签均匀（每社区约 $n/K$ 个节点）+ $\theta$ 归一化（$\sum_{z_j=k}\theta_j=n/K$）⇒
$$\bar d_i=\sum_j\mathbb E W_{ij}=(T-1)\,\theta_i\,n\,\frac{S}{K},\qquad S:=\mu_1\big(\alpha(1-P_{11})+\beta P_{11}\big)+(K-1)\nu_1\big(\alpha(1-Q_{11})+\beta Q_{11}\big),$$
$$\bar m=\frac12\sum_i\bar d_i=\frac{(T-1)n^2}{2}\cdot\frac{S}{K}\quad(\text{用到 }\textstyle\sum_i\theta_i=n).$$
5. **匹配零模型项**：把 $\theta_i\theta_j(P_{01}-Q_{01})$ 写成 $\gamma\dfrac{\bar d_i\bar d_j}{2\bar m}$ 的形状。由上式
$$\frac{\bar d_i\bar d_j}{2\bar m}=\frac{(T-1)^2\theta_i\theta_jn^2S^2/K^2}{(T-1)n^2S/K}=(T-1)\,\theta_i\theta_j\,\frac{S}{K},$$
故**使恒等式闭合的取值是**
$$\gamma=\frac{(P_{01}-Q_{01})\,K}{(T-1)\,S}.$$
代回第 2 步：(6.18) $=\sum_{i,j}\delta(z_i,z_j)\big(W_{ij}-\gamma\frac{\bar d_i\bar d_j}{2\bar m}\big)$（期望意义下），即 $\mathcal M(W,z,\gamma)$ 的期望版本；用经验度 $d_i,m$ 替代期望度即得结论。$\square$
**闭合检查**：$z$ 只经 $\delta(z_i,z_j)$ 进入，$W$ 把马尔可夫结构压缩成两个权重——这正是 Ch4 §4.4.2 可谱松弛的标准形，Algorithm 17 随之合法。注意 $\beta=\log(P_{11}/Q_{11})$ 的符号跟随 $P_{11}-Q_{11}$：同社区边更持久（$P_{11}>Q_{11}$）时 $\beta>0$ 应给持久边正权重，与 Figure 6.4 的实验方向一致。
> 校勘提示（对照原书文件页 164–165 / 印刷页 155–156）：原书对 $\gamma$ 给了两个**彼此不一致**的印刷版本——Lemma 陈述中为 $\gamma=(P_{01}-Q_{01})\frac{\alpha(\mu_1+(K-1)\nu_1)+(\beta-\alpha)(\mu_1P_{11}+(K-1)\nu_1Q_{11})}{K}$（无 $T-1$ 因子；花括号部分恰等于 $S$），证明末尾为 $\gamma=(P_{01}-Q_{01})(T-1)\frac{S}{K}$（多一个 $T-1$）；且证明中 $\bar m$ 印作 $\frac{n^2}{2}\frac{S}{K}$，比按其自身 $\bar d_i$ 公式求和的结果少一个 $T-1$。按第 5 步的闭合计算，正确的 $\bar m$ 是 $\frac{(T-1)n^2S}{2K}$，从而恒等式 $\theta_i\theta_j(P_{01}-Q_{01})=\gamma\frac{\bar d_i\bar d_j}{2\bar m}$ 唯一要求 $\gamma=\frac{(P_{01}-Q_{01})K}{(T-1)S}$；若机械沿用印刷版漏因子的 $\bar m$，则会得到另一个并不自洽的 $(T-1)^{-2}$ 版本。**结论（MLE ≈ 模块度、$W$ 与 $\alpha,\beta$ 的形式）不受影响**，但 $\gamma$ 的源文常数必须按上述校勘值使用；实践中 Algorithm 17 把 $\gamma$（及 $\alpha,\beta$）当作可调参数，正文的数值实验也正是这样做的。
完整证明Theorem 6.2（$T\to\infty$ 时 Algorithm 18 以高概率完全恢复）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：同质 Markov SBM，$n$ 固定、$T\to\infty$，$P,Q$ 已知，演化非静态且 $P\ne Q$。则 $T\to\infty$ 时 Algorithm 18 以趋于 1 的概率把每个节点分类正确（并输出 $\widehat K=K$）。
**依赖工具**：平稳遍历马尔可夫链的渐近正态性（Billingsley, 1961, Theorem 3.1 及 (3.13)）——转移计数经中心极限定理 $\sqrt{n_a}(\widehat P_{ab}-P_{ab})\Rightarrow\mathcal N(0,\lambda_{ab})$；并集界；相似图连通分量的结构（全部配对判定正确 ⇒ 连通分量 = 社区的不相交团）。
**证明思路**：$n$ 固定意味着只有有限多（$\binom n2$）个节点对要判对；每对的判别误差概率随 $T$（从而随转移计数 $n_a(i,j)\to\infty$）趋于 0；并集界把"全部判对"的概率推向 1。判别规则本身是 Algorithm 18 的加边准则：$\widehat P(i,j)$ 离 $P$ 比离 $Q$ 近 ⇒ 同社区。
**完整证明**：
1. **单对的渐近正态性**：固定 $a,b\in\{0,1\}$，记 $n_{ab}(i,j)$ 为对 $(i,j)$ 观测到的 $a\to b$ 转移数、$n_a(i,j)=\sum_bn_{ab}(i,j)$。演化非静态 ⇒ 两状态都被无限次访问，$T\to\infty$ 时 $n_a(i,j)\to\infty$ a.s.。由 Billingsley 的马尔可夫链 CLT，
$$\xi_{ab}(i,j):=\sqrt{n_a(i,j)}\,\big(\widehat P_{ab}(i,j)-P_{ab}(i,j)\big)\ \Rightarrow\ \mathcal N(0,\lambda_{ab}),\qquad \lambda_{(ab),(cd)}=\delta_{ac}\big(\delta_{bd}P_{ab}(i,j)-P_{ab}(i,j)P_{ad}(i,j)\big)$$
（多项式协方差结构）。于是对任意 $\alpha>0$，
$$\mathbb P\Big(\big|\widehat P_{ab}(i,j)-P_{ab}(i,j)\big|\ge\alpha\Big)=\mathbb P\Big(\big|\xi_{ab}(i,j)\big|\ge\alpha\sqrt{n_a(i,j)}\Big)\ \xrightarrow[T\to\infty]{}\ 0.\tag{6.19}$$
（原书此处 $\xi$ 的分子在 OCR 中误植为 $n_{ab}-n_a\widehat P_{ab}$，按 Billingsley 的标准形式应为 $n_{ab}-n_aP_{ab}$；上式即其等价写法。）
2. **同/异社区判别**：$P\ne Q$ ⇒ 存在 $(a,b)$ 使 $P_{ab}\ne Q_{ab}$；不妨 $P_{01}\ne Q_{01}$ 且 $P_{01}>Q_{01}$（否则换一对 $(a,b)$ 或交换记号）。取 $\alpha$ 使 $0<\alpha<\frac{P_{01}-Q_{01}}2$。判定规则"$i,j$ 同社区当且仅当 $\widehat P_{01}(i,j)>\frac{P_{01}+Q_{01}}2$"（即 $\widehat P$ 离 $P$ 更近）的误判概率：若 $z_i=z_j$，$\widehat P_{01}(i,j)$ 的真值是 $P_{01}$，误判要求偏差 $\ge\frac{P_{01}-Q_{01}}2>\alpha$；$z_i\ne z_j$ 时真值是 $Q_{01}$，同理。故
$$\mathbb P(\text{对 }(i,j)\text{ 误判})\le\mathbb P\Big(\big|\widehat P_{01}(i,j)-P_{01}(i,j)\big|\ge\alpha\Big),$$
其中 $P_{01}(i,j)\in\{P_{01},Q_{01}\}$ 按真实关系取值。这正是 Algorithm 18 第 6–7 行的加边准则（$|\widehat P_{ab}(i,j)-P_{ab}|\le\frac12|P_{ab}-Q_{ab}|$ 则加边）。
3. **并集界**：全部 $\binom n2=\frac{n(n-1)}2$ 个节点对都被判错的概率
$$\mathbb P(\exists\ (i,j)\ \text{误判})\le\frac{n(n-1)}2\max_{i,j}\mathbb P\Big(\big|\widehat P_{01}(i,j)-P_{01}(i,j)\big|\ge\alpha\Big)\xrightarrow[T\to\infty]{}0,$$
因为 $n$ 固定、右端每个因子由 (6.19) 趋于 0。
4. **从配对判定到社区**：全部配对判定正确时，相似图 $G=(V,E)$ 恰好是"同社区对全加边、异社区对不加边"的图——即 $K$ 个不相交团。其连通分量正好是真实社区，故 Algorithm 18 第 8–10 行输出 $\widehat K=K$、$\hat z=z$（标签置换意义下）。$\square$
**闭合检查**：渐近 regime 是"$n$ 固定、$T\to\infty$"——与 Prop 6.1 的"$n,T$ 同发散"互补，这里不需要 $\rho T$ 型的信噪比条件，只需 $P\ne Q$（可辨识）与非静态（遍历性使 $n_a\to\infty$）。常见误用：把本定理当成对 $n\to\infty$ 的结论；$n$ 发散时并集界的 $\binom n2$ 因子需要用 (6.19) 的**速率**控制，本证明不提供。
完整证明Lemma 6.3（VEM 更新的显式形式：VE 步）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：在变分族 $\mathbb Q_\tau(Z)=\prod_i\prod_k\tau(i,k)^{1(z_{i1}=k)}\prod_{t\ge2}\prod_{k,\ell}\tau(t,i,k,\ell)^{1(z_{i,t-1}=k)1(z_{it}=\ell)}$（约束 $\sum_k\tau(i,k)=1$、$\sum_\ell\tau(t,i,k,\ell)=1$）下，$\widehat\tau=\arg\max_\tau J(\theta,\tau)$ 满足
$$\widehat\tau(t,i,k,\ell)\ \propto\ \pi_{k\ell}\prod_{j\ne i}\prod_{k'=1}^K\Big(\mathrm{Ber}(p_{\ell k'})(A^t_{ij})\Big)^{\widehat\tau_{\mathrm{marg}}(t,j,k')},$$
比例常数由归一化 $\sum_\ell\widehat\tau(t,i,k,\ell)=1$ 确定；边际递推 $\tau_{\mathrm{marg}}(1,i,k)=\tau(i,k)$、$\tau_{\mathrm{marg}}(t,i,k)=\sum_\ell\tau_{\mathrm{marg}}(t-1,i,\ell)\tau(t,i,\ell,k)$。
**依赖工具**：$J(\theta,\tau)=\mathbb E_{\mathbb Q}\log\mathbb P(A^{1:T},Z)+\mathcal H(\mathbb Q)$ 的展开（三项：初始 + 转移 + 发射）；Lagrange 乘子法（归一化约束）；$\tau_{\mathrm{marg}}$ 对 $\tau$ 的导数关系 $\frac{\partial\tau_{\mathrm{marg}}(t,i,\ell)}{\partial\tau(t,i,k,\ell)}=\tau_{\mathrm{marg}}(t-1,i,k)$。
**证明思路**：$J$ 展开后，$\tau(t,i,k,\ell)$ 出现在两处——转移项（带系数 $\tau_{\mathrm{marg}}(t-1,i,k)$）与发射项（经 $\tau_{\mathrm{marg}}(t,i,\ell)$）。对 $\tau(t,i,k,\ell)$ 求偏导并置零，$\log\tau$ 项被解出为显式函数，指数化即得比例式。
**完整证明**：
1. **$J$ 的三项展开**：由 $\log\mathbb P(A^{1:T},Z)=\sum_i\log\alpha_{z_{i1}}+\sum_i\sum_{t\ge2}\log\pi_{z_{i,t-1}z_{it}}+\sum_t\sum_{i<j}\log\mathrm{Ber}(p_{z_{it}z_{jt}})(A^t_{ij})$ 与 $\mathbb Q_\tau$ 的乘积结构，
$$J=\sum_{i,k}\tau(i,k)\big[\log\alpha_k-\log\tau(i,k)\big]+\sum_{t\ge2}\sum_{i,k,\ell}\tau_{\mathrm{marg}}(t-1,i,k)\tau(t,i,k,\ell)\big[\log\pi_{k\ell}-\log\tau(t,i,k,\ell)\big]+\sum_{t}\sum_{i<j}\sum_{k,\ell}\tau_{\mathrm{marg}}(t,i,k)\tau_{\mathrm{marg}}(t,j,\ell)\log\mathrm{Ber}(p_{k\ell})(A^t_{ij}).$$
（第一、二项中的 $-\tau\log\tau$ 即熵 $\mathcal H(\mathbb Q)$ 的贡献；发射项 $\mathrm{Ber}(p)(A)=p^A(1-p)^{1-A}$。）
2. **$\tau(t,i,k,\ell)$ 出现在哪些项**：(a) 转移项：$\tau_{\mathrm{marg}}(t-1,i,k)\tau(t,i,k,\ell)[\log\pi_{k\ell}-\log\tau(t,i,k,\ell)]$；(b) 发射项中经 $\tau_{\mathrm{marg}}(t,i,\ell)$：由边际递推，$\frac{\partial\tau_{\mathrm{marg}}(t,i,\ell)}{\partial\tau(t,i,k,\ell)}=\tau_{\mathrm{marg}}(t-1,i,k)$，故发射项对 $\tau(t,i,k,\ell)$ 的偏导为
$$\tau_{\mathrm{marg}}(t-1,i,k)\sum_{j\ne i}\sum_{k'}\tau_{\mathrm{marg}}(t,j,k')\log\mathrm{Ber}(p_{\ell k'})(A^t_{ij})$$
（$i<j$ 与 $i>j$ 的项对称合并为 $j\ne i$）。
3. **置零求解**：含归一化乘子 $\mu(t,i,k)$ 的稳定条件为
$$\tau_{\mathrm{marg}}(t-1,i,k)\big[\log\pi_{k\ell}-\log\tau(t,i,k,\ell)-1\big]+\tau_{\mathrm{marg}}(t-1,i,k)\sum_{j\ne i}\sum_{k'}\tau_{\mathrm{marg}}(t,j,k')\log\mathrm{Ber}(p_{\ell k'})(A^t_{ij})+\mu(t,i,k)=0.$$
（原书此处只展示了这一导数示意；$-1$ 来自 $-\tau\log\tau$ 的导数。）设 $\tau_{\mathrm{marg}}(t-1,i,k)>0$（若 $=0$ 则该坐标对 $J$ 无影响，可取任意归一化值），解出
$$\log\widehat\tau(t,i,k,\ell)=\log\pi_{k\ell}+\sum_{j\ne i}\sum_{k'}\widehat\tau_{\mathrm{marg}}(t,j,k')\log\mathrm{Ber}(p_{\ell k'})(A^t_{ij})+\text{const}(t,i,k),$$
指数化并把常数并入归一化，即目标比例式。$\square$
**闭合检查**：更新式是不动点形式——右边含 $\widehat\tau_{\mathrm{marg}}$，实际迭代中用当前值代入（坐标上升，$J$ 每步不减，故收敛到局部极大）；发射项只对 $i$ 在时刻 $t$ 的邻居 $j$（$A^t_{ij}=1$）有非平凡贡献，稀疏图上计算量小。M 步（$\widehat\pi,\widehat p$）与初始坐标 $\tau(i,k)$ 的推导原书留给读者类推，见 [§11 补证卡](#proof-check-6-3-1-vem-remaining-coordinates)。
完整证明Proposition 6.3（在线 MAP：图项 + 预言机贴合项）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：6.3.4 模型（度校正马尔可夫成员 + 马尔可夫边动态，$K$ 一般但先验均匀）；$s\in[K]^n$ 与 $A$ 独立、错误率 $\rho=\mathbb P(s_i\ne z_{it})$ 逐节点相同。令 $\lambda=\log\frac{1-\rho}{\rho}$。则 MAP 估计 $\hat z_{\cdot t}=\arg\max_{z\in[K]^n}\mathbb P(z|A^t,A^{t-1},s)$ 等于最大化
$$\sum_{\substack{i,j\\z_i=z_j}}\Big\{\ell_{01}^{\theta_i\theta_j}\big(A^t_{ij}-A^{t-1}_{ij}A^t_{ij}\big)+\ell_{10}^{\theta_i\theta_j}\big(A^{t-1}_{ij}-A^{t-1}_{ij}A^t_{ij}\big)+\ell_{11}^{\theta_i\theta_j}A^{t-1}_{ij}A^t_{ij}-\log\frac{Q_{00}^{\theta_i\theta_j}}{P_{00}^{\theta_i\theta_j}}\Big\}+2\lambda\sum_{i=1}^n1(z_i=s_i).$$
**依赖工具**：Bayes 公式；预言机独立性（$\mathbb P(A^t|A^{t-1},z,s,\theta)=\mathbb P(A^t|A^{t-1},z,\theta)$）；Prop 6.2 证明第 3–5 步的转移项拆项（单步版）；标签均匀先验 $\mathbb P(z_i=k)=1/K$。
**证明思路**：后验 = 似然 × 先验。似然部分就是 Prop 6.2 的单步转移项；先验部分 $\mathbb P(z|s)$ 由预言机错误率展开成 $(\frac{\rho}{1-\rho})^{\#\{z_i\ne s_i\}}$ 型，取对数后化为 $\lambda\sum_i1(z_i=s_i)$（差一个与 $z$ 无关的常数）。系数 $2\lambda$ 的因子 2 来自图项按有序对求和（=$2\times$ 对数似然的同社区项）。
**完整证明**：
1. **Bayes 分解**：
$$\mathbb P(z|A^t,A^{t-1},s,\theta)\propto\mathbb P(A^t|A^{t-1},z,s,\theta)\,\mathbb P(z|A^{t-1},s,\theta),$$
比例因子 $\mathbb P(A^t|A^{t-1},s,\theta)$ 与 $z$ 无关。由马尔可夫性（给定 $z$ 与 $A^{t-1}$ 后 $A^t$ 与更早历史、与 $s$ 无关），$\mathbb P(A^t|A^{t-1},z,s,\theta)=\mathbb P(A^t|A^{t-1},z,\theta)$；又 $z_{\cdot t}$ 的先验（经 $\pi$ 与均匀性）在只看 $s$ 时化为 $\mathbb P(z|s)$（下面第 3 步；$A^{t-1}$ 对 $z_{\cdot t}$ 的信息已通过 $s=\hat z_{\cdot t-1}$ 的构造吸收）。
2. **似然项**：对 $\log\mathbb P(A^t|A^{t-1},z,\theta)$ 应用 Prop 6.2 证明第 3–5 步（单步、不计初值与边界）：
$$\log\mathbb P(A^t|A^{t-1},z,\theta)=\frac12\sum_{\substack{i,j\\z_i=z_j}}\Big\{\ell_{01}^{\theta_i\theta_j}\big(A^t_{ij}-A^{t-1}_{ij}A^t_{ij}\big)+\ell_{10}^{\theta_i\theta_j}\big(A^{t-1}_{ij}-A^{t-1}_{ij}A^t_{ij}\big)+\ell_{11}^{\theta_i\theta_j}A^{t-1}_{ij}A^t_{ij}-\log\frac{Q_{00}^{\theta_i\theta_j}}{P_{00}^{\theta_i\theta_j}}\Big\}+c(A),$$
其中三类边齐备：新生 $A^t-A^{t-1}A^t$、消失 $A^{t-1}-A^{t-1}A^t$、持久 $A^{t-1}A^t$（单步内三者加上"始终为 0"构成完备划分）。
3. **预言机先验项**：$\mathbb P(s_i|z_i)=1-\rho$（$s_i=z_i$）或 $\rho$（$s_i\ne z_i$），$\mathbb P(z_i)=1/K$（均匀），逐节点独立 ⇒
$$\mathbb P(z|s)=\prod_i\frac{\mathbb P(s_i|z_i)\mathbb P(z_i)}{\mathbb P(s_i)}=\Big(\frac{\rho}{1-\rho}\Big)^{\#\{i:z_i\ne s_i\}}(1-\rho)^n\Big(\frac1K\Big)^n\Big/\prod_i\mathbb P(s_i),$$
后三个因子与 $z$ 无关。取对数并用 $\#\{z_i\ne s_i\}=n-\sum_i1(z_i=s_i)$：
$$\log\mathbb P(z|s)=\lambda\sum_i1(z_i=s_i)+\text{const},\qquad \lambda=\log\frac{1-\rho}{\rho}.$$
4. **合并**：最大化 $\log$ 后验 = 第 2 步图项（带 $\frac12$）+ 第 3 步的 $\lambda\sum_i1(z_i=s_i)$。把图项改写成对有序对 $(i,j)$ 求和（吸收 $\frac12$ 成系数 2 的约定），整个目标乘以 2 不改变 argmax，即得题述形式（图项按有序对求和 + $2\lambda\sum_i1(z_i=s_i)$）。$\square$
**闭合检查**：目标与 Ch5 Prop 5.1 的 MAP 完全同构——"图结构项 + 预言机贴合项"，这保证 (6.21) 的二次型松弛与 Ch5 §5.4.2 的机器可直接复用。$\lambda$ 随 $\rho$ 递减：预言机越可靠（$\rho$ 小）贴合权重越大；$\rho\to1/2$（无信息）时 $\lambda\to0$ 退回纯图聚类——与 Ch5 Assumption 5.1 的"有信息预言机"条件呼应。
11. 正文隐藏验证补全
清单 §6 判为"真正留白 / 压缩证明"的条目共 3 行，逐一处理如下；其余 6 行判为修辞性/说明性/未来工作声明，不设卡片（见本文件顶部注释与 §16）。
定位说明Proposition 6.1 的证明外包（清单 §6 第 1 行，真正留白）
状态：证明骨架保留主要推导链，后续可补常数、边界或技术细节。
**条目**：Proposition 6.1 陈述后原书仅言 "whose proof can be found in (Avrachenkov et al., 2022)"（文件页 153 / 印刷页 144），书内无证明。
**处理方式**：不补证（该证明是信息论阈值论文的技术主体，篇幅远超本章定位），但把命题使用时的关键点固定下来：
1. **命题条件的完整转写**（使用 Prop 6.1 时逐条核对）：稀疏参数化 (6.7)（$\mu_1=u\rho$ 等四个常数因子）且 $\rho T\ll1$；$P_{11},Q_{11}$ 为不随 $n,T$ 变的常数；非退化条件 $(P_{11},Q_{11})\ne(1,1)$（排除"边一旦出现永不消失"）与可辨识条件 $(p_{01},P_{11})\ne(q_{01},Q_{11})$（$f_{\mathrm{in}}\ne f_{\mathrm{out}}$）；$K\asymp1$。结论三层：(i) 一致恢复阈值 $\rho T\asymp1/n$；(ii) 强一致阈值 $\rho T\asymp\log n/n$；(iii) 临界常数 $\tau\tilde I=K$（$\tilde I$ 含几何分布 Hellinger 项 $H_{11}^2$，见 [§9 卡片 T1](#sec-9-theorem-cards)）。
2. **技术出处与角色**：Avrachenkov, Dreveton & Leskelä (2022) 证明 $\rho T\tilde I$ 是两个马尔可夫链分布 $f_{\mathrm{in}},f_{\mathrm{out}}$ 间 Rényi 散度（Ch4 Definition 4.3）Taylor 展开的主项，然后套用 Ch4 §4.4.3 的"散度 → 恢复分级"框架——**证明骨架与静态 SBM 相同，新内容全在散度的计算**（马尔可夫链的非独立序列使散度不再是简单乘积，$H_{11}^2$ 项正是"边保持时长分布"的贡献）。
3. **与本书证据链的衔接**：本书侧的支撑是数值的——Figure 6.1 的 $T^*_{\mathrm{theo}}$ 由 (iii) 解出，实验精度曲线在其附近起飞；Figure 6.3 展示 $\rho=O(1/n)$ 极稀疏 regime（Remark 6.1 的断言区间）Algorithm 16 仍可恢复。
隐藏验证补全"Simple calculations"：Prop 6.2 证明中的两个示性展开（清单 §6 第 2 行）
状态：证明骨架保留主要推导链，后续可补常数、边界或技术细节。
**证明目标**（文件页 162 / 印刷页 153，原书一句带过）：对 $A^1,A^{t-1},A^t\in\{0,1\}$（省去上标 $\theta_i\theta_j$ 与下标 $ij$），
$$\text{(E1)}\quad\sum_{a\in\{0,1\}}\delta(A^1,a)\rho_a=A^1(\rho_1-\rho_0)+\rho_0;$$
$$\text{(E2)}\quad\sum_{a,b}\delta(A^{t-1},a)\delta(A^t,b)R_{ab}=R_{00}+A^{t-1}\ell_{10}+A^t\ell_{01}+A^{t-1}A^t(\ell_{11}-\ell_{01}-\ell_{10}),\quad\ell_{ab}:=R_{ab}-R_{00}.$$
**依赖工具**：二值变量的示性函数穷举；$\ell_{ab}$ 的定义。
**完整证明**：(E1)：$A^1=0$ 时左 = $\rho_0$，右 = $\rho_0$ ✓；$A^1=1$ 时左 = $\rho_1$，右 = $(\rho_1-\rho_0)+\rho_0=\rho_1$ ✓。
(E2)：左边是 $(A^{t-1},A^t)$ 的分段函数，穷举四种取值；右边记为 $\mathrm{RHS}$。
- $(0,0)$：左 = $R_{00}$；$\mathrm{RHS}=R_{00}$ ✓。
- $(1,0)$：左 = $R_{10}$；$\mathrm{RHS}=R_{00}+\ell_{10}=R_{00}+(R_{10}-R_{00})=R_{10}$ ✓。
- $(0,1)$：左 = $R_{01}$；$\mathrm{RHS}=R_{00}+\ell_{01}=R_{01}$ ✓。
- $(1,1)$：左 = $R_{11}$；$\mathrm{RHS}=R_{00}+\ell_{10}+\ell_{01}+(\ell_{11}-\ell_{01}-\ell_{10})=R_{00}+\ell_{11}=R_{11}$ ✓。$\square$
**闭合检查**：(E2) 的代数实质是"二值二元的离散泰勒展开"——$R_{ab}$ 写成基线 $R_{00}$ + 各变量的主效应 + 交互效应；交互项系数 $\ell_{11}-\ell_{01}-\ell_{10}=R_{11}-R_{01}-R_{10}+R_{00}$ 正是"持久边的超额对数似然比"，这是持久边在 Lemma 6.1 获得独立权重 $\beta$ 的代数根源。
隐藏验证补全Lemma 6.3 其余坐标：M 步 $\widehat\pi,\widehat p$ 与初始分布 $\tau(i,k)$（清单 §6 第 3 行）
状态：证明骨架保留主要推导链，后续可补常数、边界或技术细节。
**证明目标**（文件页 172 / 印刷页 163，原书证 VE 步后称其余 "direct derivation" 类推）：(i) M 步 $\widehat\pi_{k\ell}\propto\sum_{t=2}^T\sum_{i=1}^n\tau_{\mathrm{marg}}(t-1,i,k)\tau(t,i,k,\ell)$（按 $\ell$ 归一化）；(ii) $\widehat p_{k\ell}=\dfrac{\sum_t\sum_{i<j}\tau_{\mathrm{marg}}(t,i,k)\tau_{\mathrm{marg}}(t,j,\ell)A^t_{ij}}{\sum_t\sum_{i<j}\tau_{\mathrm{marg}}(t,i,k)\tau_{\mathrm{marg}}(t,j,\ell)}$；(iii) 初始坐标 $\widehat\tau(i,k)\propto\alpha_k\prod_{j\ne i}\prod_{k'}\mathrm{Ber}(p_{kk'})(A^1_{ij})^{\tau_{\mathrm{marg}}(1,j,k')}$。
**依赖工具**：[proof-lemma-6-3](#proof-lemma-6-3) 第 1 步的 $J$ 三项展开；带归一化约束的 Lagrange 乘子法；$\log$ 项的求导 $\partial(x\log x)=\log x+1$。
**完整证明**：
(i) **$\widehat\pi$**：$J$ 中含 $\pi$ 的项为 $\sum_{t\ge2}\sum_{i,k,\ell}\tau_{\mathrm{marg}}(t-1,i,k)\tau(t,i,k,\ell)\log\pi_{k\ell}$，约束 $\sum_\ell\pi_{k\ell}=1$（逐 $k$）。拉氏量对 $\pi_{k\ell}$ 求导：$\frac{1}{\pi_{k\ell}}\sum_{t,i}\tau_{\mathrm{marg}}(t-1,i,k)\tau(t,i,k,\ell)+\mu_k=0$ ⇒ $\pi_{k\ell}$ 正比于该和式，归一化即得。$\square$
(ii) **$\widehat p$**：$J$ 中含 $p_{k\ell}$ 的项为 $\sum_t\sum_{i<j}\tau_{\mathrm{marg}}(t,i,k)\tau_{\mathrm{marg}}(t,j,\ell)\big[A^t_{ij}\log p_{k\ell}+(1-A^t_{ij})\log(1-p_{k\ell})\big]$（$k\le\ell$ 时每对出现一次；$p_{k\ell}=p_{\ell k}$ 对称）。记 $w_{ij}(t)=\tau_{\mathrm{marg}}(t,i,k)\tau_{\mathrm{marg}}(t,j,\ell)$，对 $p_{k\ell}$ 求导：
$$\frac{\partial J}{\partial p_{k\ell}}=\sum_t\sum_{i<j}w_{ij}(t)\Big(\frac{A^t_{ij}}{p_{k\ell}}-\frac{1-A^t_{ij}}{1-p_{k\ell}}\Big)=0\ \Longrightarrow\ (1-p_{k\ell})\sum wA=p_{k\ell}\sum w(1-A),$$
整理得 $\widehat p_{k\ell}=\dfrac{\sum_t\sum_{i<j}w_{ij}(t)A^t_{ij}}{\sum_t\sum_{i<j}w_{ij}(t)}$。$\square$（原书印刷中分母的 $\tau_{\mathrm{marg}}(t,i,\ell)$ 应为 $\tau_{\mathrm{marg}}(t,j,\ell)$、分子 $1(A^t_{ij}\ne0)$ 即 $A^t_{ij}$——二值邻接下二者相同；OCR 的下标错位已按模型结构订正。）
(iii) **$\tau(i,k)$**：它出现在 $J$ 的第一项 $\tau(i,k)[\log\alpha_k-\log\tau(i,k)]$ 与 $t=1$ 的发射项（经 $\tau_{\mathrm{marg}}(1,i,k)=\tau(i,k)$）。求导：
$$\log\alpha_k-\log\tau(i,k)-1+\sum_{j\ne i}\sum_{k'}\tau_{\mathrm{marg}}(1,j,k')\log\mathrm{Ber}(p_{kk'})(A^1_{ij})+\mu(i)=0,$$
解出并指数化即目标比例式。$\square$
**闭合检查**：三个更新与 VE 步（[proof-lemma-6-3](#proof-lemma-6-3)）合成完整的 VEM 迭代：$\widehat\pi$ 是"软转移计数"归一化、$\widehat p$ 是"软同/异社区连边率"——都是经典 EM 在加权/软标签下的对应物；$\tau(i,k)$ 与 $\tau(t,i,k,\ell)$ 同构（$t=1$ 时无 $\pi$ 因子、先验 $\alpha_k$ 代之）。熵项 $-\tau\log\tau$ 的导数 $-1$ 在各比例式中都被归一化常数吸收，这解释了为什么所有更新都是干净的"先验 × 发射似然"形。
12. 术语与跨章链接
本章首次系统引入、已入全书术语表的术语（点击跳转定义）：
- 时序框架：时序网络（Ch1 引入）、快照、成员结构 / 相互作用结构、马尔可夫随机分块模型、持久边
- 方法：经验转移率、变分期望最大化 VEM、信念传播与时空图、在线推断与滞后问题
- 跨章复用：随机分块模型、度校正 SBM、模块度、谱聚类、MAP 估计、Rényi 散度、精确恢复 / 一致恢复、预言机、半监督学习
跨章链接：
- 第 1 章笔记：高中互动数据集（Table 1.1、Figure 1.4/1.5）——本章 6.2.3 数值节是其正式处理；Ch1"时间聚合丢信息"的警告是本章总动机。
- 第 4 章笔记：§4.4.3 的恢复分级与 Example 4.1/4.2（Prop 6.1 的对照基准）；§4.4.2 的模块度-谱松弛（Lemma 6.1 → Algorithm 17 的机器）；Prop 4.4 的 $\delta(z_i,z_j)$ 拆项代数（Prop 6.2/6.3 复用）。
- 第 5 章笔记：§5.4 噪声预言机框架（Prop 6.3 与之同构）；(6.21)–(6.23) 的松弛与 secular equation 即 Ch5 §5.4.2 推导的复用。
校勘备忘（译文与本笔记统一按此处理，详见清单 §7）：① Proposition 6.1 (i) 的 OCR 误读（下标 $_pT$、游离 $\gamma$）应为 $\rho T\lesssim 1/n$ 与 $\rho T\gg 1/n$，本页 §9 卡片 T1 按订正版转写；② Lemma 6.1 陈述处 OCR 混入 HTML 上标标签（P<sup>θiθj</sup>），应为 $P^{\theta_i\theta_j}$；③ Figure 6.7 图注 $\alpha_{22}=2$ 可由下标域确定为排印错误，校勘读法为 $\alpha_{11}=2$；同图注的 $\mu_2=0.02$ 仅有 $\nu_1=0.02$ 这一候选对应，仍保留源值；④ Lemma 6.1 的 $\gamma$ 两处印刷不一致，按定义和求和唯一闭合为 $\gamma=(P_{01}-Q_{01})K/((T-1)S)$，见 proof-lemma-6-1 校勘提示；⑤ Table 6.1 的 2011 行 $0.58$ 可确定为 $0.18$ 的排印错误，2013 行 $4.5,0.07$ 与表内概率计算不一致且缺少未四舍五入数据，按双分支复现而不作唯一修正；⑥ Theorem 6.2 证明中 $\xi_{ab}$ 分子的 OCR 误植（$\widehat P$ 应为真值 $P$），已在 proof-theorem-6-2 内注明。
校勘参数表Ch6 可直接使用的修订值与来源边界
| 位置 | 原书显示 | 项目使用值 | 状态与理由 |
|---|---|---|---|
| Lemma 6.1，模块度分辨率 | 两个互相冲突的 $\gamma$，且 $\bar m$ 漏 $(T-1)$ | $\displaystyle \bar m=\frac{(T-1)n^2S}{2K}$，$\displaystyle \gamma=\frac{(P_{01}-Q_{01})K}{(T-1)S}$ | **已关闭**；由 $\bar m=\frac12\sum_i\bar d_i$ 与零模型项逐项匹配唯一确定 |
| Figure 6.7 | $\alpha_{22}=2$ | $\alpha_{11}=2$ | **已关闭**；$a,b\in\{0,1\}$，并与 Figure 6.6 一致 |
| Table 6.1，2011 | $\widehat\beta=0.58$ | $\widehat\beta=0.18$ | **已关闭**；正文、Figure 6.5 与比值 $0.18/2.9\approx0.060$ 三重一致 |
| Figure 6.7 | $\mu_2=0.02$ | 不静默替换；复现实验时并列测试源值与候选 $\nu_1=0.02$ | **现有资料不可唯一判定**；候选只由相邻 Figure 6.6 支持，双分支即当前最终复现规则 |
| Table 6.1，2013 | $(\widehat\alpha,\widehat\beta)=(4.5,0.07)$ | 从表内四舍五入概率重算约为 $(4.16,0.47)$；两组并列 | **现有资料不可唯一判定**；精确值须由未四舍五入估计或原始代码裁决，双分支即当前最终复现规则 |
其中
$$S=\mu_1\big(\alpha(1-P_{11})+\beta P_{11}\big)+(K-1)\nu_1\big(\alpha(1-Q_{11})+\beta Q_{11}\big).$$
前三项是确定性校正，可直接用于推导与复现；后两项属于数据 provenance 问题，不影响本章结构完成度，但任何实验复现必须在结果中注明采用了哪一组候选值。
13. 章节阅读路径
| 顺序 | 小节（印刷页） | 读法 |
|---|---|---|
| 1 | 章首两段（p.140） | 精读："聚合/平滑时间轴会丢信息"是全章动机；章末一句预告两分类 |
| 2 | 6.1（p.141–143） | 精读 $Z$、$B$ 的定义与 (6.1)–(6.2)；三个 Example 各记一句话（独立 = $T$ 个静态 SBM；马尔可夫交互；保持型马尔可夫成员） |
| 3 | 6.2.1（p.143–145） | Prop 6.1 陈述 + Remark 6.1/6.2 精读（阈值 $\rho T$ 与 Ch4 对照）；证明外包，不找 |
| 4 | 6.2.2（p.145–150） | $M^t$ 递推（式 (6.8)–(6.9)）精读；Algorithm 15/16 对照读（差别只在参数是否在线估计，式 (6.10)–(6.13)）；Figure 6.1–6.3 看趋势 |
| 5 | 6.2.3（p.150–158） | 本章方法核心：$x_1/x_2$ 例子 → 持久边 → Prop 6.2 + Lemma 6.1（配合本页 §10）→ Algorithm 17；数值节 + Table 6.1 精读（高中数据集回环，Figure 6.5） |
| 6 | 6.2.4（p.158–160） | 快读：Algorithm 18 结构 + Thm 6.2 证明（短）；Remark 6.3 一句 |
| 7 | 6.3 引言 + 6.3.1（p.160–163） | 后验不可分解的解释段精读（"观测到边 ⇒ 两端标签相关"）；$J$ 的结构 + Lemma 6.3 |
| 8 | 6.3.2（p.163–165） | 读消息类型（空间/时间）与去回声室原则；更新方程不必逐行推，知道齐次化简（$\pi=rI+\cdots$ 时 $\sum_\ell\pi_{k\ell}\psi_\ell=r\psi_k+\frac{1-r}{K}$）即可 |
| 9 | 6.3.3–6.3.4（p.165–170） | 滞后问题一段精读（全章后半的动机）；Prop 6.3 → (6.21)–(6.23) → Algorithm 19；Figure 6.6/6.7 对照读 |
| 10 | Further Notes（p.170） | 见 §16 |
14. 易混点
- 编号体系：无 Theorem 6.1、无 Lemma 6.2：本章 Theorem 与 Lemma 共享计数器（Lemma 6.1 → Theorem 6.2 → Lemma 6.3），Example/Proposition/Remark 各自独立计数（均 6.1–6.3 连续）。不是 OCR 吞并。
- 时间聚合 vs 持久边加权：$\sum_t\mathrm{Cut}(A^t,z)=\mathrm{Cut}(\sum_tA^t,z)$ 只看交互次数；$x_1=(0,1,0,0,0,0,1,0,0,1)$ 与 $x_2=(0,0,1,1,1,0,0,0,0,0)$ 同为 3 次交互，但 $x_2$ 有 2 次 $1\to1$ 转移（持久）、$x_1$ 有 0 次——转移结构才是马尔可夫交互携带社区信息的地方。$A_{\mathrm{pers}}^t=A^{t-1}\odot A^t$ 正是把"次数"换成"持久"的代数操作。
- 两条轴四种组合：成员（静态/马尔可夫）× 交互（独立/马尔可夫）。本章只详细处理两种对角情形：6.2 = 静态成员 + 马尔可夫交互（Markov SBM）；6.3 = 马尔可夫成员 + 时间独立交互（6.3.4 的边动态仍是马尔可夫的，成员也马尔可夫——属第四象限的度校正版本）。Example 6.1（静态 + 独立）= $T$ 个独立静态 SBM，是 Ch4 的直接重复。别把"6.2 的交互马尔可夫"与"6.3 的成员马尔可夫"混为一谈。
- 同名符号复用：$\alpha$——6.2.3 的新生边权重 (6.17) vs 6.3 的成员初始分布 (6.20)；$\rho$——6.2.1 的稀疏参数 (6.6) vs 6.3.4 的预言机错误率（Prop 6.3）；$P$——6.2 的边转移矩阵 vs 6.3.1 的连边概率矩阵 $P=(p_{k\ell})$（$\theta=(\pi,P)$）；$Q$——6.2 的边转移矩阵 vs 6.3.1 的变分分布 $\mathbb Q_\tau$；$\lambda$——Prop 6.3 的 $\log\frac{1-\rho}{\rho}$ vs Algorithm 19 的可调 $\lambda_t$ vs Ch5 的拉氏乘子。阅读时以小节语境为准。
- "在线"的两个含义：6.2.2 的在线 = 标签静态，每个快照到来时增量更新同一个估计（信息累积，$M^t$ 单调变准）；6.3.3 的在线 = 标签漂移，每步只用最近快照 + 上一步预测（信息遗忘，故意丢弃被污染的历史）。Figure 6.6 的 $\eta=1$/$\eta=0.85$ 对照正是这两个 regime 的分界。
- VEM vs BP：两者都在逼近 $\mathbb P(Z|A^{1:T})$。VEM 是优化型近似：限制在 $\mathbb Q_\tau$ 族内最大化 ELBO（有单调收敛保证，到局部极大；Lemma 6.3 给闭式更新）；BP 是消息传递型近似：直接在时空图上迭代消息（无收敛保证但通常更准；去回声室 = 排除回送消息）。VEM 同时给出参数估计（$\widehat\pi,\widehat p$），BP 主要给标签边际。
- Prop 6.1 的 regime 与 Thm 6.2 的 regime 不同：Prop 6.1 是 $n,T$ 同发散的信息论阈值（$\rho T$ 与 $1/n$、$\log n/n$ 比较）；Thm 6.2 是 $n$ 固定、$T\to\infty$ 的遍历性结果（只要 $P\ne Q$ 就完全恢复）。一个是"信噪比够不够"，一个是"时间够长就行"。
- Figure 6.7 图注的 $\alpha_{22}=2$：交互权重 $\alpha_{ab}$ 的下标 $a,b\in\{0,1\}$，不存在 $\alpha_{22}$；且 Figure 6.6 图注同一参数写作 $\alpha_{11}=2$。下标域直接确定校勘读法为 $\alpha_{11}=2$，但译文仍不改源图注；同图注的 $\mu_2=0.02$ 不是相邻参数体系中的记号，$\nu_1=0.02$ 只是由 Figure 6.6 支持的候选修正。
- $\ell_{ab}$ 的相对定义：$\ell_{ab}=R_{ab}-R_{00}$（$R_{ab}=\log P_{ab}/Q_{ab}$）——漏掉 $-R_{00}$ 会在 Prop 6.2 的归并中丢掉 $-\log\frac{Q_{00}}{P_{00}}$ 项，进而在 Lemma 6.1 里丢掉零模型项的来源（见 §11 补证卡 的闭合检查）。Prop 6.3 的 OCR 把 $\ell$ 的定义印成 $\log\frac{P}{P}-\log\frac{P}{P}$（全 $P$），应为 $\log\frac{P_{ab}}{Q_{ab}}-\log\frac{P_{00}}{Q_{00}}$。
15. 公式卡片
按"输入 → 输出 → 用途"整理本章 8 组关键公式。
F1 一般模型（式 (6.1)–(6.2)）：$\mathbb P(Z)=\prod_i\mathscr P(Z_{i\cdot})$，$\mathbb P(A|Z,B)=\prod_{i<j}B_{Z_{i\cdot},Z_{j\cdot}}(A^{1:T}_{ij})$。输入成员分布 $\mathscr P$ 与交互测度族 $B$；输出整个张量的联合律。全章最一般形式，参数爆炸 ⇒ 必须特化。
F2 Markov SBM 核（式 (6.5)）：$f_{\mathrm{in}}=\mu_{x_1}P_{x_1x_2}\cdots P_{x_{T-1}x_T}$，$f_{\mathrm{out}}$ 同理换 $\nu,Q$。6.2 的模型本体；所有阈值与算法的出发点。
F3 稀疏参数化（式 (6.6)–(6.7)）：$\max\{\mu_1,\nu_1,P_{01},Q_{01}\}\le\rho$；$\mu_1=u\rho$ 等。使"信号量 = $\rho T$"成立：$\mathbb E\sum_tX_t\le\mu_1+(T-1)P_{01}=O(\rho T)$。Prop 6.1 的阈值语言由此而来。
F4 在线对数似然比（式 (6.8)–(6.9)）：$M^t_{ij}=\log\frac{f_{\mathrm{in}}(A^{1:t}_{ij})}{f_{\mathrm{out}}(A^{1:t}_{ij})}$，递推 $M^t=M^{t-1}+\Delta^t$（$\Delta^t_{ij}=\log\frac{P}{Q}(A^{t-1}_{ij},A^t_{ij})$ 只取 4 值）；得分 $L^t_{i,k}=\sum_{j\ne i}M^t_{ij}\delta_{\hat z^{t-1}_j,k}$。Algorithm 15/16 的引擎；复杂度 $O(Kn^2T)$。
F5 经验转移率（式 (6.10)）：$\widehat P_{ab}(i,j)=n_{ab}(i,j)/n_a(i,j)$。遍历性 ⇒ $T\to\infty$ 一致估计 $P(i,j)$；Algorithm 16（在线参数估计，式 (6.11)–(6.13)）与 Algorithm 18（相似图加边准则）共用此量。
F6 持久/新生/消失边与权重（式 (6.16)–(6.17)）：$A_{\mathrm{pers}}^t=A^{t-1}\odot A^t$，$A_{\mathrm{new}}^t=A^t-A_{\mathrm{pers}}^t$，$A_{\mathrm{old}}^t=A^{t-1}-A_{\mathrm{pers}}^t$；$W=\sum_t(\alpha A_{\mathrm{new}}^t+\beta A_{\mathrm{pers}}^t)$，$\alpha=\log\frac{P_{01}}{Q_{01}}+\log\frac{1-P_{11}}{1-Q_{11}}$，$\beta=\log\frac{P_{11}}{Q_{11}}$。输入 $\hat P,\hat Q$（如高中数据 2011 年估计），输出加权图 $W$ 供归一化谱聚类（Algorithm 17）；权重方向解释 Figure 6.4/Table 6.1。
F7 马尔可夫成员与 VEM 目标（式 (6.20) 与未编号 $J$）：$\mathbb P(z_{i\cdot})=\alpha_{z_{i1}}\prod_t\pi_{z_{i,t-1}z_{it}}$；$J(\theta,\tau)=\mathbb E_{\mathbb Q}\log\mathbb P(A^{1:T},Z)+\mathcal H(\mathbb Q)$（ELBO）。6.3 的模型与推断目标；Lemma 6.3 的更新由此求导。
F8 在线 SSL 目标（式 (6.21)–(6.23)）：$\arg\min_{z\in\{-1,1\}^n}-z^{\top}\big(W-\tau\frac{dd^{\top}}{2m}\big)z+\lambda(s-z)^{\top}(s-z)$（$W=\alpha_{01}A_{\mathrm{new}}+\alpha_{10}A_{\mathrm{old}}+\alpha_{11}A_{\mathrm{pers}}$，$\alpha_{ab}=\log\frac{P_{ab}}{Q_{ab}}$）；松弛解 $(-M+\lambda I_n-\gamma_*D)\hat x=\lambda s$（式 (6.22)），$\gamma_*$ 为 secular equation $\sum_i\big(\frac{b_i}{\delta_i-\gamma}\big)^2-2m=0$ 的最小解（式 (6.23)）。Algorithm 19 的逐步计算内核；与 Ch5 §5.4.2 同一机器。
16. Further Notes 导读（本书无习题）
本章无 Exercises；章末为两段"进一步阅读"（印刷页 170）加正文尾部一条未来工作声明。每条文献按"读什么、为什么读、与后续章的关系"解读：
第一段：信念传播文献线
- Decelle et al. (2011)、Moore (2017)（BP 综述）——读什么：静态 SBM 上 BP 的推导（腔方法/cavity）、detectability 相变的 BP 刻画、消息更新的去回声室原则。为什么读：6.3.2 的时空图消息方程只是把静态 BP 的"邻居"推广成"空间邻居 + 时间副本"，不先理解静态版本，时空版的三类消息（空间 $\psi^{i\to j}$、前向时间 $\psi^{i(t-1)\to i(t)}$、后向时间 $\psi^{i(t+1)\to i(t)}$）会显得任意。与后续章关系：Ch4 Further Notes 已把 BP 列为社区检测方法之一，这两篇是 BP 线的标准入口。
- Ghasemian et al. (2016)（动态网络 BP 起点）、Ghasemian (2019)（含 link persistence 的扩展）——读什么：动态 BP 的首次形式化与边持久机制的 BP 处理。为什么读：6.3.2 直接沿用其框架；2019 的扩展把 6.2.3 的"持久边权重"思想带进 BP。这是本章 6.3.2 的研究文献原型。
- Barucca et al. (2018)（马尔可夫成员 + 边持久）——读什么：成员与边同时马尔可夫演化的模型及其可恢复性分析。为什么读：其结论是反方向的——边持久使恢复更困难（持久边让异社区对也呈现时间相关，模糊了 $f_{\mathrm{in}}/f_{\mathrm{out}}$ 的差异），与本章 6.2.3"持久边携带信息"形成张力；理解这个反例能防止把"持久边加权"当成无条件的好主意（对照 Table 6.1：2012 年 $P_{11}\approx Q_{11}$ 时持久边确实无信息，$\hat\beta\approx0$）。
第二段：交互参数随时间演化的模型
- Xu & Hero (2014)、Bhattacharyya & Chatterjee (2020)——读什么：连边概率 $p_{k\ell}(t)$ 本身随时间演化的动态 SBM（状态空间模型视角）。为什么读：本章 6.3.4 显式假设"转移概率与度校正参数不随时间变"，这两篇说明放松该假设后的模型形态。
- Matias & Miele (2017)（可辨识性警告）——读什么：成员结构与交互核同时随时间变化时的可辨识性问题（哪个在变、变成什么，数据可能无法区分）。为什么读：这是 6.3.4"参数不随时间变"假设的理论理由，也是 6.3.1 VEM 的出处（Lemma 6.3 的更新公式即 Matias & Miele 的 VEM）；读它能理解本章为什么把两轴拆开处理。
未来工作声明（文件页 179 正文尾部，非 Further Notes 内）：原书在 Figure 6.7 讨论后声明——直觉上 $\lambda_t$ 应随 $t$ 增大（时间数据越多、对预言机的信心越强），留作未来工作。这是 Algorithm 19 留下的唯一显式开放问题：$\lambda_t$ 的数据驱动选择（可依 $\eta$ 或 $\hat P,\hat Q$ 自适应）。
17. 学习检查表
学完本章后自查：
- [ ] 能复述：成员结构与相互作用结构的定义，两轴四象限各对应哪个模型/小节；Example 6.1–6.3 各是什么特例。
- [ ] 能复述：Proposition 6.1 的三层阈值（一致 $\rho T\asymp1/n$、强一致 $\rho T\asymp\log n/n$、临界 $\tau\tilde I=K$），并能说出与 Ch4 Example 4.1/4.2 的对照关系（$\rho\to\rho T$）。
- [ ] 能解释：为什么朴素时间聚合丢失马尔可夫信息（$x_1$ vs $x_2$），持久边如何补回；$\beta=\log(P_{11}/Q_{11})$ 的符号为什么跟随 $P_{11}-Q_{11}$。
- [ ] 能推导：Prop 6.2 的 MLE 拆项（时间分解 + $\delta(z_i,z_j)$ 拆项 + 示性展开）；Lemma 6.1 从 (6.18) 到模块度的匹配（含 $\gamma$ 的校勘点）；Thm 6.2 的 CLT + 并集界；Lemma 6.3 的 VE 步求导；Prop 6.3 的 Bayes 分解与因子 2 的来源。
- [ ] 能判别：给定一个时序社区检测场景，判断该用哪条路线——参数已知/未知（Alg 15 vs 16）、是否长时间跨度（Alg 18）、成员是否漂移（Alg 17 vs 19）、批量还是在线（VEM/BP vs Alg 19）。
- [ ] 能判别：滞后问题的成因（历史交互污染当前标签）与 Figure 6.6 中 $\eta=1$/$\eta=0.85$ 两 panel 的反转（静态时聚合最优、漂移时聚合失效）。
- [ ] 能辨析：VEM 与 BP 的近似类型差异（优化 vs 消息传递）；Prop 6.1 与 Thm 6.2 的 regime 差异（$n,T$ 同发散 vs $n$ 固定 $T\to\infty$）；$\alpha,\rho,P,Q,\lambda$ 在不同小节的不同含义。
- [ ] 能定位：高中数据集三年数据的用法（2011 估计 $\hat P,\hat Q$ → 2012/2013 聚类）与 Table 6.1 对 Figure 6.5(a)/(b) 差异的解释（2012 年 $P_{11}\approx Q_{11}$ ⇒ 持久边无信息）；并能指出 2011 行 $\widehat\beta=0.58$ 与正文 $0.18$ 的确定性冲突，以及 2013 行概率代入 (6.17) 后为何必须采用双分支复现。
18. 后续衔接
- 回环闭合：Ch1 §1.1 的高中互动数据集（Table 1.1、Figure 1.4/1.5）在本章 6.2.3 被正式处理（Figure 6.5、Table 6.1）——Ch1 埋下的"按时间互动恢复班级"与"时间聚合丢信息"两个问题分别由 Algorithm 17/19 与 $x_1$/$x_2$ 分析回应。
- 反向支撑 Ch4/Ch5：Prop 6.1 把 Ch4 §4.4.3 的阈值语言推广到时间相关数据（快照数 = 信息增益的度量）；Prop 6.3 与 (6.21)–(6.23) 是 Ch5 §5.4 框架的第一个跨章复用实例，验证该框架的通用性。
- 第 7 章 Sampling in Networks：转向"拿不到全网时的估计"——与本章的共同主题是数据不完整条件下的推断（本章是时间维度不完整/演化，Ch7 是空间维度只能采样）；本章的在线/增量思想（Alg 15/16/19 的递推结构）与抽样估计的流式计算在工程上同源。
- 离书方向：Further Notes 两条线（§16）——BP 文献（Decelle et al. 2011；Moore 2017；Ghasemian et al. 2016）通往可恢复性相变的研究前沿；Xu & Hero 2014 与 Matias & Miele 2017 通往"成员与交互核同时演化"的可辨识性问题与状态空间型动态 SBM。章末未来工作（$\lambda_t$ 自适应）是 Algorithm 19 的直接改进入口。