Stochastic block models: A comparison of variants and inference methods
Stochastic block models: A comparison of variants and inference methods
复制标题
DOI：
10.1371/journal.pone.0215296
复制
发表时间：
2019-04-23
期刊：
影响因子：
3.7
通讯作者：
Becker, Till
中科院分区：
文献类型：
--
作者：
Funke, Thorben;Becker, Till
在复杂网络中发现社区是一项具有挑战性的任务，一种有前途的方法是随机块模型（SBM）。但由于受各领域的影响，其变体和推理方法也不尽相同。因此，需要对现有技术进行比较，并对其能力和弱点进行独立分析。作为第一步，我们回顾了不同的SBM变体的发展，如Karrer和纽曼或Peixoto的层次SBM的度校正SBM。除了在统一的符号中说明所有这些变体之外，我们还展示了它们发展的原因。知道的变体，我们讨论了各种方法来推断最佳分区一样的大都会黑斯廷斯算法。我们进行我们的分析的基础上，我们的扩展的Girvan-Newman测试和Lancichinetti-Rangato-Radicchi基准，以及一些真实的世界网络的选择。使用这些结果，我们给出了一些指导选择推理方法和SBM变体的挑战性任务。此外，我们给出了一个简单的启发式，以确定的步骤数的大都会黑斯廷斯算法，缺乏一个通常的停止标准。通过比较，我们希望能够指导SBM领域的研究，并突出现有技术的问题，以关注未来的研究。最后，通过免费提供我们的代码，我们希望促进更快的开发、集成和新思想的交流。
Finding communities in complex networks is a challenging task and one promising approach is the Stochastic Block Model (SBM). But the influences from various fields led to a diversity of variants and inference methods. Therefore, a comparison of the existing techniques and an independent analysis of their capabilities and weaknesses is needed. As a first step, we review the development of different SBM variants such as the degree-corrected SBM of Karrer and Newman or Peixoto's hierarchical SBM. Beside stating all these variants in a uniform notation, we show the reasons for their development. Knowing the variants, we discuss a variety of approaches to infer the optimal partition like the Metropolis-Hastings algorithm. We perform our analysis based on our extension of the Girvan-Newman test and the Lancichinetti-Fortunato-Radicchi benchmark as well as a selection of some real world networks. Using these results, we give some guidance to the challenging task of selecting an inference method and SBM variant. In addition, we give a simple heuristic to determine the number of steps for the Metropolis-Hastings algorithms that lack a usual stop criterion. With our comparison, we hope to guide researches in the field of SBM and highlight the problem of existing techniques to focus future research. Finally, by making our code freely available, we want to promote a faster development, integration and exchange of new ideas.