最优二分网络聚类
本文提出一种新的数据驱动正则化方法来解决稀疏网络中恢复邻接矩阵集中性的问题,进而探讨了一种新的谱截断方法对一般 SBM 中的分类错误率的影响,并在模型的一些扩展,包括不均匀随机图模型和二元聚类问题中得到更优性能的证明。
Mar, 2018
本文研究在通用随机块模型下的实际网络社区层次结构,使用基于非标准化图拉普拉斯矩阵的菲德勒向量的标准递归双分割算法,并在广泛的模型参数范围内证明了该方法的强一致性,包括节点度数 $O (log n)$ 的稀疏网络和连接概率相差几个数量级的多尺度网络。此外,论文通过对合成数据和现实世界例子的演示,展示了算法的性能问题。
Apr, 2020
该研究提出了一种基于谱聚类算法的新方法,可在 Bipartite 随机块模型中使用多项式时间算法实现精确和几乎全面的节点分区恢复,并改进了条件以使用现有算法进行近乎完全恢复,以及使用种植可满足问题与 BSBM(Bipartite 随机块模型)之间的联系进行研究以完全恢复种植任务。
Nov, 2019
本文提出了一种新的快速伪似然法来拟合社区内网络模型,以及一种允许任意度数分布的变体,并且在一系列设置下表现良好,并使用其提供了一个初始化值伪似然估计,其中伪似然估计在两个社区块模型的情况下提供了一致的估计。
Jul, 2012
通过引入具有顶点类型信息的双向随机块模型,我们解决了双向网络社区检测问题,并提出了一种不需要投影且统计原理明确的方法,可产生可解释的结果,成功地应用于合成和真实世界中的双向网络中。
Mar, 2014
研究了随机块模型中谱聚类在社区提取中的性能表现,并表明在最大期望度数的阶数为 $log~n$ 时,谱聚类应用于网络的邻接矩阵时,即使度数很小,也可以一致地恢复出隐藏的社区。
Dec, 2013
本研究提供一个通用 minimax 理论来解决社区检测问题,在广泛的设置中给出了 mis-match ratio 的 minimax 速率,包括同质和非同质 SBMs,密集和稀疏网络,有限和不断增长的社区数量。研究使用了一系列的惩罚最大似然方法来获得一个上界,并通过交换性质将全局 mis-match ratio 降至一个本地聚类问题来实现一个下界。结果同时阐明了在强一致性(精确恢复)和弱一致性(部分恢复)方面的阈值现象。
Jul, 2015
本文研究了具有多层网络时聚类网络的基本极限。我们在混合多层随机块模型下展示了最小极大网络聚类错误率,该率采用指数形式,并由组成网络的边概率分布的 Renyi 散度来描述。我们提出了一种包括基于张量的初始化算法和基于似然的 Lloyd 算法的新型两阶段网络聚类方法。网络聚类必须与节点社区检测相结合。我们的算法实现了最小极大网络聚类错误率,在 MMSBM 下还允许极稀疏网络。数值模拟和实际数据实验证明了我们的方法优于现有方法。此外,我们还将我们的方法和分析框架扩展到包括二项式、泊松和多层泊松网络的离散分布混合中,研究了最小极大聚类错误率。在这些离散混合中,这些最优聚类错误率均采用 Renyi 散度描述的相同指数形式。我们提出的两阶段聚类算法也可以达到这些离散混合中的最小极大聚类错误率。
Nov, 2023