Oct, 2017

随机块模型的渐近有效估计器：朴素最大似然估计、带秩约束的最大似然估计和谱估计

PDF
TL;DR使用谱嵌入来估计随机块模型图中的块概率矩阵 B，在平均度数以 n 的 Ω(√n) 的速率增长时，我们建立了渐进正常性结果；当 B 是全秩的时，从谱嵌入得到的 B 的估计是渐近有效的；当 B 是奇异的时，从谱嵌入得到的估计可以比在没有排名假设的情况下最大化对数似然获得的估计具有更小的均方误差，并且可以几乎像假定已知 rk (B) 的真实 MLE 一样有效。
stochastic blockmodel graphsspectral embeddingasymptotic normalityblock probability matrixestimation
发现论文，激发创造
  • 关于随机块模型图的谱嵌入性能和揭示网络结构

    本文分析 Laplacian 和 adjacency 频谱嵌入在随机块模型图中块分配恢复方面的相对性能，并研究了嵌入性能与底层网络结构之间的关系，结果表明 Laplacian spectral embedding 更适用于相对稀疏的图，而 adjacency spectral embedding 更适用于核心 - 边缘网络结构。

    Aug, 2018

  • 随机块模型图的一致邻接谱嵌入

    本文介绍一种通过嵌入过程估算随机块模型中节点的块成员资格的方法，并证明了该方法的一致性和可靠性，可用于大规模图形和参与虚拟谱聚类等应用。

    Aug, 2011

  • 随机块模型中谱聚类的一致性

    研究了随机块模型中谱聚类在社区提取中的性能表现，并表明在最大期望度数的阶数为 $log~n$ 时，谱聚类应用于网络的邻接矩阵时，即使度数很小，也可以一致地恢复出隐藏的社区。

    Dec, 2013

  • 隐私保护的随机块模型邻接谱嵌入

    该论文提出了一种差分隐私邻接谱嵌入算法，用于随机块模型，实现了邻接谱嵌入的近似一致性，并且在确定的隐私参数下，可以实现与邻接谱嵌入相当的准确性。

    May, 2019

  • 利用光谱嵌入技术对随机游走特征值的锐利界限

    本文介绍了利用图的随机行走矩阵的前 k 个非平凡特征向量对图进行谱嵌入的方法，并使用此框架限制了所有图的所有特征值，并提出了一种新的工具 —— 谱嵌入，在分析可逆马尔可夫链中使用。

    Nov, 2012

  • 通过邻接谱嵌入理想地对随机块模型图进行聚类

    本文证明了邻接谱嵌入可以用于完美聚类随机块模型和度校正随机块模型，以及更一般的随机点积图模型。

    Oct, 2013

  • 在未知模型参数时，针对随机块模型的一致的邻接谱划分

    研究随机图中将顶点划分为块的谱技术，通过修改邻接谱分区算法，只需估计通信概率矩阵的秩上限，从而在模型错配的情况下实现一致性，也适用于具有多种模态的邻接表以及有向或无向的图。

    May, 2012

  • 谱嵌入的统计解释：广义随机点积图

    本文提出了一种新的混合成员随机块模型，使用频谱嵌入来生成节点向量表示，并通过使用高斯混合模型进行频谱聚类以及拟合保持最小体积的简单形体，可以在异 Philic 连接和消极的特定要求中提供更好的表现。

    Sep, 2017

  • 基于最大似然估计的有向图聚类中的随机块模型

    通过统计学的角度研究了有向图聚类问题，将聚类问题建模为有向随机块模型（DSBM）中估计底层社区的过程，并通过最大似然估计（MLE）推断出给定观察到的图结构的最可能的社区分配。此外，还建立了该 MLE 公式与新型流优化启发式算法之间的等价关系，该算法同时考虑了两个重要的有向图统计量：边密度和边方向。在此基础上，提出了两种高效且可解释的有向聚类算法，即谱聚类算法和基于半定规划的聚类算法。我们利用矩阵扰动理论中的工具给出了谱聚类算法中被错误聚类的顶点数量的理论上限。通过在合成数据和真实世界数据上定量和定性地比较我们提出的算法与现有的有向聚类方法，从而进一步验证了我们的理论贡献。

    Mar, 2024

  • 带有增长度数的随机块模型的最优假设检验

    研究在平均度数与图像增长的渐近情况下，将 Erdos-Renyi 随机图模型与随机块模型进行比较的方案和方法，提出了一种线性谱统计的新方法，并构建了一系列准确的测试统计量和一类自适应测试来解决假设检验问题。

    May, 2017