信息網絡中的相似度搜索問題研究.pdf

1、現(xiàn)實生活中存在各種類型的實體，實體之間的相互聯(lián)系共同構成了大規(guī)模的、互聯(lián)的、復雜的交互網絡，這些網絡被統(tǒng)稱為信息網絡。信息網絡實體之間的鏈接關系蘊涵著豐富的語義信息，分析這些信息有助于發(fā)現(xiàn)更多有價值的潛在知識。隨著信息網絡逐漸呈現(xiàn)大規(guī)?；蛷碗s化，設計開發(fā)一種有效的軟件程序去探索網絡潛在數(shù)據(jù)結構顯得更加必要。
　　信息網絡方面的研究工作涉及到很多領域，如聚類、社區(qū)挖掘、離群點檢測、相似度搜索等。相似度搜索作為信息網絡研究中的一個重

2、要方向，在近年已經受到了廣泛關注。對于給定的查詢實體，相似度搜索的主要任務是研究如何從信息網絡中找到top-k個最相似的實體。相似度搜索問題研究對于很多實際應用具有現(xiàn)實意義，如推薦系統(tǒng)、鏈接關系預測、近似查詢等。傳統(tǒng)相似度搜索方法依據(jù)網絡全局信息計算實體相似度，需要很高的時間開銷和存儲開銷，不適用于大規(guī)模信息網絡，如SimRank、PSimRank、P-Rank等。
　　具有X-Star模式的信息網絡（簡稱X-Star網絡）是一種

3、重要類型的信息網絡，在現(xiàn)實生活中越來越普遍。X-Star網絡包括中心實體和屬性實體，實體之間的鏈接關系包括中心實體之間的鏈接關系、中心實體與屬性實體之間的鏈接關系。本文圍繞X-Star網絡中的相似度搜索問題展開研究。X-Star網絡中的相似度搜索問題研究的主要任務是根據(jù)指定的查詢（中心實體）找到top-k個最相似的中心實體。在X-Star網絡中，相似的中心實體通常指向相似的屬性實體或被相似的屬性實體指向?；谶@種直觀意義，本文提出一種X

4、-Star網絡中的相似度搜索方案，針對相似度計算的效率和存儲、在線查詢處理的執(zhí)行效率、相似度計算的精確度等幾個方面存在的問題展開研究。本文主要研究工作概括如下:
　　1.針對相似度計算的效率和存儲問題，提出一種X-Star網絡中的相似度計算模型(NetSim)，解決了現(xiàn)有相似度計算模型中存在的計算效率低、存儲開銷大等問題。首先依據(jù)網絡全局結構信息構建屬性實體之間的鏈接關系，提出了屬性網絡構建算法。在屬性網絡基礎上，通過借鑒SimR

5、ank基本思想計算屬性實體相似度。結合屬性實體相似度，提出了NetSim相似度計算模型，NetSim依據(jù)屬性實體相似度計算中心實體相似度。在計算中心實體相似度時不需要物化所有網絡實體之間的相似度，顯著降低了相似度計算的時間開銷和存儲開銷。在DBLP和Amazon兩個數(shù)據(jù)集上做了大量的實驗。實驗結果顯示，NetSim計算模型的時間開銷和存儲開銷顯著低于現(xiàn)有方法，并且具有很好的計算效果。
　　2.針對在線查詢處理的執(zhí)行效率問題，提出一

6、種X-Star網絡中的top-k相似度搜索方法，顯著降低在線查詢處理的執(zhí)行時間。首先提出了基于NetSim的在線查詢處理基本算法(NetSim-baseline)，分析了NetSim-baseline算法的時間復雜度，指出影響NetSim-baseline算法時間開銷的主要因素。結合分析，提出了剪枝索引(Pruning-index)，給出了剪枝索引構建算法?；诩糁λ饕岢鲋行膶嶓w相似度近似計算公式，并提出一種基于NetSim的在線查詢

7、處理剪枝算法(NetSim-pruning)。對NetSim-pruning算法的相關性質進行了大量理論分析和證明，指出了NetSim-pruning精確度損失的理論上界。NetSim-pruning在保證精確度的前提下，顯著降低了在線查詢處理的時間開銷。在DBLP和Amazon數(shù)據(jù)集上的實驗結果顯示，NetSim-pruning算法的時間開銷低，并且具有很好的查詢效果。
　　3.針對相似度計算的精確度問題，提出了一種信息網絡中的

8、相似度計算模型(E-Rank)。E-Rank計算模型的直觀意義是:如果從兩個實體出發(fā)能夠到達共同的實體，那么這兩個實體是相似的。E-Rank考慮了實體之間任意距離的相遇情況，同時強調了鏈接關系重要性，克服了現(xiàn)有方法存在的結構信息利用不充分和鏈接關系重要性考慮不足等問題。在Enron郵件網絡和高能物理理論引文網絡兩個數(shù)據(jù)集上做了大量實驗。實驗結果顯示，與現(xiàn)有相似度計算方法相比，E-Rank具有較高的精確度。結合E-Rank與NetSim，