Production Systems and Logistic Systems, BIBA - Bremer Institut für Produktion und Logistik GmbH at the University of Bremen, Bremen, Bremen, Germany.
Faculty of Production Engineering, University of Bremen, Bremen, Bremen, Germany.
PLoS One. 2019 Apr 23;14(4):e0215296. doi: 10.1371/journal.pone.0215296. eCollection 2019.
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.
在复杂网络中发现社区是一项具有挑战性的任务，而 Stochastic Block Model（SBM）是一种很有前途的方法。但是，来自不同领域的影响导致了各种变体和推断方法的出现。因此，需要对现有的技术进行比较，并对它们的能力和弱点进行独立分析。作为第一步，我们回顾了不同 SBM 变体的发展，例如 Karrer 和 Newman 的度修正 SBM 或 Peixoto 的层次 SBM。除了以统一的符号表示所有这些变体外，我们还展示了它们发展的原因。了解了这些变体之后，我们讨论了各种推断最佳划分的方法，例如 Metropolis-Hastings 算法。我们基于我们对 Girvan-Newman 测试和 Lancichinetti-Fortunato-Radicchi 基准的扩展以及一些真实世界网络的选择来进行分析。使用这些结果，我们为选择推断方法和 SBM 变体这一具有挑战性的任务提供了一些指导。此外，我们还提供了一种简单的启发式方法来确定缺乏常用停止标准的 Metropolis-Hastings 算法的步骤数。通过我们的比较，我们希望指导 SBM 领域的研究人员，并强调现有技术的问题，以聚焦未来的研究。最后，我们通过免费提供我们的代码，希望促进更快的发展、新思想的集成和交流。
