[發(fā)明專利]一個預測社交網(wǎng)絡演化過程和網(wǎng)絡性質(zhì)的方法

有效

• 申請?zhí)枺?/td>: 201310567085.7
• 申請日: 2013-11-14
• 公開（公告）號: CN103593438B
• 公開（公告）日: 2017-01-11
• 發(fā)明（設計）人: 童超;喬梁;羅小簡;朱薔;馬駿
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;H04L29/08
• 代理公司: 北京永創(chuàng)新實專利事務所11121
• 代理人: 祗志潔

技術領域

本發(fā)明提出一個用于預測社交網(wǎng)絡演化過程和網(wǎng)絡性質(zhì)的模型，屬于計算機技術領域和社交網(wǎng)絡技術領域。

背景技術

近年來對于社交網(wǎng)絡演化的研究非常熱，研究者也提出了一些模型。然而這些模型并不能適用于預測各種類型的社交網(wǎng)絡演化方向，目前，在該領域還沒有一個公認的較好的能夠準確預測網(wǎng)絡未來演化方向的模型。

現(xiàn)有一個比較經(jīng)典的社交網(wǎng)絡演化模型是BA模型。在BA模型中，初始時刻，假設系統(tǒng)中已存在少量節(jié)點，在之后的每一個時間間隔中都新增一個節(jié)點，并將該節(jié)點與網(wǎng)絡中已存在的節(jié)點進行連接，連接時按優(yōu)先連接進行。這樣，BA網(wǎng)絡就演化為標度不變的狀態(tài)，即節(jié)點度分布為冪指數(shù)等于3的冪律分布。但是，BA模型也存在著一定的問題，BA模型的聚類系數(shù)很小，特別當網(wǎng)絡規(guī)模很大時，網(wǎng)絡的聚類系數(shù)接近于0，這與真實網(wǎng)絡具有較大聚類系數(shù)的特點并不相符合。本發(fā)明在充分研究BA模型的優(yōu)缺點后，發(fā)現(xiàn)雖然BA模型生成網(wǎng)絡度分布與實際社交網(wǎng)絡度分布相似，但是其聚類系數(shù)較小，與實際社交網(wǎng)絡特點不符，進一步深入分析聚類系數(shù)關于度的分布之后，發(fā)現(xiàn)BA模型生成的網(wǎng)絡與真實的社交網(wǎng)絡有很大的差異，可以說根本不存在局部性，而局部性是社交網(wǎng)絡中非常重要的一個特性。

發(fā)明內(nèi)容

本發(fā)明針對BA模型生成的網(wǎng)絡與真實社交網(wǎng)絡存在很大差異的問題，提供了一種預測社交網(wǎng)絡演化過程和網(wǎng)絡性質(zhì)的方法，通過分析實際社交網(wǎng)絡特點，在BA模型中引入三元閉包的思想，改進了BA模型。三元閉包即通過在擁有共同好友的兩節(jié)點間加邊，以達到增加聚類系數(shù)，改善模型的局部性的效果。

本發(fā)明提供的預測社交網(wǎng)絡演化過程和網(wǎng)絡性質(zhì)的方法，包括如下步驟：

步驟1：將社交網(wǎng)絡用無向無權圖表示，設初始網(wǎng)絡中每兩個節(jié)點都相連，設n表示網(wǎng)絡當前的節(jié)點個數(shù)；

步驟2：新加入一個節(jié)點時，根據(jù)優(yōu)先連接概率從當前網(wǎng)絡中選取k個節(jié)點與新加入節(jié)點相連接；在連接完成后，更新網(wǎng)絡的節(jié)點數(shù)n'=n+1；

節(jié)點i的優(yōu)先連接概率H(i)為：其中，d_i、d_j分別表示節(jié)點i、節(jié)點j的度；

步驟3：更新n=n'，計算當前網(wǎng)絡中的每個節(jié)點的聚集力和網(wǎng)絡的聚集力總和；

節(jié)點i的聚集力PoA(i)為：PoA(i)=diα,di<KKα,di≥K;]]>其中，α是關于網(wǎng)絡特點的參數(shù)，K是節(jié)點度的閾值；

網(wǎng)絡的聚集力總和SPoA為：

步驟4：從當前網(wǎng)絡中選出c個節(jié)點作為中心節(jié)點，節(jié)點i被選取的概率對于每個中心節(jié)點，以等概率任取它的兩個好友節(jié)點連邊；

步驟5：檢查當前網(wǎng)絡的規(guī)模是否已經(jīng)符合設定的要求，若是，結束本方法，否則跳至步驟2執(zhí)行。

本發(fā)明的預測社交網(wǎng)絡演化過程和網(wǎng)絡性質(zhì)的方法，在一定程度上弱化了BA模型的弊端，生成接近于真實的社交網(wǎng)絡，較好地展現(xiàn)并預測網(wǎng)絡演化過程。本發(fā)明方法在保證節(jié)點度分布為冪指數(shù)為3的冪律分布的前提下，實現(xiàn)了增加聚類系數(shù)，改善模型局部性的效果，更加接近實際社交網(wǎng)絡的性質(zhì)。

附圖說明

圖1是本發(fā)明的預測社交網(wǎng)絡演化過程和網(wǎng)絡性質(zhì)的方法的流程示意圖；

圖2為本發(fā)明的預測社交網(wǎng)絡演化過程和網(wǎng)絡性質(zhì)方法的原理示意圖；

圖3為本發(fā)明的預測社交網(wǎng)絡演化過程和網(wǎng)絡性質(zhì)方法的效果圖。

具體實施方式

下面將結合附圖和實施例來說明本發(fā)明的技術方案。