Jul, 2015

随机块模型中社群检测的极小化率

PDF
TL;DR本研究提供一个通用 minimax 理论来解决社区检测问题，在广泛的设置中给出了 mis-match ratio 的 minimax 速率，包括同质和非同质 SBMs，密集和稀疏网络，有限和不断增长的社区数量。研究使用了一系列的惩罚最大似然方法来获得一个上界，并通过交换性质将全局 mis-match ratio 降至一个本地聚类问题来实现一个下界。结果同时阐明了在强一致性（精确恢复）和弱一致性（部分恢复）方面的阈值现象。
network analysisstochastic block modelcommunity detectionminimax theorypenalized likelihood-type approaches
发现论文，激发创造
  • 社群检测与随机块模型

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

    Mar, 2017

  • 加权随机块模型中的社区估计的最优速率

    研究了一种基于加权邻接矩阵的随机块模型， 并通过一种基于离散化的算法，利用 Renyi 散度来表征其误差率。

    Jun, 2017

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

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

    Mar, 2015

  • 多视角随机块模型中的社区检测

    该研究从信息论的角度考虑了在多个可能相关的图上的社区检测问题。通过建立多视图随机块模型 (MVSBM)，我们得出了一个信息论的上界和下界，当 MVSBM 的模型参数超过某个阈值时可以实现准确的社区恢复，否则期望的错误分类节点数将大于一。

    Jan, 2024

  • 关于超图社区发现的最小化最大化误分类比率

    本文提出了一个两步法的多项式时间算法，有利于利用超图的概率模型与第一步结果进行参数估计，以实现部分恢复的高精度聚类，并证明其在渐近性能上的好处。

    Feb, 2018

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

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

    Jul, 2018

  • 混合成员随机块模型中的最优估计

    这篇论文主要研究了重叠社区检测的问题，并提出了一种新的估计方法，以及建立了估计误差的下界。

    Jul, 2023

  • 随机块模型中的精确恢复

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

    May, 2014

  • 随机块模型中实现最佳误分类比例

    本论文提出了一种通用的，可以处理各种弱一致性问题的社区检测算法，在保证最优统计性能的同时，具有高计算效率和竞争性数值结果。

    May, 2015

  • 用于模块化网络的随机块模型渐近分析及其算法应用

    本文利用统计物理的空穴方法，对社交和生物网络中的随机块模型进行了研究，从拓扑学的角度来推断功能群或社区。我们详细描述了一些性质，例如检测性 / 不可检测性的相变和社区检测问题的易于 / 困难的相变，并将分析自然翻译为信念传播算法。该算法在最优方式下推断节点的组成员资格，并学习该块模型的潜在参数，最后应用于两个真实世界的网络并讨论其性能。

    Sep, 2011