Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (11): 3115-3118.DOI: 10.11772/j.issn.1001-9081.2017.11.3115

Previous Articles     Next Articles

Community detection algorithm based on belief propagation in complex networks

YOU Xinxin, GE Meng   

  1. School of Computer Software, Tianjin University, Tianjin 300350, China
  • Received:2017-05-16 Revised:2017-06-07 Online:2017-11-10 Published:2017-11-11
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61303110, 61502334), the Peiyang Scholar-Elite Scholar Program of Tianjin University (2017XRG-0016).

基于置信传播的复杂网络社团发现算法

尤心心, 葛檬   

  1. 天津大学 软件学院, 天津 300350
  • 通讯作者: 葛檬
  • 作者简介:尤心心(1993-),女,山东乐陵人,硕士研究生,主要研究方向:社团发现、数据挖掘;葛檬(1992-),男,浙江台州人,硕士研究生,主要研究方向:深度学习、社团发现。
  • 基金资助:
    国家自然科学基金资助项目(61303110,61502334);天津大学北洋学者·青年骨干教师项目(2017XRG-0016)。

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

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

CLC Number: