[發(fā)明專利]基于線性規(guī)劃的有向網(wǎng)絡(luò)鏈路預(yù)測方法

在審

• 申請?zhí)枺?/td>: 202010913525.X
• 申請日: 2020-09-03
• 公開（公告）號: CN112183820A
• 公開（公告）日: 2021-01-05
• 發(fā)明（設(shè)計）人: 劉樹新;李星;李勁松;王凱;李英樂;朱宇航;何贊園;王庚潤;衛(wèi)紅權(quán);陳鴻昶;馬宏
• 申請（專利權(quán)）人: 中國人民解放軍戰(zhàn)略支援部隊信息工程大學(xué)
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06K9/62
• 代理公司: 鄭州大通專利商標(biāo)代理有限公司 41111
• 代理人: 石丹丹

本發(fā)明屬于復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測技術(shù)領(lǐng)域，特別涉及一種基于線性規(guī)劃的有向網(wǎng)絡(luò)鏈路預(yù)測方法，該方法首先引入可調(diào)參數(shù)，區(qū)分三種類型鄰居的影響權(quán)重，然后將其對連邊形成的貢獻(xiàn)程度看作未知量，通過對有向網(wǎng)絡(luò)的結(jié)構(gòu)分析建立優(yōu)化函數(shù)，構(gòu)建關(guān)于貢獻(xiàn)程度矩陣的線性規(guī)劃問題，求解貢獻(xiàn)程度矩陣的最優(yōu)解，最后結(jié)合該最優(yōu)解構(gòu)建鏈路預(yù)測指標(biāo)，用于有向網(wǎng)絡(luò)鏈路預(yù)測。本發(fā)明考慮有向網(wǎng)絡(luò)特有局部結(jié)構(gòu)，利用可調(diào)參數(shù)區(qū)分三種類型鄰居節(jié)點對連邊形成的影響，采用線性規(guī)劃方法求解鄰居節(jié)點的最優(yōu)貢獻(xiàn)矩陣，相比傳統(tǒng)方法更符合網(wǎng)絡(luò)結(jié)構(gòu)特征，結(jié)果更具有普適性，在多種類型網(wǎng)絡(luò)中具有魯棒的預(yù)測性能。

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

本發(fā)明屬于復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測技術(shù)領(lǐng)域，特別涉及一種基于線性規(guī)劃的有向網(wǎng)絡(luò)鏈路預(yù)測方法。

背景技術(shù)

復(fù)雜網(wǎng)絡(luò)作為網(wǎng)絡(luò)科學(xué)的基本研究對象，可用于對各類復(fù)雜系統(tǒng)與非線性過程進(jìn)行抽象建模，為研究其內(nèi)在結(jié)構(gòu)機(jī)理與動態(tài)特性帶來極大便利。鏈路預(yù)測作為復(fù)雜網(wǎng)絡(luò)研究中的基本問題，旨在利用已觀測的網(wǎng)絡(luò)結(jié)構(gòu)、屬性等信息預(yù)測網(wǎng)絡(luò)中的未知連邊或未來連邊。其本質(zhì)是大規(guī)模圖數(shù)據(jù)挖掘問題，目前已在推薦系統(tǒng)、交通規(guī)劃、生物科研等諸多領(lǐng)域展現(xiàn)出巨大應(yīng)用價值。

自2003年首次被提出以來，鏈路預(yù)測已歷經(jīng)近20年的研究，相關(guān)方法日趨成熟。然而多數(shù)研究均以簡單的無向無權(quán)網(wǎng)絡(luò)作為研究對象，忽略連邊方向、權(quán)重及其它屬性，著重研究網(wǎng)絡(luò)內(nèi)在拓?fù)涮匦浴，F(xiàn)實世界中的復(fù)雜系統(tǒng)大多具有連邊方向，直接將其簡化為無向網(wǎng)絡(luò)進(jìn)行研究勢必影響結(jié)果的準(zhǔn)確性。比如微博關(guān)注關(guān)系網(wǎng)絡(luò)，其連邊方向指示好友間的關(guān)注關(guān)系，傳統(tǒng)鏈路預(yù)測方法無法確定連邊方向，導(dǎo)致預(yù)測結(jié)果的混淆。同理，在食物鏈網(wǎng)絡(luò)、論文共引網(wǎng)絡(luò)、科研合作網(wǎng)絡(luò)等典型有向網(wǎng)絡(luò)中，傳統(tǒng)鏈路預(yù)測方法均無法實現(xiàn)對連邊存在性與指向方向的同時預(yù)測。

近年來，相關(guān)學(xué)者逐步將關(guān)注點聚集于有向網(wǎng)絡(luò)，相繼提出多種適用于有向網(wǎng)絡(luò)的鏈路預(yù)測方法。其中大部分方法可視為傳統(tǒng)無向網(wǎng)絡(luò)鏈路預(yù)測方法的推廣，并未針對有向網(wǎng)絡(luò)特有的局部結(jié)構(gòu)特點進(jìn)行分析建模，預(yù)測性能存在一定瓶頸。此外，少數(shù)考慮區(qū)分鄰居節(jié)點貢獻(xiàn)程度的方法利用先驗結(jié)構(gòu)特征對節(jié)點貢獻(xiàn)程度進(jìn)行賦值，常用的結(jié)構(gòu)特征包括出入度、簇系數(shù)、介數(shù)等等。此類方法基于對網(wǎng)絡(luò)結(jié)構(gòu)的先驗假設(shè)，在不同類型的有向網(wǎng)絡(luò)中普適性差。

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

為了解決大規(guī)模靜態(tài)有向無權(quán)復(fù)雜網(wǎng)絡(luò)上的鏈路預(yù)測問題，本發(fā)明提出了一種基于線性規(guī)劃的有向網(wǎng)絡(luò)鏈路預(yù)測方法，該方法深度挖掘有向網(wǎng)絡(luò)中三種不同結(jié)構(gòu)鄰居對連邊產(chǎn)生的信息貢獻(xiàn)，通過構(gòu)建與求解線性規(guī)劃問題計算該信息貢獻(xiàn)的最優(yōu)估計值，進(jìn)而將其用于未知連邊的預(yù)測，該方法在多種類型有向網(wǎng)絡(luò)中具有較高的精度與魯棒性，可用于解決多數(shù)鏈路預(yù)測問題。

為解決上述技術(shù)問題，本發(fā)明采用以下的技術(shù)方案：

本發(fā)明提供了一種基于線性規(guī)劃的有向網(wǎng)絡(luò)鏈路預(yù)測方法，包含以下步驟：

步驟1，根據(jù)網(wǎng)絡(luò)類型與先驗信息確定可調(diào)參數(shù)的取值，引入可調(diào)參數(shù)區(qū)分不同鄰居節(jié)點的信息傳輸能力；

步驟2，利用步驟1的可調(diào)參數(shù)構(gòu)建原始有向網(wǎng)絡(luò)的有向含權(quán)同質(zhì)網(wǎng)絡(luò)；

步驟3，基于線性規(guī)劃計算最優(yōu)的鄰居節(jié)點貢獻(xiàn)矩陣；

步驟4，根據(jù)步驟3得到的最優(yōu)的鄰居節(jié)點貢獻(xiàn)矩陣，計算相似度矩陣；

步驟5，按相似度大小進(jìn)行排序，取前若干條邊作為最終預(yù)測邊。

進(jìn)一步地，在所述步驟1之前，還包括：

對目標(biāo)網(wǎng)絡(luò)進(jìn)行預(yù)處理，包括去除連邊權(quán)重、自環(huán)、重復(fù)連邊和孤立節(jié)點，得到原始網(wǎng)絡(luò)的無權(quán)同質(zhì)拓?fù)浣Y(jié)構(gòu)，作為待處理網(wǎng)絡(luò)。

進(jìn)一步地，在對目標(biāo)網(wǎng)絡(luò)進(jìn)行預(yù)處理之后，還包括：

對待處理網(wǎng)絡(luò)中的連邊按照比例f進(jìn)行隨機(jī)劃分，其中一部分作為訓(xùn)練集，另一部分作為測試集，訓(xùn)練集與測試集中的連邊數(shù)量之比為f:(1-f)，其中f為數(shù)據(jù)集劃分比例。