隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展,鏈路預(yù)測作為研究復(fù)雜網(wǎng)絡(luò)的重要手段之一,具有重要的理論和現(xiàn)實意義。近年來,該方向的研究成果層出不窮,然而現(xiàn)有算法在充分提取網(wǎng)絡(luò)信息方面仍存在不足,不能準(zhǔn)確且高效地預(yù)測缺失鏈路。為了解決以上問題,本文首先利用社區(qū)發(fā)現(xiàn)算法提取復(fù)雜網(wǎng)絡(luò)中的結(jié)構(gòu)信息,再與節(jié)點信息進(jìn)行融合,充分利用復(fù)雜網(wǎng)絡(luò)中的信息,提出一種融合社區(qū)結(jié)構(gòu)信息和節(jié)點信息的鏈路預(yù)測算法。內(nèi)容概述如下:一、針對模塊度分辨率受限和傳統(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)行修正操作,以提高種群中的個體質(zhì)量,加快全局收斂速度。二、針對現(xiàn)有的鏈路預(yù)測算法在大規(guī)模網(wǎng)絡(luò)耗時較長或者預(yù)測結(jié)果不準(zhǔn)確的問題,利用社區(qū)結(jié)構(gòu)中的結(jié)構(gòu)信息,融合節(jié)點相似性,提出融合社區(qū)結(jié)構(gòu)信息和節(jié)點信息的鏈路預(yù)測算法（Link Predictio... 

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

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

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

【部分圖文】：

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

第1章緒論5鏈路預(yù)測早期主要基于馬爾科夫鏈和機器學(xué)習(xí)來進(jìn)行研究，Sarukkai[21]于2000年首次在萬維網(wǎng)中應(yīng)用馬爾科夫鏈進(jìn)行鏈路預(yù)測和路徑分析。之后Liben和Kleinberg[22]于2003年首次研究了社會合作網(wǎng)絡(luò)中的鏈路預(yù)測。鏈路預(yù)測可以通過網(wǎng)絡(luò)中的已知信息來預(yù)測尚未產(chǎn)生連接的概率，也可以被用于識別和刪除網(wǎng)絡(luò)中的虛假連接，具體預(yù)測任務(wù)見圖1-2。圖1-2鏈路預(yù)測的預(yù)測任務(wù)根據(jù)研究方式的不同，鏈路預(yù)測可以大致分為基于結(jié)構(gòu)相似性的算法、基于似然分析的算法以及基于機器學(xué)習(xí)的算法，其中基于結(jié)構(gòu)相似性的算法又分為基于局部信息的相似性指標(biāo)、基于路徑的相似性指標(biāo)、基于隨機游走的相似性指標(biāo)以及其他相似算法�；谒迫环治龅乃惴ǎ袑哟谓Y(jié)構(gòu)模型（HierachicalStructureModel，HSM）、隨機分塊模型（StochasticBlockModel，SBM）以及閉路模型等。Clauset[23]等人提出層次結(jié)構(gòu)模型，利用分層的網(wǎng)絡(luò)結(jié)構(gòu)信息進(jìn)行鏈路預(yù)測；Dorelan[24]等人提出隨機分塊模型，在多個網(wǎng)絡(luò)上進(jìn)行實驗，提高了預(yù)測準(zhǔn)確度；潘黎明[25]等人提出閉路模型，使得預(yù)測準(zhǔn)確度更高。以上算法雖然預(yù)測準(zhǔn)確度較高，但是當(dāng)網(wǎng)絡(luò)規(guī)模過大時，其計算量會大幅增加，導(dǎo)致無法在大規(guī)模網(wǎng)絡(luò)上使用。機器學(xué)習(xí)分為有監(jiān)督、無監(jiān)督以及半監(jiān)督學(xué)習(xí)，其中基于結(jié)構(gòu)相似性和似然分析的鏈路預(yù)測算法都是利用結(jié)構(gòu)信息，它們都屬于無監(jiān)督學(xué)習(xí)的范圍。陳可佳[26]等人在鏈路預(yù)測中引入半監(jiān)督學(xué)習(xí)，利用網(wǎng)絡(luò)中未連接節(jié)點對的潛在信息去進(jìn)行預(yù)測，最后在不同規(guī)模數(shù)據(jù)集上進(jì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é)點相似性等相關(guān)概念，對社區(qū)發(fā)現(xiàn)算法、鏈路預(yù)測算法及其應(yīng)用進(jìn)行了詳細(xì)的研究，總結(jié)國內(nèi)外的相關(guān)研究情況，對現(xiàn)有算法的貢獻(xiàn)與不足進(jìn)行總結(jié)。（2）針對模塊度分辨率受限和傳統(tǒng)差分進(jìn)化準(zhǔn)確性與收斂速度方面的問題，將差分進(jìn)化和模塊密度思想引入社區(qū)發(fā)現(xiàn)中，提出結(jié)合改進(jìn)差分進(jìn)化和模塊密度的社區(qū)發(fā)現(xiàn)算法(ImprovedDifferentialEvolutionandModularityDensityCommunityDetection，IMDECD)。首先對差分進(jìn)化進(jìn)行變異策略改進(jìn)和動態(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)的修改，以提高種群中的個體質(zhì)量，加快全局收斂速度；最后，在計算機生成網(wǎng)絡(luò)數(shù)據(jù)集及5個具有代表性的真實世界網(wǎng)絡(luò)數(shù)據(jù)集上，與多個應(yīng)用較為廣泛的社區(qū)發(fā)現(xiàn)算法進(jìn)行對比實驗。實驗結(jié)果表明本文所提算法具有更高的準(zhǔn)確性和更優(yōu)的收斂性能。（3）針對現(xiàn)有的鏈路預(yù)測算法在大規(guī)模網(wǎng)絡(luò)耗時較長或者預(yù)測結(jié)果不準(zhǔn)確的問題，利用社區(qū)劃分后社區(qū)結(jié)果中的結(jié)構(gòu)信息，融合節(jié)點相似性，提出融合社區(qū)結(jié)構(gòu)信息和節(jié)點信息的鏈路預(yù)測算法（LinkPredictionAlgorithmIntegratedwithCommunityStructureInformationandNodeInformation，LPCN）。首先基于模塊密度以及劃分后的社區(qū)結(jié)構(gòu)，定義一種在不同分辨率下的社區(qū)相似性指標(biāo)；然后考慮網(wǎng)絡(luò)中的節(jié)點信息，將RA指標(biāo)進(jìn)行改進(jìn)，基于考慮增強大度節(jié)點的重要性的RAm指標(biāo)計算節(jié)點相似性指標(biāo)，再將二者融合得到融合相似性指標(biāo)；最后在多個真實世界網(wǎng)絡(luò)數(shù)據(jù)集上，與現(xiàn)有


本文編號：3350775