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

隨機(jī)塊模型;混合模型;變分EM方法

1 前言

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

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

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

2 隨機(jī)塊模型

2.1 混合模型

2.2 基于變分EM方法進(jìn)行求解

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

3 實(shí)驗(yàn)

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

對(duì)每個(gè)αq,計(jì)算最小均值誤差:

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

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

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

對(duì)每個(gè)μql,計(jì)算相對(duì)誤差:

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

表1 n=50時(shí)αq的最小均值誤差

表2 n=100時(shí)αq的最小均值誤差

表3 μql的相對(duì)誤差

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

4 結(jié)論

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

致謝作者對(duì)張海老師的指導(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.

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

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

2010 MSC:46N30