Abstract: The classical Belief Propagation (BP) algorithm can inference the marginal probability distributions and maximum likelihood probability of all nodes 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:strong energy, close loop and contradictory direction. 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 was 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

摘要： 经典的置信传播（BP）算法能够通过有限次数的迭代，推断出所有节点的边缘概率分布和最大似然概率。针对该算法在迭代过程中产生的影响精度和收敛速度的强烈震荡，找出了造成震荡的三个主要因素：强势能、紧密的环路和矛盾的方向，并有针对性地改进了该算法的核心更新规则；同时又进一步提出了异步消息传递方式，克服传统置信传播算法采用的同步消息传播方式的收敛慢、效率低等缺点。利用随机块模型拟合网络的生成过程，利用经典的期望最大化算法对模型进行求解，分别利用改进前后的置信传播算法推断隐变量的后验概率。在五个真实网络上的实验表明，两个改进均使得精度和速度不同程度地提高。

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