李慧馳
【摘 要】社團(tuán)結(jié)構(gòu)揭示了網(wǎng)絡(luò)內(nèi)部的結(jié)構(gòu),不斷優(yōu)化發(fā)現(xiàn)社團(tuán)的算法尤為重要.而隨機(jī)分塊模型是用于測(cè)試算法表現(xiàn)的基本工具,其改進(jìn)與更新對(duì)于適應(yīng)各種新算法的測(cè)試具有重要意義.筆者主要介紹一種對(duì)度進(jìn)行改進(jìn)的隨機(jī)分塊模型,淺析其性質(zhì),對(duì)比模糊程度不同的網(wǎng)絡(luò),以便于更好的將其運(yùn)用于算法的測(cè)試。
【關(guān)鍵詞】社團(tuán)結(jié)構(gòu);隨機(jī)分塊模型;模糊程度
0.引言
在復(fù)雜網(wǎng)絡(luò)中,隨機(jī)分塊模型既可以用來發(fā)現(xiàn)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu),還可用于產(chǎn)生合成網(wǎng)絡(luò),以此作為測(cè)試社團(tuán)發(fā)現(xiàn)等算法的表現(xiàn).然而,傳統(tǒng)的分塊模型忽略了節(jié)點(diǎn)度的變化性,與真實(shí)網(wǎng)絡(luò)中度的分布特征不太相符.因此,在真實(shí)網(wǎng)絡(luò)的社團(tuán)發(fā)現(xiàn)過程中,傳統(tǒng)模型的合成網(wǎng)絡(luò)對(duì)于測(cè)試算法準(zhǔn)確性并不十分適用.Brian Karrer和M.E.J.Newman對(duì)傳統(tǒng)的隨機(jī)分塊模型做了改進(jìn),使得改進(jìn)后的模型生成的網(wǎng)絡(luò)度的分布更為寬泛,這樣就更加接近于真實(shí)網(wǎng)絡(luò)的特性[1]。
1.模型介紹
本文所探討的隨機(jī)分塊模型為對(duì)度進(jìn)行改進(jìn)的模型,其相比與傳統(tǒng)的模型,度的變化范圍更為寬泛,更接近真實(shí)網(wǎng)絡(luò)的特性.在模型的理論分析過程中,我們?cè)试S節(jié)點(diǎn)自連邊以及多連邊,這主要體現(xiàn)在生成模型的連邊概率中,對(duì)網(wǎng)絡(luò)的產(chǎn)生沒有影響[2]。
該模型中網(wǎng)絡(luò)節(jié)點(diǎn)的度服從普瓦松分布,社團(tuán)大小服從均勻分布.網(wǎng)絡(luò)的生成過程主要分為兩步:首先,要確定網(wǎng)絡(luò)的群分配,即社團(tuán)結(jié);其次,要確定網(wǎng)絡(luò)中每?jī)蓷l邊之間連邊的概率.社團(tuán)結(jié)構(gòu)的劃分是預(yù)先設(shè)置的,而群gi與群gj內(nèi)節(jié)點(diǎn)連邊的概率如下式所示:
Pgigj=θiθjωgi,gj (1)
在上式中,gi表示節(jié)點(diǎn)i所屬的社團(tuán),參數(shù)θi和ωrs的最大似然值分別如下:
= rs=mrs (2)
2.合成網(wǎng)絡(luò)
在運(yùn)用隨機(jī)分塊模型生成網(wǎng)絡(luò)時(shí),涉及到參數(shù)的選擇.對(duì)于網(wǎng)絡(luò)的群分配參數(shù)g和節(jié)點(diǎn)的期望度值,我們可以根據(jù)實(shí)驗(yàn)需要進(jìn)行預(yù)設(shè)值,而對(duì)于參數(shù)ωrs的選擇,則相對(duì)復(fù)雜.理論上來說,任何滿足sωrs=kr的非負(fù)ωrs值都可以.然而,考慮到我們要用于實(shí)驗(yàn)的網(wǎng)絡(luò)并非具有同樣的社團(tuán)結(jié)構(gòu),而是千變?nèi)f化的.為了便于更便捷的生成社團(tuán)結(jié)構(gòu)不同的網(wǎng)絡(luò),我們引入?yún)?shù)λ,來調(diào)節(jié)下面線性表達(dá)式的系數(shù):
ω=λωplanted+(1-λ)ωrandom (3)
這里,ωrsandom=krks/2m對(duì)應(yīng)于隨機(jī)圖中ωrs的期望值,而ωrsplanted對(duì)應(yīng)于構(gòu)造社團(tuán)結(jié)構(gòu).例如,我們想要將網(wǎng)絡(luò)劃分為4個(gè)社團(tuán),那么就有:
ω= (4)
2.1合成網(wǎng)絡(luò)特性分析
運(yùn)用MALAB軟件,編寫以上隨機(jī)分塊模型的生成程序,并對(duì)相應(yīng)的網(wǎng)絡(luò)特性進(jìn)行分析.以500個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)為例,設(shè)置其社團(tuán)數(shù)目為5個(gè),參數(shù)λ設(shè)為0.8。
實(shí)驗(yàn)結(jié)果表明,網(wǎng)絡(luò)中節(jié)點(diǎn)度大致服從普瓦松分布,并且該生成網(wǎng)絡(luò)節(jié)點(diǎn)的度主要集中在0-50之間,度大于50的節(jié)點(diǎn)非常少.對(duì)生成網(wǎng)絡(luò)中節(jié)點(diǎn)度的分布有大致了解,有助于我們對(duì)網(wǎng)絡(luò)特性的掌握,在連邊預(yù)測(cè)以及社團(tuán)分析時(shí),能幫助我們分析實(shí)驗(yàn)結(jié)果。
2.2合成網(wǎng)絡(luò)的對(duì)比分析
我們運(yùn)用該模型,分別生成社團(tuán)結(jié)構(gòu)模糊程度不同的網(wǎng)絡(luò),預(yù)先設(shè)置社團(tuán)數(shù)為2,隨著參數(shù)λ 的不斷增大,網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)越來越清晰,當(dāng)λ=0.5時(shí),從表達(dá)式(3)可知,隨機(jī)圖與構(gòu)造社團(tuán)結(jié)構(gòu)各占一半的權(quán)重,此時(shí)生成網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)比較模糊,兩個(gè)社團(tuán)的分界并不明顯.而隨著λ 增大到0.9時(shí),網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)已經(jīng)非常清晰。
3.小結(jié)
筆者通過詳細(xì)介紹對(duì)度進(jìn)行改進(jìn)后的隨機(jī)分塊模型,了解其原理,進(jìn)而分析其生成網(wǎng)絡(luò)的機(jī)制原理.同時(shí),還提供了在運(yùn)用模型生成網(wǎng)絡(luò)時(shí),參數(shù)的選擇方式.最后,通過實(shí)驗(yàn)生成網(wǎng)絡(luò)模型,分析其節(jié)點(diǎn)度的特性,并對(duì)比分析不同參數(shù)值對(duì)應(yīng)的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu),以便于幫助剖析網(wǎng)絡(luò)的特征,為其應(yīng)用于算法測(cè)試[3]奠定基礎(chǔ)。
【參考文獻(xiàn)】
[1]汪小帆.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京:清華大學(xué)出版社,2006.
[2]胡守信.MATLAB基礎(chǔ)及其應(yīng)用教程[M].北京:科學(xué)出版社,2006.
[3]Karrer,B.and M.E.J.Newman.Stochastic block models and community structure in networks.Phys.Rev.E,83(1):016107(2011).