IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0215296.html
   My bibliography  Save this article

Stochastic block models: A comparison of variants and inference methods

Author

Listed:
  • Thorben Funke
  • Till Becker

Abstract

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.

Suggested Citation

  • Thorben Funke & Till Becker, 2019. "Stochastic block models: A comparison of variants and inference methods," PLOS ONE, Public Library of Science, vol. 14(4), pages 1-40, April.
    • Handle: RePEc:plo:pone00:0215296
    DOI: 10.1371/journal.pone.0215296
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0215296
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0215296&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0215296?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Kehui Chen & Jing Lei, 2018. "Network Cross-Validation for Determining the Number of Communities in Network Data," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 113(521), pages 241-251, January.
    2. Barucca, Paolo & Lillo, Fabrizio, 2016. "Disentangling bipartite and core-periphery structure in financial networks," Chaos, Solitons & Fractals, Elsevier, vol. 88(C), pages 244-253.
    3. Liao, Hao & Zeng, An & Zhang, Yi-Cheng, 2015. "Predicting missing links via correlation between nodes," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 436(C), pages 216-223.
    4. Paolo Barucca & Fabrizio Lillo, 2018. "The organization of the interbank network and how ECB unconventional measures affected the e-MID overnight market," Computational Management Science, Springer, vol. 15(1), pages 33-53, January.
    5. M. E. J. Newman & Aaron Clauset, 2016. "Structure and inference in annotated networks," Nature Communications, Nature, vol. 7(1), pages 1-11, September.
    6. Roger Guimerà & Alejandro Llorente & Esteban Moro & Marta Sales-Pardo, 2012. "Predicting Human Preferences Using the Block Structure of Complex Social Networks," PLOS ONE, Public Library of Science, vol. 7(9), pages 1-7, September.
    7. Aaron Clauset & Cristopher Moore & M. E. J. Newman, 2008. "Hierarchical structure and the prediction of missing links in networks," Nature, Nature, vol. 453(7191), pages 98-101, May.
    8. Dragana M Pavlovic & Petra E Vértes & Edward T Bullmore & William R Schafer & Thomas E Nichols, 2014. "Stochastic Blockmodeling of the Modules and Core of the Caenorhabditis elegans Connectome," PLOS ONE, Public Library of Science, vol. 9(7), pages 1-16, July.
    9. Catherine Matias & Vincent Miele, 2017. "Statistical clustering of temporal networks through a dynamic stochastic block model," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 79(4), pages 1119-1141, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. van Meeteren, Michiel & Trincado-Munoz, Francisco & Rubin, Tzameret H. & Vorley, Tim, 2022. "Rethinking the digital transformation in knowledge-intensive services: A technology space analysis," Technological Forecasting and Social Change, Elsevier, vol. 179(C).
    2. Luiz G. A. Alves & Higor Y. D. Sigaki & Matjaz Perc & Haroldo V. Ribeiro, 2020. "Collective dynamics of stock market efficiency," Papers 2011.14809, arXiv.org.
    3. Agnes Norris Keiller, 2020. "Detecting labour submarkets from worker-mobility networks: a preliminary study," IFS Working Papers W20/30, Institute for Fiscal Studies.
    4. Matjašič, Miha & Cugmas, Marjan & Žiberna, Aleš, 2021. "blockmodeling: an R package for Generalized Blockmodeling," SocArXiv b8cxp, Center for Open Science.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Kobayashi, Teruyoshi & Takaguchi, Taro, 2018. "Identifying relationship lending in the interbank market: A network approach," Journal of Banking & Finance, Elsevier, vol. 97(C), pages 20-36.
    2. Marnix Van Soom & Milan Van Den Heuvel & Jan Ryckebusch & Koen Schoors, 2019. "Loan Maturity Aggregation In Interbank Lending Networks Obscures Mesoscale Structure And Economic Functions," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 19/952, Ghent University, Faculty of Economics and Business Administration.
    3. Jun Liu & Jiangzhou Wang & Binghui Liu, 2020. "Community Detection of Multi-Layer Attributed Networks via Penalized Alternating Factorization," Mathematics, MDPI, vol. 8(2), pages 1-20, February.
    4. Sadamori Kojaku & Giulio Cimini & Guido Caldarelli & Naoki Masuda, 2018. "Structural changes in the interbank market across the financial crisis from multiple core-periphery analysis," Papers 1802.05139, arXiv.org.
    5. Hric, Darko & Kaski, Kimmo & Kivelä, Mikko, 2018. "Stochastic block model reveals maps of citation patterns and their evolution in time," Journal of Informetrics, Elsevier, vol. 12(3), pages 757-783.
    6. Valentina Macchiati & Piero Mazzarisi & Diego Garlaschelli, 2024. "Interbank network reconstruction enforcing density and reciprocity," Papers 2402.11136, arXiv.org, revised Jul 2024.
    7. Chunning Wang & Fengqin Tang & Xuejing Zhao, 2023. "LPGRI: A Global Relevance-Based Link Prediction Approach for Multiplex Networks," Mathematics, MDPI, vol. 11(14), pages 1-15, July.
    8. Dragana M. Pavlović & Bryan R.L. Guillaume & Soroosh Afyouni & Thomas E. Nichols, 2020. "Multi‐subject stochastic blockmodels with mixed effects for adaptive analysis of individual differences in human brain network cluster structure," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 74(3), pages 363-396, August.
    9. Yin, Likang & Zheng, Haoyang & Bian, Tian & Deng, Yong, 2017. "An evidential link prediction method and link predictability based on Shannon entropy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 482(C), pages 699-712.
    10. Fabrizio Lillo & Giorgio Rizzini, 2024. "Modelling shock propagation and resilience in financial temporal networks," Papers 2407.09340, arXiv.org.
    11. Yunpeng Zhao & Qing Pan & Chengan Du, 2019. "Logistic regression augmented community detection for network data with application in identifying autism‐related gene pathways," Biometrics, The International Biometric Society, vol. 75(1), pages 222-234, March.
    12. Andrea Flori & Fabrizio Lillo & Fabio Pammolli & Alessandro Spelta, 2021. "Better to stay apart: asset commonality, bipartite network centrality, and investment strategies," Annals of Operations Research, Springer, vol. 299(1), pages 177-213, April.
    13. Alessandro Ferracci & Giulio Cimini, 2021. "Systemic risk in interbank networks: disentangling balance sheets and network effects," Papers 2109.14360, arXiv.org, revised Sep 2022.
    14. Yao Hongxing & Lu Yunxia, 2017. "Analyzing the Potential Influence of Shanghai Stock Market Based on Link Prediction Method," Journal of Systems Science and Information, De Gruyter, vol. 5(5), pages 446-461, October.
    15. Gergely Tibély & David Sousa-Rodrigues & Péter Pollner & Gergely Palla, 2016. "Comparing the Hierarchy of Keywords in On-Line News Portals," PLOS ONE, Public Library of Science, vol. 11(11), pages 1-15, November.
    16. Ding, Ying, 2011. "Community detection: Topological vs. topical," Journal of Informetrics, Elsevier, vol. 5(4), pages 498-514.
    17. Liu, Jie & Ye, Zifeng & Chen, Kun & Zhang, Panpan, 2024. "Variational Bayesian inference for bipartite mixed-membership stochastic block model with applications to collaborative filtering," Computational Statistics & Data Analysis, Elsevier, vol. 189(C).
    18. Gräbner, Claudius, 2016. "From realism to instrumentalism - and back? Methodological implications of changes in the epistemology of economics," MPRA Paper 71933, University Library of Munich, Germany.
    19. Liu, Chuang & Zhou, Wei-Xing, 2012. "Heterogeneity in initial resource configurations improves a network-based hybrid recommendation algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(22), pages 5704-5711.
    20. Tamás Nepusz & Tamás Vicsek, 2013. "Hierarchical Self-Organization of Non-Cooperating Individuals," PLOS ONE, Public Library of Science, vol. 8(12), pages 1-9, December.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pone00:0215296. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.