Sep, 2011

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

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

    本研究在考虑顶点度数变化的情况下，提出了一种改进的目标函数用于复杂网络社区结构检测，并提出了一种针对此函数或其非度数校正版本的启发式算法，表明度数校正版本在真实和合成网络中的表现显著优于未校正版本。

    Aug, 2010

  • 社群检测与随机块模型

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

    Mar, 2017

  • 层级随机块模型中的社区检测和分类

    该论文提出了一种强大、可扩展、综合的图中社区检测和比较方法，首先将图嵌入到一个适当的欧几里得空间中以获得低维表示，然后将顶点聚类成社区，并应用非参数图推理技术识别这些社区之间的结构相似性，然后可以递归地应用这两个步骤到社区上，以检测更细粒度的结构。最后，在模拟和真实数据上证明了该算法的有效性。

    Mar, 2015

  • 应用于法国政治博客圈的重叠随机块模型

    本文介绍一种新的 Overlapping Stochastic Block Model 方法，相对于现有的大多数聚类方法，允许节点属于多个重叠的群集，具有更高的灵活性和适用性，采用全局和局部变分技术的近似推断过程。

    Oct, 2009

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

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

    Jul, 2015

  • 光谱聚类和高维随机块模型

    本文提出了用于网络中的聚类分析的一种新方法，利用谱聚类在随机块模型中发现社区和研究潜在空间模型下的特征向量。

    Jul, 2010

  • 贝叶斯随机块模型

    本文介绍了利用贝叶斯推断从网络数据中提取大规模模块化结构的方法，重点介绍了基于随机块模型（SBM），以及其度修正和重叠推广。提供了一种允许防止过度拟合，实现模型选择的非参数公式。讨论了先验选择的方面，特别是如何通过加强贝叶斯层次结构来避免欠拟合，同时描述了执行单点估计和采样网络分区的有效算法。还展示了如何利用推断 SBM 来预测丢失和虚假链接，并揭示了网络中模块化结构可检测性的根本限制。

    May, 2017

  • 标签随机块模型中的社区检测

    利用标记的随机块模型来识别多种类型相互作用的社区检测问题，证明了检测阈值可以从信度传播的不敏感转换为敏感，进而进行模型推理的相关推理问题从不可能到可能的过渡，并得出了使用信度传播进行社区检测的结果，证明了理论假设的正确性。

    Sep, 2012

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

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

    Jul, 2018

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

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

    Mar, 2015