[發(fā)明專利]一種基于二階局部群落信息分配和節(jié)點相關(guān)性的預(yù)測網(wǎng)絡(luò)連邊的方法

在審

• 申請?zhí)枺?/td>: 201710058270.1
• 申請日: 2017-01-23
• 公開（公告）號: CN106878069A
• 公開（公告）日: 2017-06-20
• 發(fā)明（設(shè)計）人: 楊旭華;俞佳;項旗立
• 申請（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 杭州斯可睿專利事務(wù)所有限公司33241
• 代理人: 王利強

技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)與鏈路預(yù)測領(lǐng)域，特別是指一種基于二階局部群落信息分配和節(jié)點相關(guān)性的預(yù)測網(wǎng)絡(luò)連邊的方法。

背景技術(shù)

隨著互聯(lián)網(wǎng)技術(shù)的蓬勃發(fā)展，人類跨入了網(wǎng)絡(luò)新時代，對世界的認識也越來越深刻。如今，網(wǎng)絡(luò)幾乎覆蓋了我們學(xué)習、工作、生活等各個方面。上網(wǎng)查資料、線上找工作、網(wǎng)上購物等均涉及到萬維網(wǎng)。越來越多的人通過互聯(lián)網(wǎng)來獲取外界信息，從而了解社會動態(tài)。實際生活中我們與人相處就會形成一張人際關(guān)系網(wǎng)，網(wǎng)上購物數(shù)據(jù)就會形成一張訂制的個人偏好網(wǎng)絡(luò)，交通出行也構(gòu)成了一張錯綜復(fù)雜的交通網(wǎng)絡(luò)。網(wǎng)絡(luò)大數(shù)據(jù)的研究為我們生活提供了便利，發(fā)展了現(xiàn)代科技，為電商等帶來極高的價值。

鏈路預(yù)測是指通過網(wǎng)絡(luò)中已知的節(jié)點信息去預(yù)測網(wǎng)絡(luò)中其他未知狀態(tài)或者還沒有直接連接的節(jié)點間產(chǎn)生連接的概率。在生物網(wǎng)、互聯(lián)網(wǎng)、交通網(wǎng)、金融網(wǎng)等各式各樣的網(wǎng)絡(luò)中都可以創(chuàng)造可觀的價值。總結(jié)前人經(jīng)驗，鏈路預(yù)測的研究主要是基于網(wǎng)絡(luò)結(jié)構(gòu)特性，給出節(jié)點連接的相似性分數(shù)，然后與真實網(wǎng)絡(luò)進行對比，衡量算法的優(yōu)劣性，如：RA指標，CN指標。由于網(wǎng)絡(luò)的多樣性以及網(wǎng)絡(luò)數(shù)據(jù)越來越龐大，越來越復(fù)雜，更新鏈路預(yù)測算法使得預(yù)測精度與效率達到滿意程度就顯得十分必要。對于簡單的網(wǎng)絡(luò)，許多算法可能都會適用，一旦網(wǎng)絡(luò)變得復(fù)雜，網(wǎng)絡(luò)數(shù)據(jù)中存在的特性難以用簡單的算法提取，常常會出現(xiàn)噪聲過多導(dǎo)致預(yù)測效果變差的情況，因此對鏈路預(yù)測的特性提取研究就顯得非常必要。

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

為了克服現(xiàn)有預(yù)測網(wǎng)絡(luò)連邊的方法的獲取網(wǎng)絡(luò)信息不全面、預(yù)測精度較低、預(yù)測性能較差的不足，為了更全面地獲取網(wǎng)絡(luò)信息，提升現(xiàn)有算法的預(yù)測性能，本發(fā)明提出一種準確性較高、預(yù)測精度較高的一種基于二階局部群落信息分配和節(jié)點相關(guān)性的預(yù)測網(wǎng)絡(luò)連邊的方法。

本發(fā)明解決其技術(shù)問題所采用的技術(shù)具體步驟是：

一種基于二階局部群落信息分配和節(jié)點相關(guān)性的預(yù)測網(wǎng)絡(luò)連邊的方法，包括如下步驟：

步驟一：構(gòu)建內(nèi)部連通的無向無權(quán)網(wǎng)絡(luò)G(V,E),E為連邊，V為節(jié)點,其鄰接矩陣用A表示；

步驟二：任意選取網(wǎng)絡(luò)G中兩個無連邊的節(jié)點i和j為兩個種子節(jié)點，i和j之間路徑長度為2的中間的一個節(jié)點為一階共同鄰居，長度為3的路徑的中間2個節(jié)點為二階共同鄰居，提取所有i和j的一階共同鄰居節(jié)點和二階共同鄰居節(jié)點以及這些節(jié)點之間的連邊，構(gòu)成二階局部群落，該群落的節(jié)點總數(shù)記為CN_ij，總連邊數(shù)量記為SCS_ij，每個節(jié)點在整體網(wǎng)絡(luò)中的度記為|Г(x)|，每個節(jié)點在二階局部群落中的度記為|γ(s)|，Г(x)表示x節(jié)點的一階和二階鄰居集合,其中與節(jié)點x的路徑長度等于1的節(jié)點為其一階鄰居，與節(jié)點x的路徑長度等于2的節(jié)點為其二階鄰居；

步驟三：計算二階局部群落的邊聚類系數(shù)：

步驟四：計算二階局部群落的簡諧平均距離：

其中，

上式中，g和h表示二階局部群落中任意兩個節(jié)點，d_gh為g和h兩個節(jié)點之間的路徑長度；

步驟五：計算二階局部群落的連邊密度：

D_ij＝SCS_ij/CN_ij；

步驟六：計算二階局部群落系數(shù)：

步驟七：計算節(jié)點i，j的皮爾遜積矩相關(guān)系數(shù)：

上式中，<A_i>表示鄰接矩陣中第i行元素的均值其中n表示鄰接矩陣A含n個節(jié)點；

步驟八：計算兩個節(jié)點i，j之間的相似性分數(shù)指標：

上式中，λ為可調(diào)參數(shù)；

步驟九：遍歷網(wǎng)絡(luò)，針對所有未直接連接的節(jié)點對，重復(fù)步驟二至步驟八，計算相應(yīng)的HRAP指標作為節(jié)點對之間的可能產(chǎn)生連邊的評價指標，HRAP指標越高，節(jié)點對之間越可能存在連邊；將網(wǎng)絡(luò)中所有的未直接相連的節(jié)點對之間的HRAP指標按照由高到低的順序排列，取前h個HRAP指標對應(yīng)的節(jié)點對為可能的預(yù)測連邊，h≤H，其中H為網(wǎng)絡(luò)中沒有直接連邊的節(jié)點對的總數(shù)。

本發(fā)明的技術(shù)構(gòu)思為：基于網(wǎng)絡(luò)結(jié)構(gòu)的鏈路預(yù)測方法，從高階鄰居網(wǎng)絡(luò)結(jié)構(gòu)中獲取的信息往往帶有一定的噪音。本發(fā)明利用二階鄰居節(jié)點，在考慮二階局部群落的結(jié)構(gòu)特征的同時，考慮了局部群落節(jié)點度的信息分配，并且使用皮爾遜積矩相關(guān)系數(shù)為高階鄰居網(wǎng)絡(luò)信息降噪，提取網(wǎng)絡(luò)中二階局部群落的有效信息，提高預(yù)測算法的預(yù)測精度和準確性。