Erdos-Renyi 随机图与展开图中的观点形成
本研究在随机的 d - 正则图中研究了图着色中颜色权重更新规则的影响,结果表明当颜色为红色的概率大于 1/2 时,随着时间的推移,红色会完全占据该图的所有节点,并通过定义新概念的方式回答了 Peleg 的开放性问题。
Nov, 2017
研究 Majority Model 和 Random Majority Model 在 social network 中的表现,证明了其稳定配置状态需要指数级的时间,以及稳定涂色方案的数量,对初态随机涂色的期望涂色数量进行了分析,并且研究了 “获胜集合” 大小的下界。
Feb, 2023
本文针对给定 n 个节点和 d 个邻居的无向图,提出了一种分布式的算法,使用随机翻转来改进图的连通性以获得新的拓展图,且经研究表明可以在 O(n ^ 2 d ^ 2 log n)的步骤内实现高概率有效。
Oct, 2015
研究了匿名代理网络中 Plurality Consensus 在 Gossip 模型中的运作,定义了新的度量 —— 单色距离来描述初始状态色彩的差距并证明了其关于收敛时间的紧确界性质,最终设计了基于随机游走的快速协议用于在正则扩展图上完成多数派表决。
Jul, 2014
本文研究了具有 $q$ 种颜色的 Potts 模型在带权图序列上的性质,证明了一定条件下的平均场预测在渐近意义下的正确性,应用于 Ising 和 Potts 模型,进一步证明了在渐近正则图上铁磁 Potts 模型和 Ising 模型的极限对数处理函数的普适性,并为渐近正则图上的 Potts 模型推导了大偏差原理。
Aug, 2015
本文研究随机图模型及其邻接矩阵、拉普拉斯矩阵的谱性质,其中包括对 Erdős-Rényi 图的分析,证明了矩阵与其期望的偏差在一定条件下的上界,并对已有的结果进行了改进。
Apr, 2012
本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度,其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图,对于稀疏随机图,其期望度数小于 o(logn),需要使这种度数正则化,本文通过一些方法,例如重量重排或删除足够的边等操作来实现,演示了在社区检测问题中,集中结果的应用。
Jun, 2015
本文介绍了一种使用谱算法的简单多项式时间用于进行图分割的方法,旨在寻找具有网络传导性和诱导子图的低导纳集合,并且提出了一种找到最佳 k 聚类的方法,其中 k 是一个整数,而且这种方法与 Cheeger's inequality 有所不同。
Sep, 2013