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

发布时间：2018-05-26 12:05

  本文选题：复杂网络 + 社团发现　； 参考：《计算机应用》2017年11期

【摘要】：经典的置信传播(BP)算法能够通过有限次数的迭代,推断出所有节点的边缘概率分布和最大似然概率。针对该算法在迭代过程中产生的影响精度和收敛速度的强烈震荡,找出了造成震荡的三个主要因素:强势能、紧密的环路和矛盾的方向,并有针对性地改进了该算法的核心更新规则;同时又进一步提出了异步消息传递方式,克服传统置信传播算法采用的同步消息传播方式的收敛慢、效率低等缺点。利用随机块模型拟合网络的生成过程,利用经典的期望最大化算法对模型进行求解,分别利用改进前后的置信传播算法推断隐变量的后验概率。在五个真实网络上的实验表明,两个改进均使得精度和速度不同程度地提高。
[Abstract]:The classical confidence Propagation (BP) algorithm can infer the edge probability distribution and the maximum likelihood probability of all nodes through a finite number of iterations. Aiming at the strong oscillation of the accuracy and convergence rate of the algorithm in the iterative process, three main factors are found out: strong energy, tight loop and contradictory direction. The core updating rules of the algorithm are improved and the asynchronous message passing method is proposed to overcome the shortcomings of slow convergence and low efficiency of the synchronous message transmission method used in the traditional confidence propagation algorithm. The stochastic block model is used to fit the generating process of the network, the classical expectation maximization algorithm is used to solve the model, and the improved confidence propagation algorithm is used to infer the posterior probability of the hidden variables. Experiments on five real networks show that both the two improvements improve the accuracy and speed to varying degrees.
【作者单位】： 天津大学软件学院;
【基金】：国家自然科学基金资助项目(61303110,61502334) 天津大学北洋学者·青年骨干教师项目(2017XRG-0016)~~
【分类号】：O157.5;TP301.6
，

本文编号：1937173