資源描述：
《an edge-based framework for fast subgraph matching in a large graph》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、DASFAA2011,pp.404–417,2011.AnEdge-BasedFrameworkforFastSubgraphMatchinginaLargeGraph大型圖中基于邊的快速子圖匹配框架SangjaeKim,InchulSong,andYoonJoonLee摘要：在子圖匹配中，我們在圖數(shù)據(jù)庫中找到與查詢圖同構(gòu)的全部子圖。子圖匹配需要子圖同構(gòu)測試，這是NPC問題。近來，已經(jīng)設(shè)計了一些用于大型圖中的子圖匹配的特定方法。它們基于過濾-驗(yàn)證框架。在過濾階段，過濾點(diǎn)不滿足同構(gòu)測試的頂點(diǎn)。在驗(yàn)證階段，執(zhí)行子圖
2、同構(gòu)測試并返回全部匹配的模式給用戶。這些稱之為基于頂點(diǎn)的方法，因?yàn)槭鞘褂庙旤c(diǎn)信息過濾掉不合格的頂點(diǎn)。然而，邊的信息也可用于高效的子圖匹配。本文提出了大型圖中基于邊的快速子圖匹配框架。通過使用邊連通信息，在過濾階段不僅過濾掉不合格的頂點(diǎn)，也避免了驗(yàn)證階段進(jìn)行不必要的邊連通性檢測。實(shí)驗(yàn)結(jié)果顯示，相對于已有的方法，本方法大大提高了大型圖中子圖匹配的方法1介紹因?yàn)閳D是對復(fù)雜數(shù)據(jù)有效表達(dá)的一種結(jié)構(gòu)，它有很多的應(yīng)用，例如Web，社交網(wǎng)絡(luò)，通信網(wǎng)絡(luò)，生物信息學(xué)，本體論工程，軟件建模，VLSI逆向工程等等。子圖匹配，就是從數(shù)據(jù)
3、庫圖中找到與查詢圖同構(gòu)的所有子圖，它是圖數(shù)據(jù)庫中最頻繁使用的操作之一。例如，在經(jīng)濟(jì)網(wǎng)絡(luò)中，頂點(diǎn)表示支票持有人或者銀行，邊代表錢的轉(zhuǎn)賬事務(wù)，那么經(jīng)濟(jì)犯罪調(diào)查就是希望找到網(wǎng)絡(luò)中所有與欺詐模式匹配的活動[1]。生物學(xué)家可能想在蛋白質(zhì)-蛋白質(zhì)交互網(wǎng)絡(luò)或者基因調(diào)控網(wǎng)中找到與特定生物模式匹配的所有情形[2]。此外，子圖匹配還可用于匿名社交網(wǎng)絡(luò)數(shù)據(jù)中的隱私攻擊的發(fā)現(xiàn)與保護(hù)[3],[4]。有兩類與子圖匹配相關(guān)的查詢。子圖包含查詢（subgraphcontainmentquery）需要找到包含了與查詢圖同構(gòu)的子圖的所有圖。許多搜
4、索都屬于這個類型的查詢[5],[6],[7],[8],[9]。在這些工作中，他們假設(shè)圖數(shù)據(jù)庫中包含很多小的圖。子圖匹配查詢（subgraphmatchingquery）是從單個的數(shù)據(jù)庫圖中，找到與查詢圖同構(gòu)的所有子圖。已經(jīng)提出了許多用于子圖匹配查詢的通用算法[10],[11]。近來，大型圖中的子圖匹配查詢有兩種方法被提出[12],[13]。本文將聚焦到大型圖中的子圖匹配查詢。因?yàn)樽訄D匹配需要子圖同構(gòu)測試，這是一個NPC問題[14]，已有的方法使用了經(jīng)典的過濾-驗(yàn)證框架。在過濾階段，如果數(shù)據(jù)圖中的頂點(diǎn)不能做為一個
5、匹配頂點(diǎn)，它將被過濾掉。這將通過比較頂點(diǎn)的簽名來實(shí)現(xiàn)，其中簽名包括頂點(diǎn)本身的信息及其鄰接頂點(diǎn)的信息。過濾之后，那些被保留的頂點(diǎn)，稱之為候選頂點(diǎn)，將進(jìn)行子圖同構(gòu)測試。在驗(yàn)證階段進(jìn)行子圖同構(gòu)測試，數(shù)據(jù)庫圖中與查詢圖同構(gòu)的所有子圖都將被找到并返回給用戶。驗(yàn)證階段的主要工作是檢驗(yàn)查詢圖中不同頂點(diǎn)對應(yīng)的候選頂點(diǎn)彼此是否恰當(dāng)?shù)南噙B。許多啟發(fā)式方法被用于加速驗(yàn)證的過程。已有的方法主要集中在減少子圖同構(gòu)測試的大小。GADDI[12]提出了基于數(shù)據(jù)挖掘的大型圖中的子圖匹配方法。它使用了判別子結(jié)構(gòu)（discriminativesu
6、bstructures）作為頂點(diǎn)簽名，這是一種從兩個頂點(diǎn)鄰接點(diǎn)的交集圖中導(dǎo)出的小的子結(jié)構(gòu)。NOVA[13]是大型圖子圖匹配的另一種方法。它使用關(guān)于頂點(diǎn)的標(biāo)簽分布信息作為頂點(diǎn)簽名。兩種方法都是基于頂點(diǎn)的框架，它們僅僅使用頂點(diǎn)信息過濾不合格的頂點(diǎn)。然而，邊的信息也可用于過濾處理。例如，通過選擇性的檢測數(shù)據(jù)庫圖中兩個頂點(diǎn)間的連通性，可以過濾掉不滿足與其它頂點(diǎn)連通的候選頂點(diǎn)。本文提出了大型圖中快速子圖匹配的基于邊的框架。該方法沿用了過濾-驗(yàn)證框架。與已有的基于頂點(diǎn)的框架不同的是，本方法在過濾和匹配階段均使用了邊連通信息
7、進(jìn)行快速子圖匹配。在過濾階段，基于邊連通信息過濾掉更多的候選頂點(diǎn)。邊連通信息也用于驗(yàn)證階段，以減少大量的頂點(diǎn)間的連通性檢測操作。一些連通性檢測操作可以整體刪除。實(shí)驗(yàn)的結(jié)果顯示我們的方法遠(yuǎn)優(yōu)于已有的大型圖中的子圖匹配方法。本文的余下部分組織如下。第二部分給出背景信息和方法綜述，第三部分描述本方法中用到的索引結(jié)構(gòu)。第四和第五部分分別描述過濾和驗(yàn)證階段。將在第六部分評估本方法。第七部分討論相關(guān)工作，第八部分總結(jié)全文。1預(yù)備知識該部分將介紹本文中使用的基本定義并給出問題的規(guī)范描述。本方法支持帶有標(biāo)簽的頂點(diǎn)與（/或）帶有
8、標(biāo)簽的邊的有向圖和無向圖。為了簡化表達(dá)，僅假定為帶標(biāo)簽的簡單圖?？上氡痉椒ㄖ苯討?yīng)用到其它類型的圖中。還假設(shè)查詢圖和數(shù)據(jù)庫圖均是連通的，也就是說，每對頂點(diǎn)間均有路徑相連。定義1（頂點(diǎn)標(biāo)簽圖）：頂點(diǎn)標(biāo)簽圖定義為G=(V,E,L,l)，其中V是頂點(diǎn)集合，E?V×V是邊集，L為頂點(diǎn)標(biāo)簽集合，l是匹配函數(shù)：V→L.定義2（子圖同構(gòu)）：假設(shè)有兩個圖，G=(V,E,L,l)和G’=(V’,E’,L’
