普適的結(jié)構(gòu)相似度在大規(guī)模網(wǎng)絡中的計算優(yōu)化技術研究.pdf

1、對象間的相似度計算是當前數(shù)據(jù)挖掘領域的重要研究課題之一。近年來，在Google網(wǎng)頁排名算法PageRank的推動下，基于網(wǎng)頁鏈接分析的普適相似度模型研究熱潮席卷全球，以SimRank、SimFusion、Penetrating-Rank(以下簡稱P-Rank)為代表的新相似度模型相繼問世，成為目前國內(nèi)外共同關注的熱點問題。隨著Internet網(wǎng)絡規(guī)模的日異膨脹與應用需求的不斷提高，這些新出現(xiàn)的相似度模型理論已端倪漸顯，但尚有一系列科學技

2、術難題亟待解決，主要包括算法的時空復雜度優(yōu)化、誤差與穩(wěn)定性分析、規(guī)?？蓴U性問題等。針對這類相似度模型的核心理論與算法優(yōu)化問題進行研究，可為網(wǎng)頁排名、協(xié)同過濾、搜索引擎優(yōu)化、網(wǎng)絡圖聚類等提供堅實的理論和技術基礎，具有重要的科研和應用價值。
　　 本文針對三種基于鏈接的新相似度模型(即SimRank、SimFusion、P(-)Rank)，旨在深入研究這些相似度計算的優(yōu)化問題，其中包括:相似度解的精度控制、加快迭代的收斂速度、降低計

3、算時間與內(nèi)存空間的代價、實現(xiàn)并行計算與增量算法等。結(jié)合這三種模型遞歸定義的特點，本文重點對相似度高效計算的關鍵技術進行研究，通過矩陣優(yōu)化等途徑，在可控精度下提高相似度算法性能并降低其代價開銷。此外，本文還對這些相似度模型進行改進，研究并實現(xiàn)了具有可控精度、高穩(wěn)定性、低時空復雜度特點的結(jié)構(gòu)相似度改進算法。主要研究成果如下:
　　 1)提出了SimRank相似度計算的優(yōu)化方法。利用矩陣形式表示SimRank方程，設計出一種新的Sim

4、Rank迭代范式，可以指數(shù)級加快SimRank解的收斂速度。通過建立低維的Krylov子空間，把原SimRank方程（n×n維）投影到這個低維子空間（r×r維）計算，從而使計算時問由原來的O（Knm）降為O(rm+r2n+Kr3)，內(nèi)存空間由O(n2)降為O（rn），其中n，m是圖的總結(jié)點數(shù)和邊數(shù)，r（＜＜n)是鄰接矩陣的秩，K是總迭代次數(shù)。為進一步降低SimRank時間復雜度，對無向圖的SimRank進行優(yōu)化，借助鄰接矩陣的特征向量分

5、解，將計算時問再降到O(rm+Kr2)，同時實現(xiàn)無向圖的SimRank并行算法。
　　 2)改進了SimFusion模型并優(yōu)化其相似度算法。針對原SimFusion模型中存在的兩個問題——同構(gòu)網(wǎng)絡中的發(fā)散解、異構(gòu)網(wǎng)絡的平凡解，提出一種改進的SimFusion模型（下稱SimFusion+），通過引入一致鄰接矩陣(UAM)和“推遲行歸一化”操作，確保SimFusion+方程解的存在唯一性。為解決SimFusion+計算的優(yōu)化問題，

6、利用UAM矩陣的主特征向量表示SimFusion+相似度，把計算時間從原先的O(Kn3)降為O(n2），內(nèi)存空間由O(n2)降到0（n）。還探索了SimFusion+的近似算法與增量算法，分別適用于大型與動態(tài)網(wǎng)絡圖上的相似度計算，解決了SimFusion+算法的規(guī)?？蓴U性問題。
　　 3)優(yōu)化了P-Rank模型的計算。通過矩陣形式給出P-Rank相似度的兩種表現(xiàn)形式——逆矩陣式、冪級數(shù)式?；赑-Rank逆矩陣式，利用轉(zhuǎn)移矩陣的

7、奇異值分解，提出一種新的P-Rank確定性算法，把計算時間由原來的O(Kn4)降為O(v4n2+v2n)，同時給出誤差估計，其中v(＜＜n)是一個時間與精度權衡參數(shù)。基于P-Rank冪級數(shù)式，結(jié)合MonteCarlo法，提出一種規(guī)模可擴的P-Rank隨機算法，把計算時間進一步降到O(Nn)，其中N是樣本大小。還通過定義P-Rank條件數(shù)并估計其上界，研究P-Rank相似度的穩(wěn)定性。在無向圖中，利用矩陣對角變換，提出一種P-Rank非迭代

8、算法，把時間再降為O(vn2)。
　　 在人工與實際數(shù)據(jù)集上的實驗結(jié)果表明，基于鏈接結(jié)構(gòu)的三種相似度模型經(jīng)算法優(yōu)化與模型改進后，具有時空復雜度低、穩(wěn)定性強、規(guī)模可擴、精度可控等特點，其計算性能比原先的算法提高若干數(shù)量級，這些模型在大規(guī)模網(wǎng)絡圖上計算有顯著的加速效果。尤其是提出的并行和增量相似度算法能有效降低代價開銷，改善相似度在多處理器、動態(tài)網(wǎng)絡圖中的計算性能。相關研究成果為結(jié)構(gòu)相似度的計算提供了較好的解決方案和理論分析基礎，可