大规模稀疏网络中基于伪似然方法的社区发现
本研究在考虑顶点度数变化的情况下,提出了一种改进的目标函数用于复杂网络社区结构检测,并提出了一种针对此函数或其非度数校正版本的启发式算法,表明度数校正版本在真实和合成网络中的表现显著优于未校正版本。
Aug, 2010
研究了随机块模型中谱聚类在社区提取中的性能表现,并表明在最大期望度数的阶数为 $log~n$ 时,谱聚类应用于网络的邻接矩阵时,即使度数很小,也可以一致地恢复出隐藏的社区。
Dec, 2013
提出了一种基于低阶多项式、半定规划和张量分解的高效贝叶斯估计问题的元算法,该算法的重点在于尽量紧密(达到添加低阶项的下限),并且通常可以达到统计阈值或猜测的计算阈值。在样本复杂度方面改善了社交网络检测和混合式社交网络模型的恢复保证,并且表明该任务可能需要指数时间。算法的基本策略是计算参数的后验分布的最佳低阶逼近,然后使用一个健壮的张量分解算法从这些近似的后验时刻中恢复参数。
Sep, 2017
本文研究在通用随机块模型下的实际网络社区层次结构,使用基于非标准化图拉普拉斯矩阵的菲德勒向量的标准递归双分割算法,并在广泛的模型参数范围内证明了该方法的强一致性,包括节点度数 $O (log n)$ 的稀疏网络和连接概率相差几个数量级的多尺度网络。此外,论文通过对合成数据和现实世界例子的演示,展示了算法的性能问题。
Apr, 2020
研究一种用于不规则网络与潜在属性的随机图模型,提出了一种计算有效性的光谱算法并展示了其可在部分可观察网络下进行渐近正确的推测,作为其分析的副产品,该模型提供了一种构建具有预先指定的特征谱的随机图模型的通用程序。
Jun, 2014
本文针对网络模型选择面临的数据稀疏、公共依赖、高维度和大量潜变量等挑战,通过研究将图分为一致连接模式的节点块的关键网络分析问题来说明这些挑战及其解决方法,提出了一种基于新的大图渐近分布对随机块模型的对数似然比分布的模型选择方法,发现在稀疏图中与经典结果存在显著差异,同时开发了度校正模型的对数似然的线性时间逼近算法,并在模拟和真实网络中的应用中表现出与我们的逼近算法极好的一致性。
Jul, 2012
本文提出一种基于谱初始化和伪似然分类器的两阶段快速过程,用于网络双分区检测或更一般地解决网络双聚类问题。该程序是弱一致的,同时在双分块随机模型下建立。通过数值模拟,证明了这种程序的有效性。
Mar, 2018
该论文提出了一种基于规范化拉普拉斯矩阵的正交对称非负矩阵三因式分解的方法,用于在复杂网络中进行社区检测,在包括稀疏和高度异质性的图中均表现良好,并且比现有技术表现更优。
May, 2016