- 具有异构奖励的分散随机分布的多智能体多臂赌博机
研究了去中心化多智能体多臂赌博问题,使用随机图来优化整个系统的综合悔恨度,引入了新的算法框架,其中包含加权技巧和上置信边界方法,算法具有较好的鲁棒性,并且考虑了图随机性,同时给出了不同命题下的悔恨度的上限。
- 未知流形上潜在结构网络中的半监督回归
本文利用潜在位置随机图模型和流形学习与图嵌入技术,通过预测节点响应变量来了解基于一维曲线的潜在位置向量的几何学特征,并为这些响应变量建立收敛保证,同时支持 Drosophila 大脑数据的实证应用。
- 稀疏扩张图拥有负曲率
研究证明,在有界次数扩展器中,不存在非负 Ollivier-Ricci 曲率,即使允许大量度数、特征值和负曲率边的比例缩小到零,这解决了 Naor 和 Milman 提出并由 Ollivier(2010)宣传的长期存在的一个问题。
- 大规模随机图上图卷积网络的收敛性和稳定性
本研究通过对随机图模型的分析,研究了图卷积网络(GCN)的性质,包括 GCN 达到其连续对应的收敛性以及 GCN 对随机图小变形的稳定性,这有助于解释卷积表示在欧几里得域中成功的原因。
- 基于叠加随机块模型的高阶谱聚类
本研究旨在探究超级叠加随机块模型 (SupSBM) 在解决复杂网络社区检测问题中的作用。研究者提出使用新模型可以更精确地捕获局部聚类、短平均路径和社区结构等更真实的网络现象,并进一步证明多个高阶谱聚类方法的性能在该模型下是满足特定的误分类错 - 光谱图锻造:以模块化为目标的图形生成
本文介绍了一种基于矩阵表示和谱结构的合成方法:调控模块度矩阵的低秩近似,生成保留原真实网络社区结构和随机性的合成网络,该方法在精度和结构保留上优于现有技术。
- 图与集合的集合的调和
本研究探讨了集合对账问题的推广,包括图对账,我们提供了几种算法来解决此问题,并且还讨论了该算法在图表、数据库和文档集合中的应用。针对图对账,我们提供了基于集合对账的协议,适用于随机图和有根树。
- 随机块模型中的社区检测主动学习
本文主要研究了随机块模型的聚类问题和主动学习的应用,发现在一定条件下,即使在聚类阈值以下,仅仅采样少量的节点标签,也能高概率地完成完整的社区检测,所提供的高效学习算法能够很好地验证这一理论,并通过数值实验进行了验证。
- 可交换随机测度生成的随机图类
介绍了一类随机图形,通过定义概率对称性:图形的每个排列都不影响其分布,使用简单的 Kallenberg 定理特化的表示定理得到其分布特征,可得期望与度分布等结构信息,研究表明其可以产生包含极少连接的图结构且某些构型可产生一个连通部分包含任意 - MM随机图的浓缩和正则化
本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度,其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图,对于稀疏随机图,其期望度数小于 o(logn),需要使这种度数正 - 稀疏随机图上的半定规划及其在社区发现中的应用
研究了 Erdos-Renyi 图和随机图在半定规划过程中的类似行为,用一些新的工具进行了证明,证明了 SDP 检测带有信息隐匿的随机图中的对称社区检测问题达到了信息论阈值。
- 随机正则图的局部半圆定理
研究了顶点数为 $N$,每个顶点度数为 $d$ 的 $d$-regular 随机图的谱特性,得出了这些图的距离谱特性与 Wigner 半圆律高度吻合,从而证明了所有特征向量的完全离散与量子唯一性吗的概率版本。
- 稀疏随机图:正则化和拉普拉斯的集中
本文研究了具有可能不同边缘概率的随机图,位于期望度数有限的稀疏区域。通过在邻接矩阵的每个条目中添加数量级为 1/n 的常数,达到正则化的效果,证明了其集中作用,从而证实了在随机块模型下基于正则化谱聚类的一种最简单和最快速的社区检测方法的有效 - 在线社区识别的顺序变点方法
本文提出了基于 Erdos-Renyi 随机图的新算法,用于从时序观测中检测网络中社区的出现。 所开发的三个算法分别为 Exhaustive Search(ES),mixture,和 Hierarchical Mixture(H-Mix)。 - 关联方案、非交换多项式集中和种植团问题中的平方和下界
本文介绍了一种求解随机图和 “planted” clique 变体中单个 clique 大小的问题的算法,证明了使用 Sum-of-Squares Hierarchy 算法的 r 轮仅能解决 t > sqrt (n)/(Clogn)^(r^ - 随机图上的硬核模型重访
本文通过采用空腔方法,研究硬核模型在随机规则图上的最密堆积密度与相变性质,证明了硬核模型是结构玻璃和堵塞问题最简单的平均场晶格模型。
- 稀疏随机图上本地算法的限制
本文研究了关于在图上的局部算法。我们证明了局部算法产生的每个独立集都比最大集合要小,而且通过聚类属性,我们强调了在随机图上的局部算法存在局限性。
- 利用含噪度进行推断:差分隐私 β- 模型和合成图
本文利用 $eta$-model of random graphs 建立隐私机制并研究了 MLE 存在条件问题,提出了一种私有的参数估计器并证明了其一致性和渐近正态分布特性,同时解决了通过隐私机制释放的数据如何有效地进行统计推断的基础问题 - 反铁磁伊辛模型和硬核模型的分区函数不可近似性
研究了在随机图上估计硬核模型和反铁磁伊辛模型的区别,证明了对于反铁磁伊辛模型在非一意性区域内不存在近似方案。
- 随机块模型与重构
本文研究了稀疏种植分区模型(即随机块模型)中的聚类阈值问题,证明了在某些情况下聚类是不可能的,并提供一种简单高效的算法来估计模型参数。