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

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

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

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

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

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

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