加权网络结构分析

潘琪,张海

(西北大学大学数学系,陕西西安 710127)

加权网络结构分析

潘琪,张海

(西北大学大学数学系,陕西西安 710127)

网络研究已经成为机器学习领域中的热点问题之一,近年来发展起来的随机块模型是通过建模生成网络的一种方法.本文对随机块模型加以推广,建立加权的随机块模型,在求解过程中,采用一种可以广泛的用于求解混合模型的变分EM算法.最后通过数据模拟,证明了此方法的可行性.

随机块模型;混合模型;变分EM方法

1 前言

在自然界中存在着大量的复杂系统,而这些系统都可以通过复杂网络来描述.复杂网络的研究涉及到生物科学,计算机科学,统计物理学,社会科学以及生命科学等各个领域.可以说,现实世界是一个由各种复杂网络构成的集合体.要分析一个网络并研究它的性质,可以有许多种方法.像度分布和聚类相关[1]等这些方法是可以被用来描述网络的,但它们却不能很好的研究整个网络的全局性.文献[2]在2002年提出一个直接的方法来研究网络的结构,即社区发现.在社区发现中用到的方法有:贪婪算法和基于图的邻接矩阵的谱分析的聚类算法.这些算法都假设组内关系强而组间关系弱.这可能对真实的所谓的社区是适用的,但对其他类型的网络可能就不适用了.而基于模型的方法是通过对比不同组之间点的不均匀性,从而得到明确模型,来直观的去理解它.其中,文献[3-4]最早在1971年提出了随机块模型.

而在传统的随机块模型中,考虑的是无权网络,无权网络只能给出两点之间的相互作用存在与否.但是,在许多的情况下,两点之间的关系或相互作用的强度的差异起着至关重要的作用.例如:Internet网络上的宽带、交通网络中的两站之前的车流量及乘客数量等都是影响网络性质的重要因素.大量的研究发现,权重及其分布会对整个网络的性质及其功能产生重要影响,所以加权网络已经成为复杂网络研究的一个重要领域.而本文所要研究的交通网络就是一个典型的加权网,其模型为高斯混合模型.

本文对随机块模型加以推广,建立加权的随机块模型.加权的随机块模型可以更好的解决现实问题.在求解过程中,若采用传统的极大似然估计将很难达到高速求解,所以用一种可以广泛的用于求解混合模型的变分EM算法.

2 随机块模型

2.1 混合模型

2.2 基于变分EM方法进行求解

本节利用变分EM方法,求出了服从高斯分布的加权随机快模型的参数估计值.在下一节中,将研究两个例子,以此来说明本节所涉及的算法的可行性.

3 实验

例1考虑两个无向网络,令n=50与n=100,分三组Q=3,令αq=(0.33,0.33,0.33).最后考虑µql与σ2ql,当q=l时,令µqq=2,σ2qq=4,而当q/=l时,令µql=2γ,σ2ql=4γ.其中,参数γ是控制组内和组间的联系强度的.若γ取值接近1,则导致很难区分组,而γ大于1则会使得组间关联强度大于组内关联强度,因此令γ=0.1,0.2,对每个参数的生成,模拟S=100次随机图,根据对应的高斯混合模型,用前面描述的算法来得到参数.

对每个αq,计算最小均值误差:

当n=50时得到表1.

当n=100时得到表2.

通过得到的结果可以看出,利用该算法求出的αq的最小均值误差的数值较小.这里γ取的很小是由于γ控制的是组间的联系强度,γ的值越小说明这个网络中的组内联系越强.若γ值取太大,则会导致组间的联系强度强强于组内的,这与现实不符,所以这里取γ很小.

对每个µql,计算相对误差:

同样,与αq一样,模拟n=50与n=100两个无向网络,且γ也取0.1与0.2两个值.得到表3.

表1 n=50时αq的最小均值误差

表2 n=100时αq的最小均值误差

表3 µql的相对误差

从得到的结果可以看出,当γ取很小时,得到的相对误差比较小.这里的γ取值比较小也是由于取值太大会导致组间联系强度比组内联系强度大.

4 结论

本文对随机块模型进行推广,研究了加权的随机块模型,更接近现实情况.在求解模型时,采用变分EM方法来代替传统的极大似然估计方法,有效地避免了求解似然函数方程的复杂性.由此可见,变分EM算法可以解决一些特殊的参数估计问题,尤其是一些混合模型求解.且这种算法也越来越得到人们的重视,可以说变分EM算法已成为实际应用中的一种有效方法.

致谢作者对张海老师的指导表示衷心感谢！

[1]Barabasi A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286:509-512.

[2]Girvan M,Newman M E J.Community structure in socialand biological networks[J].Proceedings of the National Academy of Sciences,2002,99:7821-7826.

[3]Lorrain F,White H C.Structural equivalence of individuals in social networks[J].Mathematical Sociology, 1971,1:49-80.

[4]Nowicki K,Snijders T A B.Estimation and prediction for stochastic blockstructures[J].American Statistical Association,2001,96:1077-1087.

[5]Jaakkola T.Tutorial on variational approximation methods.In Advanced Mean Field Methods:Theory and Practice[M].Cambridge:MIT Press,2000.

[6]Dempster A P,Laird N M,Rubin D B.Maximum likelihood from incomplete data via the EM algorithm[J]. Royal Statistical Socirty,Series B,1977,39:1-38.

[7]Jordan M I,Ghahramani Z,Jaakkola T,et al.An introduction to variationalmethods for graphical models[J]. Machine Learning,1999,37:183-233.

[8]Mahendra M,Stephane R,Corinne V.Uncovering latent structure in valued graphs:a variational approach[J]. The Annals of Applied Statistics,2010,2:715-742.

[9]Pierre L,Etienne B,Christophe A.Overlapping stochastic block models[J].Statistics for Systems Billogy, 2009,38:309-336.

[10]Zhang Yiyun.Regularization Parameter Selection for Variable Selection in High-Dimensional Modelling[M]. Ann Arbor:ProQuest,Umi Dissertation Publishing,2011.

[11]Newman M E J.Communities,modules and large-scale structure in networks[J].Nature Physics,2012,8:25-31.

[12]Newman M E J.The structure and function of networks[J].Computer Physics Communications,2002,8: 40-45.

[13]Nadakuditi R,Newman M.Graph spectra and the detectability of community structure in networks[J]. Physical Review Letters,2012,188701:1-5.

[14]Newman M.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2006,23:8577-8582.

[15]von Luxburg U.A tutorial on spectral clustering[J].Statistics and Computing,2007,17:395-416.

Structural analysis of weighted networks

Pan Qi,Zhang Hai

(Department of Mathematics,Northwest University,Xi′an710127,China)

Network research has become a hot topic in the feld of machine learning.Developed in recent years the stochastic block model is a method of generating network by modeling.This paper extends the stochastic block model,the establishment of a weighted random block model.In the solution process,you can use a wide range of models for solving mixed variational EM algorithm.Finally,through numerical simulations we prove the feasibility of this approach.

stochastic block model,mixed model,variational

O212.6

A

1008-5513(2013)06-0634-07

10.3969/j.issn.1008-5513.2013.06.013

2013-05-18.

国家自然科学基金(11171272).

潘琪(1988-),硕士生,研究方向：机器学习.

2010 MSC:46N30