[發(fā)明專利]一種基于局部拓?fù)湫畔⒑蜕鐖F(tuán)相關(guān)性的鏈路預(yù)測方法

在審

• 申請?zhí)枺?/td>: 201710260562.3
• 申請日: 2017-04-20
• 公開（公告）號(hào): CN107248923A
• 公開（公告）日: 2017-10-13
• 發(fā)明（設(shè)計(jì)）人: 楊清海;席敏燕
• 申請（專利權(quán)）人: 西安電子科技大學(xué);西安中電科西電科大雷達(dá)技術(shù)協(xié)同創(chuàng)新研究院有限公司
• 主分類號(hào): H04L12/24
• 分類號(hào): H04L12/24
• 代理公司: 西安長和專利代理有限公司61227
• 代理人: 黃偉洪

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

本發(fā)明屬于網(wǎng)絡(luò)科學(xué)和鏈路預(yù)測技術(shù)領(lǐng)域，尤其涉及一種基于局部拓?fù)湫畔⒑蜕鐖F(tuán)相關(guān)性的鏈路預(yù)測方法。

背景技術(shù)

鏈路預(yù)測是將復(fù)雜網(wǎng)路與信息科學(xué)聯(lián)系起來的重要橋梁之一，有重要的實(shí)際應(yīng)用價(jià)值。鏈路預(yù)測是指通過已知網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)等信息預(yù)測網(wǎng)絡(luò)中尚未鏈接的兩個(gè)節(jié)點(diǎn)之間產(chǎn)生鏈接的可能性。鏈接包括未知和未來鏈接兩種，未知鏈接指的是目前的網(wǎng)絡(luò)中本來存在但是由于某種原因缺失的鏈接，未來鏈接指的是目前的網(wǎng)絡(luò)中沒有但是在將來有可能出現(xiàn)的鏈接。目前，基于局部拓?fù)湫畔⒌逆溌奉A(yù)測算法由于算法復(fù)雜度低，計(jì)算簡便，已經(jīng)成為主流的方法。例如現(xiàn)有的共同鄰居算法(CN)、Adamic-Adar算法(AA)、資源分配算法(RA)，這些算法都是基于局部拓?fù)湫畔⑦M(jìn)行鏈路預(yù)測的，但是它們沒有考慮到社團(tuán)結(jié)構(gòu)對鏈路預(yù)測的影響，因此預(yù)測的準(zhǔn)確度不高。現(xiàn)在已有一些研究者把社團(tuán)結(jié)構(gòu)加入到鏈路預(yù)測中，他們認(rèn)為處在同一個(gè)社團(tuán)的節(jié)點(diǎn)相似性比較高，處在不同社團(tuán)的節(jié)點(diǎn)相似性相對低。然而，他們只考慮了社團(tuán)內(nèi)部的節(jié)點(diǎn)之間的關(guān)系，而忽略了社團(tuán)之間的相似性，且這些方法都是在共同鄰居存在的前提下定義的，當(dāng)處于不同社團(tuán)的兩個(gè)節(jié)點(diǎn)之間沒有共同鄰居時(shí)，則認(rèn)為這兩個(gè)節(jié)點(diǎn)的相似性為0，因此這些算法的預(yù)測準(zhǔn)確性比較低。

綜上所述，現(xiàn)有技術(shù)存在的問題是：目前基于局部拓?fù)湫畔⒌逆溌奉A(yù)測方法預(yù)測準(zhǔn)確度不高。

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

針對現(xiàn)有技術(shù)存在的問題，本發(fā)明提供了一種基于局部拓?fù)湫畔⒑蜕鐖F(tuán)相關(guān)性的鏈路預(yù)測方法。

本發(fā)明是這樣實(shí)現(xiàn)的，一種基于局部拓?fù)湫畔⒑蜕鐖F(tuán)相關(guān)性的鏈路預(yù)測方法，所述基于局部拓?fù)湫畔⒑蜕鐖F(tuán)相關(guān)性的鏈路預(yù)測方法利用節(jié)點(diǎn)之間局部拓?fù)湫畔⒂?jì)算節(jié)點(diǎn)之間的相似性值。當(dāng)兩個(gè)節(jié)點(diǎn)處于同一個(gè)社團(tuán)時(shí)，社團(tuán)相關(guān)性為最大值，當(dāng)兩個(gè)節(jié)點(diǎn)處于不同社團(tuán)時(shí)，在考慮局部拓?fù)湫畔⒌幕A(chǔ)上，將節(jié)點(diǎn)之間的相似性轉(zhuǎn)化為兩個(gè)社團(tuán)之間的相關(guān)性，然后計(jì)算兩個(gè)社團(tuán)之間的相關(guān)性值。最后綜合考慮局部拓?fù)湫畔⒑蜕鐖F(tuán)相關(guān)性的影響進(jìn)行鏈路預(yù)測；

所述基于局部拓?fù)湫畔⒑蜕鐖F(tuán)相關(guān)性的鏈路預(yù)測方法在無權(quán)無向的復(fù)雜網(wǎng)絡(luò)中進(jìn)行；用A表示鄰接矩陣，如果節(jié)點(diǎn)i和節(jié)點(diǎn)j有聯(lián)系，那么A的第i行第j列上的值為A_ij＝1，否則A_ij＝0；節(jié)點(diǎn)的度被定義為網(wǎng)絡(luò)中所有與該節(jié)點(diǎn)直接相連的節(jié)點(diǎn)的個(gè)數(shù)，節(jié)點(diǎn)i的度通常被記為k_i，可以用公式表示；定義：Γ(x)為x的鄰居集合，其中x可以是節(jié)點(diǎn)也可以是社團(tuán)。

進(jìn)一步，所述基于局部拓?fù)湫畔⒑蜕鐖F(tuán)相關(guān)性的鏈路預(yù)測方法包括以下步驟：

步驟一，建立網(wǎng)絡(luò)模型G(V,E),V＝{v₁,v₂,...v_n}為網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，E＝{(v_x,v_y)|v_x∈V,v_y∈V}代表邊的集合，基于網(wǎng)絡(luò)模型生成鄰接矩陣A，其中

步驟二，網(wǎng)絡(luò)被劃分成四個(gè)社團(tuán)，記為C＝{c₁,c₂,c₃,c₄}，其中V(c₁)＝{1,2,3,4}，V(c₂)＝{5,6,7,8,9}，V(c₃)＝{10,11,12,13}，V(c₄)＝{14,15,16,17}；

步驟三，將網(wǎng)絡(luò)中所有的節(jié)點(diǎn)對(i,j)挑選出來作為候選節(jié)點(diǎn)對；

步驟四，利用候選節(jié)點(diǎn)對之間的局部拓?fù)湫畔⒂?jì)算步驟三所述的節(jié)點(diǎn)對之間的相似性值，因?yàn)檫@兩對節(jié)點(diǎn)都沒有共同鄰居，所以用局部拓?fù)湫畔⒂?jì)算出來的兩對節(jié)點(diǎn)的相似性值都為0；

步驟五，計(jì)算步驟三所述的節(jié)點(diǎn)對所在社團(tuán)的社團(tuán)相關(guān)性；

步驟六，綜合考慮局部拓?fù)湫畔⒑蜕鐖F(tuán)相關(guān)性對節(jié)點(diǎn)相似性的影響，重新計(jì)算候選節(jié)點(diǎn)對之間的相似性值S_u,v。例如采用公式因此節(jié)點(diǎn)5和節(jié)點(diǎn)10之間的相似性比節(jié)點(diǎn)10和節(jié)點(diǎn)14之間的相似性高；

步驟七，重復(fù)步驟四至步驟六，計(jì)算每個(gè)節(jié)點(diǎn)對的相似性值，并將相似性值按降序排列，構(gòu)建相似性列表；

步驟八，根據(jù)某種相似性準(zhǔn)則，獲取相似性列表中前N個(gè)節(jié)點(diǎn)對，這些排在前N個(gè)的節(jié)點(diǎn)對即為本鏈路預(yù)測方法得出的最有可能在未來產(chǎn)生連邊的節(jié)點(diǎn)對，其中N為正整數(shù)。

進(jìn)一步，所述步驟五中具體過程如下：

(1)分別找到候選節(jié)點(diǎn)5和10所在的社團(tuán)c₂和c₃；