本文研究了主流模型在不同随机图中的表现，证明了连接度阈值可以切换颜色，同时发现此模型可作为 `good' and`fast' density classifier，此外还提出了一种在正规扩展图中的方法来使其快速转化。

May, 2018

本文讨论如何设计图形拓扑结构，以减少分散式优化算法的通信复杂度，发现扩展图形是最优选择之一，并提出三种方法以构建不同节点数和节点度数的扩展图形，数值结果显示分散式优化在扩展图形上的性能显著优于其他定期图形。

Dec, 2016

研究在 MPC 模型下对图连通性问题进行优化，通过图直径参数化时间复杂度，得到了对于直径为 D 的图的时间复杂度为 O (logDloglog (m/n) n)、总内存为 Θ(m) 的连通性算法，并扩展到生成森林、DFS 序列、最小生成森林和瓶颈生成森林等相关图问题，并指出这些问题的类似界限推导可以应用于更快的布尔矩阵乘法算法。

May, 2018

本文探讨了非后退随机游走在正则扩张图上的混合速率问题，证明了其速率可能是简单随机游走速率的两倍，并给出了其应用，并提出了一种类似于投掷球到篮子中的方法来描述所访问的点的多集。

Oct, 2006

通过在边上交换信息，图神经网络对图结构化数据进行操作。然而，信息过于压缩问题限制了这种信息传递范式，可能导致信息丢失。为了解决这个问题，最新的研究探索使用低直径高连通度的稀疏图 —— 扩展图来进行信息传递。然而，现有的扩展图传播方法只考虑了两两交互，忽略了复杂数据中的高阶结构。为了探索在利用扩展图的同时捕捉这些高阶相关性的好处，我们引入了高阶扩展图传播。我们提出了两种构建二分扩展图的方法，并在合成数据集和真实世界数据集上评估了其性能。

Nov, 2023

本文提出了一种基于随机游走的局部聚类算法，通过将内部连接性参数考虑入内，改进了先前结果，得到更优秀的聚类精度和 conductance，并探讨了其与全局谱算法之间的联系。

Apr, 2013

提出一种用于分析过度压缩的基于信息收缩的框架，此分析是基于 von Neumann 的可靠计算模型的，该计算模型认为在噪声计算图中过度压缩会导致信号闷灭。同时，本研究提出了一种基于重连的算法来缓解过度压缩问题。

Aug, 2022

本文提出了一种边交换性的随机图模型，与传统的节点交换性的随机图模型不同，可以规避 Aldous-Hoover 定理，呈现稀疏性，且与聚类等同构结构相关。

Mar, 2016

研究了小世界网络模型，证明该模型展现了正常的连续相变，提出实空间重整化群转化方法并计算了临界指数的准确值以及两个节点在网络中连接的平均度数随三个独立变量变化的比例。结果通过大量数值模拟得到证实。

Mar, 1999

本研究证明：在随机图中，最大独立集问题的组合结构会在独立集大小 k 超过 k nln (d)/d 这个点时发生相变，形成一个错综复杂的景象，局部搜索算法难以摆脱。这一现象通过 Metropolis 过程，即一个用于采样独立集的马尔可夫链实现了指数下界。

Jul, 2010