不確定圖間α-β子圖同構(gòu)匹配算法

摘 要： 子圖查詢返回圖數(shù)據(jù)集合中所有包含查詢圖的數(shù)據(jù)圖。在查詢圖和數(shù)據(jù)圖同時為不確定性圖的前提下，提出了不確定圖間的期望子圖同構(gòu)定義和α－β子圖同構(gòu)匹配定義。不確定圖間的期望子圖同構(gòu)是確定圖上子圖同構(gòu)在概率圖模型上的直接推廣，不確定圖間α－β子圖同構(gòu)利用兩個限制閾值來衡量查詢圖和數(shù)據(jù)圖間的匹配質(zhì)量。文章詳細(xì)闡述了α－β子圖同構(gòu)匹配的語義特點(diǎn)，分析了其和期望子圖同構(gòu)的聯(lián)系和差別，設(shè)計實(shí)現(xiàn)α－β子圖同構(gòu)匹配判定算法。

關(guān)鍵詞：

中圖分類號： ＴＰ３９３．１ 文獻(xiàn)標(biāo)識碼： Ａ 文章編號：２０９５－２１６３（２０１１）０３－０００１－０４

Ａｌｇｏｒｉｔｈｍ ｆｏｒ α－β Ｓｕｂｇｒａｐｈ Ｉｓｏｍｏｒｐｈｉｓｍ Ｐｒｏｂｌｅｍ ｏｎ Ｕｎｃｅｒｔａｉｎ Ｇｒａｐｈ

ＺＨＡＮＧ Ｙｉｎａｎ， ＺＯＵ Ｚｈａｏｎｉａｎ， ＬＩ Ｊｉａｎｚｈｏｎｇ

Ａｂｓｔｒａｃｔ：Subgraph query in graph set returns data graph containing query graph. When the query graph and data graph both are uncertain， this paper proposes a definition of subgraph isomorphism between uncertain graphs and a definition of α-β subgraph isomorphism matching. Expectation subgraph isomorphism between uncertain graphs is a direct extension of subgraph isomorphism between deterministic graphs on probability graph model. There are two parameters α and β which are the thresholds to restrict quality of matching between query graph and data graph. This paper elaborates features of α-β subgraph isomorphism matching in detail， analyzes the differences between it and expectation subgraph isomorphism， meanwhile proposes α-β subgraph isomorphism matching decision algorithm.

Ｋｅｙ ｗｏｒｄｓ：Uncertain Graph; Expectation Subgraph Isomorphism; α-β Subgraph Isomorphism Matching

０ 引言

確定圖數(shù)據(jù)挖掘和查詢處理等問題是圖數(shù)據(jù)研究領(lǐng)域熱點(diǎn)之一。子圖查詢返回圖數(shù)據(jù)集合中所有包含查詢圖的數(shù)據(jù)圖，這是圖數(shù)據(jù)集合上的一種基本操作。研究不確定圖數(shù)據(jù)上的子圖查詢具有重要意義。

針對不確定圖數(shù)據(jù)，研究者已經(jīng)提出了許多相關(guān)算法[１－６]。例如，文獻(xiàn)[１]討論了不確定圖上關(guān)系查詢，文獻(xiàn)[２]定義不確定圖上ｔｏｐ－ｋ最大團(tuán)查詢。文獻(xiàn)[３]提出ｔｏｐ－ｋ子圖匹配查詢，該查詢的主要目標(biāo)是返回不確定圖數(shù)據(jù)集中最有可能包含指定查詢圖的ｋ個不確定圖。

本文提出了不確定圖數(shù)據(jù)間子圖同構(gòu)匹配的兩種定義。期望子圖同構(gòu)是確定圖子圖同構(gòu)定義在概率模型下的直接擴(kuò)展。期望子圖同構(gòu)通過比較φ的概率期望值是否超過指定閾值進(jìn)行同構(gòu)判定。期望子圖同構(gòu)的概率意義十分直觀，但存在計算代價巨大和匹配結(jié)果描述復(fù)雜兩點(diǎn)不足。為此本文進(jìn)一步提出α－β子圖同構(gòu)定義和判定算法。不確定圖間α－β子圖同構(gòu)判定利用兩個限制閾值來替代期望子圖同構(gòu)判定中的單一限定閾值。

１ 不確定圖數(shù)據(jù)模型

定義１：不確定圖Ｇ為五元組(Ｖ，Ｅ，∑，ｌ，Ｐ)。Ｖ是Ｇ的頂點(diǎn)集； Ｅ是Ｇ的全部邊的集合，Ｇ中任意兩頂點(diǎn)ｕ和ｖ間至多存在一條邊，表示為ｕｖ或ｖｕ；∑為頂點(diǎn)標(biāo)號集； ｌ：Ｖ→∑是標(biāo)號函數(shù)，該函數(shù)計算圖Ｇ各頂點(diǎn)的標(biāo)號，對頂點(diǎn)集Ｖ中任意頂點(diǎn)ｖ，其標(biāo)號為ｌｖ＝ｌ(ｖ)；Ｐ：Ｅ→(０，１]是邊存在可能性函數(shù)，對Ｅ中任意邊ｅ，Ｐ(ｅ)是ｅ實(shí)際存在的概率。不確定圖Ｇ蘊(yùn)含一組確定圖。

根據(jù)Ｐ(ｅ)值是否為１，可劃分邊集Ｅ為彼此不相交的子集Ｅｃ＝{ｅ∈Ｅ｜Ｐ(ｅ)＝１}和Ｅｕｃ＝{ｅ∈Ｅ｜０＜Ｐ(ｅ)＜１}。集Ｅｃ稱為Ｇ的確定邊集，集Ｅｕｃ稱為Ｇ的不確定邊集， 二集合滿足Ｅｃ∩Ｅｕｃ＝且Ｅ＝Ｅｃ∪Ｅｕｃ。冪集２是Ｅｕｃ所有子集的集族。對應(yīng)每個Ｅ＇∈２，不確定圖Ｇ＝(Ｖ，Ｅ，∑，ｌ，Ｐ)蘊(yùn)含確定圖Ｉ＝(ＶＩ，ＥＩ，∑Ｉ，ｌＩ)，其中ＶＩ＝Ｖ，ＥＩ＝Ｅｃ∪Ｅ＇，∑Ｉ＝∑且ｌＩ＝ｌ。Ｇ蘊(yùn)含Ｉ記為Ｇ?圯Ｉ，則“Ｇ蘊(yùn)含Ｉ”的概率Ｐ(Ｇ?圯Ｉ)可依下述公式（１）進(jìn)行計算：

Ｐ(Ｇ?圯Ｉ)＝∏Ｐ(ｅ)#8226;∏(１－Ｐ(ｅ)) （１）

２ 不確定圖間的期望子圖同構(gòu)判定

已知不確定圖Ｇ１和Ｇ２，設(shè)Ｇ１實(shí)際中以確定圖Ｉ１形式存在，Ｇ２實(shí)際中以確定圖Ｉ２形式存在。“Ｇ１子圖同構(gòu)于Ｇ２”當(dāng)且僅當(dāng)Ｉ１子圖同構(gòu)于Ｉ２。因?yàn)椋桑焙停桑彩俏粗模?Ｉ１可能是ｓ(Ｇ１)中任一確定圖，Ｉ２可能是ｓ(Ｇ２)中任一確定圖，所以Ｇ１是否子圖同構(gòu)于Ｇ２無法簡單用“是”或“否”回答。依據(jù)公式（１），可計算Ｇ１子圖同構(gòu)于Ｇ２的概率Ｐ(Ｇ１Ｇ２)，計算公式（２）如下：

Ｐ(Ｇ１Ｇ２)＝∑Ｐ(Ｇ１?圯Ｉ１)

Ｐ(Ｇ２Ｉ２)φ(Ｉ１，Ｉ２) （２）

函數(shù)φ(Ｉ１，Ｉ２)值域?yàn)閧０，１}，如果Ｉ１子圖同構(gòu)于Ｉ２，則φ(Ｉ１，Ｉ２)值為１，否則φ(Ｉ１，Ｉ２)值為０。不難發(fā)現(xiàn)， Ｐ(Ｇ１Ｇ２)是φ(Ｉ１，Ｉ２)的概率期望值。根據(jù)該期望值可定義不確定圖期望子圖同構(gòu)。

定義２：已知不確定圖Ｇ１和Ｇ２，期望閾值δ∈（０，１]， Ｇ１期望子圖同構(gòu)于Ｇ２當(dāng)且僅當(dāng)Ｐ(Ｇ１Ｇ２)?叟δ，記為Ｇ１ δＧ２。

期望子圖同構(gòu)判定算法計算代價巨大。設(shè)Ｇ１和Ｇ２的不確定邊數(shù)目分別為Ｎ１和Ｎ２，則｜ｓ(Ｇ１)｜×｜ｓ(Ｇ２)｜等于２。除計算代價外，限制期望子圖同構(gòu)應(yīng)用的另一個問題是匹配結(jié)果描述困難。許多實(shí)際應(yīng)用要求獲知圖Ｇ１和Ｇ２中節(jié)點(diǎn)和／或邊間的匹配關(guān)系。對于期望子圖同構(gòu)，最壞情況下，用戶將得到２個不同的匹配結(jié)果，伴隨每個匹配結(jié)果是該匹配成立的概率。

３ 不確定圖間的α－β子圖同構(gòu)判定

３．１ α－β子圖同構(gòu)定義

定義３：不確定圖Ｇ的不確定邊集為Ｅｕｃ，函數(shù)α：２→[０，１]稱為誤差函數(shù)，對Ｅｕｃ的任一子集Ｅ△，誤差函數(shù)值α（Ｅ△）按下述公式（３）計算：

１－∏(１－Ｐ(ｅ))Ｅ△≠

定義４：不確定圖Ｇ的邊集為Ｅ，函數(shù)β：２Ｅ→(０，１]稱為強(qiáng)度函數(shù)，對Ｅ的任一子集ＥΩ，強(qiáng)度函數(shù)值β(ＥΩ)按下述公式（４）計算：

β(ＥΩ)＝ （４）

為簡化表述作以下規(guī)定。Ｉｍａｘ(Ｇ)表示不確定圖Ｇ蘊(yùn)含的最大確定圖，如果Ｇ＝(Ｖ，Ｅ，∑，ｌ，Ｐ)，那么Ｉｍａｘ(Ｇ)＝(Ｖ，Ｅ，∑，ｌ)。Ｅ△是Ｇ不確定邊集Ｅｕｃ的子集，Ｉｍａｘ(Ｇ)－Ｅ△表示在圖Ｉｍａｘ(Ｇ)里刪除Ｅ△中全部邊后形成的確定圖。ｆ(Ｅ１)表示Ｅ２中所有對應(yīng)邊的集合，即ｆ(Ｅ１)＝{ｆ(ｅ)｜ｅ∈Ｅ１}。

定義５：已知不確定圖Ｇ１和Ｇ２，設(shè)Ｇ１的不確定邊集為Ｅｕｃ；如果存在Ｅ△Ｅｕｃ和映射函數(shù)ｆ同時滿足：

（１） Ｉｍａｘ(Ｇ１)－Ｅ△子圖同構(gòu)于Ｉｍａｘ(Ｇ２)，ｆ為同構(gòu)映射函數(shù)；

（２） α（Ｅ△）αｍａｘ，常數(shù)αｍａｘ稱為誤差閾值，αｍａｘ∈[０，１]；

（３） β(ｆ(Ｅ１))?叟βｍｉｎ，常數(shù)βｍｉｎ稱為強(qiáng)度閾值，βｍｉｎ∈[０，１]；

那么Ｇ１“α－β子圖同構(gòu)于”Ｇ２，記為Ｇ１α，βＧ２。

３．２ α－β子圖同構(gòu)的語義

條件（１）“Ｉｍａｘ(Ｇ１)－Ｅ△子圖同構(gòu)于Ｉｍａｘ(Ｇ２)”可表述為：子樣本空間ｓ(Ｇ１，Ｅ△)中每個圖都是確定圖Ｉｍａｘ(Ｇ２)的子圖。集合ｓ(Ｇ１)是被Ｇ１蘊(yùn)含的所有確定圖的集合，Ｅ△將ｓ(Ｇ１)分為ｓ(Ｇ１，Ｅ△)和ｓ(Ｇ１)＼ ｓ(Ｇ１，Ｅ△)，其中，ｓ(Ｇ１，Ｅ△)＝{Ｉ｜ＩＩｍａｘ(Ｇ１)－Ｅ△}。

條件（２）“α(Ｅ△)”對Ｅ△進(jìn)行限制，以保證“不確定圖Ｇ１ 蘊(yùn)含子樣本空間ｓ(Ｇ１，Ｅ△)”的概率Ｐ（Ｇ１?圯ｓ(Ｇ１，Ｅ△))足夠大。參照公式（３）， Ｐ（Ｇ１?圯ｓ(Ｇ１，Ｅ△))按下述公式（６）計算。

Ｐ（Ｇ１?圯ｓ(Ｇ１，Ｅ△))＝∑Ｐ(Ｇ１?圯Ｉ)?叟１－α(Ｅ△) （６）

條件（３）“β(ｆ(Ｅ１))?叟βｍｉｎ”對同構(gòu)匹配函數(shù)ｆ進(jìn)行限制，以保證不確定圖Ｇ２蘊(yùn)含確定圖Ｉｍａｘ(Ｇ１)－Ｅ△的概率Ｐ（Ｇ２?圯Ｉｍａｘ(Ｇ１)－Ｅ△)足夠大。所以Ｉｍａｘ(Ｇ２)的以ｆ(Ｅ１)為邊集的子圖Ｉ＇（ｆ）和Ｉｍａｘ(Ｇ１)－Ｅ△彼此同構(gòu)。對每個確定的映射函數(shù)ｆ，下述公式成立：

Ｐ（Ｇ２?圯Ｉｍａｘ(Ｇ１)－Ｅ△) ?叟∏Ｐ(ｅ)＝β(ｆ(Ｅ)) （７）

已知不確定圖Ｇ１在閾值αｍａｘ和βｍｉｎ限制下α－β子圖同構(gòu)于Ｇ２，下述定理１揭示了α－β子圖同構(gòu)和期望子圖同構(gòu)定義的聯(lián)系。

定理１：如果不確定圖Ｇ１在閾值αｍａｘ和βｍｉｎ限制下子圖同構(gòu)于Ｇ２，那么Ｐ(Ｇ１Ｇ２)?叟δ(αｍａｘ，βｍｉｎ)，其中，δ(αｍａｘ，βｍｉｎ)等于(１－αｍａｘ)βｍｉｎＭ， Ｍ等于確定圖Ｉｍａｘ(Ｇ１)－Ｅ△邊數(shù)。

不確定圖Ｇ１“α－β子圖同構(gòu)”于Ｇ２，則圖Ｇ１在現(xiàn)實(shí)中子圖同構(gòu)于Ｇ２的概率Ｐ(Ｇ１Ｇ２)大于等于δ(αｍａｘ，βｍｉｎ)。如定義２所示，期望子圖同構(gòu)使用單一常數(shù)δ作為限定閾值；α－β子圖同構(gòu)使用兩個常數(shù)αｍａｘ和βｍｉｎ作為替代δ的限定閾值。α－β子圖同構(gòu)具有概率意義，概括表述為：如果Ｇ１“α－β子圖同構(gòu)”于Ｇ２且δ(αｍａｘ，βｍｉｎ)不小于期望閾值δ，那么圖Ｇ１期望子圖同構(gòu)于Ｇ２。

α－β子圖同構(gòu)計算代價較期望子圖同構(gòu)定義小很多。在不確定圖Ｇ１和Ｇ２間進(jìn)行α－β子圖同構(gòu)判定的計算代價接近于在確定圖Ｉｍａｘ(Ｇ１)和Ｉｍａｘ(Ｇ２)間進(jìn)行子圖同構(gòu)判定的代價。α－β子圖同構(gòu)的匹配結(jié)果描述簡單，便于用戶理解和使用。匹配結(jié)果可用二元組(Ｅ△，ｆ)表示。α－β子圖同構(gòu)具有實(shí)用意義。在一些應(yīng)用中，查詢圖的不確定性反映了用戶對查詢圖中各種元素存在的可能性的期望。在這種情況下，用戶傾向于利用查詢算法在數(shù)據(jù)圖Ｇ２上找到查詢圖Ｇ１的一個有意義的匹配，而不只是用一個閾值告知匹配成功的概率有多大。在查詢圖Ｇ１上引入不確定性的可能原因是用戶允許在查詢過程中忽略Ｇ１的某些因素，而頂點(diǎn)或邊的存在概率值恰恰反映了用戶對這種“忽略”行為的容忍程度。

４ α－β子圖同構(gòu)判定算法

不確定圖α－β子圖同構(gòu)判定算法是對確定圖子圖同構(gòu)算法的推廣，本文以確定圖上常用子圖同構(gòu)判定算法ｕｌｌｍａｎ算法為基礎(chǔ)，設(shè)計實(shí)現(xiàn)不確定圖α－β子圖同構(gòu)判定算法如下：

ＡｄｖＵｍＡｌｇｏ(Ｇ１，Ｇ２，Ｈ，Ｆ，ｄ，α，β)

Ｉｎｐｕｔ：Ｕｎｃｅｒｔａｉｎ ｑｕｅｒｙ ｇｒａｐｈ Ｇ１ ｗｉｔｈ Ｎ１ ｎｏｄｅｓ

Ｕｎｃｅｒｔａｉｎ ｄａｔａ ｇｒａｐｈ Ｇ２ ｗｉｔｈ Ｎ２ ｎｏｄｅｓ

ＡｒｒａｙＨ[Ｎ１]， Ｈ[ｉ] ｉｎｉｔｉａｌｉｚｅｄｂｙ ０，１ｉＮ１

ＡｒｒａｙＦ[Ｎ１]， Ｆ[ｉ] ｉｎｉｔｉａｌｉｚｅｄｂｙ ０，１ｉＮ２

Ｉｎｔｅｇｅｒｄ， ｉｎｉｔｉａｌｉｚｅｄｂｙ １ ，

α，ｉｎｉｔｉａｌｉｚｅｄ ｂｙ ０

β，ｉｎｉｔｉａｌｉｚｅｄ ｂｙ ０

Ｏｕｔｐｕｔ：ｂｏｏｌｅａｎ：Ｇ１α，βＧ２

（１）ｉｆ ｄ＞Ｎ１ ｔｈｅｎ

（２） ｉｆ β＜βｍｉｎ ｔｈｅｎ ｒｅｔｕｒｎｆａｌｓｅ

（３） ｅｌｓｅ ｒｅｔｕｒｎ ｔｒｕｅ

（４） ｅｎｄ ｉｆ

（５）ｅｎｄ ｉｆ

（６）ｆｏｒ ｅａｃｈ １ｋＮ２∧Ｆ[ｋ]＝０ ｄｏ

（７） ｉｆ ｌ(ｄ)≠ｌ(ｋ) ｔｈｅｎ ｇｏｔｏ ｌｉｎｅ６

（８） ｃａｌｃｕｌａｔｅ ａｎｄ ｕｐｄａｔｅ α

（９） ｉｆ α＞αｍａｘ ｔｈｅｎ

（１０） ｒｅｃｏｖｅｒ α ａｎｄ ｇｏｔｏ ｌｉｎｅ６

（１１） ｅｎｄ ｉｆ

（１２） Ｈ[ｄ]：＝ｋ

（１３） Ｆ[ｋ]：＝１

（１４） ｃａｌｃｕｌａｔｅ ａｎｄ ｕｐｄａｔｅ β

（１５） ｉｆＡｄｖＵｍＡｌｇｏ(Ｇ１，Ｇ２，Ｈ，Ｆ，ｄ＋１)ｔｈｅｎ

（１６） ｒｅｔｕｒｎ ｔｒｕｅ

（１７） ｅｎｄ ｉｆ

（１８） Ｆ[ｋ]：＝０

（１９） ｒｅｃｏｖｅｒ α ａｎｄ β

（２０）ｅｎｄ ｆｏｒ

（２１）ｒｅｔｕｒｎ ｆａｌｓｅ

算法ＡｄｖＵｍＡｌｇｏ是先深策略搜索狀態(tài)空間，以遞歸調(diào)用的方式實(shí)現(xiàn)。該算法包含七個輸入，分別是：不確定查詢圖Ｇ１，設(shè)Ｇ１頂點(diǎn)數(shù)等于Ｎ１；不確定數(shù)據(jù)圖Ｇ２，設(shè)Ｇ２頂點(diǎn)數(shù)等于Ｎ２；整數(shù)ｄ初始化為１，始終等于遞歸深度；α初始化為０，計算方法參公式（３）；β初始化為０，計算方法參公式（４）；數(shù)組Ｈ記錄圖Ｇ１頂點(diǎn)和Ｇ２頂點(diǎn)匹配關(guān)系， Ｈ[ｉ]＝ｋ當(dāng)且僅當(dāng)在當(dāng)前匹配中Ｇ１的頂點(diǎn)ｉ對應(yīng)Ｇ２的頂點(diǎn)ｋ；數(shù)組Ｆ記錄 Ｇ２頂點(diǎn)占用情況，Ｆ[ｋ]＝１說明Ｇ２的頂點(diǎn)ｋ被當(dāng)前匹配占用，即存在Ｈ[ｉ]＝ｋ，其中，１ｉｄ－１，Ｆ[ｋ]＝０說明ｋ尚未匹配Ｇ１中的任何頂點(diǎn)。

在深度為ｄ的遞歸調(diào)用開始前，Ｇ１的前ｄ－１個頂點(diǎn)已經(jīng)匹配完畢，頂點(diǎn)對應(yīng)關(guān)系存儲在數(shù)組Ｈ的前ｄ－１位中。算法開始，首先檢查迭代深度是否超過Ｇ１頂點(diǎn)數(shù)，如果ｄ＞Ｎ１，說明匹配完成，在這種情況下，如果β小于閾值βｍｉｎ，那么返回上層繼續(xù)進(jìn)行搜索，否則返回真值。如果ｄ＜Ｎ１，則為Ｇ１的頂點(diǎn)ｄ在Ｇ２中尋找匹配頂點(diǎn)。與ｕｌｌｍａｎ算法的主要差別在于搜索剪枝條件的不同：在ｕｌｌｍａｎ算法中，如果當(dāng)前數(shù)據(jù)圖中沒有合適頂點(diǎn)與查詢圖中當(dāng)前節(jié)點(diǎn)相匹配，那么進(jìn)行搜索剪枝并回溯。在不確定圖上的“α－β”子圖同構(gòu)匹配的精確算法中，如果當(dāng)前數(shù)據(jù)圖中沒有合適頂點(diǎn)與查詢圖中當(dāng)前節(jié)點(diǎn)相匹配，則嘗試忽略查詢圖中當(dāng)前節(jié)點(diǎn)的若干鄰接邊。

５ 實(shí)驗(yàn)

本文通過實(shí)驗(yàn)分析α－β子圖同構(gòu)判定算法，測試判定算法在不同規(guī)模圖數(shù)據(jù)和不同閾值限制下的表現(xiàn)，主要關(guān)注算法的執(zhí)行時間。因?yàn)楝F(xiàn)有不確定圖子圖匹配查詢方法中查詢圖基本為確定圖，所以實(shí)驗(yàn)無法利用這些方法進(jìn)行對比實(shí)驗(yàn)，但實(shí)驗(yàn)對比優(yōu)化前后的α－β子圖同構(gòu)判定算法。

本文提出的算法采用標(biāo)準(zhǔn)Ｃ＋＋和ＳＴＬ庫實(shí)現(xiàn)，使用ｇｃｃ／ｇ＋＋編譯器編譯，所有實(shí)驗(yàn)均在Ｐ４ １．７ＧＨｚ／２Ｇ ＲＡＭ的機(jī)器上進(jìn)行。

５．１ 數(shù)據(jù)集和參數(shù)設(shè)定

不確定圖數(shù)據(jù)，包括查詢圖和數(shù)據(jù)圖，以上述ＡＩＤＳ數(shù)據(jù)集為基礎(chǔ)生成，其基本思想是隨機(jī)為數(shù)據(jù)集中確定圖的部分邊添加存在概率作為權(quán)值。實(shí)驗(yàn)中用到五組不確定查詢圖Ｑ８、Ｑ１２、Ｑ１６、Ｑ２０和Ｑ２４，Ｑｎ包含１００個圖，每個圖的邊數(shù)都是ｎ。不確定圖數(shù)據(jù)間α－β子圖同構(gòu)主要實(shí)驗(yàn)參數(shù)為αｍａｘ和βｍｉｎ，實(shí)驗(yàn)在三種不同參數(shù)條件下進(jìn)行測試，三組設(shè)定參數(shù)分別為(αｍａｘ，βｍｉｎ)＝(０．８，０．４)、(αｍａｘ，βｍｉｎ)＝(０．２，０．４)和(αｍａｘ，βｍｉｎ)＝(０．２，０．８)。第二組參數(shù)作為參數(shù)的一般設(shè)定值；對比第一組和第二組參數(shù)設(shè)定可分析αｍａｘ與算法性能效果的關(guān)系；對比第三組和第二組參數(shù)設(shè)定可以分析βｍｉｎ對判定算法性能的影響。

５．２ 實(shí)驗(yàn)分析

實(shí)驗(yàn)對比α－β子圖同構(gòu)判定算法在三種不同條件下的執(zhí)行時間，結(jié)果如圖１所示。圖中橫軸標(biāo)明查詢圖規(guī)模（查詢圖邊數(shù)），每組查詢圖包含１００個查詢圖；圖中縱軸為判定算法在不同查詢圖和不同參數(shù)條件下的平均執(zhí)行時間。第１組參數(shù)設(shè)定為(αｍａｘ＝０．８，βｍｉｎ＝０．４)，第２組參數(shù)設(shè)定為(αｍａｘ＝０．２，βｍｉｎ＝０．４)，第 ３組參數(shù)設(shè)定為(αｍａｘ＝０．２，βｍｉｎ＝０．８)。

通過分析圖１可知：在查詢圖邊數(shù)相同條件下，判定算法在第１組參數(shù)下的平均執(zhí)行時間大于第２組參數(shù)。在強(qiáng)度閾值βｍｉｎ相同的條件下，誤差閾值αｍａｘ越小，則算法的執(zhí)行時間越短。在誤差閾值αｍａｘ相同的條件下，強(qiáng)度閾值βｍｉｎ越大，則算法的執(zhí)行時間越長。

圖２為優(yōu)化前后的α－β子圖同構(gòu)判定算法的平均執(zhí)行時間。該項(xiàng)實(shí)驗(yàn)將參數(shù)固定為具有代表性的第二組(αｍａｘ＝０．２，βｍｉｎ＝０．４)。通過分析圖２可知，判定算法在搜索順序進(jìn)行優(yōu)化以后執(zhí)行時間大幅縮短。

６ 結(jié)束語

子圖同構(gòu)判定問題是ＮＰ完全問題，將不確定性引入子圖同構(gòu)匹配進(jìn)一步增大了判定算法的計算代價。不確定圖間α－β子圖同構(gòu)判定較之于期望子圖同構(gòu)判定具有較小的計算代價，但時間上界仍是指數(shù)級的。為將不確定圖數(shù)據(jù)上的子圖查詢或與之類似的其他查詢在多項(xiàng)式時間內(nèi)完成，最為可行的方法是結(jié)合實(shí)際應(yīng)用背景在圖數(shù)據(jù)匹配的語義層面尋求突破。

參考文獻(xiàn)：

[ １ ] ＤＡＬＶＩ Ｎ Ｎ，ＳＵＣＩＵ Ｄ： Ｅｆｆｉｃｉｅｎｔ ｑｕｅｒｙ ｅｖａｌｕａｔｉｏｎ ｏｎ ｐｒｏｂａ－

ｂｉｌｉｓｔｉｃ ｄａｔａｂａｓｅｓ[Ｃ]／／ ＶＬＤＢ Ｊ． １６（４）： ５２５４４ （２００７）．

[ ２ ] ＳＯＬＩＭＡＮ Ｍ Ａ，ＩＬＹＡＳ Ｉ Ｆ， Ｋｅｖｉｎ Ｃｈｅｎ－Ｃｈｕａｎ Ｃｈａｎｇ： Ｔｏｐ－

ｋ Ｑｕｅｒｙ Ｐｒｏｃｅｓｓｉｎｇ ｉｎ Ｕｎｃｅｒｔａｉｎ Ｄａｔａｂａｓｅｓ[Ｃ]／／ ＩＣＤＥ ２００７：

８９６－９０５．

[ ３ ] 張碩，高宏，李建中． 不確定圖數(shù)據(jù)庫中高效查詢處理． 計算

機(jī)學(xué)報[Ｊ]． ２００９， ３２（１０）：２０６６－２０７９．

[ ４ ] 周傲英，金澈清，王國仁，等． 不確定性數(shù)據(jù)管理技術(shù)研究綜述．

計算機(jī)學(xué)報[Ｊ]． ２００９， ３２（１）：１－１６．

[ ５ ] ＧＡＯ Ｈｏｎｇ， ＺＨＡＮＧ Ｗｅｉ． Ｒｅｓｅａｒｃｈ ｓｔａｔｕｓ ｏｆ ｔｈｅ ｍａｎａｇｅｍｅｎｔ

ｏｆ ｕｎｃｅｒｔａｉｎ ｇｒａｐｈ ｄａｔａ． Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｏｆ ｔｈｅ Ｃｈｉｎａ Ｃｏｍｐｕｔ－

ｅｒ Ｆｅｄｅｒａｔｉｏｎ[Ｃ]／／ ２００９， ５（４）：３１－３６．

[ ６ ] ＨＩＮＴＳＡＮＥＮ Ｐ，ＴＯＩＶＯＮＥＮ Ｈ． Ｆｉｎｄｉｎｇ ｒｅｌｉａｂｌｅ ｓｕｂｇｒａｐｈｓ ｆｒ－

ｏｍ ｌａｒｇｅ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｇｒａｐｈｓ[Ｃ]／／ Ｄａｔａ Ｍｉｎ． Ｋｎｏｗｌ． Ｄｉｓｃｏｖ．

２００８，１７（１）：２３．