加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)分析

潘琪,張海

(西北大學(xué)大學(xué)數(shù)學(xué)系,陜西西安 710127)

加權(quán)網(wǎng)絡(luò)結(jié)構(gòu)分析

潘琪,張海

(西北大學(xué)大學(xué)數(shù)學(xué)系,陜西西安 710127)

網(wǎng)絡(luò)研究已經(jīng)成為機器學(xué)習(xí)領(lǐng)域中的熱點問題之一,近年來發(fā)展起來的隨機塊模型是通過建模生成網(wǎng)絡(luò)的一種方法.本文對隨機塊模型加以推廣,建立加權(quán)的隨機塊模型,在求解過程中,采用一種可以廣泛的用于求解混合模型的變分EM算法.最后通過數(shù)據(jù)模擬,證明了此方法的可行性.

隨機塊模型;混合模型;變分EM方法

1 前言

在自然界中存在著大量的復(fù)雜系統(tǒng),而這些系統(tǒng)都可以通過復(fù)雜網(wǎng)絡(luò)來描述.復(fù)雜網(wǎng)絡(luò)的研究涉及到生物科學(xué),計算機科學(xué),統(tǒng)計物理學(xué),社會科學(xué)以及生命科學(xué)等各個領(lǐng)域.可以說,現(xiàn)實世界是一個由各種復(fù)雜網(wǎng)絡(luò)構(gòu)成的集合體.要分析一個網(wǎng)絡(luò)并研究它的性質(zhì),可以有許多種方法.像度分布和聚類相關(guān)[1]等這些方法是可以被用來描述網(wǎng)絡(luò)的,但它們卻不能很好的研究整個網(wǎng)絡(luò)的全局性.文獻[2]在2002年提出一個直接的方法來研究網(wǎng)絡(luò)的結(jié)構(gòu),即社區(qū)發(fā)現(xiàn).在社區(qū)發(fā)現(xiàn)中用到的方法有:貪婪算法和基于圖的鄰接矩陣的譜分析的聚類算法.這些算法都假設(shè)組內(nèi)關(guān)系強而組間關(guān)系弱.這可能對真實的所謂的社區(qū)是適用的,但對其他類型的網(wǎng)絡(luò)可能就不適用了.而基于模型的方法是通過對比不同組之間點的不均勻性,從而得到明確模型,來直觀的去理解它.其中,文獻[3-4]最早在1971年提出了隨機塊模型.

而在傳統(tǒng)的隨機塊模型中,考慮的是無權(quán)網(wǎng)絡(luò),無權(quán)網(wǎng)絡(luò)只能給出兩點之間的相互作用存在與否.但是,在許多的情況下,兩點之間的關(guān)系或相互作用的強度的差異起著至關(guān)重要的作用.例如:Internet網(wǎng)絡(luò)上的寬帶、交通網(wǎng)絡(luò)中的兩站之前的車流量及乘客數(shù)量等都是影響網(wǎng)絡(luò)性質(zhì)的重要因素.大量的研究發(fā)現(xiàn),權(quán)重及其分布會對整個網(wǎng)絡(luò)的性質(zhì)及其功能產(chǎn)生重要影響,所以加權(quán)網(wǎng)絡(luò)已經(jīng)成為復(fù)雜網(wǎng)絡(luò)研究的一個重要領(lǐng)域.而本文所要研究的交通網(wǎng)絡(luò)就是一個典型的加權(quán)網(wǎng),其模型為高斯混合模型.

本文對隨機塊模型加以推廣,建立加權(quán)的隨機塊模型.加權(quán)的隨機塊模型可以更好的解決現(xiàn)實問題.在求解過程中,若采用傳統(tǒng)的極大似然估計將很難達(dá)到高速求解,所以用一種可以廣泛的用于求解混合模型的變分EM算法.

2 隨機塊模型

2.1 混合模型

2.2 基于變分EM方法進行求解

本節(jié)利用變分EM方法,求出了服從高斯分布的加權(quán)隨機快模型的參數(shù)估計值.在下一節(jié)中,將研究兩個例子,以此來說明本節(jié)所涉及的算法的可行性.

3 實驗

例1考慮兩個無向網(wǎng)絡(luò),令n=50與n=100,分三組Q=3,令αq=(0.33,0.33,0.33).最后考慮μql與σ2ql,當(dāng)q=l時,令μqq=2,σ2qq=4,而當(dāng)q/=l時,令μql=2γ,σ2ql=4γ.其中,參數(shù)γ是控制組內(nèi)和組間的聯(lián)系強度的.若γ取值接近1,則導(dǎo)致很難區(qū)分組,而γ大于1則會使得組間關(guān)聯(lián)強度大于組內(nèi)關(guān)聯(lián)強度,因此令γ=0.1,0.2,對每個參數(shù)的生成,模擬S=100次隨機圖,根據(jù)對應(yīng)的高斯混合模型,用前面描述的算法來得到參數(shù).

對每個αq,計算最小均值誤差:

當(dāng)n=50時得到表1.

當(dāng)n=100時得到表2.

通過得到的結(jié)果可以看出,利用該算法求出的αq的最小均值誤差的數(shù)值較小.這里γ取的很小是由于γ控制的是組間的聯(lián)系強度,γ的值越小說明這個網(wǎng)絡(luò)中的組內(nèi)聯(lián)系越強.若γ值取太大,則會導(dǎo)致組間的聯(lián)系強度強強于組內(nèi)的,這與現(xiàn)實不符,所以這里取γ很小.

對每個μql,計算相對誤差:

同樣,與αq一樣,模擬n=50與n=100兩個無向網(wǎng)絡(luò),且γ也取0.1與0.2兩個值.得到表3.

表1 n=50時αq的最小均值誤差

表2 n=100時αq的最小均值誤差

表3 μql的相對誤差

從得到的結(jié)果可以看出,當(dāng)γ取很小時,得到的相對誤差比較小.這里的γ取值比較小也是由于取值太大會導(dǎo)致組間聯(lián)系強度比組內(nèi)聯(lián)系強度大.

4 結(jié)論

本文對隨機塊模型進行推廣,研究了加權(quán)的隨機塊模型,更接近現(xiàn)實情況.在求解模型時,采用變分EM方法來代替?zhèn)鹘y(tǒng)的極大似然估計方法,有效地避免了求解似然函數(shù)方程的復(fù)雜性.由此可見,變分EM算法可以解決一些特殊的參數(shù)估計問題,尤其是一些混合模型求解.且這種算法也越來越得到人們的重視,可以說變分EM算法已成為實際應(yīng)用中的一種有效方法.

致謝作者對張海老師的指導(dǎo)表示衷心感謝！

[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.

國家自然科學(xué)基金(11171272).

潘琪(1988-),碩士生,研究方向：機器學(xué)習(xí).

2010 MSC:46N30