基于局部路徑算法去重復(fù)路徑的鏈路預(yù)測(cè).pdf

1、現(xiàn)實(shí)生活中以及科研工作中運(yùn)用到的各個(gè)單位以及他們之間的關(guān)系可以抽象化成一個(gè)網(wǎng)絡(luò)，由于網(wǎng)絡(luò)信息的復(fù)雜性，將這種網(wǎng)絡(luò)稱之為復(fù)雜網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)就是復(fù)雜系統(tǒng)的結(jié)構(gòu)，其中包括結(jié)構(gòu)復(fù)雜性：就是網(wǎng)絡(luò)系統(tǒng)具有豐富的結(jié)構(gòu)他包括社區(qū)，基序，集聚性，生成規(guī)律性等。網(wǎng)絡(luò)的結(jié)構(gòu)可能會(huì)隨著時(shí)間而變化的；節(jié)點(diǎn)復(fù)雜性，它包括復(fù)雜網(wǎng)絡(luò)之間相互影響的復(fù)雜性以及網(wǎng)絡(luò)分層結(jié)構(gòu)的復(fù)雜性；網(wǎng)絡(luò)進(jìn)化，表現(xiàn)在節(jié)點(diǎn)或鏈接的產(chǎn)生與消失，這也表明了網(wǎng)絡(luò)結(jié)構(gòu)的時(shí)變性；連接多樣性，他包括連接權(quán)

2、重的多樣以及方向的多樣性；動(dòng)力學(xué)復(fù)雜性以及多重復(fù)雜性融合等等。以上的種種特征表明，廣義網(wǎng)絡(luò)的復(fù)雜性可從多方面去討論研究。
　　復(fù)雜網(wǎng)絡(luò)根據(jù)節(jié)點(diǎn)分布社區(qū)集聚特性，可分為單分網(wǎng)絡(luò)和二分網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間都存在連接關(guān)系或是存在潛在的連接關(guān)系的網(wǎng)絡(luò)稱之為單分網(wǎng)絡(luò)；然而二分網(wǎng)絡(luò)是將所有的節(jié)點(diǎn)劃分為兩個(gè)集合，兩個(gè)集合內(nèi)部之間沒有連接關(guān)系，集合之間存在連接關(guān)系或是存在可能的連接關(guān)系。
　　網(wǎng)絡(luò)的鏈路預(yù)測(cè)是指通過(guò)已有的節(jié)點(diǎn)連接關(guān)系

3、去預(yù)測(cè)不存在連接關(guān)系的節(jié)點(diǎn)存在連接關(guān)系的可能性。這種預(yù)測(cè)既包含了對(duì)本身不存在且以后也不會(huì)存在鏈接的預(yù)測(cè)，同時(shí)也包含了對(duì)未來(lái)可能存在鏈接的預(yù)測(cè)。本文所做工作如下：
　　首先了解了復(fù)雜網(wǎng)絡(luò)以及網(wǎng)絡(luò)鏈路預(yù)測(cè)的相關(guān)知識(shí)，通過(guò)生物種群網(wǎng)絡(luò)之間的互惠和捕殺行為中找到二分網(wǎng)絡(luò)在復(fù)雜網(wǎng)絡(luò)中的具體實(shí)現(xiàn)，同時(shí)還發(fā)現(xiàn)在實(shí)際生活中存在著很多二分網(wǎng)絡(luò)跡象。通過(guò)對(duì)二分網(wǎng)絡(luò)特性的了解，找到關(guān)于二分網(wǎng)絡(luò)特有的鏈路預(yù)測(cè)方法，不僅僅局限于現(xiàn)有的一般性的鏈路預(yù)測(cè)方法，

4、這種鏈路預(yù)測(cè)方法就是基于局部路徑的思想而得到的算法。首先觀察到二分網(wǎng)絡(luò)路徑長(zhǎng)度只存在奇數(shù)路徑，因此從指數(shù)度量函數(shù)聯(lián)想到刪除偶數(shù)路徑之后就可得到奇數(shù)路徑，而這個(gè)奇數(shù)路徑從數(shù)學(xué)的角度上來(lái)看，其公式就是三角函數(shù)中的雙曲正弦函數(shù)；還包括馮諾依曼指標(biāo)，也是同樣進(jìn)行奇數(shù)部分的保留來(lái)進(jìn)行二分網(wǎng)絡(luò)的鏈路預(yù)測(cè)。
　　通過(guò)對(duì)二分網(wǎng)絡(luò)的了解與預(yù)測(cè)，在進(jìn)行路徑矩陣分析發(fā)現(xiàn)，在路徑矩陣中存在著重復(fù)路徑的問(wèn)題，且路徑長(zhǎng)度越長(zhǎng)其重復(fù)的個(gè)數(shù)越多，造成不必要的資源

5、浪費(fèi)，且在一定程度上影響著網(wǎng)絡(luò)真實(shí)路徑信息的觀察和了解，去重復(fù)路徑問(wèn)題就成為本文現(xiàn)階段討論的主要問(wèn)題。通過(guò)對(duì)路徑矩陣生成的形式觀察，找出重復(fù)路徑產(chǎn)生的原因，以及去重復(fù)路徑的方法。在發(fā)現(xiàn)去除重復(fù)路徑之后的預(yù)測(cè)結(jié)果能夠良好的得到預(yù)想的實(shí)驗(yàn)結(jié)果。
　　從二分網(wǎng)絡(luò)中聯(lián)想到在一般網(wǎng)絡(luò)中是否實(shí)際也同樣存在著重復(fù)路徑，答案是肯定的。但是由于網(wǎng)絡(luò)本身的性質(zhì)因此它并不區(qū)分奇數(shù)路徑和偶數(shù)路徑。采用和二分網(wǎng)絡(luò)同樣的思路進(jìn)行重復(fù)路徑的去除，再對(duì)其進(jìn)行實(shí)驗(yàn)