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

在審

• 申請(qǐng)?zhí)枺?/td>: 201710058277.3
• 申請(qǐng)日: 2017-01-23
• 公開（公告）號(hào): CN106921516A
• 公開（公告）日: 2017-07-04
• 發(fā)明（設(shè)計(jì)）人: 楊旭華;俞佳;沈敏
• 申請(qǐng)（專利權(quán)）人: 浙江工業(yè)大學(xué)
• 主分類號(hào): H04L12/24
• 分類號(hào): H04L12/24
• 代理公司: 杭州斯可睿專利事務(wù)所有限公司33241
• 代理人: 王利強(qiáng)

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

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

背景技術(shù)

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

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

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

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

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

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

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

步驟二：任意選取網(wǎng)絡(luò)G中兩個(gè)無連邊的節(jié)點(diǎn)i和j為兩個(gè)種子節(jié)點(diǎn)，i和j之間路徑長度為2的中間的一個(gè)節(jié)點(diǎn)為一階共同鄰居，長度為3的路徑的中間2個(gè)節(jié)點(diǎn)為二階共同鄰居，提取所有i和j的一階共同鄰居節(jié)點(diǎn)和二階共同鄰居節(jié)點(diǎn)以及這些節(jié)點(diǎn)之間的連邊，構(gòu)成二階局部群落，該群落的節(jié)點(diǎn)總數(shù)記為CN_ij，總連邊數(shù)量記為SCS_ij，節(jié)點(diǎn)i和j的一階和二階鄰居的總數(shù)分別記為T_i和T_j，其中與節(jié)點(diǎn)i或j的路徑長度等于1的節(jié)點(diǎn)為其一階鄰居，與節(jié)點(diǎn)i或j的路徑長度等于2的節(jié)點(diǎn)為其二階鄰居；

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

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

其中，

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

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

D_ij＝SCS_ij/CN_ij；

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

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

上式中，＜A_i＞表示鄰接矩陣中第i行元素的均值其中n表示鄰接矩陣A含n個(gè)節(jié)點(diǎn)；

步驟八：計(jì)算兩個(gè)節(jié)點(diǎn)i，j之間的相似性分?jǐn)?shù)指標(biāo)：

HLNP_ij＝LCT_ij*CN_ij*SCS_ij/(T_i*T_j)+λ*S_ij；

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

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