加權網絡結構分析

潘琪,張海

(西北大學大學數學系,陜西西安 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