Phys. Rev. E 102, 012305 (2020) - Merge-split Markov chain Monte Carlo for community detection

Learn about our response to COVID-19, including freely available research and expanded remote access support.

Go Mobile »
Access by University of Bath Library

Merge-split Markov chain Monte Carlo for community detection

Tiago P. Peixoto

Phys. Rev. E 102, 012305 – Published 13 July 2020

Abstract

We present a Markov chain Monte Carlo scheme based on merges and splits of groups that is capable of efficiently sampling from the posterior distribution of network partitions, defined according to the stochastic block model (SBM). We demonstrate how schemes based on the move of single nodes between groups systematically fail at correctly sampling from the posterior distribution even on small networks, and how our merge-split approach behaves significantly better, and improves the mixing time of the Markov chain by several orders of magnitude in typical cases. We also show how the scheme can be straightforwardly extended to nested versions of the SBM, yielding asymptotically exact samples of hierarchical network partitions.

Received 24 March 2020
Accepted 19 June 2020

DOI:https://doi.org/10.1103/PhysRevE.102.012305

©2020 American Physical Society

Physics Subject Headings (PhySH)

Community structure Stochastic inference

Block models Community detection algorithms Monte Carlo methods

Interdisciplinary PhysicsStatistical PhysicsNetworks

Authors & Affiliations

Tiago P. Peixoto ^*

Department of Network and Data Science, Central European University, H-1051 Budapest, Hungary; ISI Foundation, Via Chisola 5, 10126 Torino, Italy; and Department of Mathematical Sciences, University of Bath, Claverton Down, Bath BA2 7AY, United Kingdom

^*peixotot@ceu.edu

Article Text

Click to Expand

References

Click to Expand

Issue

Vol. 102, Iss. 1 — July 2020

Reuse & Permissions

Physical Review A•B•C•D - 50 Years

To celebrate 50 years of enduring discoveries, APS is offering 50% off APCs for any manuscript submitted in 2020, published in any of its hybrid journals: PRL, PRA, PRB, PRC, PRD, PRE, PRApplied, PRFluids, and PRMaterials. Learn More »

Operations in the APS Offices, including the Editorial Office, will pause starting Friday, December 25 through Friday, January 1. Journal articles will continue to be published during this time. Submissions, referee reports, and other correspondence will be received and timestamped. Normal business operations will resume on Monday, January 4, 2021. We appreciate your understanding as processing and response times will be delayed.

APS and the Physical Review Editorial Office Continue to Support Researchers

COVID-19 has impacted many institutions and organizations around the world, disrupting the progress of research. Through this difficult time APS and the Physical Review editorial office are fully equipped and actively working to support researchers by continuing to carry out all editorial and peer-review functions and publish research in the journals as well as minimizing disruption to journal access.

We appreciate your continued effort and commitment to helping advance science, and allowing us to publish the best physics journals in the world. And we hope you, and your loved ones, are staying safe and healthy.

Ways to Access APS Journal Articles Off-Campus

Many researchers now find themselves working away from their institutions and, thus, may have trouble accessing the Physical Review journals. To address this, we have been improving access via several different mechanisms. See Off-Campus Access to Physical Review for further instructions.

Number of single-node move proposals (top panel) and acceptances (bottom panel) per second, for several empirical networks gathered from the KONECT repository [], with number of nodes , average degree and occupied groups indicated in axis legends. The different curves correspond to the single-node moves described in the text, as well as the algorithm by Riolo [], as shown in the legend. Missing points indicate a lack of recorded events in the allotted time. All algorithms were initialized with the same partition obtained with the agglomerative heuristic of [], and run for the same amount of time.
Comparison of runs with the single-node and merge-split MCMC algorithms, for a network of friendships between high school students [], starting for and states (except for the single-node algorithm, where the initialization is replaced with an agglomerative heuristic) showing the values of the effective number of groups as a function of the number of sweeps (where one sweep equals move proposals), the resulting distribution of values and unnormalized posterior probability for each run, drawn with different colors.
Posterior distribution of the effective number of groups obtained with the single-node and merge-split algorithms (top panel), as well as the respective autocorrelation functions (bottom panel), for the co-appearance network of characters of the novel Les Misérables by Victor Hugo [].
Posterior distribution of the effective number of groups obtained with the single-node and merge-split algorithms (top panel), as well as the respective autocorrelation functions (bottom panel), for the network of American football games between teams [].
Distribution of the effective number of groups at the lowest hierarchical level, obtained for several merge-split MCMC runs, starting from different initial conditions (with and an approximation of the ground state) drawn with different colors (left) and corresponding marginal hierarchical partition (right), for the neural network the organism [], the co-authorship network of network scientists [], and the network of recombinant antigen genes from the human malaria parasite []. In all cases, the different distributions coincide, indicating convergence to the target distribution.
Effective number of groups at the lowest level during several long runs of the merge-split MCMC algorithm using the hierarchical SBM, drawn with different colors, and corresponding distribution, for a network of political blogs [] and flights between airports from . In this case, discrepancies between the different distributions are still noticeable after long runs, indicating a lack of convergence to the target distribution.

Sign up to receive regular email alerts from Physical Review E

This site uses cookies. To find out more, read our Privacy Policy. I Agree