Nov, 2019

基于双分图随机块模型的改进聚类算法

PDF
TL;DR该研究提出了一种基于谱聚类算法的新方法，可在 Bipartite 随机块模型中使用多项式时间算法实现精确和几乎全面的节点分区恢复，并改进了条件以使用现有算法进行近乎完全恢复，以及使用种植可满足问题与 BSBM（Bipartite 随机块模型）之间的联系进行研究以完全恢复种植任务。
发现论文，激发创造
  • 随机块模型中的精确恢复

    本文讨论了随机块模型的精确恢复问题，提出了一个基于半定规划松弛的高效算法，并找到了一个能成功恢复社区的尖锐阈值现象，该算法可以在该阈值上成功地进行聚类。

    May, 2014

  • 存在误差下的学习社区

    本文研究了学习社区并提供了鲁棒性恢复算法来解决 SBM 中建模误差的问题，SBM 广泛用于各个领域中的社区检测和图划分。我们考虑了两种 adversarial error，并回答了一个开放性问题，证明了我们的算法即使在 k>2 的情况下也可以实现几乎精确的恢复，并证明了我们的算法不仅适用于 SBM 生成的图，还应用于与 SBM 在 Kullback-Leibler 散度上相似的任何图分布。

    Nov, 2015

  • 隐私保护的随机块模型精确恢复

    使用边差分隐私模型，我们针对非对称 SBM（具有非均匀大小的社区）、一般结构 SBM（带有异常值）和被审查 SBM（带有边特征）推导了准确可恢复性的条件。与之前针对 SBM 的对称情况（社区大小相等）的最佳结果相比，我们的私有算法在多项式时间内具有与非私有设置相匹配的恢复阈值。

    Jun, 2024

  • 基于谱聚类算法的社区检测分析：一般二分图情形

    本文提出一种新的数据驱动正则化方法来解决稀疏网络中恢复邻接矩阵集中性的问题，进而探讨了一种新的谱截断方法对一般 SBM 中的分类错误率的影响，并在模型的一些扩展，包括不均匀随机图模型和二元聚类问题中得到更优性能的证明。

    Mar, 2018

  • 社群检测与随机块模型

    这份论文调查了随机块模型在社群检测中的基本极限，研究其信息理论和计算统计学等问题，列举了几种主要算法用于实现这些极限，并探讨了其他块模型以及一些待解决的问题。

    Mar, 2017

  • 基于随机块模型的超图：统计极限和半定规划方法

    该文章探讨了在随机超图模型中用于社区检测的随机块模型问题（k-SBM），研究了正确定位问题并表明其存在阈值现象：在阈值以下不可能以非零概率找回社区，而在阈值之上，有一个估计器几乎可以确定性地找回社区。作者还考虑了一种基于半定松弛技术的精确恢复问题的简单有效算法。

    Jul, 2018

  • 标记随机块模型中的最优簇恢复

    本文针对标记随机块模型中的社群检测或聚类问题研究了一种基于谱方法的算法，通过观察随机标签，找到至多 s 个错误分类项的聚类算法，并给出了该算法的时间复杂度为 O (npolylog (n))。

    Oct, 2015

  • 最优二分网络聚类

    本文提出一种基于谱初始化和伪似然分类器的两阶段快速过程，用于网络双分区检测或更一般地解决网络双聚类问题。该程序是弱一致的，同时在双分块随机模型下建立。通过数值模拟，证明了这种程序的有效性。

    Mar, 2018

  • 一般随机块模型下的社区发现：基本限制和高效恢复算法

    本文研究随机块模型中社区的分割和恢复问题，通过新的分歧函数来确定恢复阈值并提出了一个复杂度为准线性的算法来恢复社区，即使带有重叠部分的多个社区也可以进行恢复和检测。

    Mar, 2015

  • 通过半正定规划实现精确群集恢复阈值：扩展

    通过对 Semidefinite Programming（SDP）放松的最大似然估计进行研究，本文论证了 SDP 放松技术在社区检测中的可行性和通用性。

    Feb, 2015