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

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

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

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

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

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

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

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

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