現(xiàn)實世界中許多系統(tǒng)都以網(wǎng)絡的形式存在,例如社會關(guān)系網(wǎng)絡、科學家合作網(wǎng)絡、因特網(wǎng)絡和蛋白質(zhì)交互網(wǎng)絡等。這些網(wǎng)絡具有很高的復雜性,被稱為復雜網(wǎng)絡。近年來,對復雜網(wǎng)絡的結(jié)構(gòu)和特性已給予充分研究,然而對網(wǎng)絡信息的識別和恢復仍然是現(xiàn)代信息科學領域一項長期的挑戰(zhàn),具有重要的理論和現(xiàn)實意義。鏈路預測是解決上述問題的一個重要方向,在計算機、物理、生物等許多領域已有較為深入的研究。鏈路預測是指通過已知的節(jié)點以及網(wǎng)絡結(jié)構(gòu)等信息預測網(wǎng)絡中尚未產(chǎn)生連邊的兩個節(jié)點之間出現(xiàn)鏈接的可能性。使用鏈路預測能夠很好的恢復網(wǎng)絡的拓撲結(jié)構(gòu),揭示網(wǎng)絡的演化行為。與鏈路預測相對應的是丟失節(jié)點識別,丟失節(jié)點識別是指利用已知的網(wǎng)絡信息識別未知的網(wǎng)絡節(jié)點并恢復網(wǎng)絡的拓撲結(jié)構(gòu)。與鏈路預測一樣,丟失節(jié)點識別對于網(wǎng)絡信息的識別和恢復具有重要意義。本文針對復雜網(wǎng)絡中的丟失節(jié)點識別問題進行研究。解決丟失節(jié)點識別問題一般情況下需要進行條件約束,增加已知信息,然后予以解決。占位符框架和模糊點框架是解決丟失節(jié)點識別問題的兩個框架,本文在這兩種不同的丟失節(jié)點識別框架下分別設計了相應的丟失節(jié)點識別算法。在占位符框架下,設計了基于圖嵌入的丟失節(jié)點識別算法G... 

【文章來源】：蘭州大學甘肅省 211工程院校 985工程院校 教育部直屬院校

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

【學位級別】：碩士

【圖文】：

完整網(wǎng)絡H[8]

蘭州大學碩士學位論文復雜網(wǎng)絡中丟失節(jié)點識別算法研究圖2-2克羅內(nèi)克圖模型[8]M步直到最后收斂求出Z，即目標未知網(wǎng)絡。雖然KronEM算法能夠在已知網(wǎng)絡信息很少的情況下推斷出剩余未知的網(wǎng)絡結(jié)構(gòu)，但由于該方法是基于克羅內(nèi)克構(gòu)圖的方法，使得該方法過于依賴具體網(wǎng)絡性質(zhì)，如果網(wǎng)絡自相似性質(zhì)明顯，則效果好，如果網(wǎng)絡自相似性質(zhì)不明顯，則效果欠佳。2.2聚類2.2.1k-meansk-means聚類算法是一種應用廣泛的聚類算法[18]。k-means算法首先隨機選擇k個數(shù)據(jù)點作為k個初始的簇中心，然后計算每個數(shù)據(jù)點與各個簇中心之間的距離，把每個數(shù)據(jù)點分配到距離這個數(shù)據(jù)點最近的簇中心，簇中心和分配的數(shù)據(jù)點構(gòu)成了一個聚類。根據(jù)現(xiàn)有的聚類，重新計算每個聚類的聚類中心，再將所有樣本點重新分類，不斷迭代上述過程直到?jīng)]有數(shù)據(jù)點被重新分配給不同的聚類、聚類中心不再發(fā)生變化或者達到迭代次數(shù)。k-means算法計算效率高，使用范圍廣泛，但是因為初始的聚類中心是隨機選擇的，初始聚類中心的選擇對聚類結(jié)果影響較大。2.2.2聚類層次聚類分成自底向上的凝聚方法和自頂向下的分裂方法[28]。凝聚法初始將毎個節(jié)點視作一個小簇，通過合并相似的簇實現(xiàn)聚類。分裂法初始將所有節(jié)點視作同一個大簇，不斷分裂成更小的簇。層次聚類算法并不是直接給出聚類的結(jié)果，而是每聚類一個階段產(chǎn)生一個聚類結(jié)果。比如凝聚法，初始將每個節(jié)點作為一個簇，然后每次迭代計算選取距離最近的兩個簇，并將它們合并，直到只有一個簇為止。8

完整網(wǎng)絡


本文編號：3255605