異構(gòu)信息網(wǎng)查詢和分析研究.pdf

1、信息網(wǎng)絡(luò)表示現(xiàn)實(shí)世界中實(shí)體以及實(shí)體之間的聯(lián)系。隨著科技的進(jìn)步和互聯(lián)網(wǎng)的普及，信息網(wǎng)絡(luò)應(yīng)用廣泛，如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等。信息網(wǎng)絡(luò)可以用圖數(shù)據(jù)模型進(jìn)行建模，包含頂點(diǎn)和邊兩個(gè)元素，其中頂點(diǎn)對(duì)應(yīng)現(xiàn)實(shí)世界中的實(shí)體對(duì)象，邊對(duì)應(yīng)實(shí)體之間的聯(lián)系。按照信息網(wǎng)絡(luò)中頂點(diǎn)和關(guān)系的類型的數(shù)量，信息網(wǎng)絡(luò)被劃分為兩類：同構(gòu)信息網(wǎng)和異構(gòu)信息網(wǎng)。同構(gòu)信息網(wǎng)中頂點(diǎn)和邊的類型都只有一種，如朋友網(wǎng)、作者合作網(wǎng)等。異構(gòu)信息網(wǎng)包含多種類型的頂點(diǎn)和邊。大多數(shù)真實(shí)世界的信息

2、網(wǎng)絡(luò)都是異構(gòu)的，如知識(shí)圖譜、社交網(wǎng)絡(luò)、物聯(lián)網(wǎng)等。異構(gòu)信息網(wǎng)絡(luò)強(qiáng)大的表達(dá)能力使其蘊(yùn)含大量有價(jià)值的信息，使異構(gòu)信息網(wǎng)絡(luò)查詢和分析研究具有重要的現(xiàn)實(shí)意義。本文運(yùn)用算法學(xué)、數(shù)據(jù)分析和計(jì)算復(fù)雜性的相關(guān)技術(shù)，結(jié)合異構(gòu)信息網(wǎng)信息豐富和結(jié)構(gòu)復(fù)雜的特點(diǎn)，對(duì)異構(gòu)信息網(wǎng)絡(luò)查詢和分析問題進(jìn)行深入研究，主要研究成果概括如下：
　　1.本文研究了異構(gòu)信息網(wǎng)上可達(dá)性查詢問題?？蛇_(dá)性查詢是查詢兩個(gè)頂點(diǎn)之間是否存在路徑連接，是信息網(wǎng)絡(luò)中的基本查詢。研究?jī)蓚€(gè)頂點(diǎn)的關(guān)

3、系時(shí)，首先考慮的查詢也是兩點(diǎn)的可達(dá)性。然而，信息網(wǎng)絡(luò)上的可達(dá)性查詢不涉及頂點(diǎn)的類型和邊的類型，且都是建立在有向無環(huán)圖的基礎(chǔ)上。在異構(gòu)信息網(wǎng)中環(huán)路是經(jīng)常存在的，把異構(gòu)信息網(wǎng)中強(qiáng)連通組件壓縮成一個(gè)頂點(diǎn)會(huì)丟失不同類型頂點(diǎn)之間的路徑信息，現(xiàn)有的信息網(wǎng)絡(luò)上可達(dá)性研究都無法解決異構(gòu)信息網(wǎng)上基于不同關(guān)系的可達(dá)性查詢。本文形式化的定義了異構(gòu)信息網(wǎng)上可達(dá)性查詢問題，并證明該問題的時(shí)間復(fù)雜性是PTIME的。隨著網(wǎng)絡(luò)規(guī)模的爆炸式增長(zhǎng)，每個(gè)查詢都需要遍歷一遍網(wǎng)

4、絡(luò)的時(shí)間開銷是不能容忍的。因此，本文提出MP索引結(jié)構(gòu)用于快速響應(yīng)查詢。通過將網(wǎng)絡(luò)的元路徑按照長(zhǎng)度進(jìn)行分層，構(gòu)建元路徑的偏序圖。在偏序圖上選擇一部分元路徑，并預(yù)計(jì)算元路徑上頂點(diǎn)的可達(dá)信息，使多個(gè)查詢可以共享相同元路徑中頂點(diǎn)可達(dá)信息。在真實(shí)和人工數(shù)據(jù)集上實(shí)驗(yàn)驗(yàn)證了本文算法可以快速響應(yīng)查詢。
　　2.本文研究了異構(gòu)信息網(wǎng)上聚集算法。聚集操作允許用戶從特定的維度上觀察數(shù)據(jù)的視圖，是多維分析的基礎(chǔ)。然而，信息網(wǎng)絡(luò)上的聚集操作只基于同構(gòu)信息網(wǎng)

5、上頂點(diǎn)的屬性維度，與頂點(diǎn)的類型、邊的類型、以及網(wǎng)絡(luò)的結(jié)構(gòu)無關(guān)。異構(gòu)信息網(wǎng)不僅包含多種類型的頂點(diǎn)，還包含多種類型的關(guān)系，聚集的維度不應(yīng)該僅限于頂點(diǎn)的屬性，而忽略豐富的結(jié)構(gòu)信息。因此信息網(wǎng)絡(luò)上現(xiàn)有的聚集工作無法用于異構(gòu)信息網(wǎng)。本文提出了基于多種類型頂點(diǎn)和多種類型邊的聚集操作，聚集的維度包括：頂點(diǎn)的類型、頂點(diǎn)的屬性和邊的類型。定義了異構(gòu)信息網(wǎng)上基于圖熵的度量函數(shù)，該函數(shù)能夠很好的刻畫異構(gòu)信息網(wǎng)中頂點(diǎn)在不同關(guān)系上的相似度。本文證明了異構(gòu)信息網(wǎng)上

6、的聚集問題是NP難的，并提出了線性時(shí)間和空間的高效近似聚集算法。聚集算法包括兩個(gè)過程：信息維聚集和結(jié)構(gòu)維聚集。本文進(jìn)一步證明了算法的近似比。最后在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果顯示異構(gòu)信息網(wǎng)上的聚集算法能夠在特定的維度上對(duì)異構(gòu)信息網(wǎng)進(jìn)行深入的分析，并具有較好的可擴(kuò)展性。
　　3.本文研究了異構(gòu)信息網(wǎng)上立方體計(jì)算問題。立方體計(jì)算允許用戶從不同的維度觀察數(shù)據(jù)對(duì)象的概括，是多維數(shù)據(jù)分析的核心。由于信息網(wǎng)絡(luò)上聚集操作的維度定義的局限制，也導(dǎo)致其立

7、方體物化技術(shù)只基于頂點(diǎn)的屬性維度，通過屬性子集合之間的包含關(guān)系，選擇部分立方體進(jìn)行物化。異構(gòu)信息網(wǎng)上維度概念的復(fù)雜化，使得傳統(tǒng)立方體物化技術(shù)并不適用于異構(gòu)信息網(wǎng)。本文提出了異構(gòu)信息網(wǎng)上立方體概念，從多個(gè)維度分析網(wǎng)絡(luò)：頂點(diǎn)屬性、頂點(diǎn)類型和元路徑。本文研究了異構(gòu)信息網(wǎng)上的部分立方體物化問題，證明了該問題是NP難的。為了解決部分立方體物化問題，本文提出了異構(gòu)信息網(wǎng)上聚集圖之間兩種依賴關(guān)系：屬性依賴和路徑依賴，利用這兩種依賴關(guān)系建立代價(jià)模型和構(gòu)

8、建方體格。本文為解決部分立方體物化問題提出了貪心算法，證明了該算法的近似比。在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果顯示異構(gòu)信息網(wǎng)立方體可以從多個(gè)維度上對(duì)網(wǎng)絡(luò)進(jìn)行有效的分析，部分立方體物化算法可以提高查詢效率。
　　4.本文研究了異構(gòu)信息網(wǎng)上近似冰山立方體問題。冰山立方體問題是計(jì)算聚集值大于閾值的立方體，是多維數(shù)據(jù)分析中的重要操作。然而，現(xiàn)有信息網(wǎng)絡(luò)上冰山立方體也是基于同構(gòu)信息網(wǎng)中頂點(diǎn)的屬性維度。顯然，這并不適用于異構(gòu)信息網(wǎng)。對(duì)于具有多種類型頂點(diǎn)

9、和邊的異構(gòu)信息網(wǎng)來說，冰山立方體需要涉及頂點(diǎn)的屬性維度、類型維度，以及結(jié)構(gòu)維度，聚集函數(shù)也更加復(fù)雜。因此，需要一種新的冰山立方體定義，刻畫異構(gòu)信息網(wǎng)復(fù)雜的語義和結(jié)構(gòu)。本文形式化的定義了異構(gòu)信息網(wǎng)上冰山立方體，證明了該問題是NP難的。為了快速求解問題，本文設(shè)計(jì)了基于隨機(jī)游走的近似算法，并證明了基于隨機(jī)游走計(jì)算頂點(diǎn)相似性的相對(duì)誤差界。本文設(shè)計(jì)了兩種剪枝策略。當(dāng)聚集函數(shù)滿足單調(diào)性時(shí)，可以提前結(jié)束方體計(jì)算或直接對(duì)方體進(jìn)行剪枝。在真實(shí)和人工數(shù)據(jù)集