随机块模型

论文主要针对三类实例证明了加速效果：含大量偏置变量的公式、半随机2-CNF公式、正则扩展图上的Max-Cut和随机块模型图。

论文将算法应用于正则扩展图和随机块模型生成的图上的Max-Cut问题，同样获得了指数级加速。

随机块模型是一种生成具有社区结构的随机图的模型，图中顶点被划分为若干社区，社区内部和社区之间的边以不同的概率随机生成。