稀疏随机图:正则化和拉普拉斯的集中
本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度,其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图,对于稀疏随机图,其期望度数小于 o(logn),需要使这种度数正则化,本文通过一些方法,例如重量重排或删除足够的边等操作来实现,演示了在社区检测问题中,集中结果的应用。
Jun, 2015
在随机图中,将边权值视为概率,如果最小期望度数为 ω(ln n),则随机图的邻接矩阵和拉普拉斯矩阵集中于边权为概率的加权图,应用于债券渗透和不均匀随机图问题中,通过引入矩阵 concenetration 和集中不等式得到新的结论。
Nov, 2009
通过利用 Laplacian 约束的高斯图模型解决网络拓扑推断问题,我们将任务重塑为估计一个图拉普拉斯形式的精度矩阵。通过在此模型中检验广泛使用的 l₁范数的局限性,我们发现正则化参数的增大会导致解中非零条目的数量增加,理论上,大的正则化参数会导致完全连接(最密)的图。为了克服这些挑战,我们提出了一种图拉普拉斯估计方法,结合了 l₀范数约束。我们开发了一个高效的梯度投影算法来解决由稀疏性和拉普拉斯约束所特征化的优化问题。通过对合成和金融时间序列数据集进行数值实验证明了所提方法在网络拓扑推断中的有效性。
Sep, 2023
本文通过研究高阶超图随机游走,介绍了一组超图拉普拉斯算子以统一超图的不同版本,证明这些拉普拉斯算子的特征值可以有效地控制高阶随机游走的混合速率,推广距离 / 直径和边界扩展。
Feb, 2011
通过对随机块模型和其延伸的研究,我们表明,通过正规化可以显著提高谱聚类的性能,并且证明了利用正规化参数估计的数据驱动技术 DKest 可以很好地应用于实际数据集和仿真数据集。
Dec, 2013
本文提供一种有偏差方差权衡的图拉普拉斯正则化方法,该方法广泛应用于图信号处理和半监督学习任务。在分析中,将最优正则化参数的尺度定于谱图属性和信噪比参数,并应用于三种应用(包括随机信号、带限信号和多样本图信号)。通过实验验证了所建立分析的接近最优性能。
Jun, 2017
通过概率测度采样子流形在欧几里得空间的样本,可以构造一个邻域图,作为子流形的近似。本文确定了文献中使用的三种不同图 Laplacian 在样本大小增加且邻域大小趋近于零时的点态极限。我们表明,在子流形上的均匀测度下,所有图 Laplacians 在常数的意义下均具有相同的极限。然而,对于在子流形上的非均匀测度的情况,只有所谓的随机游走图 Laplacian 收敛于加权 Laplace-Beltrami 算子。
Aug, 2006
本文介绍了一种扩展了边远离独立性的稀疏随机图的一般模型,并且通过构造非齐性随机超图来替代每个超边,再通过与某个积分算子的范数相关来解释巨型连通性的临界点,并将该巨型连通量与某些(非 Poisson)多类型分支过程的生存概率关联起来,同时研究度分布和数量小子图的细节。
Jul, 2008