基于社交網(wǎng)絡(luò)的BA無(wú)標(biāo)度演化模型的研究

◎王筱蕾

（西北政法大學(xué) 圖書館，西安 710122）

基于社交網(wǎng)絡(luò)的BA無(wú)標(biāo)度演化模型的研究

◎王筱蕾

（西北政法大學(xué) 圖書館，西安 710122）

針對(duì)社交網(wǎng)絡(luò)中用戶間好友關(guān)系的特殊性，結(jié)合重啟特征和稀疏網(wǎng)絡(luò)平滑特征，提出了PageRank改進(jìn)算法PRS；針對(duì)BA網(wǎng)絡(luò)模型的缺陷以及實(shí)際社交網(wǎng)絡(luò)的連接特性，將改進(jìn)算法PRS作為擇優(yōu)連邊考量因素之一，加入隨機(jī)連邊機(jī)制，構(gòu)建了一種適合社交網(wǎng)絡(luò)的BA無(wú)標(biāo)度網(wǎng)絡(luò)的改進(jìn)模型。實(shí)驗(yàn)證明，改進(jìn)模型具有更優(yōu)的網(wǎng)絡(luò)特性，適合構(gòu)建與描述社交網(wǎng)絡(luò)。

PageRank算法；BA無(wú)標(biāo)度網(wǎng)絡(luò)；社交網(wǎng)絡(luò)；改進(jìn)模型

近年來(lái)，社交網(wǎng)絡(luò)因其發(fā)展迅速、用戶量巨大已成為最有影響力的信息交互平臺(tái)。掌握社交網(wǎng)絡(luò)的內(nèi)部結(jié)構(gòu)以及生長(zhǎng)模式，對(duì)社交網(wǎng)站的建立與維護(hù)有著重要的理論指導(dǎo)意義。社交網(wǎng)絡(luò)作為復(fù)雜網(wǎng)絡(luò)的一個(gè)典型代表，其內(nèi)部結(jié)構(gòu)與生長(zhǎng)特征都符合復(fù)雜網(wǎng)絡(luò)的特點(diǎn)。目前，多數(shù)研究者使用復(fù)雜網(wǎng)絡(luò)中的經(jīng)典模型——BA無(wú)標(biāo)度模型來(lái)描述社交網(wǎng)絡(luò)。然而，社交網(wǎng)絡(luò)因其自身特殊性，其節(jié)點(diǎn)具有多重連接方式且網(wǎng)絡(luò)特征參數(shù)多變。使用具有單一節(jié)點(diǎn)連接方式和網(wǎng)絡(luò)特征參數(shù)的BA無(wú)標(biāo)度模型無(wú)法全面描述社交網(wǎng)絡(luò)[1]。針對(duì)這一問(wèn)題，本文將借鑒BA無(wú)標(biāo)度模型的構(gòu)造算法以及網(wǎng)頁(yè)影響力排名算法PageRank，使用回顧性模擬的網(wǎng)絡(luò)建模方法，對(duì)傳統(tǒng)BA無(wú)標(biāo)度模型進(jìn)行，以期更全面準(zhǔn)確的描述實(shí)際社交網(wǎng)絡(luò)的特征。

1 BA無(wú)標(biāo)度模型算法介紹及缺陷分析

1.1 BA無(wú)標(biāo)度模型算法

BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的構(gòu)造算法[2]如下:

（1）增長(zhǎng)：在一個(gè)具有m0個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，依次連入新節(jié)點(diǎn)，直到新節(jié)點(diǎn)被連接到已存在的m個(gè)節(jié)點(diǎn)上，這里m≤m0。

（2）擇優(yōu)連接：?jiǎn)蝹€(gè)已存在的節(jié)點(diǎn)i和單個(gè)新節(jié)點(diǎn)，它們能被連接到一起的概率∏（ki）與j節(jié)點(diǎn)的度kj以及i節(jié)點(diǎn)的度ki之間滿足以下關(guān)系：

1.2 缺陷分析

首先，連接機(jī)制選擇。BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的連接機(jī)制考慮的是擇優(yōu)連接，然而在實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)之間的連接機(jī)制不僅僅為擇優(yōu)連接，還存在隨機(jī)連接，例如，在社交網(wǎng)絡(luò)中，用戶在添加好友時(shí)除了會(huì)優(yōu)先選擇一些好友以外，還會(huì)隨機(jī)添加一些感興趣的陌生人，因此在構(gòu)造社交網(wǎng)絡(luò)模型時(shí)必須考慮到隨機(jī)連接這一條件。

其次，擇優(yōu)連接的條件。BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的擇優(yōu)連接機(jī)制中考慮的是節(jié)點(diǎn)的度數(shù)，即度越大，被選擇連接的可能性越大，在社交網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)就是用戶，節(jié)點(diǎn)的度就是用戶的好友數(shù)目，因此，BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的連接條件在社交網(wǎng)絡(luò)背景下就是用戶傾向于與好友數(shù)目較多的用戶建立連接，顯然這一觀點(diǎn)是片面的，在實(shí)際的社交網(wǎng)絡(luò)中，用戶除了會(huì)選擇好友數(shù)目多的用戶建立連接外，用戶的影響力也是十分重要的因素，如新浪微博中有一個(gè)名人影響力排名，通過(guò)一定的算法算出網(wǎng)絡(luò)上的名人影響力，并對(duì)其排名，一般用戶會(huì)根據(jù)影響力的大小選擇與其建立連接。因此，在構(gòu)造社交網(wǎng)絡(luò)模型時(shí)，擇優(yōu)連接中應(yīng)當(dāng)考慮到影響力因素。

2 基于社交網(wǎng)絡(luò)的BA無(wú)標(biāo)度演化模型

2.1 PageRank算法介紹及改進(jìn)

經(jīng)典網(wǎng)頁(yè)排名PageRank算法為每個(gè)網(wǎng)頁(yè)設(shè)定PR值為網(wǎng)頁(yè)的影響力分?jǐn)?shù)，借鑒PageRank算法的思想來(lái)對(duì)社交網(wǎng)絡(luò)中每個(gè)用戶進(jìn)行影響力估算[3]，為了更準(zhǔn)確地計(jì)算用戶的影響力，筆者對(duì)原PageRank算法進(jìn)行改進(jìn)，使用改進(jìn)的PageRank算法來(lái)計(jì)算社交網(wǎng)絡(luò)中用戶的影響力大小。

2.1.1 PageRank算法介紹

PageRank算法[4]又稱網(wǎng)頁(yè)排名算法，是Google搜索引擎中的重要算法。算法思想是：當(dāng)網(wǎng)頁(yè)A有一個(gè)鏈接指向網(wǎng)頁(yè)B時(shí)，就認(rèn)為網(wǎng)頁(yè)B獲得了一定的分?jǐn)?shù)，該分值的多少取決于網(wǎng)頁(yè)A的重要程度，即網(wǎng)頁(yè)A的重要性越大，網(wǎng)頁(yè)B獲得的分?jǐn)?shù)就越高。由于網(wǎng)頁(yè)上的鏈接相互指向的復(fù)雜程度，該分值的計(jì)算過(guò)程是一個(gè)迭代過(guò)程，最終網(wǎng)頁(yè)將依照所得的分?jǐn)?shù)進(jìn)行排序并將結(jié)果送交給用戶，這個(gè)量化了的分?jǐn)?shù)就是PageRank值。

要計(jì)算網(wǎng)頁(yè)A的PR值，就得利用指向它的網(wǎng)頁(yè)Ti的PR值，這就導(dǎo)致要求解一個(gè)巨大的方程組，然而復(fù)雜網(wǎng)絡(luò)中的結(jié)點(diǎn)是非常多的，求解這個(gè)方程組往往不現(xiàn)實(shí)的[5]。針對(duì)這一問(wèn)題，筆者引入馬爾科夫假設(shè)，結(jié)合重啟特征與平滑特征，給出經(jīng)典PageRank算法的求解方法：

Step1.由網(wǎng)絡(luò)鄰接矩陣A經(jīng)過(guò)行歸一化得到矩陣W；

Step2.確定PageRank初始向量p0的值；

Step3.反復(fù)迭代經(jīng)典PageRank算法計(jì)算公式pt+1，直到pt和pt+1的夾角余弦小于某一個(gè)小的閾值ε時(shí)停止；

Step4.pt即是各個(gè)結(jié)點(diǎn)的重要性向量，對(duì)其按照從大到小的順序排序，就可以得到節(jié)點(diǎn)重要性的排序結(jié)果。

2.1.2 PageRank算法改進(jìn)

傳統(tǒng)的PageRank算法存在以下兩個(gè)問(wèn)題：

（1）實(shí)際中存在用戶回退瀏覽不同頁(yè)面的情況，這個(gè)因素不應(yīng)該被忽略，而上面原始的計(jì)算PR值公式并沒(méi)有考慮到這一點(diǎn)。

針對(duì)這一問(wèn)題，筆者將引入一個(gè)較小的系數(shù)d，作為重置系數(shù)，并結(jié)合經(jīng)典PageRank算法給出計(jì)算公式。用戶在網(wǎng)上瀏覽網(wǎng)頁(yè)時(shí)，可能會(huì)以某個(gè)概率跳轉(zhuǎn)到下一個(gè)頁(yè)面，當(dāng)然也可能會(huì)回到上一個(gè)頁(yè)面。不妨假設(shè)用戶在每一次瀏覽網(wǎng)頁(yè)時(shí)都可能會(huì)以一定的概率去瀏覽當(dāng)前頁(yè)面的鄰居，還會(huì)有一定的概率回到初始瀏覽的網(wǎng)頁(yè)，所以對(duì)于向量p，改為如下定義：

其中，d是一個(gè)介于0到1之間的常數(shù)，叫做重啟系數(shù)，即沖浪者以d的概率回到原點(diǎn)，并且d∈（0，1]；p0表示初始向量。從上式可以看出，用戶每次跳轉(zhuǎn)網(wǎng)頁(yè)時(shí)都會(huì)以概率d回到原始的網(wǎng)頁(yè)，或者按照概率去跳轉(zhuǎn)到其他網(wǎng)頁(yè)。對(duì)于復(fù)雜網(wǎng)絡(luò)而言，重啟特征會(huì)使得PageRank算法更加精準(zhǔn)。

（2）網(wǎng)頁(yè)之間的鏈接的數(shù)量相比互聯(lián)網(wǎng)的規(guī)模非常稀疏，因此計(jì)算網(wǎng)頁(yè)的網(wǎng)頁(yè)排名也需要對(duì)零概率或者小概率事件進(jìn)行平滑處理。

針對(duì)這一問(wèn)題，筆者將引入一個(gè)很小的系數(shù)c，作為平滑處理系數(shù)。對(duì)于互聯(lián)網(wǎng)網(wǎng)絡(luò)而言，網(wǎng)頁(yè)結(jié)點(diǎn)之間鏈接的數(shù)量相比互聯(lián)網(wǎng)節(jié)點(diǎn)的規(guī)模比較稀疏，社交網(wǎng)絡(luò)中，用戶的連接關(guān)系數(shù)目較網(wǎng)絡(luò)節(jié)點(diǎn)規(guī)模也十分稀疏。因此計(jì)算網(wǎng)頁(yè)的網(wǎng)頁(yè)排名也需要對(duì)零概率或者小概率事件進(jìn)行平滑處理。由于網(wǎng)頁(yè)的排名是個(gè)一維向量，對(duì)它的平滑處理可以利用一個(gè)小的常數(shù)c，表達(dá)如下：

其中，N表示互聯(lián)網(wǎng)網(wǎng)頁(yè)的數(shù)量，c是一個(gè)介于0到1之間的常數(shù)，稱為平滑系數(shù)，I是單位矩陣。上式通過(guò)平滑系數(shù)c，來(lái)對(duì)零概率或者小概率事件進(jìn)行平滑。

綜合以上兩個(gè)特征，筆者將以上改進(jìn)算法PRS計(jì)算過(guò)程總結(jié)如下：

Step1.由網(wǎng)絡(luò)鄰接矩陣A經(jīng)過(guò)行歸一化得到矩陣W；

Step2.確定PRS初始向量p0的值；

Step4.pt即是各個(gè)結(jié)點(diǎn)的重要性向量，對(duì)其按照從大到小的順序排序，就可以得到結(jié)點(diǎn)重要性的排序結(jié)果。

2.2 演化模型構(gòu)建思想

前面介紹了BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的算法，并分析了該算法應(yīng)用到社交網(wǎng)絡(luò)中的缺陷，針對(duì)該缺陷以及社交網(wǎng)絡(luò)的實(shí)際特征來(lái)構(gòu)建適合描述社交網(wǎng)絡(luò)的演化模型。

首先，BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的連接機(jī)制是擇優(yōu)連接，然而在實(shí)際的社交網(wǎng)絡(luò)中，用戶選擇好友并不總是擇優(yōu)選擇[6,7]，除了有選擇性的添加好友以外還會(huì)隨機(jī)的添加一些陌生人作為好友，也就是存在一定概率的隨機(jī)選擇，因此應(yīng)當(dāng)設(shè)置一個(gè)參數(shù)p(0≤p≤1)，p表示用戶擇優(yōu)選擇的概率，那么1-p則表示用戶隨機(jī)選擇的概率，p=0時(shí)表示網(wǎng)絡(luò)中所有用戶的連接全部都為隨機(jī)連接，p=1則表示網(wǎng)絡(luò)中所有用戶的連接全部都為擇優(yōu)連接。

其次，在BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的擇優(yōu)連接中是以節(jié)點(diǎn)的度作為衡量標(biāo)準(zhǔn)，節(jié)點(diǎn)的度越大，越容易與其他節(jié)點(diǎn)建立連接，在社交網(wǎng)絡(luò)中就是指一個(gè)用戶傾向于選擇好友數(shù)多的用戶來(lái)建立好友關(guān)系，客觀地說(shuō)，這一觀點(diǎn)是片面的，實(shí)際上用戶選擇好友的標(biāo)準(zhǔn)不僅僅看一個(gè)用戶的人氣，影響力也是不容忽視的一個(gè)因素，用戶傾向于選擇人氣高或者影響力大的用戶來(lái)建立好友關(guān)系。在考慮影響力時(shí)，這里利用改進(jìn)的PageRank算法PRS，將社交網(wǎng)絡(luò)中的每個(gè)用戶視為因特網(wǎng)中的每個(gè)網(wǎng)頁(yè)，像對(duì)每個(gè)網(wǎng)頁(yè)投票一樣為每個(gè)用戶投票，并設(shè)置PRS值，PRS值越高表示該用戶的影響力越大。算法開始時(shí)，為每個(gè)用戶分配一個(gè)相同的PRS值，然后進(jìn)行迭代計(jì)算，每個(gè)用戶把自己的PRS值平均的分配給與其有連接關(guān)系的好友，然后每個(gè)用戶根據(jù)所得的權(quán)值進(jìn)行求和，以此來(lái)對(duì)每個(gè)用戶的PRS值進(jìn)行更新，在每一輪計(jì)算中用戶的PRS值都會(huì)更新，直到算法結(jié)束。因此，設(shè)置參數(shù)a(0≤a≤1),a表示用戶選擇人氣高即好友數(shù)多的用戶來(lái)建立好友關(guān)系，1-a表示用戶選擇影響力大的即PRS值高的用戶來(lái)建立好友關(guān)系。當(dāng)a=0時(shí)表示網(wǎng)絡(luò)中的用戶在擇優(yōu)選擇時(shí)只以影響力作為衡量標(biāo)準(zhǔn)，只選擇影響力大的用戶來(lái)建立好友關(guān)系。當(dāng)a=1時(shí)表示網(wǎng)絡(luò)中的用戶在擇優(yōu)選擇時(shí)只選擇人氣高的用戶來(lái)建立好友關(guān)系，也就是BA無(wú)標(biāo)度網(wǎng)絡(luò)中的擇優(yōu)連接思想。

另外，在實(shí)際的社交網(wǎng)絡(luò)中存在不同的社群，同一社群中的用戶聯(lián)系相對(duì)比較緊密，具有較大的聚類系數(shù)以及較小的平均路徑長(zhǎng)度，而沒(méi)在社群中的用戶則可能互相聯(lián)系較少、聚類系數(shù)較小且平均路徑長(zhǎng)度較大。然而普通的BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的聚類系數(shù)以及平均路徑長(zhǎng)度是固定的，無(wú)法綜合的描述實(shí)際社交網(wǎng)絡(luò)的多種情況，因此需要一種具有可變聚類系數(shù)和可變平均路徑長(zhǎng)度的模型來(lái)描述實(shí)際的社交網(wǎng)絡(luò)。通過(guò)調(diào)節(jié)參數(shù)p，a，我們可以控制隨機(jī)連接和擇優(yōu)連接，以及擇優(yōu)連接中度數(shù)和影響力的比例。

2.3 演化模型構(gòu)建算法

（1）增長(zhǎng)：在一個(gè)具有m0個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，依次連入新節(jié)點(diǎn)，直到新節(jié)點(diǎn)被連接到已存在的m個(gè)節(jié)點(diǎn)上，這里m≤m0。

（2）擇優(yōu)選擇：一個(gè)新節(jié)點(diǎn)與網(wǎng)絡(luò)中已有的節(jié)點(diǎn)相連接，且選擇節(jié)點(diǎn)i概率與節(jié)點(diǎn)度成正比，即

選擇這種操作的概率為a，這里將a記為度指數(shù)；

新節(jié)點(diǎn)與網(wǎng)絡(luò)中已有的節(jié)點(diǎn)相連接，且選擇節(jié)點(diǎn)i概率與節(jié)點(diǎn)的影響力（PRS值）成正比，即

選擇這種操作的概率為1-a。

這里假設(shè)擇優(yōu)選擇的選擇概率為p，將p記為擇優(yōu)指數(shù)。

（3）隨機(jī)選擇：在已有網(wǎng)絡(luò)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)與新節(jié)點(diǎn)連接。隨機(jī)選擇的選擇概率為1-p。

在改進(jìn)模型構(gòu)造算法中，任意兩點(diǎn)之間的距離為1，且連邊總是由老節(jié)點(diǎn)指向新節(jié)點(diǎn)，所以改進(jìn)模型為有向無(wú)權(quán)網(wǎng)絡(luò)。所引入的兩個(gè)參數(shù)p和a都是可以調(diào)節(jié)的，當(dāng)p=1且a=1時(shí)，改進(jìn)模型退化為基本的BA無(wú)標(biāo)度網(wǎng)絡(luò)模型。

在改進(jìn)模型中，新節(jié)點(diǎn)以概率a隨機(jī)選擇網(wǎng)絡(luò)中的已有節(jié)點(diǎn)進(jìn)行連接，以概率1-a進(jìn)行擇優(yōu)選擇，在擇優(yōu)選擇中，以概率p選擇度數(shù)大的節(jié)點(diǎn)進(jìn)行連接，以概率1-p選擇影響力高(即PRS值大)的節(jié)點(diǎn)進(jìn)行連接。

3 .仿真結(jié)果

采用Matlab R2013a在Windows7環(huán)境下模擬仿真改進(jìn)模型的網(wǎng)絡(luò)生成過(guò)程，并編程得出模擬網(wǎng)絡(luò)的度分布示意圖，并調(diào)整參數(shù)得出不同條件下的平均路徑長(zhǎng)度、聚類系數(shù)變化圖。

3.1 度分布

對(duì)于改進(jìn)模型的度分布，我們?cè)O(shè)計(jì)了三組不同的實(shí)驗(yàn)，當(dāng)參數(shù)取不同值時(shí)，來(lái)驗(yàn)證生成網(wǎng)絡(luò)的度分布是否符合冪律分布。每組實(shí)驗(yàn)的設(shè)計(jì)思想是，固定一個(gè)參數(shù)，使另外兩個(gè)參數(shù)兩兩變化，觀察度分布圖形，然后改變固定的參數(shù)，再觀察度分布圖形。在第一組實(shí)驗(yàn)中，分別設(shè)置d=0.2和d=0.6得到圖1、圖2中的雙對(duì)數(shù)坐標(biāo)下的改進(jìn)模型度分布圖。在兩個(gè)圖中使用符號(hào)“*”表示a=0.1，p=0.2時(shí)的度分布圖，命名為A分布；使用符號(hào)“+”表示a=0.5，p=0.2時(shí)的度分布圖，命名為B分布；使用符號(hào)“o”表示a= 0.1，p=0.6時(shí)的度分布圖，命名為C分布。

圖1 d=0.2時(shí)改進(jìn)模型度分布

圖2 d=0.6時(shí)改進(jìn)模型度分布

在這組實(shí)驗(yàn)中，以上兩圖中B分布與A、C分布稍有差異，也就是說(shuō)，當(dāng)a取0.1時(shí)，度較大的節(jié)點(diǎn)數(shù)較多，當(dāng)a取0.6時(shí)，度較小的節(jié)點(diǎn)數(shù)較多。

在第二組實(shí)驗(yàn)中，分別設(shè)置a=0.2和a=0.6得到圖3、圖4中的雙對(duì)數(shù)坐標(biāo)下的改進(jìn)模型度分布圖。在兩個(gè)圖中使用符號(hào)“*”表示d=0.1，p=0.2時(shí)的度分布圖，使用符號(hào)“+”表示d=0.5，p=0.2時(shí)的度分布圖，使用符號(hào)“o”表示d=0.1，p=0.6時(shí)的度分布圖。

圖3 a=0.2時(shí)改進(jìn)模型的度分布

圖4 a=0.6時(shí)改進(jìn)模型的度分布

在這組實(shí)驗(yàn)中，從以上兩個(gè)圖可以看到改變a值的大小，度分布圖的形狀有變化，a取0.2時(shí)三種不同情況的度分布可擬合的直線斜率略大于a取0.6時(shí)。

在第三組實(shí)驗(yàn)中，分別設(shè)置p=0.2和p=0.6得到圖5、圖6中的雙對(duì)數(shù)坐標(biāo)下的改進(jìn)模型度分布圖。在兩個(gè)圖中使用符號(hào)“*”表示d=0.1，a=0.2時(shí)的度分布圖，使用符號(hào)“+”表示d=0.5，a=0.2時(shí)的度分布圖，使用符號(hào)“o”表示d=0.1，a=0.6時(shí)的度分布圖。

圖5 p=0.2時(shí)改進(jìn)模型的度分布

圖6 p=0.6時(shí)改進(jìn)模型的度分布

在這組實(shí)驗(yàn)中，由以上兩圖的度分布可以看到，p值取0.6時(shí)，度分布較為均勻，度數(shù)小的節(jié)點(diǎn)出現(xiàn)的概率較p取0.2時(shí)多一些，度數(shù)大的節(jié)點(diǎn)出現(xiàn)的概率較p取0.2時(shí)少一些。

由以上的6張圖可以看到，在取不同的參數(shù)下，改進(jìn)模型都呈現(xiàn)出冪律分布，與BA模型一樣具有“胖尾”特征，不同之處在于，度數(shù)的大小與出現(xiàn)的概率大小不一致。也就是說(shuō)，在改進(jìn)模型中，隨機(jī)選擇與擇優(yōu)選擇的比重以及擇優(yōu)選擇采用哪種方式均不會(huì)影響模型的度分布特征。

3.2 聚類系數(shù)與平均路徑長(zhǎng)度

以上的節(jié)點(diǎn)度分布圖說(shuō)明了改進(jìn)模型與BA模型一樣具有冪律特征，為了進(jìn)一步分析改進(jìn)模型的網(wǎng)絡(luò)特征，我們還對(duì)該網(wǎng)絡(luò)模型的聚類系數(shù)以及平均路徑長(zhǎng)度進(jìn)行了仿真，分別設(shè)置不同的參數(shù)取值來(lái)對(duì)比分析。由于d、a、p的值均在0到1之間，這里d和p我們分別去三個(gè)值：0.1、0.5、0.9，a從0.1取到0.9，得到不同的聚類系數(shù)與平均路徑長(zhǎng)度。

分別選取d和p值為0.1、0.5、0.9，a從0.1取到0.9，作出不同參數(shù)取值時(shí)改進(jìn)模型的聚類系數(shù)和平均路徑長(zhǎng)度。圖7到圖9分別為d取0.1、0.5、0.9時(shí)改進(jìn)模型的聚類系數(shù)變化圖。

圖7 聚類系數(shù)(d=0.1)

圖8 聚類系數(shù)(d=0.5)

圖9 聚類系數(shù)(d=0.9)

觀察以上三圖，圖7和圖8中聚類系數(shù)總體會(huì)隨著a值的增加呈上升趨勢(shì)，而圖9中聚類系數(shù)的變化趨勢(shì)與前面兩圖有所不同，紅色折線（p=0.9）在a=0.5之后趨于平穩(wěn)，說(shuō)明在d和p取得較大值0.9的情況下，當(dāng)a取值大于0.5時(shí)，聚類系數(shù)不再逐漸增加而是趨于一個(gè)相對(duì)平穩(wěn)的值。因?yàn)楫?dāng)d，p，a同時(shí)取得較大值時(shí)，用戶之間進(jìn)行連接時(shí)，隨機(jī)因素削弱，用戶影響力得分逐漸取決于固定的舊好友的PRS值，這使得連接方式趨于固定，因此，聚類系數(shù)逐漸趨于平穩(wěn)。

圖10到圖12分別為d取0.1、0.5、0.9時(shí)改進(jìn)模型的平均路徑長(zhǎng)度變化圖。

圖10 平均路徑長(zhǎng)度(d=0.1)

圖11 平均路徑長(zhǎng)度(d=0.5)

圖12 平均路徑長(zhǎng)度(d=0.9)

3.3 實(shí)驗(yàn)結(jié)果分析

（1）筆者改進(jìn)BA模型聚類系數(shù)和平均路徑長(zhǎng)度可調(diào)控范圍較大。聚類系數(shù)隨著可變參數(shù)d、a、p的增大成增大趨勢(shì)，而平均路徑長(zhǎng)度成減小趨勢(shì)，這是目前的一些BA改進(jìn)模型所不及的。筆者的模型更能滿足現(xiàn)實(shí)社交網(wǎng)絡(luò)的需求，因?yàn)樵趯?shí)際社交網(wǎng)絡(luò)中存在社群，當(dāng)我們?cè)谘芯坎煌秶鷥?nèi)的網(wǎng)絡(luò)特征時(shí)，其中的社群規(guī)模及數(shù)目也不同，有的網(wǎng)絡(luò)中社群規(guī)模較大，則它的聚類系數(shù)相對(duì)較大，平均路徑長(zhǎng)度相對(duì)較小。

（2）筆者改進(jìn)BA模型的平均路徑長(zhǎng)度與原始BA模型相比總體偏小，而聚類系數(shù)偏大。在社交網(wǎng)絡(luò)中，從聚類系數(shù)的大小可以看出社團(tuán)朋友圈的聚集程度，聚類系數(shù)越大表示聚集程度越高，越適合描述熟人網(wǎng)絡(luò)。在熟人網(wǎng)絡(luò)中，人們之間的信任度相對(duì)較強(qiáng)，傳播信息可信度較高。正是因?yàn)楦倪M(jìn)模型的聚類系數(shù)增大，因此它的平均路徑長(zhǎng)度也減小到了合理的范圍之內(nèi)，符合復(fù)雜網(wǎng)絡(luò)理論中的小世界網(wǎng)絡(luò)特征。

4 結(jié)束語(yǔ)

筆者針對(duì)BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的缺陷以及實(shí)際社交網(wǎng)絡(luò)的連接特性，提出了一種適合社交網(wǎng)絡(luò)的BA無(wú)標(biāo)度網(wǎng)絡(luò)的改進(jìn)模型，該模型基于多因素且具有混合連邊方式，考量節(jié)點(diǎn)連接概率方面，在擇優(yōu)連接的基礎(chǔ)上增加了隨機(jī)連接，擇優(yōu)連接的因素不僅只是節(jié)點(diǎn)的度還由節(jié)點(diǎn)的影響力來(lái)決定。仿真結(jié)果顯示，該模型的度分布呈冪律分布，通過(guò)調(diào)節(jié)參數(shù)值可大范圍調(diào)節(jié)聚類系數(shù)及平均路徑長(zhǎng)度，比原始BA模型具有更優(yōu)的統(tǒng)計(jì)特性，適合構(gòu)建與描述具有大聚類系數(shù)特性的社交網(wǎng)絡(luò),為構(gòu)建不同需求的網(wǎng)絡(luò)提供了一種較為靈活的方案，具有普適性。

[1]侯麗芳.無(wú)標(biāo)度網(wǎng)絡(luò)的演化模型研究及應(yīng)用[D].秦皇島：燕山大學(xué),2016.

[2]DL Wang,Z G Yu,Anh V.Multifractal analysis of complex networks[J].Chinese Physics B,2012(8): 89-99.

[3]李志宏,莊云蓓.基于PageRank算法的雙維度微博用戶影響力實(shí)時(shí)度量模型[J].系統(tǒng)工程,2016(2):128-137.

[4]Page L,Brin S,Motwani R,et al.The PageRank citation ranking:bringing order to the web[EB/OL].http: //ilpubs.stanford.edu:8090/422/.2012-05-13.

[5]張琨,李配配,朱保平,等.基于PageRank的有向加權(quán)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要性評(píng)估方法[J].南京航空航天大學(xué)學(xué)報(bào),2013(3):429-434.

[6]王金龍.在線社交網(wǎng)絡(luò)模型演化及傳播機(jī)制研究[D].濟(jì)南：山東師范大學(xué),2016.

[7]許進(jìn),楊揚(yáng),蔣飛,等.社交網(wǎng)絡(luò)結(jié)構(gòu)特性分析及建模研究進(jìn)展[J].中國(guó)科學(xué)院院刊,2015(2):216-228.

（責(zé)任編輯 卞建寧）

Study on BA Scare-free Evolving Model Based on Social Network

WANG Xiaolei
(Northwest University of Political Science and Law Library,Xi’an,710122,China)

TP311

B

1671-9123（2017）02-0133-07

2017-03-30

王筱蕾（1989-），女，陜西眉縣人，西北政法大學(xué)圖書館助理館員。