尤心心，葛 檬

(天津大学 软件学院，天津 300350)

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

尤心心，葛 檬*

(天津大学 软件学院，天津 300350)

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

复杂网络；社团发现；置信传播；随机块模型；收敛速度

0 引言

社团结构是复杂网络[1]的一个重要特征，它将网络分成具有密集内在联系的子群，同一社团中的节点通常拥有共同的性质和紧密的关系[2]。因此，社团发现[3]问题成为了复杂网络研究中的一个重要的热点问题，激发了大量来自不同领域的学者对其进行研究。从社团发现算法的研究内容方面，可分为：1)基于网络结构的社团发现，代表方法有：凝聚或分裂算法[4]、基于模块度优化的方法[5]、谱方法[6]、动力学方法[2]、基于标签传播的方法[7]、基于仿生算法的方法[8]；……