关键词: 复杂网络, 社团发现, 置信传播, 随机块模型, 收敛速度

Abstract: The Belief Propagation (BP) algorithm can inference the marginal probability distributions of all nodes and maximum likelihood probability by a finite number of iterations. However, BP algorithm always causes strong oscillation in the iterative process, and it uses synchronous way to pass messages which seriously affects the convergence rate. According to a lot of research, three main factors which caused oscillation were found. Furthermore, a new update formula and an asynchronous way of passing messages were proposed to solve above two problems. Stochastic block model was used to model the network generation process and the result of community division is obtained by using classical expectation maximization algorithm combined with BP. Extensive experimental results on real-world networks show the superior performance of the new method over the state-of-the-art approaches.

Key words: complex network, community detection, Belief Propagation (BP), stochastic block model, convergence rate