隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展,鏈路預(yù)測(cè)作為研究復(fù)雜網(wǎng)絡(luò)的重要手段之一,具有重要的理論和現(xiàn)實(shí)意義。近年來,該方向的研究成果層出不窮,然而現(xiàn)有算法在充分提取網(wǎng)絡(luò)信息方面仍存在不足,不能準(zhǔn)確且高效地預(yù)測(cè)缺失鏈路。為了解決以上問題,本文首先利用社區(qū)發(fā)現(xiàn)算法提取復(fù)雜網(wǎng)絡(luò)中的結(jié)構(gòu)信息,再與節(jié)點(diǎn)信息進(jìn)行融合,充分利用復(fù)雜網(wǎng)絡(luò)中的信息,提出一種融合社區(qū)結(jié)構(gòu)信息和節(jié)點(diǎn)信息的鏈路預(yù)測(cè)算法。內(nèi)容概述如下:一、針對(duì)模塊度分辨率受限和傳統(tǒng)差分進(jìn)化準(zhǔn)確性與收斂速度方面的問題,提出結(jié)合改進(jìn)差分進(jìn)化和模塊密度的社區(qū)發(fā)現(xiàn)算法（Improved Differential Evolution and Modularity Density Community Detection,IMDECD）。首先調(diào)整差分進(jìn)化的變異策略和參數(shù),再將模塊密度作為適應(yīng)度函數(shù)以克服模塊度分辨率限制;最后根據(jù)社區(qū)結(jié)構(gòu)進(jìn)行修正操作,以提高種群中的個(gè)體質(zhì)量,加快全局收斂速度。二、針對(duì)現(xiàn)有的鏈路預(yù)測(cè)算法在大規(guī)模網(wǎng)絡(luò)耗時(shí)較長(zhǎng)或者預(yù)測(cè)結(jié)果不準(zhǔn)確的問題,利用社區(qū)結(jié)構(gòu)中的結(jié)構(gòu)信息,融合節(jié)點(diǎn)相似性,提出融合社區(qū)結(jié)構(gòu)信息和節(jié)點(diǎn)信息的鏈路預(yù)測(cè)算法（Link Predictio... 

【文章來源】：遼寧大學(xué)遼寧省 211工程院校

【文章頁(yè)數(shù)】：63 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

空手道俱樂部網(wǎng)絡(luò)圖

第1章緒論5鏈路預(yù)測(cè)早期主要基于馬爾科夫鏈和機(jī)器學(xué)習(xí)來進(jìn)行研究，Sarukkai[21]于2000年首次在萬維網(wǎng)中應(yīng)用馬爾科夫鏈進(jìn)行鏈路預(yù)測(cè)和路徑分析。之后Liben和Kleinberg[22]于2003年首次研究了社會(huì)合作網(wǎng)絡(luò)中的鏈路預(yù)測(cè)。鏈路預(yù)測(cè)可以通過網(wǎng)絡(luò)中的已知信息來預(yù)測(cè)尚未產(chǎn)生連接的概率，也可以被用于識(shí)別和刪除網(wǎng)絡(luò)中的虛假連接，具體預(yù)測(cè)任務(wù)見圖1-2。圖1-2鏈路預(yù)測(cè)的預(yù)測(cè)任務(wù)根據(jù)研究方式的不同，鏈路預(yù)測(cè)可以大致分為基于結(jié)構(gòu)相似性的算法、基于似然分析的算法以及基于機(jī)器學(xué)習(xí)的算法，其中基于結(jié)構(gòu)相似性的算法又分為基于局部信息的相似性指標(biāo)、基于路徑的相似性指標(biāo)、基于隨機(jī)游走的相似性指標(biāo)以及其他相似算法。基于似然分析的算法，有層次結(jié)構(gòu)模型（HierachicalStructureModel，HSM）、隨機(jī)分塊模型（StochasticBlockModel，SBM）以及閉路模型等。Clauset[23]等人提出層次結(jié)構(gòu)模型，利用分層的網(wǎng)絡(luò)結(jié)構(gòu)信息進(jìn)行鏈路預(yù)測(cè)；Dorelan[24]等人提出隨機(jī)分塊模型，在多個(gè)網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)，提高了預(yù)測(cè)準(zhǔn)確度；潘黎明[25]等人提出閉路模型，使得預(yù)測(cè)準(zhǔn)確度更高。以上算法雖然預(yù)測(cè)準(zhǔn)確度較高，但是當(dāng)網(wǎng)絡(luò)規(guī)模過大時(shí)，其計(jì)算量會(huì)大幅增加，導(dǎo)致無法在大規(guī)模網(wǎng)絡(luò)上使用。機(jī)器學(xué)習(xí)分為有監(jiān)督、無監(jiān)督以及半監(jiān)督學(xué)習(xí)，其中基于結(jié)構(gòu)相似性和似然分析的鏈路預(yù)測(cè)算法都是利用結(jié)構(gòu)信息，它們都屬于無監(jiān)督學(xué)習(xí)的范圍。陳可佳[26]等人在鏈路預(yù)測(cè)中引入半監(jiān)督學(xué)習(xí)，利用網(wǎng)絡(luò)中未連接節(jié)點(diǎn)對(duì)的潛在信息去進(jìn)行預(yù)測(cè)，最后在不同規(guī)模數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證。基于有監(jiān)督學(xué)習(xí)的算

第1章緒論7圖1-3本文算法的整體流程圖（1）學(xué)習(xí)有關(guān)技術(shù)、收集相關(guān)文獻(xiàn)，了解差分進(jìn)化、模塊度、模塊密度、社區(qū)結(jié)構(gòu)信息和節(jié)點(diǎn)相似性等相關(guān)概念，對(duì)社區(qū)發(fā)現(xiàn)算法、鏈路預(yù)測(cè)算法及其應(yīng)用進(jìn)行了詳細(xì)的研究，總結(jié)國(guó)內(nèi)外的相關(guān)研究情況，對(duì)現(xiàn)有算法的貢獻(xiàn)與不足進(jìn)行總結(jié)。（2）針對(duì)模塊度分辨率受限和傳統(tǒng)差分進(jìn)化準(zhǔn)確性與收斂速度方面的問題，將差分進(jìn)化和模塊密度思想引入社區(qū)發(fā)現(xiàn)中，提出結(jié)合改進(jìn)差分進(jìn)化和模塊密度的社區(qū)發(fā)現(xiàn)算法(ImprovedDifferentialEvolutionandModularityDensityCommunityDetection，IMDECD)。首先對(duì)差分進(jìn)化進(jìn)行變異策略改進(jìn)和動(dòng)態(tài)自適應(yīng)參數(shù)調(diào)整，提出改進(jìn)的差分進(jìn)化策略(ImprovedDifferentialEvolution，IMDE)，再將模塊密度作為適應(yīng)度函數(shù)以克服模塊度分辨率限制；然后在改進(jìn)差分進(jìn)化結(jié)合社區(qū)發(fā)現(xiàn)的過程中，進(jìn)行基于社區(qū)結(jié)構(gòu)的修改，以提高種群中的個(gè)體質(zhì)量，加快全局收斂速度；最后，在計(jì)算機(jī)生成網(wǎng)絡(luò)數(shù)據(jù)集及5個(gè)具有代表性的真實(shí)世界網(wǎng)絡(luò)數(shù)據(jù)集上，與多個(gè)應(yīng)用較為廣泛的社區(qū)發(fā)現(xiàn)算法進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明本文所提算法具有更高的準(zhǔn)確性和更優(yōu)的收斂性能。（3）針對(duì)現(xiàn)有的鏈路預(yù)測(cè)算法在大規(guī)模網(wǎng)絡(luò)耗時(shí)較長(zhǎng)或者預(yù)測(cè)結(jié)果不準(zhǔn)確的問題，利用社區(qū)劃分后社區(qū)結(jié)果中的結(jié)構(gòu)信息，融合節(jié)點(diǎn)相似性，提出融合社區(qū)結(jié)構(gòu)信息和節(jié)點(diǎn)信息的鏈路預(yù)測(cè)算法（LinkPredictionAlgorithmIntegratedwithCommunityStructureInformationandNodeInformation，LPCN）。首先基于模塊密度以及劃分后的社區(qū)結(jié)構(gòu)，定義一種在不同分辨率下的社區(qū)相似性指標(biāo)；然后考慮網(wǎng)絡(luò)中的節(jié)點(diǎn)信息，將RA指標(biāo)進(jìn)行改進(jìn)，基于考慮增強(qiáng)大度節(jié)點(diǎn)的重要性的RAm指標(biāo)計(jì)算節(jié)點(diǎn)相似性指標(biāo)，再將二者融合得到融合相似性指標(biāo)；最后在多個(gè)真實(shí)世界網(wǎng)絡(luò)數(shù)據(jù)集上，與現(xiàn)有


本文編號(hào)：3350775