信息網(wǎng)絡(luò)中的相似度搜索問題研究.pdf

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

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

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

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

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

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

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

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