不确定图间α-β子图同构匹配算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇不确定图间α-β子图同构匹配算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要： 子图查询返回图数据集合中所有包含查询图的数据图。在查询图和数据图同时为不确定性图的前提下，提出了不确定图间的期望子图同构定义和α－β子图同构匹配定义。不确定图间的期望子图同构是确定图上子图同构在概率图模型上的直接推广，不确定图间α－β子图同构利用两个限制阈值来衡量查询图和数据图间的匹配质量。文章详细阐述了α－β子图同构匹配的语义特点，分析了其和期望子图同构的联系和差别，设计实现α－β子图同构匹配判定算法。

关键词：

中图分类号： TP393．1 文献标识码： A 文章编号：2095－2163（2011）03－0001－04

Algorithm for α－β Subgraph Isomorphism Problem on Uncertain Graph

ZHANG Yinan， ZOU Zhaonian， LI Jianzhong

Abstract：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.

Key words：Uncertain Graph; Expectation Subgraph Isomorphism; α-β Subgraph Isomorphism Matching

0 引言

确定图数据挖掘和查询处理等问题是图数据研究领域热点之一。子图查询返回图数据集合中所有包含查询图的数据图，这是图数据集合上的一种基本操作。研究不确定图数据上的子图查询具有重要意义。

针对不确定图数据，研究者已经提出了许多相关算法[1－6]。例如，文献[1]讨论了不确定图上关系查询，文献[2]定义不确定图上top－k最大团查询。文献[3]提出top－k子图匹配查询，该查询的主要目标是返回不确定图数据集中最有可能包含指定查询图的k个不确定图。

本文提出了不确定图数据间子图同构匹配的两种定义。期望子图同构是确定图子图同构定义在概率模型下的直接扩展。期望子图同构通过比较φ的概率期望值是否超过指定阈值进行同构判定。期望子图同构的概率意义十分直观，但存在计算代价巨大和匹配结果描述复杂两点不足。为此本文进一步提出α－β子图同构定义和判定算法。不确定图间α－β子图同构判定利用两个限制阈值来替代期望子图同构判定中的单一限定阈值。

1 不确定图数据模型

定义1：不确定图G为五元组(V,E,∑,l,P)。V是G的顶点集； E是G的全部边的集合，G中任意两顶点u和v间至多存在一条边，表示为uv或vu；∑为顶点标号集； l：V∑是标号函数，该函数计算图G各顶点的标号，对顶点集V中任意顶点v，其标号为lv＝l(v)；P：E(0,1]是边存在可能性函数，对E中任意边e，P(e)是e实际存在的概率。不确定图G蕴含一组确定图。

根据P(e)值是否为1，可划分边集E为彼此不相交的子集Ec＝{e∈E｜P(e)＝1}和Euc＝{e∈E｜0＜P(e)＜1}。集Ec称为G的确定边集，集Euc称为G的不确定边集， 二集合满足Ec∩Euc＝且E＝Ec∪Euc。幂集2是Euc所有子集的集族。对应每个E＇∈2，不确定图G＝(V,E,∑,l,P)蕴含确定图I＝(VI,EI,∑I,lI)，其中VI＝V，EI＝Ec∪E＇，∑I＝∑且lI＝l。G蕴含I记为G?圯I，则“G蕴含I”的概率P(G?圯I)可依下述公式（1）进行计算：

P(G?圯I)＝∏P(e)•∏(1－P(e)) （1）

2 不确定图间的期望子图同构判定

已知不确定图G1和G2，设G1实际中以确定图I1形式存在，G2实际中以确定图I2形式存在。“G1子图同构于G2”当且仅当I1子图同构于I2。因为I1和I2是未知的， I1可能是s(G1)中任一确定图，I2可能是s(G2)中任一确定图，所以G1是否子图同构于G2无法简单用“是”或“否”回答。依据公式（1），可计算G1子图同构于G2的概率P(G1G2)，计算公式（2）如下：

P(G1G2)＝∑P(G1?圯I1)

P(G2I2)φ(I1,I2) （2）

函数φ(I1,I2)值域为{0,1}，如果I1子图同构于I2，则φ(I1,I2)值为1，否则φ(I1,I2)值为0。不难发现， P(G1G2)是φ(I1,I2)的概率期望值。根据该期望值可定义不确定图期望子图同构。

定义2：已知不确定图G1和G2，期望阈值δ∈（0，1]， G1期望子图同构于G2当且仅当P(G1G2)?叟δ，记为G1 δG2。

期望子图同构判定算法计算代价巨大。设G1和G2的不确定边数目分别为N1和N2，则｜s(G1)｜×｜s(G2)｜等于2。除计算代价外，限制期望子图同构应用的另一个问题是匹配结果描述困难。许多实际应用要求获知图G1和G2中节点和／或边间的匹配关系。对于期望子图同构，最坏情况下，用户将得到2个不同的匹配结果，伴随每个匹配结果是该匹配成立的概率。

3 不确定图间的α－β子图同构判定

3．1 α－β子图同构定义

定义3：不确定图G的不确定边集为Euc，函数α：2[0,1]称为误差函数，对Euc的任一子集E，误差函数值α（E）按下述公式（3）计算：

1－∏(1－P(e))E≠

定义4：不确定图G的边集为E，函数β：2E(0,1]称为强度函数，对E的任一子集EΩ，强度函数值β(EΩ)按下述公式（4）计算：

β(EΩ)＝ （4）

为简化表述作以下规定。Imax(G)表示不确定图G蕴含的最大确定图，如果G＝(V,E,∑,l,P)，那么Imax(G)＝(V,E,∑,l)。E是G不确定边集Euc的子集，Imax(G)－E表示在图Imax(G)里删除E中全部边后形成的确定图。f(E1)表示E2中所有对应边的集合，即f(E1)＝{f(e)｜e∈E1}。

定义5：已知不确定图G1和G2，设G1的不确定边集为Euc；如果存在EEuc和映射函数f同时满足：

（1） Imax(G1)－E子图同构于Imax(G2)，f为同构映射函数；

（2） α（E）αmax，常数αmax称为误差阈值，αmax∈[0,1]；

（3） β(f(E1))?叟βmin，常数βmin称为强度阈值，βmin∈[0,1]；

那么G1“α－β子图同构于”G2，记为G1α,βG2。

3．2 α－β子图同构的语义

条件（1）“Imax(G1)－E子图同构于Imax(G2)”可表述为：子样本空间s(G1,E)中每个图都是确定图Imax(G2)的子图。集合s(G1)是被G1蕴含的所有确定图的集合，E将s(G1)分为s(G1,E)和s(G1)＼ s(G1,E)，其中，s(G1,E)＝{I｜IImax(G1)－E}。

条件（2）“α(E)”对E进行限制，以保证“不确定图G1 蕴含子样本空间s(G1,E)”的概率P（G1?圯s(G1,E))足够大。参照公式（3）， P（G1?圯s(G1,E))按下述公式（6）计算。

P（G1?圯s(G1,E))＝∑P(G1?圯I)?叟1－α(E) （6）

条件（3）“β(f(E1))?叟βmin”对同构匹配函数f进行限制，以保证不确定图G2蕴含确定图Imax(G1)－E的概率P（G2?圯Imax(G1)－E)足够大。所以Imax(G2)的以f(E1)为边集的子图I＇（f）和Imax(G1)－E彼此同构。对每个确定的映射函数f，下述公式成立：

P（G2?圯Imax(G1)－E) ?叟∏P(e)＝β(f(E)) （7）

已知不确定图G1在阈值αmax和βmin限制下α－β子图同构于G2，下述定理1揭示了α－β子图同构和期望子图同构定义的联系。

定理1：如果不确定图G1在阈值αmax和βmin限制下子图同构于G2，那么P(G1G2)?叟δ(αmax,βmin)，其中，δ(αmax,βmin)等于(1－αmax)βminM， M等于确定图Imax(G1)－E边数。

不确定图G1“α－β子图同构”于G2，则图G1在现实中子图同构于G2的概率P(G1G2)大于等于δ(αmax,βmin)。如定义2所示，期望子图同构使用单一常数δ作为限定阈值；α－β子图同构使用两个常数αmax和βmin作为替代δ的限定阈值。α－β子图同构具有概率意义，概括表述为：如果G1“α－β子图同构”于G2且δ(αmax,βmin)不小于期望阈值δ，那么图G1期望子图同构于G2。

α－β子图同构计算代价较期望子图同构定义小很多。在不确定图G1和G2间进行α－β子图同构判定的计算代价接近于在确定图Imax(G1)和Imax(G2)间进行子图同构判定的代价。α－β子图同构的匹配结果描述简单，便于用户理解和使用。匹配结果可用二元组(E,f)表示。α－β子图同构具有实用意义。在一些应用中，查询图的不确定性反映了用户对查询图中各种元素存在的可能性的期望。在这种情况下，用户倾向于利用查询算法在数据图G2上找到查询图G1的一个有意义的匹配，而不只是用一个阈值告知匹配成功的概率有多大。在查询图G1上引入不确定性的可能原因是用户允许在查询过程中忽略G1的某些因素，而顶点或边的存在概率值恰恰反映了用户对这种“忽略”行为的容忍程度。

4 α－β子图同构判定算法

不确定图α－β子图同构判定算法是对确定图子图同构算法的推广，本文以确定图上常用子图同构判定算法ullman算法为基础，设计实现不确定图α－β子图同构判定算法如下：

AdvUmAlgo(G1,G2,H,F,d,α,β)

Input：Uncertain query graph G1 with N1 nodes

Uncertain data graph G2 with N2 nodes

ArrayH[N1], H[i] initializedby 0,1iN1

ArrayF[N1], F[i] initializedby 0,1iN2

Integerd, initializedby 1 ,

α，initialized by 0

β，initialized by 0

Output：boolean：G1α,βG2

（1） if d＞N1 then

（2） if β＜βmin then returnfalse

（3） else return true

（4） end if

（5） end if

（6） for each 1kN2∧F[k]＝0 do

（7） if l(d)≠l(k) then goto line6

（8） calculate and update α

（9） if α＞αmax then

（10） recover α and goto line6

（11） end if

（12） H[d]：＝k

（13） F[k]：＝1

（14） calculate and update β

（15） ifAdvUmAlgo(G1,G2,H,F,d＋1)then

（16） return true

（17） end if

（18） F[k]：＝0

（19） recover α and β

（20） end for

（21） return false

算法AdvUmAlgo是先深策略搜索状态空间，以递归调用的方式实现。该算法包含七个输入，分别是：不确定查询图G1，设G1顶点数等于N1；不确定数据图G2，设G2顶点数等于N2；整数d初始化为1，始终等于递归深度；α初始化为0，计算方法参公式（3）；β初始化为0，计算方法参公式（4）；数组H记录图G1顶点和G2顶点匹配关系， H[i]＝k当且仅当在当前匹配中G1的顶点i对应G2的顶点k；数组F记录 G2顶点占用情况，F[k]＝1说明G2的顶点k被当前匹配占用，即存在H[i]＝k，其中，1id－1，F[k]＝0说明k尚未匹配G1中的任何顶点。

在深度为d的递归调用开始前，G1的前d－1个顶点已经匹配完毕，顶点对应关系存储在数组H的前d－1位中。算法开始,首先检查迭代深度是否超过G1顶点数，如果d＞N1，说明匹配完成，在这种情况下，如果β小于阈值βmin，那么返回上层继续进行搜索，否则返回真值。如果d＜N1，则为G1的顶点d在G2中寻找匹配顶点。与ullman算法的主要差别在于搜索剪枝条件的不同：在ullman算法中，如果当前数据图中没有合适顶点与查询图中当前节点相匹配，那么进行搜索剪枝并回溯。在不确定图上的“α－β”子图同构匹配的精确算法中，如果当前数据图中没有合适顶点与查询图中当前节点相匹配，则尝试忽略查询图中当前节点的若干邻接边。

5 实验

本文通过实验分析α－β子图同构判定算法，测试判定算法在不同规模图数据和不同阈值限制下的表现，主要关注算法的执行时间。因为现有不确定图子图匹配查询方法中查询图基本为确定图，所以实验无法利用这些方法进行对比实验，但实验对比优化前后的α－β子图同构判定算法。

本文提出的算法采用标准C＋＋和STL库实现，使用gcc／g＋＋编译器编译，所有实验均在P4 1．7GHz／2G RAM的机器上进行。

5．1 数据集和参数设定

不确定图数据，包括查询图和数据图，以上述AIDS数据集为基础生成，其基本思想是随机为数据集中确定图的部分边添加存在概率作为权值。实验中用到五组不确定查询图Q8、Q12、Q16、Q20和Q24，Qn包含100个图，每个图的边数都是n。不确定图数据间α－β子图同构主要实验参数为αmax和βmin，实验在三种不同参数条件下进行测试，三组设定参数分别为(αmax,βmin)＝(0．8,0．4)、(αmax，βmin)＝(0．2,0．4)和(αmax，βmin)＝(0．2，0．8)。第二组参数作为参数的一般设定值；对比第一组和第二组参数设定可分析αmax与算法性能效果的关系；对比第三组和第二组参数设定可以分析βmin对判定算法性能的影响。

5．2 实验分析

实验对比α－β子图同构判定算法在三种不同条件下的执行时间，结果如图1所示。图中横轴标明查询图规模（查询图边数），每组查询图包含100个查询图；图中纵轴为判定算法在不同查询图和不同参数条件下的平均执行时间。第1组参数设定为(αmax＝0．8,βmin＝0．4)，第2组参数设定为(αmax＝0．2,βmin＝0．4)，第 3组参数设定为(αmax＝0．2,βmin＝0．8)。

通过分析图1可知：在查询图边数相同条件下，判定算法在第1组参数下的平均执行时间大于第2组参数。在强度阈值βmin相同的条件下，误差阈值αmax越小，则算法的执行时间越短。在误差阈值αmax相同的条件下，强度阈值βmin越大，则算法的执行时间越长。

图2为优化前后的α－β子图同构判定算法的平均执行时间。该项实验将参数固定为具有代表性的第二组(αmax＝0．2,βmin＝0．4)。通过分析图2可知，判定算法在搜索顺序进行优化以后执行时间大幅缩短。

6 结束语

子图同构判定问题是NP完全问题，将不确定性引入子图同构匹配进一步增大了判定算法的计算代价。不确定图间α－β子图同构判定较之于期望子图同构判定具有较小的计算代价，但时间上界仍是指数级的。为将不确定图数据上的子图查询或与之类似的其他查询在多项式时间内完成，最为可行的方法是结合实际应用背景在图数据匹配的语义层面寻求突破。

参考文献：

[ 1 ] DALVI N N，SUCIU D： Efficient query evaluation on proba－

bilistic databases[C]／／ VLDB J． 16（4）： 52544 （2007）．

[ 2 ] SOLIMAN M A，ILYAS I F, Kevin Chen－Chuan Chang： Top－

k Query Processing in Uncertain Databases[C]／／ ICDE 2007：

896－905．

[ 3 ] 张硕，高宏，李建中． 不确定图数据库中高效查询处理． 计算

机学报[J]． 2009, 32（10）：2066－2079．

[ 4 ] 周傲英，金澈清，王国仁，等． 不确定性数据管理技术研究综述．

计算机学报[J]． 2009, 32（1）：1－16．

[ 5 ] GAO Hong, ZHANG Wei． Research status of the management

of uncertain graph data． Communications of the China Comput－

er Federation[C]／／ 2009, 5（4）：31－36．

[ 6 ] HINTSANEN P，TOIVONEN H． Finding reliable subgraphs fr－

om large probabilistic graphs[C]／／ Data Min． Knowl． Discov．

2008，17（1）：23．