《《系列文章》》【统计-计算间隙：归约法的理论与实验】第16章：完整案例研究——社区检测中的统计-计算间隙
第16章：完整案例研究——社区检测中的统计-计算间隙
知识公有化声明：本章为基于公开教材与论文的独立教学讲义，所有公式为通用形式推导，图表为原创设计，代码为独立实现。
16.1 引言：一个问题的四重透视
核心工程问题：社区检测（Community Detection）是网络科学中最基础的无监督学习任务之一。给定一张图，判断其是否具有社区结构，并恢复社区标签。本问题在统计-计算间隙的研究中具有特殊地位——它是少数几个信息论阈值被精确确定、计算阈值被广泛研究、归约下界可得、且低度方法给出匹配预测的问题。
本章将社区检测作为"完整案例研究"，从四个视角进行系统分析：
- 信息论视角：检测与恢复的信息论极限在哪里？
- 算法视角：实际算法（谱聚类、信念传播、SDP）能做什么？
- 归约视角：如何从 PC 出发证明社区检测的困难性？
- 低度视角：低度多项式如何预测 Kesten-Stigum 阈值？