改進(jìn)的隨機(jī)分塊模型
2013-12-05 08:13:32李慧馳
李慧馳
【摘 要】社團(tuán)結(jié)構(gòu)揭示了網(wǎng)絡(luò)內(nèi)部的結(jié)構(gòu)，不斷優(yōu)化發(fā)現(xiàn)社團(tuán)的算法尤為重要.而隨機(jī)分塊模型是用于測試算法表現(xiàn)的基本工具，其改進(jìn)與更新對于適應(yīng)各種新算法的測試具有重要意義.筆者主要介紹一種對度進(jìn)行改進(jìn)的隨機(jī)分塊模型，淺析其性質(zhì)，對比模糊程度不同的網(wǎng)絡(luò)，以便于更好的將其運(yùn)用于算法的測試。
【關(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ò)，以此作為測試社團(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ò)對于測試算法準(zhǔn)確性并不十分適用.Brian Karrer和M.E.J.Newman對傳統(tǒng)的隨機(jī)分塊模型做了改進(jìn)，使得改進(jìn)后的模型生成的網(wǎng)絡(luò)度的分布更為寬泛，這樣就更加接近于真實(shí)網(wǎng)絡(luò)的特性[1]。
1.模型介紹
本文所探討的隨機(jī)分塊模型為對度進(jìn)行改進(jìn)的模型，其相比與傳統(tǒng)的模型，度的變化范圍更為寬泛，更接近真實(shí)網(wǎng)絡(luò)的特性.在模型的理論分析過程中，我們允許節(jié)點(diǎn)自連邊以及多連邊，這主要體現(xiàn)在生成模型的連邊概率中，對網(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ò)中每兩條邊之間連邊的概率.社團(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ù)的選擇.對于網(wǎng)絡(luò)的群分配參數(shù)g和節(jié)點(diǎn)的期望度值，我們可以根據(jù)實(shí)驗(yàn)需要進(jìn)行預(yù)設(shè)值，而對于參數(shù)ωrs的選擇，則相對復(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對應(yīng)于隨機(jī)圖中ωrs的期望值，而ωrsplanted對應(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ī)分塊模型的生成程序，并對相應(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)非常少.對生成網(wǎng)絡(luò)中節(jié)點(diǎn)度的分布有大致了解，有助于我們對網(wǎng)絡(luò)特性的掌握，在連邊預(yù)測以及社團(tuán)分析時(shí)，能幫助我們分析實(shí)驗(yàn)結(jié)果。
2.2合成網(wǎng)絡(luò)的對比分析
我們運(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ì)介紹對度進(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)度的特性，并對比分析不同參數(shù)值對應(yīng)的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)，以便于幫助剖析網(wǎng)絡(luò)的特征，為其應(yīng)用于算法測試[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）.
