朱 玉 游進(jìn)國* 付子玉

1(昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院 云南 昆明 650500)2(大連民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 遼寧 大連 116000)

0 引 言

近年來，圖挖掘(Graph Mining)方向作為數(shù)據(jù)挖掘領(lǐng)域中的重要組成部分引起了社會(huì)各界的極大關(guān)注。圖在生物信息學(xué)(蛋白質(zhì)結(jié)構(gòu)分析、基因組織識(shí)別等)、社交網(wǎng)絡(luò)(用戶之間的聯(lián)系等)、Web分析(Web內(nèi)容挖掘、Web連接結(jié)構(gòu)分析、Web日志搜索等)、網(wǎng)絡(luò)計(jì)算等方面有著豐富的應(yīng)用。圖查詢是圖挖掘的一個(gè)重要研究方向。一直以來其中的數(shù)據(jù)查詢問題和方法都受到了人們廣泛的關(guān)注和研究。

在圖數(shù)據(jù)挖掘領(lǐng)域中，傳統(tǒng)圖查詢方法大體上可分為關(guān)鍵字查詢和頻繁子圖挖掘兩大類。其中關(guān)于圖數(shù)據(jù)中的頻繁子圖挖掘可分為如下幾種方法：Apriori-based[1]方法：主要采用Apriori的性質(zhì)，枚舉重復(fù)出現(xiàn)的子圖，其中AGM(Apriori-based Graph Mining)[2]是一種基于圖論的思想，挖掘各種不同類型的子圖；AcGM(Apriori-based connected Graph Mining)[3]方法是原有AGM方法拓展到連通圖上；FSG(Frequent Subgraph)[4]采用多種優(yōu)化規(guī)則的方式使其適用于大數(shù)據(jù)集；path-join[5]算法等。由于使用了Apriori性質(zhì)，在擴(kuò)展邊的過程中，會(huì)產(chǎn)生大量的重復(fù)候選子圖，從而降低了算法的整體效率。FP-growth[6]方法：是一種執(zhí)行效率較高的方法，其中g(shù)Span(graph-based Substructure pattern mining)[7]是一種典型的基于深度優(yōu)先思想查詢頻繁子圖的算法，但是無法避免子圖同構(gòu)的問題，從而算法復(fù)雜度比較高；CloseGraph(A closed graph pattern mining algorithm)[8]用于查詢相同頻率下最大規(guī)模子圖。也有一些其他的頻繁子圖挖掘算法，例如：Zhu等[9]提出了一種基于用戶約束條件的頻繁子圖挖掘算法gPrune；Wang等[10]提出了一種基于索引的頻繁子圖挖掘算法GraphMiner； Karste等[11]提出了適合于動(dòng)態(tài)圖挖掘DynamicGREW算法等。Danai等[12]提出了VoG方法，構(gòu)造一組子圖和一個(gè)高頻子圖類型的詞匯表(例如：星形、團(tuán)和鏈)，根據(jù)詞匯表找出最簡潔的圖描述方式并通過最小描述長度(MDL)原則來衡量描述結(jié)果。本文提出一種MDL-based Random-walk Query Algorithm(MRQ)算法，將圖聚集應(yīng)用到頻繁子圖查詢中，對(duì)原圖和特殊子圖進(jìn)行聚集，解決傳統(tǒng)算法復(fù)雜度高的問題。

為了降低百萬節(jié)點(diǎn)大圖所占用的內(nèi)存，加快執(zhí)行時(shí)間，本文選取ApxGreedy[17]聚集方法對(duì)原圖進(jìn)行聚集。首先將原圖分為有兩個(gè)部分：第一個(gè)部分是聚集圖(遠(yuǎn)小于輸入圖)，得到輸入圖聚集之后超邊和超點(diǎn)的關(guān)系，第二個(gè)部分是一組修正圖，用于重建原始輸入圖。選取此聚集方法具有以下好處：(1) 聚集圖占內(nèi)存較小。應(yīng)用于可視化等圖分析技術(shù)是可行的，因?yàn)?，它提供了?duì)圖的高級(jí)結(jié)構(gòu)的洞察，以及各種點(diǎn)簇之間的主要關(guān)系。(2) 此方法實(shí)現(xiàn)了將大圖高度壓縮。此外，它還支持調(diào)整參數(shù)，可用于實(shí)現(xiàn)有損壓縮。

1 問題引入

如圖1所示，給定一個(gè)簡單無向圖。

圖1 簡單無向原圖

經(jīng)過ApxGreedy聚集算法預(yù)處理之后可以得到一個(gè)如圖2所示的隨機(jī)游走圖。

圖2 聚集圖

語義結(jié)構(gòu)以星形圖為例，星形圖的示例圖和聚集之后的結(jié)構(gòu)如圖3和圖4所示。

圖3 星形圖

圖4 星形圖聚集結(jié)構(gòu)

根據(jù)星形圖聚集后的通用特征進(jìn)行隨機(jī)游走查詢，由于聚集過程中并非能恰好聚集成目的語義結(jié)構(gòu)的隨機(jī)游走圖，所以需要放松隨機(jī)游走時(shí)的查詢條件。本文利用強(qiáng)弱關(guān)聯(lián)來取替嚴(yán)格的隨機(jī)游走查詢跳轉(zhuǎn)概率，在聚集處理后的隨機(jī)游走圖上查詢星形圖的流程如下：

(1) 查找超點(diǎn)間強(qiáng)關(guān)聯(lián)的一個(gè)超點(diǎn)對(duì)；

(2) 一個(gè)超點(diǎn)內(nèi)包含一個(gè)點(diǎn)，一個(gè)超點(diǎn)內(nèi)包含大于等于兩個(gè)點(diǎn)；

(3) 多個(gè)點(diǎn)簇成的超點(diǎn)內(nèi)為弱關(guān)聯(lián)。

在上述整個(gè)過程中采用隨機(jī)游走查詢算法，減少多余的遍歷，提高了查詢效率。

2 算法描述

隨機(jī)游走算法是一個(gè)半監(jiān)督的全局最優(yōu)化算法，旨在減少其遍歷路徑中，被極大極小算法評(píng)估的路徑數(shù)。在查詢算法中優(yōu)化使用隨機(jī)游走思想，用來減少一些不必要的遍歷過程。其中如何通過聚集預(yù)處理結(jié)果生成隨機(jī)游走圖以及在隨機(jī)游走查詢中如何設(shè)定跳轉(zhuǎn)概率是應(yīng)用隨機(jī)游走查詢的核心問題，也就是說，需要構(gòu)建超點(diǎn)之間的相似度并標(biāo)記超邊，從而降低查詢時(shí)間和錯(cuò)誤率。本文利用隨機(jī)游走查詢算法在聚集圖上查詢語義結(jié)構(gòu)，具體算法描述如下：

將目標(biāo)社交網(wǎng)絡(luò)抽象成一個(gè)無向無加權(quán)簡單圖G=(V,E)，其中V是用戶之間相互關(guān)系的集合，E代表每個(gè)用戶。對(duì)此大圖用聚集算法進(jìn)行壓縮，根據(jù)超點(diǎn)之間的相似度標(biāo)記超邊并生成隨機(jī)游走圖，在此基礎(chǔ)上進(jìn)行隨機(jī)游走查詢，最后查詢到的語義結(jié)構(gòu)根據(jù)誤差率排序并輸出結(jié)果。

2.1 ApxGreedy算法聚集處理

用聚集算法預(yù)處理大圖的效果可以直接影響查詢的效果，本文目的在于選取一個(gè)高效、快速的聚集算法。針對(duì)包含百萬結(jié)點(diǎn)的大圖可以快速并低損耗的聚集方法視為可用于查詢預(yù)處理的方法。比較BUS(Bottom Up Algorithm)聚集算法 、GGS(Greedy Graph Summary)和貪婪聚集(Greedy)算法等多種聚集算法，實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，目前ApxGreedy聚集算法效果最優(yōu)。

定義1(聚集圖Gs) 給定一個(gè)簡單無向無加權(quán)圖G=(V,E)，若無向加權(quán)圖Gs表示為原圖的聚集圖，則圖Gs的的公式化表示為Gs=(Vs,Es)，其中，聚集圖Gs中的超點(diǎn)集合用Vs=(vs1,vs2,…,vsk)表示，聚集圖Gs中的超邊Es集合的公式為Es=Vs×Es，則聚集圖Gs和原圖G=(V,E)滿足以下關(guān)系：

(1)Vi∈Vs,Vi?V,Vi≠Φ；

(3)Es={(Vi,Vj)|?u∈Vi,v∈Vj,(u,v∈E)}。

圖聚集是一個(gè)不斷合并頂點(diǎn)及創(chuàng)建超邊的過程。超邊的概率用Pij來表示，其中概率Pij和關(guān)聯(lián)強(qiáng)度相關(guān)，若原圖中頂點(diǎn)內(nèi)或頂點(diǎn)間實(shí)際存在的邊數(shù)越多，即關(guān)聯(lián)強(qiáng)度越高，說明在生成聚集圖時(shí)，超邊存在的概率越高，反之當(dāng)關(guān)聯(lián)強(qiáng)度越低時(shí)，超邊存在的概率越低。

具體的超邊之間存在的概率P的計(jì)算方法定義如下：

超點(diǎn)內(nèi)點(diǎn)全連接之后的邊數(shù)為Γij，實(shí)際存在的邊數(shù)為Eij，則：

定義2(超點(diǎn)之間的概率)

P=Eij/Γij

(1)

2.2 隨機(jī)游走查詢

本文引入隨機(jī)游走的方式進(jìn)行查詢，構(gòu)建隨機(jī)游走模型，包括生成隨機(jī)游走圖和在圖上隨機(jī)游走查詢兩個(gè)部分。

(1) 生成隨機(jī)游走圖：

在聚集預(yù)處理的步驟里根據(jù)兩點(diǎn)之間的關(guān)聯(lián)強(qiáng)度即概率Pij決定是否用邊將兩點(diǎn)相連。為方便求解，將聚集之后的兩點(diǎn)之間的關(guān)聯(lián)強(qiáng)度即概率Pij作為邊的權(quán)重。當(dāng)兩點(diǎn)之間的概率Pij很小或者為0時(shí)，節(jié)點(diǎn)之間的權(quán)重視為零。

定義3(隨機(jī)游走圖中超點(diǎn)之間的距離) 假設(shè)圖G=(V,E)，其中超點(diǎn)個(gè)數(shù)為n。邊權(quán)重使用高斯核函數(shù)計(jì)算，公式為：

(2)

(3)

(2) 隨機(jī)游走查詢:

超圖中的一條超邊包含可能超過兩個(gè)以上的超點(diǎn)，所以對(duì)超圖使用隨機(jī)游走查詢方法。隨機(jī)游走的過程為：選定初始定點(diǎn)u，根據(jù)超邊的權(quán)重W(e)大小的概率成正比的選擇一條包含當(dāng)前定點(diǎn)u的特定超邊e；在已經(jīng)選中的超邊中，根據(jù)頂點(diǎn)權(quán)重大小概率成正比的選擇轉(zhuǎn)移頂點(diǎn)v。設(shè)P為隨機(jī)游走的轉(zhuǎn)移矩陣，其計(jì)算式表示為:

(4)

根據(jù)聚集圖的權(quán)重矩陣P計(jì)算圖G的概率轉(zhuǎn)移矩陣，其計(jì)算式表示為：

(5)

隨機(jī)游走查詢過程使用以下函數(shù)表示：

(6)

2.3 語義結(jié)構(gòu)相關(guān)定義

在社交網(wǎng)絡(luò)中，我們關(guān)注用戶之間的關(guān)系，比如名人與粉絲之間的關(guān)系，互相都關(guān)注的親友團(tuán)體，存在共同粉絲的明星等，由此可以根據(jù)這些重要的關(guān)系來形成值得討論的語義結(jié)構(gòu)。

本文著重討論四種語義結(jié)構(gòu)：星形圖、鏈、團(tuán)、二部圖。

經(jīng)過聚集算法得到聚集圖結(jié)構(gòu)后，可總結(jié)出以下四種語義結(jié)構(gòu)的通用特征的重新的定義：

(1) 星形圖：超點(diǎn)和超點(diǎn)之間是強(qiáng)關(guān)聯(lián)，中心點(diǎn)經(jīng)過聚集之后的超點(diǎn)中只有一個(gè)點(diǎn)，各個(gè)結(jié)點(diǎn)聚合后的超點(diǎn)有至少超過兩個(gè)點(diǎn)，且超點(diǎn)內(nèi)部為弱關(guān)聯(lián)。

(2) 二部圖：聚合在兩個(gè)超點(diǎn)內(nèi)，且每個(gè)超點(diǎn)內(nèi)的點(diǎn)個(gè)數(shù)大于等于2個(gè)，超點(diǎn)內(nèi)部概率為0，超點(diǎn)之間概率為1 。

以上兩個(gè)結(jié)果在聚集之后的通用特征統(tǒng)一，而對(duì)于鏈和團(tuán)針對(duì)點(diǎn)個(gè)數(shù)的增多，聚集效果并不相同，所以利用實(shí)際聚集之后的效果對(duì)鏈和團(tuán)結(jié)構(gòu)的通用特征進(jìn)行總結(jié)。

(3) 鏈：鏈聚集之后還是鏈，但其每個(gè)超點(diǎn)內(nèi)包含的點(diǎn)數(shù)小于等于2個(gè)，且聚集圖對(duì)應(yīng)的鄰接矩陣對(duì)角線的值都為0。

(4) 團(tuán)：本文實(shí)驗(yàn)發(fā)現(xiàn)，點(diǎn)數(shù)n<9時(shí)，團(tuán)會(huì)聚集成一個(gè)新的團(tuán)結(jié)構(gòu)，且聚集圖所對(duì)應(yīng)的鄰接矩陣對(duì)角線不為0；當(dāng)951時(shí)會(huì)聚集在一個(gè)超點(diǎn)內(nèi)，且聚集圖所對(duì)應(yīng)的鄰接矩陣對(duì)角線不為0。

2.4 成本誤差排序

除此之外，本文引入了成本來計(jì)算誤差，并根據(jù)誤差的大小，來對(duì)查詢到的語義結(jié)構(gòu)進(jìn)行排序。

在隨機(jī)聚集(ApxGreedy)算法中，一般而言，用c′v近似表示點(diǎn)v的成本，其中c′v是點(diǎn)v鏈接的邊中所有點(diǎn)的近似最小總成本。之后，將兩個(gè)點(diǎn)u和v合并成一個(gè)新的超點(diǎn)w，其中超點(diǎn)w的成本降低了s′(u,v)，用公式(c′u+c′v-c′w)/(c′u+c′v)表示點(diǎn)u和v合并為超點(diǎn)w后的損失，因此s′(u,v)是點(diǎn)u和v合并后的成本誤差。

在聚集基礎(chǔ)上繼續(xù)討論成本誤差，并根據(jù)此項(xiàng)標(biāo)準(zhǔn)對(duì)查找到的語義結(jié)構(gòu)進(jìn)行排序，相關(guān)定義如下：

引入交叉熵的概念，通常交叉熵可在神經(jīng)網(wǎng)絡(luò)(機(jī)器學(xué)習(xí))中作為損失函數(shù)，真實(shí)標(biāo)記的分布表示為p，訓(xùn)練后的模型的預(yù)測標(biāo)記分布表示為q，p與q的相似性可以用交叉熵?fù)p失函數(shù)來衡量。

標(biāo)準(zhǔn)的交叉熵公式為：

C(p,q)=-qlog(p/q)

式中：由于強(qiáng)關(guān)聯(lián)概率q=1，所以C(p)=-log(p)。

此后，將總的誤差轉(zhuǎn)化為了聚集部分的誤差與查詢部分誤差的和，如下所示：

C=C(u,v)+C(p)

2.5 算法復(fù)雜度

本算法包含三個(gè)步驟：(1) 對(duì)輸入的簡單無向大圖進(jìn)行隨機(jī)聚集處理。(2) 利用各個(gè)語義結(jié)構(gòu)聚集之后的特點(diǎn)進(jìn)行查詢。(3) 根據(jù)MDL誤差排序并輸入。其中，對(duì)輸入的簡單無向大圖進(jìn)行隨機(jī)聚集處理時(shí)間復(fù)雜度為： 在每個(gè)合并步驟中，計(jì)算包含v的所有2Hop(v)對(duì)的成本降低；這總共需要O(3Hop(v))時(shí)間。再次，假設(shè)平均查詢邊數(shù)為dav，這變成O(dav3)。利用隨機(jī)游走進(jìn)行查詢的時(shí)間復(fù)雜度為O(|E|)。

本文是基于隨機(jī)游走的語義結(jié)構(gòu)剪枝查詢算法，先使用聚集預(yù)處理之后再利用隨機(jī)游走的思想進(jìn)行查詢，且查詢部分只與邊有關(guān)系。所以本算法的時(shí)間復(fù)雜度最壞為O(dav3)+O(|E|)。其中|E|為給定社交網(wǎng)絡(luò)的邊數(shù)。

綜上，本算法的時(shí)間復(fù)雜度為O(dav3)+O(|E|)。

2.6 算法流程圖

本算法的流程圖如圖5所示。

圖5 算法流程圖

2.7 算法偽代碼

對(duì)于輸入的簡單無向大圖，本文中先利用隨機(jī)聚集算法進(jìn)行聚集處理，根據(jù)定義生成隨機(jī)游走圖，再利用隨機(jī)游走查詢算法對(duì)語義結(jié)構(gòu)進(jìn)行查詢，最后根據(jù)MDL誤差來進(jìn)行優(yōu)良排序，并輸出查到的最優(yōu)結(jié)構(gòu)所處的超點(diǎn)位置。

算法: MDL-based Random-walk Query Algorithm(MRQ)輸入: 圖G=(V,E)輸出: 輸出查詢到的語義結(jié)構(gòu)1: /?初始化階段?/2: 對(duì)圖G=(V,E)用ApxGreedy算法進(jìn)行聚集處理,存儲(chǔ)聚集圖Gs=(Vs,Es)的超點(diǎn)和超邊3: 通過儲(chǔ)存的超點(diǎn)Es與超邊Vs計(jì)算強(qiáng)弱關(guān)聯(lián)pij4: 通過遍歷聚集之后邊上的強(qiáng)弱關(guān)聯(lián)pij 來隨機(jī)游走查找4種語義結(jié)構(gòu)5: 通過已查詢到的結(jié)構(gòu)計(jì)算其成本損失誤差C6: 根據(jù)成本誤差C對(duì)語義結(jié)構(gòu)進(jìn)行排序并輸出前n個(gè)結(jié)構(gòu)

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)環(huán)境

本文所有實(shí)驗(yàn)都是在一臺(tái)PC機(jī)上運(yùn)行的，PC機(jī)的配置如下：Intel(R) Xeon(R) CPU E51630 v4 ,3.70 GHz，內(nèi)存8 GB，Windows10 操作系統(tǒng)。本文的算法是基于Java語言編程實(shí)現(xiàn)的，其中開發(fā)工具是IntelliJ IDEA。

3.2 實(shí)驗(yàn)環(huán)境

第一組數(shù)據(jù)集是使用來自歐洲大型研究機(jī)構(gòu)的電子郵件數(shù)據(jù)生成的(email-Eu-core network)。如果發(fā)送了至少一封電子郵件，那么網(wǎng)絡(luò)中存在邊緣(u,v)。 電子郵件僅代表機(jī)構(gòu)成員(核心)之間的通信，數(shù)據(jù)集不包含來自世界其他地方的傳入消息或傳出消息。數(shù)據(jù)是以 TXT 格式進(jìn)行加載和使用的。圖中的頂點(diǎn)數(shù)是1 005個(gè)，邊數(shù)是25 571條。

第二組數(shù)據(jù)集是使用來自歐洲大型研究機(jī)構(gòu)的電子郵件數(shù)據(jù)生成的(email-Eu-core network)。如果發(fā)送了至少一封電子郵件，那么網(wǎng)絡(luò)中存在邊(u,v)。 電子郵件僅代表機(jī)構(gòu)成員(核心)之間的通信，數(shù)據(jù)集不包含來自世界其他地方的傳入消息或傳出消息。數(shù)據(jù)是以 TXT 格式進(jìn)行加載和使用的。圖中的頂點(diǎn)數(shù)為1 005個(gè)，邊數(shù)為25 571條。

第三組數(shù)據(jù)集是DBLP計(jì)算機(jī)科學(xué)書目提供了計(jì)算機(jī)科學(xué)研究論文的綜合列表(DBLP collaboration network and ground-truth communities)。如果至少發(fā)表一篇論文，構(gòu)建一個(gè)共同作者網(wǎng)絡(luò)，兩個(gè)作者之間相互關(guān)聯(lián)。作者發(fā)布到某個(gè)期刊或會(huì)議形成一個(gè)社區(qū)。圖中的頂點(diǎn)代表論文，邊代表作者之間存在的合著關(guān)系。數(shù)據(jù)是以 TXT 格式進(jìn)行加載和使用的。圖中的頂點(diǎn)數(shù)為317 080個(gè)，邊數(shù)為 1 049 866 條。

第四組數(shù)據(jù)是利用python代碼生成的已知圖，每個(gè)圖都含有固定數(shù)量的語義結(jié)構(gòu)，其中共構(gòu)造了七個(gè)圖，這七個(gè)圖中包含四種語義結(jié)構(gòu)，鏈(ch)、星形圖(st)、二部圖(bc)和團(tuán)(fc)各20、40、60、80、100、1 000，10 000個(gè)。

3.3 實(shí)驗(yàn)結(jié)果分析

本文從不同方面分析算法在不同大小的數(shù)據(jù)上的效率表現(xiàn)。

根據(jù)VoG中使用的數(shù)據(jù)集Notre Damesi，使用MRQ算法在不同數(shù)量的邊上與VoG結(jié)果進(jìn)行比較，并根據(jù)VoG實(shí)驗(yàn)給出的數(shù)據(jù)得出結(jié)果，如圖6所示。

圖6 MRQ和VoG在數(shù)據(jù)集Notre Damesi上的執(zhí)行時(shí)間

在第二個(gè)數(shù)據(jù)集上使用本文MRQ算法和VoG算法，由表1可知，隨著邊的數(shù)量逐漸增加，本文算法和VoG算法的運(yùn)行時(shí)間也越來越長，當(dāng)邊的數(shù)量增加到一定程度時(shí)，算法的運(yùn)行成本也會(huì)大幅增加。

表1 MRQ、VoG在數(shù)據(jù)集email-Eu-corenetwork的響應(yīng)時(shí)間

通過表1可以清晰地對(duì)比出，在同樣的數(shù)據(jù)集上本文的算法MRQ與VoG在時(shí)間上有了本質(zhì)上的縮減。隨著邊數(shù)的增加，VoG迭代的次數(shù)會(huì)越來越大導(dǎo)致時(shí)間的增長速度的比較大，而本文的MRQ比VoG快了兩個(gè)數(shù)量級(jí)。

在第二個(gè)數(shù)據(jù)集上運(yùn)行了本文MRQ算法，檢驗(yàn)其在大數(shù)據(jù)集上的響應(yīng)時(shí)間，結(jié)果如表2所示，充分驗(yàn)證了本文算法在大數(shù)據(jù)集上也有很大的提升，百萬邊的大數(shù)據(jù)集運(yùn)行時(shí)間都控制在1 min以內(nèi)。

表2 MRQ在數(shù)據(jù)集DBLP上的響應(yīng)時(shí)間

在確認(rèn)本文MRQ算法與VoG算法在時(shí)間上有了很大優(yōu)化之后，對(duì)第三組數(shù)據(jù)集上查找的準(zhǔn)確率進(jìn)行對(duì)比實(shí)驗(yàn)，如圖7所示。

圖7 MRQ和VoG在構(gòu)造圖上的準(zhǔn)確率

通過第三組實(shí)驗(yàn)，可以清晰地看出，MRQ算法和VoG算法都可以保持比較高效的準(zhǔn)確性，MRQ算法的平均準(zhǔn)確率可以達(dá)到98%左右，而VoG算法在小數(shù)據(jù)集上的準(zhǔn)確率沒有MRP算法的準(zhǔn)確率高，最大相差5%左右，并且MRQ算法的平均準(zhǔn)確率比VoG高3%左右。

綜上所述，與VoG算法相比，MRQ算法在時(shí)間上快了10倍，并且在大數(shù)據(jù)集上的子圖查詢的準(zhǔn)確率表現(xiàn)的更加優(yōu)異，無論在大數(shù)據(jù)集還是小數(shù)據(jù)集MRQ都有很好的表現(xiàn)，不僅比VoG節(jié)省更多的查詢時(shí)間，而且準(zhǔn)確率也有很好的表現(xiàn)。

4 結(jié) 語

當(dāng)前關(guān)于語義結(jié)構(gòu)的查詢大多是基于大圖上直接查詢的，本文對(duì)簡單無向大圖使用ApxGreedy算法進(jìn)行聚集處理，再根據(jù)聚集后的語義結(jié)構(gòu)的特征，即超點(diǎn)之間和超點(diǎn)內(nèi)的強(qiáng)弱關(guān)系確定跳轉(zhuǎn)概率來對(duì)每種語義結(jié)構(gòu)進(jìn)行隨機(jī)游走查詢。最后定義成本誤差來對(duì)查找到的結(jié)構(gòu)進(jìn)行排序并輸出結(jié)果。用本文的算法與VoG算法進(jìn)行了對(duì)比實(shí)驗(yàn)，在相同的真實(shí)數(shù)據(jù)集下，本文算法明顯在時(shí)間和準(zhǔn)確性上優(yōu)于VoG，說明本文的算法能提高查詢語義結(jié)構(gòu)的效果和效率。

本文使用的簡單無向無加權(quán)的大圖都是同構(gòu)圖，即圖中頂點(diǎn)的屬性是一致的。現(xiàn)實(shí)生活中還存在異構(gòu)圖，即頂點(diǎn)的屬性是不一致的。所以，下一步將研究帶異構(gòu)圖中的基于聚集圖的語義結(jié)構(gòu)剪枝查詢算法。