Stochastic block models: A comparison of variants and inference methods.
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2019-01-01
|
| Series: | PLoS ONE |
| Online Access: | https://doi.org/10.1371/journal.pone.0215296 |
| _version_ | 1797661367979737088 |
|---|---|
| author | Thorben Funke Till Becker |
| author_facet | Thorben Funke Till Becker |
| author_sort | Thorben Funke |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T18:44:31Z |
| format | Article |
| id | doaj.art-28c490ba667c4abe8027f1f11f03ce3e |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-03-11T18:44:31Z |
| publishDate | 2019-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-28c490ba667c4abe8027f1f11f03ce3e2023-10-12T05:31:55ZengPublic Library of Science (PLoS)PLoS ONE1932-62032019-01-01144e021529610.1371/journal.pone.0215296Stochastic block models: A comparison of variants and inference methods.Thorben FunkeTill BeckerFinding 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.https://doi.org/10.1371/journal.pone.0215296 |
| spellingShingle | Thorben Funke Till Becker Stochastic block models: A comparison of variants and inference methods. PLoS ONE |
| title | Stochastic block models: A comparison of variants and inference methods. |
| title_full | Stochastic block models: A comparison of variants and inference methods. |
| title_fullStr | Stochastic block models: A comparison of variants and inference methods. |
| title_full_unstemmed | Stochastic block models: A comparison of variants and inference methods. |
| title_short | Stochastic block models: A comparison of variants and inference methods. |
| title_sort | stochastic block models a comparison of variants and inference methods |
| url | https://doi.org/10.1371/journal.pone.0215296 |
| work_keys_str_mv | AT thorbenfunke stochasticblockmodelsacomparisonofvariantsandinferencemethods AT tillbecker stochasticblockmodelsacomparisonofvariantsandinferencemethods |