在随机图中测试高维几何
考虑在稀疏随机网络中检测紧密社区的问题,将其形式化为在随机图中测试是否存在密集子图。在本文中,我们研究渐近稀疏情况下的信息理论下限,并比较了各种测试方法的性能,发现我们的检测边界是尖锐的。
Aug, 2013
给定以未知密度 f 为基础的 n 个 i.i.d. 随机向量 Xi 产生的随机几何图 Gn,估计其潜在空间的维度 d 的问题。研究发现,在满足条件 n^(3/2) r_n^d→∞和 r_n=o (1) 的情况下,存在一个估计器,其在概率意义下收敛于 d,对于所有满足∫f^5<∞的密度函数。条件允许极其稀疏的图,当 n^(3/2) r_n^d→0 时,图仅包含孤立边的概率很高。同时证明,在不对密度函数做任何条件的情况下,当 n r_n^d→∞和 r_n=o (1) 时,存在一个一致估计器来估计 d。
Nov, 2023
本文提出了一种基于样本点的谱估计器来构建随机几何图的方法,并证明其与非参数估计方法具有相同的收敛速率,同时提供了一种高效的计算方法,并通过该方法能够稳定地估计潜在空间的维度。
Sep, 2019
本文提出了一种利用角度信息和奇异值分解的子线性时间图聚类算法,并在其基础上给出了测试聚类可行性的查询复杂度下界,并且通过这些技术,也实现了新的子线性时间下界近似最大割价值的问题。
Aug, 2018
本文以最小极小值检验的角度考虑解决在高维信息检测中,两个离散随机图集合的假设检验问题,并提出了 Frobenius 范数和算子范数算法,能在小样本量下有效地求解较为稀疏的两种份离散图模型问题。
Jul, 2017
研究在平均度数与图像增长的渐近情况下,将 Erdos-Renyi 随机图模型与随机块模型进行比较的方案和方法,提出了一种线性谱统计的新方法,并构建了一系列准确的测试统计量和一类自适应测试来解决假设检验问题。
May, 2017
本文研究随机图模型及其邻接矩阵、拉普拉斯矩阵的谱性质,其中包括对 Erdős-Rényi 图的分析,证明了矩阵与其期望的偏差在一定条件下的上界,并对已有的结果进行了改进。
Apr, 2012
研究使用小子图的观察频率之间的关系来测试网络结构的问题,证明了在 Erdős-Rényi 空模型下的 T2,T3 的中心极限定理,并分析了与一般类别的替代模型相关的 χ2 检验统计量的功率。
Apr, 2017
本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度,其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图,对于稀疏随机图,其期望度数小于 o(logn),需要使这种度数正则化,本文通过一些方法,例如重量重排或删除足够的边等操作来实现,演示了在社区检测问题中,集中结果的应用。
Jun, 2015
在有界度模型的性质测试框架中研究了识别图的集群结构问题,提出了一个亚线性算法,可识别由参数 k, phi, epsilon 制定的 (d) 有界度图,并且是渐近最优的,关键是集群内外的 conductance。
Apr, 2015