Title: An improved belief propagation algorithm for detecting meso-scale structure in complex networks,
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.