復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)分析與鏈路預(yù)測.pdf

1、研究復(fù)雜網(wǎng)絡(luò)是認(rèn)識復(fù)雜系統(tǒng)的重要手段。諸多對于復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的研究成果表明，真實系統(tǒng)往往會涌現(xiàn)出許多有趣的性質(zhì)，而這些性質(zhì)往往又決定了復(fù)雜系統(tǒng)的功能，并影響著復(fù)雜網(wǎng)絡(luò)領(lǐng)域中的許多理論研究。鏈路預(yù)測是其中一個重要的研究方向，在理論和應(yīng)用層面上都有重大的意義和價值。理論上講，改善鏈路預(yù)測算法與挖掘網(wǎng)絡(luò)結(jié)構(gòu)特征是相互促進(jìn)的，這對于模擬網(wǎng)絡(luò)演化過程有著重要的意義；從應(yīng)用上講，鏈路預(yù)測算法可以直接應(yīng)用于社交網(wǎng)絡(luò)的關(guān)系預(yù)測，與另一重要的信息過濾技

2、術(shù)即推薦系統(tǒng)也有著緊密的聯(lián)系。
　　以復(fù)雜網(wǎng)絡(luò)為研究對象，本文先對網(wǎng)絡(luò)結(jié)構(gòu)做了不同尺度的分析，包括宏觀、中觀和微觀的尺度，然后針對網(wǎng)絡(luò)結(jié)構(gòu)特征提出了相應(yīng)的鏈路預(yù)測算法，最后將鏈路預(yù)測算法應(yīng)用到了推薦系統(tǒng)中。此研究利用了計算機科學(xué)、統(tǒng)計物理學(xué)等諸多學(xué)科常用的理論和方法，不僅發(fā)現(xiàn)了一些有趣且有效的結(jié)構(gòu)特征，還通過分析鏈路預(yù)測與推薦系統(tǒng)在目標(biāo)上的差異，進(jìn)而抽取了網(wǎng)絡(luò)的信息骨架。本文研究的問題包括：
　?。?）在宏觀層面的網(wǎng)絡(luò)結(jié)構(gòu)分

3、析中，對比了不同演化機制對于真實網(wǎng)絡(luò)的影響。針對復(fù)雜網(wǎng)絡(luò)演化模型是否優(yōu)秀的評估問題，提出了一種基于似然分析的模型，該模型突破了傳統(tǒng)方法在此問題上的缺陷：它不需要統(tǒng)計任何網(wǎng)絡(luò)特征指標(biāo)，且首次量化了多種演化機制在網(wǎng)絡(luò)演化過程中的作用大小。
　?。?）在中觀層面上，提出了一種新的方法論，推斷并驗證了有向網(wǎng)絡(luò)中的一個顯著子圖。將勢能理論引入到有向網(wǎng)絡(luò)中，結(jié)合聚類性和同質(zhì)性，得到了同時擁有這三種性質(zhì)的Bi-fan結(jié)構(gòu)；然后通過在多個真實網(wǎng)絡(luò)

4、中開展實驗以驗證該結(jié)構(gòu)的有效性。對于該問題的研究形成了一套適用于挖掘網(wǎng)絡(luò)結(jié)構(gòu)的新方法論，即通過理論分析進(jìn)行推導(dǎo)，再通過實驗進(jìn)行驗證。
　　（3）在微觀層面上，重點研究了節(jié)點的中心性指標(biāo)。通過分析企業(yè)員工在關(guān)系網(wǎng)絡(luò)中的中心性指標(biāo)，對員工是否升職或是否離職進(jìn)行了分類，其中度和核數(shù)都是非常優(yōu)秀的指標(biāo)。進(jìn)一步地，本文首次發(fā)現(xiàn)了度和核數(shù)之間的緊密聯(lián)系：僅僅通過給節(jié)點上的值迭代地施加一個算子，節(jié)點上的值就會從度變?yōu)镠指數(shù)，并最終收斂到核數(shù)。收

5、斂過程中的每一個值都是對節(jié)點中心性的刻畫。
　?。?）應(yīng)用網(wǎng)絡(luò)結(jié)構(gòu)特征的分析結(jié)果以提高鏈路預(yù)測算法。在微觀層面上，通過研究每個節(jié)點在聚類性上的差異，提出了基于樸素貝葉斯的鏈路預(yù)測算法，它不僅將同類算法的預(yù)測準(zhǔn)確度提高了5.7％，還有助于發(fā)現(xiàn)一些相似性很高卻沒有產(chǎn)生連邊的節(jié)點對。在中觀層面上，受計算機通信網(wǎng)絡(luò)中最可信路由問題的啟發(fā)，提出了含權(quán)的鏈路預(yù)測算法，此算法在眾多含權(quán)網(wǎng)絡(luò)中的整體表現(xiàn)最好、也最穩(wěn)定。
　?。?）將鏈路預(yù)測

6、模型應(yīng)用于網(wǎng)絡(luò)演化和推薦系統(tǒng)中。在網(wǎng)絡(luò)演化問題中，討論了鏈路預(yù)測模型在量化演化機制貢獻(xiàn)時的缺陷，同時分析了基于似然分析的評估模型的優(yōu)勢。在推薦系統(tǒng)方面，發(fā)現(xiàn)用戶的活躍度以及商品的流行度能直接影響推薦算法的準(zhǔn)確性，而且恰當(dāng)?shù)乩门c目標(biāo)用戶沒有相似興趣的用戶，反而會取得更好的推薦效果。于是我們猜想信息系統(tǒng)中可能存在一些冗余的甚至是有誤導(dǎo)性的信息，并通過考察網(wǎng)絡(luò)結(jié)構(gòu)和興趣漂移對推薦效果的影響，創(chuàng)新性地提出了信息骨架的概念，用于實驗的網(wǎng)絡(luò)只需要