聚類系數(shù)和度相關(guān)性均可調(diào)的HK擴(kuò)展模型

周玉江,王 娟

(深圳大學(xué) 信息工程學(xué)院,廣東 深圳 518060)(*通信作者電子郵箱juanwang@szu.edu.cn)

0 引言

通過研究網(wǎng)絡(luò)的生長演化模型,可以更好地了解網(wǎng)絡(luò)的演化規(guī)律和形成過程，并且針對(duì)社交網(wǎng)絡(luò)拓?fù)涮匦缘难芯坑兄谏钊胝J(rèn)識(shí)社交網(wǎng)絡(luò)的形成過程。

現(xiàn)實(shí)生活中,很多復(fù)雜網(wǎng)絡(luò)都具備一些共同的特征,如:高聚類系數(shù)、小世界、冪律型度分布等。為了解釋冪律分布,學(xué)者Barabási和Albert提出BA模型[1],解釋了冪律分布產(chǎn)生機(jī)理;但BA模型產(chǎn)生的網(wǎng)絡(luò),聚類系數(shù)幾乎為0,為提高BA模型的聚類系數(shù),Holme和Kim提出HK模型[2],該模型具有較高的聚類系數(shù)。受到HK模型啟發(fā),此后眾多學(xué)者提出各種適用場合的網(wǎng)絡(luò)演化增長模型。

錢大千等[3]根據(jù)現(xiàn)實(shí)社交網(wǎng)絡(luò)中的熟人推薦原理,提出二步式增長模型(Two-Stage Growth Model, TSGM);王丹等[4]考慮到網(wǎng)絡(luò)中的舊節(jié)點(diǎn)也會(huì)發(fā)生連接,將 HK 模型中的三角結(jié)構(gòu)擴(kuò)展到了舊節(jié)點(diǎn)之間, 并且考慮到每個(gè)時(shí)間步新增邊的數(shù)量不是固定值,提出了度分布和聚類系數(shù)可調(diào)的擴(kuò)展HK(Extended HK, EHK)模型;Li等[5]同樣考慮到舊節(jié)點(diǎn)之間也會(huì)發(fā)生連接,提出一個(gè)聚類系數(shù)可調(diào)的擴(kuò)展HK模型;徐玉珠等[6]考慮到在新節(jié)點(diǎn)加入時(shí), 可能是單個(gè)節(jié)點(diǎn)也可能是一個(gè)社團(tuán), 并且將熟人推薦連接機(jī)理應(yīng)用到舊節(jié)點(diǎn)之間進(jìn)行網(wǎng)絡(luò)演化，提出了兩個(gè)度分布與聚類系數(shù)均可調(diào)的改進(jìn)HK網(wǎng)絡(luò)模型;崔愛香等[7]考慮網(wǎng)絡(luò)演化時(shí)會(huì)出現(xiàn)加速增長這種情況,提出一種改進(jìn)的加速增長HK演化模型;李穩(wěn)國等[8]考慮到每個(gè)節(jié)點(diǎn)在加入網(wǎng)絡(luò)時(shí),添加的邊數(shù)可能不同,提出改進(jìn)的HK模型。

盡管以上復(fù)雜網(wǎng)絡(luò)增長演化模型抓住了復(fù)雜網(wǎng)絡(luò)演化的基本特征:增長和擇優(yōu),構(gòu)造的網(wǎng)絡(luò)能符合冪律型度分布的特征,但忽略了網(wǎng)絡(luò)的度相關(guān)性?，F(xiàn)實(shí)生活中,所有的生物網(wǎng)絡(luò)和技術(shù)網(wǎng)絡(luò)都是負(fù)相關(guān)的,但是大多社交網(wǎng)絡(luò)卻是正相關(guān),即度值較大的節(jié)點(diǎn)更傾向于連接度值較大的節(jié)點(diǎn)。高聚類特性和度正相關(guān)特性是社交網(wǎng)絡(luò)的顯著特征[9-10]。

最近,一些研究正負(fù)相關(guān)性可調(diào)的網(wǎng)絡(luò)增長演化模型被提出來。Wang等[11]在權(quán)重網(wǎng)絡(luò)中,將初始吸引度加入到雙向選擇機(jī)制中[12],從而成為了新的雙向吸引機(jī)制,該模型生成的網(wǎng)絡(luò)具有正負(fù)相關(guān)性可調(diào)的特性;劉建國[13]先提出一個(gè)兩步增長模型，隨后在兩步增長模型的基礎(chǔ)上又提出一個(gè)度相關(guān)性正負(fù)可調(diào)的復(fù)雜網(wǎng)絡(luò)增長演化模型,通過調(diào)節(jié)擇優(yōu)參數(shù)達(dá)到調(diào)整網(wǎng)絡(luò)正負(fù)相關(guān)性的目的;Catanzaro等[14]在BA模型的基礎(chǔ)上,以概率p增加舊節(jié)點(diǎn)之間的連接,且舊節(jié)點(diǎn)之間的連接以條件概率p(k2|k1)進(jìn)行,通過調(diào)節(jié)p可以實(shí)現(xiàn)網(wǎng)絡(luò)正負(fù)相關(guān)性可調(diào)的特性。以上網(wǎng)絡(luò)增長演化模型未能采用HK模型中的聚類系數(shù)可調(diào)的優(yōu)點(diǎn)。

本文在HK增長模型的基礎(chǔ)上作出改善,提出聚類系數(shù)和度相關(guān)性均可調(diào)的HK擴(kuò)展模型(HK extended model with Turnable Degree Correlation and Clustering coefficient, HK-TDC&C)。用該模型能生成各種拓?fù)涞木W(wǎng)絡(luò),包括高聚類、度相關(guān)為正的社交網(wǎng)絡(luò)。

1 社交網(wǎng)絡(luò)的統(tǒng)計(jì)參量

常用以下統(tǒng)計(jì)參量來刻畫社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu):

1)度分布p(k)。

在網(wǎng)絡(luò)中隨機(jī)抽取一個(gè)節(jié)點(diǎn)i,它的度為k的概率可表示為p(k),p(k)通常稱為度的分布函數(shù),簡稱度分布。

2)平均聚類系數(shù)C。

社交網(wǎng)絡(luò)是社會(huì)關(guān)系的一個(gè)反映,在許多真實(shí)的社交網(wǎng)絡(luò)中,一個(gè)用戶的朋友圈的成員之間的聯(lián)系通常比較緊密,可用聚類系數(shù)刻畫這種關(guān)系。聚類系數(shù)就是一個(gè)用戶連接中實(shí)際存在的三角形數(shù)量與所有可能存在的三角形數(shù)量之比。平均聚類系數(shù)是網(wǎng)絡(luò)中所有節(jié)點(diǎn)聚類系數(shù)之和與網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的商。

3)平均最短路徑L及網(wǎng)絡(luò)直徑D。

網(wǎng)絡(luò)的平均最小路徑定義為網(wǎng)絡(luò)中所有兩兩節(jié)點(diǎn)之間最短距離的算術(shù)平均值;而網(wǎng)絡(luò)直徑定義為所有兩兩節(jié)點(diǎn)之間最短距離的最大值。

4)度相關(guān)性r。

Newman利用Pearson相關(guān)系數(shù)r來描述度的相關(guān)性:通過任意一條邊都可以找到兩個(gè)節(jié)點(diǎn),進(jìn)而得到兩個(gè)節(jié)點(diǎn)的度值,這樣遍歷所有的邊得到了兩個(gè)序列,分析這兩個(gè)序列的相關(guān)性,即為網(wǎng)絡(luò)的度相關(guān)性,用公式[15]可以表示為:

(1)

其中:ki、ji分別為第i(i=1,2,…,M,M為網(wǎng)絡(luò)的總邊數(shù))條邊的兩個(gè)端點(diǎn)的度值。

相關(guān)系數(shù)r∈[-1,1]。當(dāng)r<0時(shí),表示網(wǎng)絡(luò)是負(fù)相關(guān)的,即異配網(wǎng)絡(luò);當(dāng)r>0時(shí),網(wǎng)絡(luò)正相關(guān)的,即同配網(wǎng)絡(luò);當(dāng)r=0時(shí),網(wǎng)絡(luò)是不相關(guān)的。

近期研究發(fā)現(xiàn),大部分社交網(wǎng)絡(luò)是正相關(guān)的,而技術(shù)網(wǎng)絡(luò)、生物網(wǎng)絡(luò)是負(fù)相關(guān)的。

2 現(xiàn)實(shí)中的社交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

本文所用數(shù)據(jù)集為斯坦福大學(xué)收集的Facebook的社交數(shù)據(jù)[16],該數(shù)據(jù)集抓取節(jié)點(diǎn)4 039個(gè),邊88 234條,平均聚類系數(shù)C=0.605 5。

計(jì)算該網(wǎng)絡(luò)的以下拓?fù)鋮?shù):平均最短路徑、平均聚類系數(shù)、相關(guān)系數(shù)和度分布函數(shù)。相關(guān)數(shù)據(jù)如表1所示。

表1 Facebook網(wǎng)絡(luò)拓?fù)鋮?shù)Tab.1 Facebook network topological parameters

通過分析表1,可以發(fā)現(xiàn)該網(wǎng)絡(luò)具有典型的社交網(wǎng)絡(luò)特征:小世界特性(L=3.690 7)、較高的聚類系數(shù)(C=0.605 4)和正相關(guān)性(r=0.206 3)。

此外,節(jié)點(diǎn)的度分布也是描述一個(gè)網(wǎng)絡(luò)的重要特征, Facebook網(wǎng)絡(luò)的度分布雙對(duì)數(shù)曲線如圖1所示。

圖1 Facebook社交網(wǎng)絡(luò)度分布曲線Fig. 1 Social network degree distribution curve of Facebook

從圖1可以看出,Facebook網(wǎng)絡(luò)的度分布符合冪律分布的特征。

3 聚類系數(shù)和度相關(guān)性可調(diào)的HK擴(kuò)展模型

利用建模的方式研究網(wǎng)絡(luò)結(jié)構(gòu)的方法由來已久。早在20世紀(jì)60年代,Erds和Rényi[17]利用隨機(jī)圖理論構(gòu)建了隨機(jī)網(wǎng)絡(luò),稱為ER模型,開創(chuàng)了用隨機(jī)理論創(chuàng)建網(wǎng)絡(luò)的先例;隨后Barabási和Albert[1]對(duì)已有的網(wǎng)絡(luò)模型進(jìn)行分析后,對(duì)網(wǎng)絡(luò)增長演化模型進(jìn)行改進(jìn),提出實(shí)際網(wǎng)絡(luò)增長過程中具備的兩個(gè)重要特性:增長和擇優(yōu)?；谝陨蟽蓚€(gè)特性,文獻(xiàn)[1]于1999年提出了一個(gè)無標(biāo)度網(wǎng)絡(luò)模型。但BA模型產(chǎn)生的網(wǎng)絡(luò),聚類系數(shù)幾乎為0,為提高BA模型的聚類系數(shù),Holme和Kim提出HK模型[2],該模型具有較高的聚類系數(shù)。

HK模型是高聚類系數(shù)網(wǎng)絡(luò)增長演化模型的代表, 在BA模型擇優(yōu)連接(Preferential Attachment, PA)的基礎(chǔ)上,引入三角連接(Triad Formation, TF)方法。該模型算法步驟為:首先按照PA步驟連接網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn);然后以概率p進(jìn)行TF方式連接或者以概率(1-p) 再次進(jìn)行 PA 方式連接, 增加其余的(m-1) 條邊,使得網(wǎng)絡(luò)聚類系數(shù)隨參數(shù)p變化。

3.1 本文提出的演化增長模型HK-TDC&C

HK模型可以同時(shí)實(shí)現(xiàn)網(wǎng)絡(luò)的高聚類系數(shù)和無標(biāo)度特征, 成功地實(shí)現(xiàn)了復(fù)雜網(wǎng)絡(luò)中小世界特征與無標(biāo)度特征的統(tǒng)一。但該模型在連接時(shí),過分強(qiáng)調(diào)度基于度值的優(yōu)先連接,所以新加入的節(jié)點(diǎn)更傾向于連接度值最大的節(jié)點(diǎn),造成網(wǎng)絡(luò)度值出現(xiàn)負(fù)相關(guān)的情況。

本文在HK模型的基礎(chǔ)上進(jìn)行改進(jìn),提出HK-TDC&C模型。該模型在上述TF連接步驟中,通過調(diào)節(jié)參數(shù),分別實(shí)現(xiàn)擇優(yōu)與擇弱的連接,解決HK模型中度相關(guān)性為負(fù)數(shù)的狀況,可以實(shí)現(xiàn)網(wǎng)絡(luò)的聚類系數(shù)和相關(guān)性均可調(diào)的目的。HK-TDC&C模型演化步驟如下:

1)初始狀態(tài)。網(wǎng)絡(luò)初始狀態(tài)含有m0個(gè)完全連接的節(jié)點(diǎn)。

2)每一個(gè)時(shí)間步內(nèi),一個(gè)新的節(jié)點(diǎn)v連同m條邊加入網(wǎng)絡(luò)。

3)在生成的網(wǎng)絡(luò)中,按照式(2)的概率,隨機(jī)選取網(wǎng)絡(luò)中的一個(gè)任意節(jié)點(diǎn)(包含初始狀態(tài)的m0個(gè)節(jié)點(diǎn))i,添加一條邊。這種連接方式通常稱為PA擇優(yōu)連接;

(2)

4)以概率p按照改進(jìn)的三角連接(Improved Triad Formation, ITF)方式進(jìn)行連接,或者以概率1-p再次進(jìn)行PA方式連接, 增加其余的m-1條邊。其中p為三角連接概率。

ITF規(guī)則是指對(duì)于已經(jīng)選定的一個(gè)節(jié)點(diǎn)i, 按照式(3)的概率隨機(jī)選取它的一個(gè)鄰居節(jié)點(diǎn)a進(jìn)行連接。

(3)

其中:Γ(i)表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合。β稱為擇優(yōu)參數(shù),用于調(diào)整網(wǎng)絡(luò)的度相關(guān)性。當(dāng)β>0時(shí),度值高的節(jié)點(diǎn)有較高的連接概率,屬于擇強(qiáng)連接;當(dāng)β<0時(shí),度值低的節(jié)點(diǎn)有較高的連接概率,屬于擇弱連接;當(dāng)β=0時(shí),節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)被選中的概率相同,此時(shí)改進(jìn)模型與HK模型等同。

在HK-TDC&C網(wǎng)絡(luò)演化模型中,步驟3)的PA連接和步驟4)的ITF連接,這兩種連接方式可用圖2作進(jìn)一步說明。

圖2 PA連接方式和ITF連接方式Fig. 2 PA connection method and ITF connection method

圖2(a)表示PA連接方式:新節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí)更傾向于連接度值較大的節(jié)點(diǎn);圖2(b)表示ITF連接方式,選定節(jié)點(diǎn)i的非鄰居節(jié)點(diǎn)(圖中以畫叉節(jié)點(diǎn)表示)不能選,只能按照式(3)的概率,隨機(jī)選取節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)進(jìn)行連接,如連接節(jié)點(diǎn)a。

5)返回步驟2),直到滿足終止條件:網(wǎng)絡(luò)的規(guī)模N達(dá)到所希望的值,生成了一個(gè)節(jié)點(diǎn)數(shù)為N的網(wǎng)絡(luò)。

3.2 度分布的分析

根據(jù)3.1節(jié)對(duì)HK_TDC&C模型的描述,采用連續(xù)場理論[1]。在該模型中,研究網(wǎng)絡(luò)中某一節(jié)點(diǎn)i的度值ki隨時(shí)間的變化,假設(shè)其度值是連續(xù)變化的,則如下表達(dá)式成立:

(4)

其中:m是每個(gè)時(shí)間步時(shí)加入的邊數(shù)量；G為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合。

以下分別詳細(xì)討論擇優(yōu)參數(shù)β取值為0和非0的情況,對(duì)度分布產(chǎn)生的影響。

1)β=0的情況。

由式(4)可以得到如下等式成立:

(5)

由于網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量之和等于邊的數(shù)量之和的兩倍,每一時(shí)間步t有下式[1]成立:

(6)

將式(6)代入式(5),并解微分方程可以得到:

(7)

該微分方程的初始條件為:

ki(ti)=m

(8)

式(8)表示在ti時(shí)刻節(jié)點(diǎn)i的度值為m。其中，ti為節(jié)點(diǎn)i加入網(wǎng)絡(luò)的時(shí)間。

例(5)：If he buys two cents worth of peanuts, his father says, “ Remember what Franklin has said, my son- ’ A groat a day’s a penny a year ”

由初始條件,可以得到方程式(7)的解為:

ki(t)=m(t/ti)1/2

(9)

其中:t表示網(wǎng)絡(luò)建立的總時(shí)間?？梢钥闯?ti越小(即節(jié)點(diǎn)加入網(wǎng)絡(luò)越早),度值越大,符合社交網(wǎng)絡(luò)“富者越富”的現(xiàn)象。

假定用戶節(jié)點(diǎn)都是等時(shí)間間隔加入到網(wǎng)絡(luò)系統(tǒng),則ti是一個(gè)均勻分布,密度函數(shù)可寫為:

(10)

結(jié)合式(9),ki的分布函數(shù)可以表示為:

(11)

(12)

所以度的分布函數(shù)為:

(13)

系統(tǒng)在經(jīng)歷過足夠長的時(shí)間后,當(dāng)t→ ∞,式(13)可寫為:

p(k)=2m2·k-3

(14)

綜上所述,在β=0時(shí),HK-TDC&C模型完全符合冪律分布的特征,且γ=3。

2)β≠0的情況。

(15)

由式(15)可以得出該模型的度分布并非嚴(yán)格服從冪律分布的結(jié)論。而通過分析圖1中Facebook社交網(wǎng)絡(luò)的雙對(duì)數(shù)曲線,可以看出:現(xiàn)實(shí)網(wǎng)絡(luò)中的度分布具有冪律分布的趨勢,而并非嚴(yán)格地服從冪律分布。因此,HK-TDC&C模型可以理解為在嚴(yán)格的冪律分布的基礎(chǔ)上疊加了一些噪聲。

可以通過調(diào)節(jié)模型中的參數(shù):連接概率p及擇優(yōu)參數(shù)β,對(duì)網(wǎng)絡(luò)的聚類系數(shù)、度相關(guān)性進(jìn)行修正,使之能更好地接近現(xiàn)實(shí)中的社交網(wǎng)絡(luò)。

4 實(shí)驗(yàn)與評(píng)估

下面通過仿真的方法,按照HK-TDC&C模型算法生成一個(gè)網(wǎng)絡(luò),并分析該網(wǎng)絡(luò)的各拓?fù)鋮?shù):度分布特征P(k)、平均最小路徑L、聚類系數(shù)C、度相關(guān)性r。

實(shí)驗(yàn)參數(shù)設(shè)定如下:初始網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)m0=20,每步添加的邊數(shù)m=18,網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量N=2 000,p和β作為網(wǎng)絡(luò)的調(diào)節(jié)參數(shù)。

1)擇優(yōu)參數(shù)β對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響。

取p=0.8,當(dāng)擇優(yōu)參數(shù)β=-0.8,0,0.8時(shí),生成網(wǎng)絡(luò)的各參數(shù)如表2所示。

表2 擇優(yōu)參數(shù)β對(duì)網(wǎng)絡(luò)的影響Tab.2 Influence of preferred parameters β on the network

通過分析表2,可以得出:

①當(dāng)β取值為負(fù)值時(shí)(β=-0.8),可以生成正相關(guān)網(wǎng)絡(luò)。對(duì)比表1中的Facebook網(wǎng)絡(luò)數(shù)據(jù),可以看到,網(wǎng)絡(luò)的各項(xiàng)參數(shù),如網(wǎng)絡(luò)直徑D、平均最小距離L、度相關(guān)系數(shù)r,都能較好地符合真實(shí)社交網(wǎng)絡(luò)特征。平均聚類系數(shù)C有待進(jìn)一步提高,但在大多數(shù)社交數(shù)據(jù)集中,平均聚類系數(shù)C通常為0.2左右[9]。

②當(dāng)β取值為0時(shí),HK-TDC&C模型與HK模型等同。可以發(fā)現(xiàn),HK模型及其后的擴(kuò)展模型[3-8],由于未采用擇優(yōu)參數(shù)進(jìn)行調(diào)節(jié),生成的是不相關(guān)網(wǎng)絡(luò)(或稱為較弱的負(fù)相關(guān)網(wǎng)絡(luò)),這是該類模型的共同特征。

③當(dāng)β取值為正時(shí),可以生成負(fù)相關(guān)性的網(wǎng)絡(luò)。

2)連接概率p對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響。

取β=-0.8,當(dāng)p=0.2、0.5、0.9時(shí),生成網(wǎng)絡(luò)的各參數(shù)如表3所示。

表3 連接概率p對(duì)網(wǎng)絡(luò)的影響Tab.3 Influence of connection probability p on the network

通過表3,可以看出:聚類系數(shù)和度相關(guān)系數(shù)都與擇優(yōu)參數(shù)p正相關(guān),即p取值越大,聚類系數(shù)和度相關(guān)系數(shù)也越大。

3)網(wǎng)絡(luò)的度分布情況。

取p=0.8,β=-0.8,0,0.8的情況下,度分布雙對(duì)數(shù)曲線如圖3所示。

圖3 HK-TDC&C網(wǎng)絡(luò)度分布曲線(p=0.8)Fig. 3 HK-TDC&C network degree distribution curve (p=0.8)

通過圖3可以看到:HK-TDC&C模型構(gòu)建的網(wǎng)絡(luò),它的度分布符合冪律分布的特征。

4)基于上述1)、2)、3)項(xiàng)對(duì)HK-TDC&C模型的數(shù)據(jù)分析,可以看到,在β取負(fù)值(如-0.8),p取值較高(如 0.8)的情況下,該模型生成的網(wǎng)絡(luò)能較好地符合社交網(wǎng)絡(luò)的基本特征:度值服從冪律分布、度的正相關(guān)性、較高的聚類系數(shù)、較短的平均距離。因此該模型可用來生成各種拓?fù)浣Y(jié)構(gòu)的社交網(wǎng)絡(luò)。

5 結(jié)語

本文以HK模型為基礎(chǔ),提出了一種新型的社交網(wǎng)絡(luò)建模方法:通過調(diào)節(jié)擇優(yōu)參數(shù)β實(shí)現(xiàn)不同程度的擇優(yōu)或擇弱連接,實(shí)現(xiàn)網(wǎng)絡(luò)正負(fù)相關(guān)性可調(diào)的目的。仿真結(jié)果表明,通過選取適當(dāng)參數(shù),該模型生成的社交網(wǎng)絡(luò)具有的拓?fù)涮卣髋c社交網(wǎng)絡(luò)相符,包括:高聚類系數(shù)、較短的平均最短路徑、度的冪律分布特性、度的正相關(guān)特性。本文算法構(gòu)造的社交網(wǎng)路與真實(shí)社交網(wǎng)絡(luò)各參數(shù)相比,較為接近。