稀疏随机网络中的社区检测

Aug, 2013

Community Detection in Sparse Random Networks

Ery Arias-Castro, Nicolas Verzelen

TL;DR考虑在稀疏随机网络中检测紧密社区的问题，将其形式化为在随机图中测试是否存在密集子图。在本文中，我们研究渐近稀疏情况下的信息理论下限，并比较了各种测试方法的性能，发现我们的检测边界是尖锐的。

Abstract

We consider the problem of detecting a tight community in a sparse random network. This is formalized as testing for the existence of a dense random subgraph in a random graph. Under the null hypothesis, the graph is a realization of an Erd\"os-R\'enyi graph on $N$ vertices and with co

tight community sparse random network dense random subgraph unknown subgraph detection bounds

发现论文，激发创造

随机图上社区检测的计算下界

研究检测大型 Erdős-Rényi 随机图中种植的小型密集社区的问题，并探究其计算复杂性及相变现象，结果可应用于恢复密集社区和逼近最密 $K$- 子图。

Jun, 2014

利用 Grothendieck 不等式在稀疏网络中进行社区检测

本研究提出一种基于 Grothendieck inequality 的方法，旨在证明随机图上半定规划问题的一致性，可适用于众多的网络随机模型和半定规划问题，并具有普适性。同时通过应用该方法于稀疏网络中的社交圈问题，可利用各种简单和自然的半定规划方案恢复社交圈结构。

Nov, 2014

在随机图中测试高维几何

研究了如何检测随机图中的高维几何结构问题，提出了一种基于新量的近乎最优和高效的测试方法，并针对稠密和稀疏情况提出了检测界和估计维度的猜想。

Nov, 2014

随机图的集中性与社区检测应用

本文回顾了随机图在其期望周围的浓缩区域中的不同模式，并讨论了这些浓缩结果在网络社区检测问题中的应用，同时介绍了一些与其相关的随机矩阵理论模型和工具。

Jan, 2018

稀疏网络社区检测的信息论门限

论文提出了信息论阈值的上下界，并进一步证明了当组数较大且特定参数取值时，物理条件下的凝聚阈值是具有严格界限的，若邻居间与组间边缘概率不同，则分配问题可以解决，否则无算法可优于随机。

Jan, 2016

大规模稀疏网络中的社群筛选

在研究中，我们介绍了一种适用于大规模稀疏网络的直观客观函数来量化聚类结果的质量，并且通过模拟网络的优化试验和基准问题的应用来证明了这种方法的实用性和准确性。

May, 2024

社区检测阈值与弱 Ramanujan 性质

通过邻域扩展构建的修改过的邻接矩阵，展现出弱的 Ramanujan 特性，从而在稀疏图中实现社区检测。

Nov, 2013

欧几里得随机图上的社区检测

本研究考虑在具有二元社区标签和 R^d 值位置标签的欧几里得随机几何图上进行社区检测问题，其中边缘概率依赖于社区和位置标签。我们针对稀疏和对数度规则建立了相变现象，并给出了阈值的约束。此外，我们还展示了在我们的模型与没有社区标签的空模型之间进行测试的可区分性问题的阈值没有相变现象，并且特别地与 SBM 不同。

Jun, 2017

利用小子图统计量测试全局网络结构

使用小子图的观察频率之间的关系，提出了一种基于三节点子图频率的社区结构存在简单检验方法，该方法能够在网络引导模型的零假设下，显示出渐近正态的检验统计量，并在纠正度量复合备选假设下具有接近于一的功率，此外，该方法亦可用于多元高斯数据的检验，并应用于社交网络、科学文章的引用网络和标普 500 公司之间的股票回报率的检测。

Oct, 2017

随机图的浓缩和正则化

本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度，其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图，对于稀疏随机图，其期望度数小于 o（logn），需要使这种度数正则化，本文通过一些方法，例如重量重排或删除足够的边等操作来实现，演示了在社区检测问题中，集中结果的应用。

Jun, 2015