◎王筱蕾

（西北政法大學 圖書館，西安 710122）

基于社交網(wǎng)絡的BA無標度演化模型的研究

◎王筱蕾

（西北政法大學 圖書館，西安 710122）

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

PageRank算法；BA無標度網(wǎng)絡；社交網(wǎng)絡；改進模型

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

1 BA無標度模型算法介紹及缺陷分析

1.1 BA無標度模型算法

BA無標度網(wǎng)絡模型的構造算法[2]如下:

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

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

1.2 缺陷分析

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

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

2 基于社交網(wǎng)絡的BA無標度演化模型

2.1 PageRank算法介紹及改進

經(jīng)典網(wǎng)頁排名PageRank算法為每個網(wǎng)頁設定PR值為網(wǎng)頁的影響力分數(shù)，借鑒PageRank算法的思想來對社交網(wǎng)絡中每個用戶進行影響力估算[3]，為了更準確地計算用戶的影響力，筆者對原PageRank算法進行改進，使用改進的PageRank算法來計算社交網(wǎng)絡中用戶的影響力大小。

2.1.1 PageRank算法介紹

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

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

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

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

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

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

2.1.2 PageRank算法改進

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

（1）實際中存在用戶回退瀏覽不同頁面的情況，這個因素不應該被忽略，而上面原始的計算PR值公式并沒有考慮到這一點。

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

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

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

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

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

綜合以上兩個特征，筆者將以上改進算法PRS計算過程總結如下：

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

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

Step4.pt即是各個結點的重要性向量，對其按照從大到小的順序排序，就可以得到結點重要性的排序結果。

2.2 演化模型構建思想

前面介紹了BA無標度網(wǎng)絡模型的算法，并分析了該算法應用到社交網(wǎng)絡中的缺陷，針對該缺陷以及社交網(wǎng)絡的實際特征來構建適合描述社交網(wǎng)絡的演化模型。

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

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

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

2.3 演化模型構建算法

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

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

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

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

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

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

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

在改進模型構造算法中，任意兩點之間的距離為1，且連邊總是由老節(jié)點指向新節(jié)點，所以改進模型為有向無權網(wǎng)絡。所引入的兩個參數(shù)p和a都是可以調節(jié)的，當p=1且a=1時，改進模型退化為基本的BA無標度網(wǎng)絡模型。

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

3 .仿真結果

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

3.1 度分布

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

圖1 d=0.2時改進模型度分布

圖2 d=0.6時改進模型度分布

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

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

圖3 a=0.2時改進模型的度分布

圖4 a=0.6時改進模型的度分布

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

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

圖5 p=0.2時改進模型的度分布

圖6 p=0.6時改進模型的度分布

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

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

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

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

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

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

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

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

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

圖10到圖12分別為d取0.1、0.5、0.9時改進模型的平均路徑長度變化圖。

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

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

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

3.3 實驗結果分析

（1）筆者改進BA模型聚類系數(shù)和平均路徑長度可調控范圍較大。聚類系數(shù)隨著可變參數(shù)d、a、p的增大成增大趨勢，而平均路徑長度成減小趨勢，這是目前的一些BA改進模型所不及的。筆者的模型更能滿足現(xiàn)實社交網(wǎng)絡的需求，因為在實際社交網(wǎng)絡中存在社群，當我們在研究不同范圍內(nèi)的網(wǎng)絡特征時，其中的社群規(guī)模及數(shù)目也不同，有的網(wǎng)絡中社群規(guī)模較大，則它的聚類系數(shù)相對較大，平均路徑長度相對較小。

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

4 結束語

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

[1]侯麗芳.無標度網(wǎng)絡的演化模型研究及應用[D].秦皇島：燕山大學,2016.

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

[3]李志宏,莊云蓓.基于PageRank算法的雙維度微博用戶影響力實時度量模型[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的有向加權復雜網(wǎng)絡節(jié)點重要性評估方法[J].南京航空航天大學學報,2013(3):429-434.

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

[7]許進,楊揚,蔣飛,等.社交網(wǎng)絡結構特性分析及建模研究進展[J].中國科學院院刊,2015(2):216-228.

（責任編輯 卞建寧）

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-），女，陜西眉縣人，西北政法大學圖書館助理館員。