基于平均场近似的BP 算法求解随机块模型*

马闯 杨晓龙 陈含爽 张海峰

1) (安徽大学互联网学院,合肥 230039)

2) (安徽大学物理与材料科学学院,合肥 230601)

3) (安徽大学数学科学学院,合肥 230601)

置信传播(BP)算法作为推断概率图模型的主流算法是求解随机块模型中联合概率分布的重要方法之一.但现有的方法要么在处理核边结构问题上存在精度不足问题,要么在理论的推导上存在近似太多,导致求解过程复杂且难以理解问题,或两个问题均存在.当然,精度不足也是由近似多造成的.导致理论近似多且推导复杂的主要原因,是随机块模型推断过程中求解联合概率分布并不是直接套用BP 算法,即处理的图(网络)与概率图模型的图不统一.因此,本文利用平均场近似修正联合概率分布,使其完全匹配BP 算法的迭代公式,这样使得在理论推导上简单易懂.最后通过实验验证,该方法是有效的.

1 引言

复杂系统可以用复杂网络进行建模,而复杂网络主要由点与边组成.在现实中,点与边的信息是可以直接或间接[1]获取的,如在航空网络系统中[2],节点为机场,如果机场之间具有航班,就存在一条边;科学家合作网络[3],节点表示科学家,如果两个科学家有合作就存在一条边等.这些简单的点与连边关系可以帮助我们揭示复杂系统的隐藏信息,如节点的属性,可以对应着节点在系统中属于哪个功能块或组织[4].如航空网络中的核心与外围(边缘)机场[5],科学家合作网络中的特定研究领域的小组[6]等.因此,如何通过节点的连边信息去探测这些中尺度结构,如社团结构、核边结构(核心-边缘),是一个重要的科学问题,这些问题得到了来自各个领域学者的研究.

社团结构的描述为社团内部紧密相连,而社团之间连接稀疏[6].社团结构的探测方法已经有很多,主要有基于模块度的方法[7−9]、谱划分的方法[4,10]、矩阵分解的方法[11,12]、基于动力学的方法[13,14]、随机块模型的方法[15,16]以及其他方法[17,18];核边结构的描述为核与核紧密相连,核与边紧密相连,边与边连接稀疏[19,20].相较于社团结构,对核边结构探测方法的研究相对较少.主要有给定某种中心性指标,然后通过截断选取最重要的一部分节点作为核心节点[21,22];定义核边结构的指标,然后利用最优化方法求解[23,24];通过随机块模型探测核边结构[25,26]以及其他方法[5,27−29].

可以看出,随机块模型在解决社团结构与核边结构的探测问题上都是行之有效的[25].随机块模型是一种生成模型,可以生成具有模块结构的网络[15].即首先给定n 个节点,随机分配到k 个模块中.假设向量 γ 表示每个模块的规模,即 γr表示第r 个模块的大小占总节点个数的比例,则每个节点就以 γr的概率分配到第r 模块中.然后给定一个k×k的关联矩阵p (对称矩阵),任意两个节点(一个节点属于模块s,一个节点属于模块r)以 prs的概率相连.这样就可以得到一个以参数 γ 与p 生成的随机网络.如,当 k=2 时,如果p11>p12,p22>p12,生成的网络具有社团结构;如果 p11≥p12≥p22,生成的网络具有核边结构.

给定特定参数 γ 与p,可以生成具有社团结构或核边结构的网络.也就是说,如果一个网络具有社团或核边结构,那么可以通过学习该模型(即模型参数),来确定它是怎么生成的,以此来探测哪些节点属于哪个社团,或者哪些节点属于核,哪些节点属于边.因此,随机块模型不仅可以用来探测社团结构,还可以用来探测核心边缘结构.其中EM 算法是学习该模型的重要方法[16,25,26,30,31],而通过联合概率公式,确定边际概率又是EM 算法的关键部分与难点.基于马尔科夫链的蒙特卡罗方法(MCMC)是解决该难点的一种较好的方法[30],但是由于采样空间非常大,会造成时间复杂度过高、精度低的问题.置信传播(BP)算法[32]可以很好地解决上述问题[16,25,26,31],因此被广泛用来解决社团或核边结构的探测问题.BP 算法用来推断马尔科夫随机场中的边际概率,当马尔可夫网络是树状图时,具有精确解;当马尔可夫网络是稀疏的,会得到近似精确解[33].

应用BP 算法解决社团结构的探测问题时,由于网络的稀疏性,在公式的推导中关于节点邻居可以忽略不计的近似是合理的[16,31],但是处理核边结构探测问题时,这种近似却是致命的,因为核节点具有天然的大度性质.因此,在另外一篇文章中,我们对BP 算法进行了稍微的改进(IBP),就可以很好地解决此问题[25].但是伴随而来的就是IBP 算法的推导过程中,需要进行大量的近似处理,以及各种模糊的推导,并不是可以套用BP 算法公式[34]直接得到的.同样的道理,BP 算法解决社团结构的探测问题时,即使其中各种近似是合理的,也会存在上述不能套用BP 算法公式直接得到的情况.这使得即使BP 或IBP 算法在社团划分或核边结构探测中能得到很好的结果,但是推导过程却是复杂且难于理解,或者说是不那么精确的.因此,本文从平均场近似[35]的角度出发,先应用平均场近似对联合概率进行处理,得到可以完全匹配BP 算法的形式,然后再套用BP 算法公式(而不是以往的先套用公式,然后在公式里近似处理),在不需要任何修改、近似以及假设的情况下直接得到求解边际概率的迭代公式.使得随机块模型解决社团结构或核边结构探测问题时,既可以保证结果的精度,又可以保证理论的简单明了、有理有据.

2 知识回顾

随机块模型最直接的用处就是按照某种需求生成具有某种模块结构的人工网络.例如在社团探测中,就可以用随机块模型生成具有社团结构的人工网络,以此来评估社团挖掘算法的好坏.但是本文将用到它的另外一个重要应用,就是通过学习随机块模型中的参数使其最好地匹配给定网络,从而揭示给定网络的结构.显然,这是一个参数估计问题,可以采用最大似然估计的方法进行解决[16,25,26].

2.1 最大似然估计

最大似然估计研究的是给定什么样的参数可以使得似然函数的值最大,也就是使得已经发生的事件概率最大.假设给定一个无权无向网络的邻接矩阵A,其中 Aij=1 表示第i 个节点与第j 个节点相连,Aij=0 表示不相连.在随机块模型中,当给定参数p 与 γ,则似然函数就可以用P(A|p,γ) 来表示.因此,需要最大化 P(A|p,γ),以此求解p 与γ,从而来揭示网络的结构.但是,通过观察可以发现,似然函数里包含一个隐形变量g,其中 gi表示节点i 所属的模块.因此有

可以看出,最大化公式(1)是一个含有隐变量的最大似然估计问题,因此可以应用EM 算法进行求解[36].

2.2 EM 算法求解随机块模型

EM 算法在理论推导上是根据詹森不等式不断求解对数似然函数的下界函数最优值,以此逐渐收敛到原始函数的最优值.因此,对(1)式取对数,然后根据詹森不等式有[25,26]:

其中

可以看出,q(g)=P(g|A,p,γ),表示给定一个网络,在参数p 与 γ 给定的条件下,该网络每个节点分配为g 的概率,这是一个联合概率.

当(3)式成立的情况下,(2)式等号成立,所以最大化公式(1)问题可以转化为最大化 L(p,γ) 问题.对 L(p,γ) 进一步推导有:

如果gi=r,则δgi,r=1,否则δgi,r=0.

根据上述推导过程,可以得到一个迭代公式.即首先初始化p 与 γ,根据(3)式计算边际概率与,然后根据(7)式与(8)式计算新的p 与 γ,重复上述过程直到收敛为止.最后可以通过收敛的边际概率的值对每个节点进行划分.其中,当需要探测社团结构时,只需初始化p 为具有社团结构形式的关联矩阵,如果需要探测核边结构时,则需要初始化p 为具有核边结构形式的关联矩阵.

需要注意的是,在应用(7)式求解 prs时,需要计算任意节点对之间的值,这将花费大量的计算时间.因此可以化简为

所以(7)式可以写成:

应用(11)式代替(7)式只需要计算有边的节点对的两节点边际概率,这将很大程度上减少计算量,特别是在稀疏网络.而且在BP 算法中这种处理更显得尤为必要,后面将进一步介绍.

到这里并没结束,通过遍历所有构型(kn种构型)的方法根据(3)式求解全概率 q(g) 以此求解边际概率是显然不可行的.因此如何根据(3)式求解边际概率是EM 算法的难点,也是关键部分.下面将介绍两种求解方法:MC 采样和BP 算法,并分析他们在处理社团与核边结构探测中存在的不足之处.

2.3 马尔科夫链蒙特卡罗方法(MCMC)

这里应用MCMC 模拟的方法按照联合概率公式(3)对网络的划分构型(即 g=[g1,g2,···,gn]T)进行采样.本文将采用单分量 Metropolis-Hastings(M-H) 方法[37].设表示在马尔科夫链中第t 轮迭代后的状态,其中每一轮迭代都需要对每个分量的状态进行一次迭代更新.

例如,在 t+1 轮迭代中,已经迭代好的分量(第i 个分量)的状态记为.假设要对第j 个分量进行采样,首先设表示在 t+1 轮迭代中在对第j 个分量进行处理时,其他分量的状态.特别地,当对每一轮的各个分量进行迭代是按照顺序处理时,有:

但是,由于所有构型共用 kn种可能,在网络较大的情况下,采样空间巨大,很难收敛到(3)式的概率分布,从而造成计算结果产生误差,并且不稳定.下面介绍一种快速求解边际概率的方法,即BP 算法.

2.4 BP 算法

2.4.1 BP 算法简介

BP 算法可以用来推断马尔科夫随机场(又称为概率图模型)中的边际概率[33].在本文中,考虑一种特殊的概率图模型—成对图模型.成对图模型定义在一个无向图G(V,E) 上,每一个顶点vi∈V表示X 中的一个随机变量 xi,每一条边(vi,vj)∈E表示随机变量 xi与 xj之间的某种依赖关系.给定每个节点 vi一个点位势 φi(xi),以及每一条边 (vi,vj)∈E 一个边位势 ψij(xi,xj),则在该成对马尔科夫网上的分布为

其中Z 为归一化常数,通常称为配分函数.

求解(14)式这个联合概率的边际概率可以通过BP 算法迭代公式求得,迭代过程如下[34]:

其中,N(i) 表示节点 vi的邻居,vi→j(xi) 为概率图修改后(即删除节点 vj) xi的边际概率,bi(xi) 为xi的边际概率.另外还可以得到一条边上两个节点的联合概率:

2.4.2 BP 算法求解随机块模型

对于联合概率公式(3),可以看成是一个马尔科夫网上的概率分布.在这里,马尔科夫网是一个全连通图,且随机变量为 g=[g1,g2,···,gn]T.对于一对节点 (vi,vj),如果 Aij=1,其边位势为ψij(gi,gj)=Pgigj,如果 Aij=0,其边位势 为ψij(gi,gj)=1−Pgigj,节点 vi的点位势为 φi(gi)=γgi.所以根据BP 算法的迭代公式(15),当j 节点是i 节点的邻居时,可以得到[26,31]:

假设1 如果第j 个节点不是第i 节点的邻居,移除节点 vj对节点 vi属于模块r 的概率没有影响,即有;

假设2 当网络规模很大且很稀疏的时候,对集合 V/N∗中所有元素做运算近似于对集合V 中所有元素做运算,即有 f(V/N∗)≈f(V),其中f(∗)代表某种运算.

根据上述两个假设,有:

这是一个外场量.所以(18)式可以写成:

其中配分函数为

其中配分函数为

根据(17)式可以得到一条边上两个点的联合概率:

通过不停迭代(20)式和(22)式,直到收敛,然后通过(22)式与(24)式即可计算出

上述算法在网络规模比较大且稀疏的时候是适用的,但是应用此方法探测核边结构,就会存在问题.众所周知,一个具有核边结构的网络的核节点不仅和核节点紧密相连,而且和边节点紧密相连,也就是说核节点与整个网络中的节点都是紧密相连的,具有天然的大度性质.所以在假设2 中,对集合 V/N∗中所有元素做运算近似于对集合V 中所有元素做运算,这种假设在核边结构的探测中是不合理的,有可能是错误的.针对于此,我们在另外一篇文章中对BP 算法进行了修正[25],可以很好地解决这个问题.

2.4.3 修正后的BP 算法(IBP)

首先对联合概率分布公式(3)稍作处理,可得:

则每条边的信使为[25,38]

给定一个假设:

假设3 当网络很大且很稀疏的时候,对集合V/{i,j}中所有元素做运算近似于对集合V 中所有元素做运算.显然,这个假设对结果的影响可以忽略不计.

根据假设1 与假设3 可以得到下面近似:

这是一个与(19)式一样的外场量,但是这里的近似与(19)式的近似相比,也就是假设3 与假设2 相比不会依赖节点度的大小,所以更适用于具有核边结构的网络.(26)式可以写成:

其中配分函数为

其中

根据(17)式可以得到一条边上两个点的联合概率:

通过(28)式,(30)式,(32)式与(20)式,(22)式,(24)相比,可以发现算法改进后,最终的结果仅仅是代替了 prs,没有增加任何多余的计算复杂度,但是修改后的方法已经验证了更适用于含有大度节点的网络[25],如核边结构网络.

改进后的算法虽然在结果上表现出来强大的优势,但是在理论推导上存在一定的问题.根据BP 算法的计算信使公式(15),从联合概率公式(25)并不能直接推导得到的信使迭代公式(26)(这种直接写法是参考文献[35]).这是因为概率分布公式(25)相比(3)式虽然做了变形处理,但是两个公式在数值上依然相等,即在把一个全连通图当做一个马尔科夫网的情况下,对于一对节点 (vi,vj),如果 Aij=1,其边位势还是 ψij(gi,gj)=Pgigj,如果 Aij=0,其边位势也还是 ψij(gi,gj)=1−Pgigj.所以说这里得到的信使迭代公式应该还是(18)式而不是(26)式.

在这里如果想从概率分布公式(25)得到相比信使迭代公式(18)更好的(26)式,换句话说,如果想得到比BP 算法更好的IBP 算法,可以按照下面的思路去理解.这里的马尔科夫网不仅仅是一个全连通图,还需要在全连通图上再加上M (原网络上边的个数)条额外边.对于一对节点 (vi,vj),如果 Aij=1,马尔科夫网上的边就要看成两条边,其边位势就分解成 ψij(gi,gj)=1−Pgigj与如果 Aij=0,其边位势还是 ψij(gi,gj)=1−Pgigj.这样理解以后,就可以按照BP 算法公式(15)得到信使迭代公式(26).即使这样,根据假设3 与假设2 还是得不到最终的信使迭代公式(28),在这里还应满足相比假设2更严格的假设,即:在马尔科夫网中所有边位势为ψij(gi,gj)=1−Pgigj的节点对 (vi,vj) (包括原网络中不存在边以及额外增加的存在边),有意思就是存在一些少部分节点对 (vi,vj),即使 vj是vi的邻居也要近似处理,即移除节点 vj对节点 vi属于模块r 的概率的影响忽略不计.总的来说,虽然改进后的BP 算法在实验结果上会表现出很好的效果,但是存在理论推导上比较复杂、近似处理的过程太多、不易理解等问题.

2.4.4 小 结

BP 算法可以对联合概率公式(3)与(25)进行求解,以此得到两种迭代公式(前者用BP 算法表示,后者用IBP 算法表示)求解边际概率.但是都存在一些问题:1)在BP 算法中,要满足假设1 与假设2,因此不适用核边结构的探测;2)在IBP 算法中,虽然在实验中已经验证了比BP 算法有着更好的性能,但是在理论上处理得太过复杂,还存在一些在理论上不易理解的假设.

而且,通过观察可以看出,无论是BP 算法还是IBP 算法所处理的马尔科夫网(至少也是全连通图)都是与要处理的原始网络不一致的.虽然原始网络是稀疏的,但是马尔科夫网络却是全连通的,这也造成了即使BP 算法与IBP 算法表现得效果好,却有所疑惑.这是因为我们都知道:当马尔科夫网是树状网络,BP 算法是精确的,当马尔科夫网是稀疏的时候,BP 算法是近似精确的.

所以,下面将从另外一个角度出发,即首先对联合概率公式(3)与(25)进行近似处理(而不是在BP 算法的推理中近似处理),得到一个新的概率公式,这个概率公式要满足两个条件:1)由这个公式导出的马尔科夫随机网与原始网络一致;2)这个公式在形式上与(14)式完全一致.前者可以保证马尔科夫网的稀疏性,后者可以保证在应用BP 算法的时候简洁明了且便于理解.

3 基于平均场近似的BP 算法

首先对联合概率公式(3)进行平均场近似处理.概率分布(3)式可以表示为

再应用一次平均场近似,即

因此联合概率公式(3)经过两次平均场近似可以写成:

把此联合概率分布定义为一个成对马尔科夫网上的概率分布,而且马尔科夫网与原始网络一致.其中,对于一条边 (vi,vj),其边位势为ψij(gi,gj)=[Pgigj,对于一个(节点 vi,) 其点位]势为φi(gi)=所以直接根据BP 算法的公式(15)—(17)式,可以不经过任何近似地得到:

其中配分函数 Zi→j与 Zi可以分别表示为

上述迭代过程我们记为MFBP 算法.

类似地,针对IBP 算法处理过程,也可以对联合概率公式(3)先进行变形、再平均场近似处理.即概率分布(3)式可以表示为

因此联合概率公式(3)经过一次平均场近似可以写成

把此联合概率分布定义为一个成对马尔科夫网上的概率分布,而且马尔科夫网与原始网络一致.其中,对于一条边 (vi,vj),其边位势为ψij(gi,gj)=对于一个节点vi,其点位势为φi(gi)=所以直接根据BP 算法的公式(15)—(17)式,可以得到:

其中配分函数 Zi→j与 Zi可以分别表示为

上述迭代过程记为MFIBP 算法.

对比BP 算法与MFBP 算法、IBP 算法与MFIBP 算法的最终迭代公式,发现不同的只是外场量.在节点个数足够多,且网络比较稀疏的情况下,BP 与IBP 算法的外场都可以表示为

又因为,di/n →0 且 ln(1−prs)→ prs,则MFBP 算法的外场量可以近似为

MFIBP 算法的外场量可以近似为

可以看出:理论上,经过平均场近似后得到的MFBP 算法和MFIBP 算法在一定条件下分别与原有的BP 算法和IBP 算法是等价的.但是在理论推导上,平均场近似的方法要更简单合理且便于理解.MFIBP 算法与MFBP 算法相比较,少了一次平均场近似.

下面将对比BP 算法和MFBP 算法,以及IBP 算法和MFIBP 算法实验上的效果.

4 中尺度结构的探测

下面将在社团结构及核边结构探测上进行实验验证.在社团结构探测中,为了验证不同算法探测结果的好坏,将采用NMI 指标进行衡量,即[39]:

其中,X 与Y 分别为算法探测的结果以及真实的结果;I(X,Y) 表示X 与Y 之间的互信息;H(X) 与H(Y)分别表示X 与Y 的信息熵.

对于核边结构的探测结果的评价,NMI 并不是一个合理的指标,这是因为核边结构的核与边的地位并不是等价的.所以将采用 F1 指标进行衡量,即[40]:

其中,P 表示预测结果中,预测为正(本文中为核)的样本中预测正确的概率,R 表示数据样本中,正样本中预测正确的概率.

4.1 社团结构探测

首先采用随机块模型生成具有社团结构的基准网络,以此来验证MFBP 算法和MFIBP 算法分别与BP 算法和IBP 算法的区别.假设有k 个模块,则每个节点就以 γr的概率分配到第r 模块中.社团之间节点的连边概率定义为prs=cin/n(r=s)和 prs=cout/n(rs),因此网络的平均度为c=

如果每个模块的大小一致,即 γr=1/k,则网络的平均度为 c=[cin+q(cout−1)]/q.定义模块外部与社团内部的连接概率比为 ε=cout/cin.所以,当 ε<1 时生成网络具有社团结构,且越小社团结构越明显;当 ε=1 时生成网络为ER 随机图.当n →∞时,网络检测社团结构会存在一个阈值[38]:

即,如果 ε>ε∗时,各种社团算法都无法检测出社团结构;当ε<ε∗时,BP 算法可以探测出社团结构.

从理论上,前面的分析可以看出,当网络节点个数足够多,网络连接比较稀疏时,BP 算法、MFBP 算法、IBP 算法以及MFIBP 算法是近似等价的,通过图1(a)可以验证,所有结果为10 次结果的平均值(下同).通过图1(b)—图1(d)可以发现,当网络连接稀疏且规模较小时,BP 算法、MFBP 算法、IBP 算法以及MFIBP 算法的结果也是一致的.但是,在网络连接稠密的情况下(如图2),可以发现MFBP 算法要优于BP 算法,且与MFIBP 算法、IBP 算法一致.

图1 稀疏基准网络社团结构探测 (a) n=10000,c=3,γ=[0.5,0.5]T,ε∗=0.27 ;(b) n=200,c=10,γ=[0.5,0.5]T,ε∗=0.520;(c) n=200,c=10,γ=[0.3,0.7]T ;(d) n=200,c=10,γ=[1/3,1/3,1/3]T,ε∗=0.419Fig.1.Community structure detection in sparse benchmark networks:(a) n=10000,c=3,γ=[0.5,0.5]T,ε∗=0.27 ;(b) n=200,c=10,γ=[0.5,0.5]T,ε∗=0.520 ;(c) n=200,c=10,γ=[0.3,0.7]T ;(d) n=200,c=10,γ=[1/3,1/3,1/3]T,ε∗=0.419.

图2 稠密基准网络社团结构探测 (a) n=200,c=50,γ=[0.5,0.5]T,ε∗=0.75 ;(b) n=200,c=50,γ=[0.3,0.7]T,(c) n=200,c=30,γ=[1/3,1/3,1/3]T,ε∗=0.599Fig.2.Community structure detection in dense benchmark networks:(a) n=200,c=50,γ=[0.5,0.5]T,ε∗=0.75 ;(b) n=200,c=50,γ=[0.3,0.7]T ;(c) n=200,c=30,γ=[1/3,1/3,1/3]T,ε∗=0.599.

4.2 核边结构探测

生成具有核边结构特性的基准网络来验证MFBP 算法和MFIBP 算法分别与BP 算法和IBP 算法的区别.给定3 个参数:核与核的连边概率 PCC,核与边的连边概率 PCP,以及边与边的连边概率PPP,当设置 PCC>PCP>PPP时,可以生成一个具有核边结构的网络[28].在本文中,设PPP=0.05,PCC=θ,PCP=0.6θ.网络的大小 n=200,其中核节点的个数为50,边节点的个数为150.图3所示为4 种算法在不同参数基准网络的核边结构的探测情况,其中实验结果为10 次结果的平均值.同样可以发现,MFBP 算法要优于BP 算法,且与MFIBP 算法、IBP 算法一致.在BP 算法中,当核边结构足够明显时,却表现出了较差的结果,这是因为核边结构明显,意味着网络结构稠密,特别是核节点的度很大,这会导致(19)式关于用所有节点集合近似邻居的补集变得极其不合理,而MFBP 算法、IBP 算法以及MFIBP 算法没有这方面的缺陷.

图3 基准网络的核边结构探测Fig.3.CP structure detection in benchmark networks.

接着,在美国航空网络上验证本文中的算法,其中每个节点代表一个机场,共有332 个节点;每条边表示两个机场具有航班,共有2126 条边[5].应用BP 算法,求解结果有27 个核;应用MFBP 算法,求解结果有34 个核;应用IBP 算法,求解结果有47 个核;应用MFIBP 算法,求解结果有47 个核.其中对应的参数结果见(54)式—(57)式.为了验证上述4 个算法求得结果的精确性,采用MCMC 采样求解EM 算法,共采样1000 轮(每轮n次),得到的结果共有47 核,具体参数如(58)式.如果把MCMC 结果作为真实结果,则BP 算法、MFBP 算法、IBP算法以及MFIBP 算法结果的F1值分别为0.730,0.840,1.000 以及1.000.从上述结果可以看出,在美国航空网络的核边结构实验中,MFBP 算法结果要优于BP 算法,MFIBP 算法结果与IBP 算法一致,且接近精确解.而且MFIBP算法要优于MFBP 算法,这是因为MFBP 算法比MFIBP 算法多一次平均场近似.

5 结论

本文详细描述了随机块模型探测社团结构、核边结构的理论,以及MCMC 和BP 算法求解该理论的方法,并分析其优缺点.通过理论分析以得到:1)原始的BP 算法不适用于核边结构的探测;2)修正后得到的IBP 算法,虽然适用于核边结构,但在理论上推导近似多且不明朗;3)无论是BP 算法还是IBP 算法,所处理的马尔科夫网(联合概率分布),既不是原始网络,也不满足网络稀疏条件.最后一条是造成随机块模型中BP 算法和IBP 算法理论难以理解的主要原因.针对于此,本文首先对联合概率分布进行平均场近似,得到一个好的联合分布函数,然后可以直接套用BP 算法理论,且在这一步不需要任何近似,使得BP 算法求解随机块模型这一套方法,不仅在结果上效果显著,而且在理论上通俗易懂.这种先通过平均场近似再套用BP 算法还适用于利用最小化哈密顿量(关于模块度的函数)探测社团结构的方法中[38],和本文一样,将使得理该论推导部分变得简单易懂.

本文的计算工作得到了安徽大学高性能计算平台的支持.