An improved belief propagation algorithm for detecting mesoscale structure in complex networks

DOI10.1063/1.5097002zbMATH Open1435.62432arXiv1808.09080OpenAlexW3004813960WikidataQ89953298 ScholiaQ89953298MaRDI QIDQ5220488FDOQ5220488

Authors: Chuang Ma, Bing-Bing Xiang, Han-Shuang Chen, Hai-Feng Zhang 

Publication date: 26 March 2020

Published in: Chaos: An Interdisciplinary Journal of Nonlinear Science (Search for Journal in Brave)

Abstract: The framework of statistical inference has been successfully used to detect the meso-scale structures in complex networks, such as community structure, core-periphery (CP) structure. The main principle is that the stochastic block model (SBM) is used to fit the observed network and the learnt parameters indicate the group assignment, in which the parameters of model are often calculated via an expectation-maximization (EM) algorithm and a belief propagation (BP) algorithm is implemented to calculate the decomposition itself. In the derivation process of the BP algorithm, some approximations were made by omitting the effects of node's neighbors, the approximations do not hold if networks are dense or some nodes holding large degrees. As a result, for example, the BP algorithm cannot well detect CP structure in networks and even yields wrong detection because the nodal degrees in core group are very large. In doing so, we propose an improved BP algorithm to solve the problem in the original BP algorithm without increasing any computational complexity. By comparing the improved BP algorithm with the original BP algorithm on community detection and CP detection, we find that the two algorithms yield the same performance on the community detection when the network is sparse, for the community structure in dense networks or CP structure in networks, our improved BP algorithm is much better and more stable. The improved BP algorithm may help us correctly partition different types of meso-scale structures in networks.

Full work available at URL: https://arxiv.org/abs/1808.09080

Recommendations

• An improved algorithm for generalized community structure inference in complex networks
• Core-periphery structure in networks (revisited)
• Correlation enhanced modularity-based belief propagation method for community detection in networks
• Core-periphery structure in networks
• Multilayer modularity belief propagation to assess detectability of community structure

zbMATH Keywords

networksstatistical inference

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Applications of statistics to social sciences (62P25)

Cites Work

• Title not available (Why is that?)
• Community structure in social and biological networks
• Core-Periphery Structure in Networks (Revisited)
• Weighted community detection and data clustering using message passing
• Double phase transition of the Ising model in core–periphery networks

This page was built for publication: An improved belief propagation algorithm for detecting mesoscale structure in complex networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5220488)