一种支持模糊约束关系的图模式匹配方法

摘要

本发明提供一种支持模糊约束关系的图模式匹配方法，涉及图信息查询技术领域，用于解决现有技术无法在满足所有精确约束的基础上，支持对模糊约束关系的匹配的问题。所述方法包括：通过输入层，获取用户输入的查询图Q和存储的目标数据图G，所述查询图中既包含精确约束关系又包含模糊约束关系；通过精确匹配层，在所述目标数据图中，针对用户输入的查询图中的精确约束关系进行精确地图匹配，并在所述目标数据图中构建带有合并节点的引导图；通过模糊搜索层，在所述引导图中，找出并输出在满足所有精确约束基础上对模糊约束匹配质量最好的K个匹配图。本发明适用于在大规模目标数据图中，进行支持模糊约束关系与精确约束关系的混合查询。

说明书

技术领域

本发明涉及图信息查询技术领域，尤其涉及一种支持模糊约束关系的图模 式匹配方法。

背景技术

近些年，随着互联网技术的发展，越来越多的社会网络相继出现，比如以 Facebook、Twitter、新浪微博等为代表的大型在线社交网络网站，通过手机通信、 电子邮件等形成的人际关系网络等。目前，这些网络展现出了如下特征：1、网 络规模不断扩大，如何把用户看作定点，他们之间的关系看作边，那么所构建 的网络逐步成海量信息网络。2、用户属性与关系类型繁多，不同的社会网络通 常有不同的用户属性与关系类型。如何从这种海量的网络中提取有价值的信息 是目前许多研究的热点。除此之外，一些其他领域所需处理的图信息也表现出 相同的特征，比如软件剽窃检测中的软件调用关系图、数据流图，生物信息图 PPI(Protein-ProteinInteraction，蛋白质相互作用)网络及知识网络等。

图模式匹配是一种图信息查询方法，已经广泛用于各种图数据库的查询中。 一般而言，用户需要通过从实际应用中抽象出来的一组对图数据中节点关系与 属性的约束，来对目标图信息进行查询，获取由若干节点与边(节点间关系) 组成的目标图的子图，使得该数据子图完全满足用户给定的约束，该子图即为 匹配结果图，又称匹配图。这种约束通常表达为一个查询图，其中包含带有标 签属性的节点及其关系。

目前的图模式匹配方法中，首先按照目标数据图类型来分，可以分为针对 若干不连通的小规模图组成的图数据库的图模式匹配方法，以及针对一个大规 模连通图的图模式匹配方法，两者各为互补。此外，按照约束要求的类型，可 以分为精确图模式匹配方法和近似匹配方法。精确图模式匹配方法要求所匹配 得到的结果图必须严格满足所有给定的约束，其中包括所有的点与边的映射关 系，例如子图同构。而近似匹配方法试图降低对约束满足的程度来提升效率， 其中又包含两种，一种是通过一个用户给定的参数Φ，来控制约束满足的程度 的相似匹配方法，比如允许结果图中有最多Φ个边或点与查询图中不匹配。另 一种近似匹配方法首先定义一个目标约束函数，来衡量查询图与目标子图的相 似性，试图找出一个能使得目标约束函数最大的子图作为结果匹配图。这两类 近似匹配方法较精确匹配更为高效，但是会损失匹配精度，并且无法提前预知 哪些查询图中的信息会无法得到匹配或错误匹配(错误匹配点)。最后，按照约 束类型来分，可以分为两种，一种是连接查询图方法，即查询图为一个连通的 子图，例如图同构匹配、图模拟匹配等，而另一种是独立点查询图方法，即只 有带有约束属性的节点，没有任何连接约束信息，所查询出来的结果匹配图需 要满足所有节点约束，并保证匹配图是连通即可，可以看做是只带有模糊约束 的匹配方法。

尽管如此，现存的图模式匹配方法不能满足如下实际分析需求：随着网络 规模的增加与网络信息的异构性，用户很难构建应用所需精确的查询图。通常 只能给出一部分精确约束的连接关系与模糊约束关系(只要求节点的连通)，例 如在社会网络中寻找两个有特殊属性的团体，来完成一个创业项目或者营销策 略，团体中成员的连接约束关系与属性是通过应用背景可知的，但是对于团队 之间是如何连接的，并没有精确约束，但是要求他们以代价最小的方式连通。 如果依赖用户手工处理模糊约束，穷举所有可能的连接关系，然后再利用现存 的方法来进行查询，需要极大的工作量，时空开销极大。此外，如果直接利用 现存的独立点查询图方法，又无法保证满足给定的其他精确约束。所以，现有 的技术方法无法在满足所有精确约束的基础上，支持对模糊约束关系的匹配。

发明内容

本发明提供一种支持模糊约束关系的图模式匹配方法，能够在大规模目标 数据图中支持模糊约束关系与精确约束关系的混合查询，得到同时满足两种约 束要求的结果匹配图。

本发明提供的支持模糊约束关系的图模式匹配方法，包括：

通过输入层，获取用户输入的查询图Q和存储的目标数据图G，所述查询图 中既包含精确约束关系又包含模糊约束关系；

通过精确匹配层，在所述目标数据图中，针对用户输入的查询图中的精确 约束关系进行精确地图匹配，并在所述目标数据图中构建带有合并节点的引导 图；

通过模糊搜索层，在所述引导图中，找出并输出在满足所有精确约束基础 上对模糊约束匹配质量最好的K个匹配图。

本发明提供的支持模糊约束关系的图模式匹配方法，支持模糊约束关系与 精确约束的混合查询，能够在大规模目标数据图中，针对既含有图同构的精确 约束关系又含有模糊约束关系的查询请求进行处理，得到满足同时两种约束要 求的结果匹配图，扩展了图模式匹配的实用范围；能够降低使用人员构造查询 图的成本，更灵活的对查询约束进行建模，无需获取全部的精确约束关系，使 得在无法构造所有精确约束关系的情况下，也可以查询到匹配质量良好的结果 子图。

附图说明

为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所 需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明 的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下， 还可以根据这些附图获得其它的附图。

图1本发明实施例提供的支持模糊约束关系的图模式匹配方法的总体层次 结构图；

图2为查询图的输入格式的示意图；

图3为实际实施案例的合作关系网络图片段；

图4为以实际应用为背景所提出的待查询关系约束示意图；

图5为通过图3转换得到的目标数据图；

图6为通过图4转换得到的带有模糊关系约束的查询图及其输入形式的示意 图；

图7为经过精确匹配层，输出的带合并节点的引导图；

图8为经过模糊搜索层，输出的还原合并节点后的最佳匹配图；

图9为通过图8转换到实际应用的查询结果图；

图10为通过图5构建的高速索引数据(当λ＝0，H＝2)的示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清 楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是 全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造 性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。

本发明实施例提供一种支持模糊约束关系的图模式匹配方法，该方法的总 体步骤框架如图1所示，主要包括输入层、精确匹配层、模糊搜索层三部分。 输入层包括用户输入器和目标数据图导入器，精确匹配层包括图同构器和图仿 真器，而模糊搜索层包括单源搜索器和高速单源搜索器。

所述支持模糊约束关系的图模式匹配方法具体包括如下步骤：

S11、通过输入层，获取用户输入的查询图Q和存储的目标数据图G，所述 查询图中既包含精确约束关系又包含模糊约束关系。

该查询图Q与目标数据图G均为带标签的无向图，查询图是无权图，而目 标数据图是有权图，即节点之间的边上存在不同的权重信息。该标签信息面向 具体应用，代表节点的属性。

本发明所处理的查询图Q包含若干个独立的约束模块图(假设为P个， Q＝{q₁，q₂，…，q_i，…，q_p｝)，每个约束模块q_i(V，E，L)为一个带有节点标签 的连通的无向无权图，其中定义面向应用的精确约束，其中包括节点集合V， 节点间连接约束关系E，标签集合L；对于每个节点v∈V，包含节点序号v.Id， 节点标签属性集合子图之间为模糊约束关系，所以一共有C(P，2)组合 数个模糊约束关系。

查询图的输入格式如图2所示，其中第一行定义约束模块总数P，每个约束 模块有两部分组成，第一部分为节点属性集合定义区，第二部分是节点连接约 束关系定义区，每个部分结束都由“#”分隔。

本发明所处理的目标数据图G(V，E，L)为一个带有节点标签的无向有权图。 其中包括节点集合V，节点间连接关系E和标签集合L；每个连接关系带有一 个权重信息e.weight(e∈E)；每个节点信息包括节点序号v.Id，节点标签属性集 合

本发明所述用户输入器的功能在于从硬件存储器中读入按照本发明所规定 的查询图输入格式定义的查询图，或者通过图形界面输入查询图；目标数据图 导入器负责从硬件存储器中读入目标数据图与预处理所产生的数据索引。

S12、通过精确匹配层，在所述目标数据图中，针对用户输入的查询图中的 精确约束关系进行精确地图匹配，并在所述目标数据图中构建带有合并节点的 引导图。

本发明通过精确匹配层提供了两种可选方法：图同构器和图仿真器，用于 保证精确约束得以高效地匹配，并生成带合并节点的引导图。图同构器和图仿 真器首先通过不同方法，针对每个查询图中的约束模块，分别在目标数据图中， 找出能够与精确约束匹配的候选子图；再依照这些候选子图，按照相同的方法 生成带有合并节点的引导图。

同构器通过现存的图同构(graphisomorphism)匹配方法，例如VF2， Ullmann，QuickSI等，对查询图中每个约束模块q_i分别进行图同构匹配，即可 直接找出目标数据图G中，所有的匹配精确约束的候选子图，定义为集合IM_i， 这些候选子图同构于至少一个约束模块。

图仿真器通过现有的图仿真方法(graphsimulation)，对查询图中每个约束 模块q_i分别进行图仿真匹配，得到目标数据图中的所有图仿真候选子图，定义 为SM_i。

通过图仿真器所产生的图仿真候选子图中一定包含所有的图同构候选子 图，但是反之不然。因此图仿真候选子图中可能包含非同构子图。图同构器时 间开销与目标数据图和查询图规模成指数关系，而图仿真器只需要O(n^2)的时 间开销，n为目标数据图中的总节点数。

图同构器采用索引技术，例如频繁子图索引，可以提升对小规模图组成的 图数据库的匹配速度，但是由于空间开销大，依然无法对大规模图产生有效索 引。所以图仿真器适用于大规模网络图上的匹配查询，而图同构器适用于若干 不连通的小规模图组成的图数据库匹配查询。

在获取所有的候选子图集合后，生成的引导图将每个候选子图合并为一个 带标识的合并节点，并设置标识为该候选子图匹配的约束模块的序号。如果存 在候选子图是彼此重合的，那么将合并所有重合候选子图到同一个合并节点中， 设置标识为所有对应的约束模块序号的并集。生成引导图的具体操作的伪代码 如下：

输入：1、查询图Q＝{q₁，q₂，…，q_i，…，q_p}.2、目标数据图G(V，E，L). 3、通过图同构器或图仿真器得到的候选子图集合SM＝{SM₁，SM₂，…，SM_i，…， SM_p}或IM＝＝{IM₁，IM₂，…，IM_i，…，IM_p}。

初始化一个候选子图集合IM:SM；

对于每个FM_i∈FM做循环(1)：

对于每个子图fm∈FM_i做循环(2)：

创建一个合并节点的指针mn＝null；

(1)如果任取一个节点v∈fm，都有v∈G，那么：

在G中，初始化并新增一个特殊的合并节点，并由mn指向，该节点拥有 标识集合B＝{i}；

把fm作为mn的内部图进行存储(mn.fm)；

否则：

对于每一个节点v∈fm且做循环(3)：

获取G中已存在的合并节点mn’，满足v∈mn’.fm；

(2)如果mn＝null，那么：

增加标识i到mn’.B中；

合并fm的其他节点与边到mn’.fm中；

否则

增加mn.B到mn’.B；

合并mn.fm到mn’.fm中；

把mn的连接边合并到mn’上，设置权重为最小边值；

删除合并节点mn；

结束条件判断(2)

令mn指针指向mn’；

结束循环(3)；

结束条件判断(1)

从G中删除fm中所有节点与边集合；

如果fm中有节点与fm的外部点(其他不在fm中的节点)存在连接边，那 么创建mn与该外部点的连接关系(创建外部边)，并设置边权重为fm中节点与 该外部点所有连接边权重的最小值；

结束循环(2)；

如果fm中存在中枢节点，那么设置mn为中枢节点(此操作仅限于取用高 速单源搜索器时)；

结束循环(1)；

返回修改后的G作为带有合并节点的引导图G_m。

S13、通过模糊搜索层，在所述引导图中，找出并输出在满足所有精确约束 基础上对模糊约束匹配质量最好的K个匹配图。

本发明在给定目标数据图G与查询图Q后，所输出的匹配图M需要满足如 下要求：

1、M是G的一个连通子图；

2、对于每一个查询图中的约束模块q_i，M中都存在一个子图m_i，满足m_i 同构(isomorphism)于q_i(m_i∝_isoq_i)的精确约束，其中i为约束模块序号；

3、在这些子图中，任取一对m_i与m_j且i≠j，m_i.V∩m_j.

模糊约束的匹配通过m_i与m_j直接相连或通过其他节点所组成的路径间接相 连。匹配图M按照模糊约束的匹配质量予以衡量，给定一个匹配图M，匹配质 量衡量函数定义如下：Quality(M)＝∑_p(i，j)∈Mlength(p(i，j))，其中p(i，j)为m_i与 m_j之间的最短连接路径，length(p(i，j))为该路径长度，即路径中所有边上的权 重合。质量函数值越小说明该匹配图与查询图的匹配效果越好，因为关系越密 切，权重合越小。本发明支持在无需找出所有满足要求的匹配图的情况下，找 出与查询图匹配最好的K个匹配图，并按照质量函数值从小到大排序。

本发明把通过精确层输出的带有合并节点的引导图作为输入传递给模糊搜 索层的两个搜索器，进行模糊匹配搜索。这两个搜索器是单源搜索器和高速单 源搜索器。两者之间的区别是后者利用了一种新型的高速索引方法，能够缩短 搜索的时间开销，但是需要以牺牲质量为代价，所以他们适用于不同场合。搜 索器的目的在于对查询图中约束模块之间的模糊约束关系进行匹配搜索，进而 找出质量最好的K个匹配图。

这两个搜索器的核心算法在于创建一个约束模块个数的优先队列组，并从 每个合并节点作为源点，依次传播标识信息，一个优先队列负责传播一种标识， 直到找到一个拥有所有种类的标识信息的节点。通过该节点作为根节点，就可 以通过遍历的路径找到一棵树。对于每个约束模块，树中至少包括一个合并节 点，其拥有该约束模块的标识，并且他的内部图能够匹配该约束模块的所有约 束条件(精确同构匹配)。此外，如果结果树种存在一个合并节点匹配多个约束 模块(即作为多个标识的源节点)，那么其内部图中，至少存在两个不重合的子 图，能够分别精确同构匹配于对应的约束模块。最后，按照结果树中的合并节 点的标识，即可还原对应的内部图信息，组成最终匹配图，而还原的内部图中 满足精确约束要求的候选图之间所连接的路径信息是对约束模块间模糊约束的 匹配。

单源搜索器的具体操作的伪代码如下：

输入：1、查询图Q＝{q₁，q₂，…，q_i，…，q_p}，共p个约束模块；2、带合 并节点的引导图G_m，3、待寻找的匹配图个数K。

定义：1、MN为G_m中所有合并节点的集合；2、node.parent(i)为该node节 点在第i个队列中，遍历路径上的父节点；3、node.source(i)为该node节点在第 i个队列中的源节点；4、node.sharedLabels是一个标识集合，其中包含所有来源 于同一合并节点的标识；5、优先队列中的元素为(node，distance)，即(节点 信息，距离其源节点的距离)；6、一个合并节点为合法的，当且仅当，他的内 部图中存在至少一组不重合的子图分别满足其标识对应的约束模块的所有约束 条件(同构匹配)。

初始化一个堆

初始化一个含有p个优先队列的集合queues＝{queue₁，…queue_p}；

对于每个合并节点mn∈MN做循环(1)：

对于每个标识b∈mn.B做循环(2)：

增加mn到queue_b中，并设置初始距离为0，即入队列元素为(mn，0)，并 设置mn.parent(b)＝mn，mn.source(b)＝mn；

结束循环(2)；

如果mn.B中包含多个标识，那么设置mn.sharedLabels＝mn.B；

设置

结束循环(1)；

当存在至少一个queue中节点不为空时，做循环(3)：

依次遍历queues中不为空的所有队列queue_i(1)：

得到头元素(v，v.distance)并使其移出队列；

如果那么v.B＝v.B∪i；(传播标识)

如果(v.B中元素的个数等于p)且(或者v的所有源节 点都是合法的)那么(1)：

从v开始依据路径信息(每个路径上节点的parent信息)生成一棵结果树 tree；

对于v的每个标识的源合并节点，穷举能匹配该标识所对应的约束模块的 子图进行还原，并利用外边连接信息还原其内部连接路径；

计算该结果数树的代价tree.cost＝原结果树中所有边权重合+还原内部图所 引入的内部连接路径的权重合Δcost；

把结果树tree加入到TreeHeap中；

如果TreeHeap中的结果树数量大于K，那么继续遍历过程直到每个队列达 到Δcost的距离，排序所有产生的结果树，返回前K个；(终止条件)

结束判断(1)

如果v是中枢节点，那么通过高速索引生成结果树，如不为空，则把其还 原版本加入到TreeHeap中；(高速单源搜索器步骤)

遍历v的边表元素(u，weight)，其中u为其边表中邻接节点，weight是其边 权重(2)；

如果那么(2)：

1、当时，设置u.source(i)＝v.source(i)，u.parent＝v，并把(u， weight+v.distance)加入到queuei中等待后续遍历，如果v.source(i)之前过传播其 他标识给u，把所有来源于该合并节点的标识一并加入u.sharedLabels中；

2、当满足如下2个条件(u∈queue_i)且(weight+v.distance<u.distance)时， 更新u.source(i)＝v.source(i)，u.parent＝v，并更新队列queue_i中u的距离为 weight+v.distance；如果i∈u.sharedLabels且v.source(i)之前没有传播其他标识给 u,那么从u.sharedLabels中，删除i与其来源相同的其他标识。如果v.source(i)之 前传播过其他标识给u，把所有来源于该合并节点的标识一并加入u.sharedLabels 中；如果引导图G_m是由图仿真器得到的，那么当(u∈queue_i)且 (weight+v.distance≥u.distance)时，调用验证步骤check(u.source(i),v.source(i)), 当返回true时，更新队列queue_i中u的距离为weight+v.distance，同理更新 u.sharedLabels。

否则：

如果满足i∈u.B且i∈u.sharedLabels且v.source(i)之前没有传播其他标识 给u，那么更新u.sharedLabels，设置u.source(i)＝v.source(i)，u.parent＝v，从u.B 中删除i，并把(u，weight+v.distance)重新加入queue_i中；

如果引导图G_m是由图仿真器得到的，当满足i∈u.B且(或者v.source(i)之前有传播其他标识给u)时，调用验证步骤 check(u.source(i),v.source(i)),当返回true时，那么更新u.sharedLabels，设置 u.source(i)＝v.source(i)，u.parent＝v，从u.B中删除i，并把(u，weight+v.distance) 重新加入queue_i中。

结束判断(2)；

结束遍历(2)；

结束遍历(1)；

结束循环(3)

当引导图通过图仿真器得到时，为了保证得到的匹配图中满足图同构的约 束，需要在节点被舍弃(停止标识传播给邻接节点)时，通过验证步骤 check(u.source(i),v.source(i))进一步判断。u.source(i),v.source(i)中是否包含同构于 约束模块i的子图。具体验证步骤如下：通过图同构算法验证合并节点v.source(i) 中(内部图)是否包含同构于约束模块i的子图，如果不包含，返回false，否则 如果包含，继续判断u.source(i)中(内部图)是否包含同构于约束模块i的子图, 如果不包含，返回true,否则，如果包含，需要对比两者同构子图到节点u的最 短距离，如果v.source(i)中的同构子图与u的最短路径距离更短，那么返回true， 否则返回false。

当在搜索器中判断一个合并节点是否合法时，如果在精确匹配层通过图仿 真器得到的引导图，需要在此处调用图同构算法进行验证，否则直接在内部图 中判断是否匹配子图相交即可。

本发明所述的高速单源搜索器与上述单源搜索器的步骤区别在于：1、高速 单源搜索器需要提前对目标数据图做预处理，生成高速搜索索引；2、在单源搜 索器的上述步骤中，加入高速搜索步骤，具体见单源搜索器操作伪代码中的高 速搜索步骤。创建高速索引的具体步骤的伪代码如下：

输入：1、目标数据图G，2、中枢节点数量H，3、中枢节点间距离阈限θ；

计算G图中每个节点的度(degree)与介数(betweenness)，存储于数据表中， 每行元素为<node，degree，betweenness>；

对每个节点按照归一化的中枢性从大到小进行排序，中枢性的计算方法为： HubValue＝(degree+λ*betweenness)，其中λ为用户给定的参数；

选取前H个节点，作为中枢节点集合；

计算中枢节点两两之间最短路径长度(边权重合)length与路径信息；

针对每个中枢节点v，构建高速索引，格式为<key，value>，其中key为从 该中枢节点可达的其他中枢节点u，value是一个数组，每个元素为v、u节点之 间最短路径长度和路径本身所组成的数据结构；

只保留路径长度length(v，u)<θ的高速索引，存储高速索引到存储器中。

本发明实施例还提供一种贪婪算法，能够通过高速索引生成结果树，其具 体步骤如下：

假设当前节点为n；

(1)如果n是合并节点，那么遍历其内部图中每个中枢节点v做如下操作， 否则v＝n做如下操作：从高速索引中，读取v的高速索引内容，获取所有的从v 可达的中枢节点，存入数组Hubs中；

(2)对于每个标识构建一个节点集合A_b，其中每个节点满足 u∈Hubs且b∈u.B，如果结束算法并返回

(3)遍历每个集合A_b，在每个集合A_b中选出到v最短路径最短的节点u_b。 当A_b中没有新候选节点时，返回

(4)获取每个u_b在b队列中的源合并节点，并判断条件：如果存在两个选 中的中枢节点u_i，u_j，他们的源合并节点是重合的，判断该合并节点的内部图中 是否存在不相交的子图分别同构匹配于标识所对应的约束模块，如果不存在， 依次尝试从A_i与A_j中删除u_i，u_j，并选择次优节点，直到上述条件满足，最后 删除u_i，u_j中到该合并节点路径较长的节点；

(5)利用高速索引中的路径，把选中的中枢节点、相应的合并节点与节点 n连接成结果树。

本发明的单源搜索器搜索得到的结果匹配图与目标数据图中存在的最佳结 果匹配图之间的质量关系如下：

假设给定目标数据图G与带模糊约束的查询图Q＝{q₁，q₂，…，q_i，…，q_p}. 共p个约束模块，通过单源搜索器得到的最优结果匹配图M的质量为Q_M；在G 中实际存在的最优匹配图R的质量为Q_R；那么根据单源搜索器的操作步骤，质 量约束等式Q_M/Q_R≤p一定成立。

而对于高速单源搜索器得到的最优结果匹配图M的质量Q_M，满足质量约 束等式Q_M/Q_R≤(θ(p-1)+εp)/(ε+1)，其中ε为M图中从所有原合并节点到中枢节点 距离长度的最大值，p为查询图中约束模块总个数，θ为中枢节点间距离阈限。

当用户设置θ为0时，高速单源搜索器就退化成了单源搜索器，结果匹配质 量与单源搜索器一致。通过调节参数θ，高速单源搜索器能够更好的平衡输出质 量与执行效率。两种单源搜索器适用于不同场合。

本发明实施例提供的支持模糊约束关系的图模式匹配方法，支持模糊约束 关系与精确约束的混合查询，能够在大规模目标数据图中，针对既含有图同构 的精确约束关系又含有模糊约束关系的查询请求进行处理，得到满足同时两种 约束要求的结果匹配图，扩展了图模式匹配的实用范围；能够降低使用人员构 造查询图的成本，更灵活的对查询约束进行建模，无需获取全部的精确约束关 系，使得在无法构造所有精确约束关系的情况下，也可以查询到匹配质量良好 的结果子图。

下面通过对某网络公司软件开发人员历史合作网络中的实际查询需求的处 理，说明本专利所述方法的具体实施。

该公司首先收集开发人员的合作历史数据，并构建了合作关系网络图，其 中的一个典型片段如图3所示，其中节点代表人员，属性标注于节点下方((a) PRG：程序员，(b)DB：数据工程师，(c)TS：测试工程师，(d)PM:项目经理)。 节点间的连接代表两个节点共同直接合作参与过项目，边权重值代表合作密切 程度，权重值越大越疏远。

为了叙述的简洁，在该实例中，假设边权重均为1。利用图3，该公司试图 为一个新软件开发项目组件最适合的团队。团队要求由3个独立小组，共5位人 员组成，小组具体要求如下：(1)组1包含两位程序员，且他们共同参与过项目； (2)组2包含一位程序员与一名数据工程师，且他们共同参与过项目；(3)组3 包括一名测试人员；(4)三个组间存在成员间直接或间接的历史合作关系，且 合作越密切越好。

利用本专利能够更好的从合作关系网络图中查询出满足上述需求的候选团 队。首先对团队的要求进行建模，表达成如图4所示的约束关系，其中由三个约 束模块所组成，每个约束模块刻画了对小组成员关系的约束。分别对合作关系 网络图(图3)与约束关系(图4)建模成目标数据图与带模糊约束的查询图， 分别如图5、图6所示。图5中{}内为节点的属性值，图6(右)展示了查询图的 输入格式。

在读取目标数据图后，对其进行预处理，构建高速索引，假设在高速单源 搜索器中设置的参数为λ＝0，H＝2，那么按照节点度排序后，可知拥有最高度的 节点为6、1、2，取前两个构建高速索引，在目标数据图中，获取它们之间的最 小路径(1，5，6)，权重为2，构建的高速索引如图10所示。

查询的具体操作过程如下：

首先通过输入层读入图5、图6的信息(如果采用高速单源搜索器，还需读 入图10的索引信息)。把目标数据图G与查询图Q传递给精确匹配层的图同构器 或图仿真器(按照用户的选择)，经过图同构器的具体操作步骤，分别对Q中每 个子约束模块进行匹配和合并，生成引导图，如图7所示。图7中，包括了三个 合并节点(m₁，m₂，m₃)，其中m₁的内部图同构匹配于(通过图同构器)或仿真 匹配于(通过图仿真器)约束模块q₁和q₂，同理，m₂匹配于q₁和q₂，m₃匹配于q₃。 并且m₃为中枢节点因为其内部图中，包括了节点6。

下一步，精确匹配层把得到的引导图传递给模糊搜索层。模糊搜索层采用 单源搜索器或高速单源搜索器对引导图中合并节点的关系进行的挖掘搜索，最 终找到的最佳结果树经还原合并节点后，如图8所示(假设K＝1)。在该图中，节 点6，9匹配q₁，节点7，8匹配q₂，节点10匹配q₃，该匹配的质量值为4，为最佳 匹配图。

最终的组件团队的最佳候选图如图9所示。

与现有的图模式匹配方法相比，本方法提出的匹配方法能够有效地在满足 精确约束关系的基础上，抵抗对目标图中所存在的噪声数据，有效挖掘满足模 糊约束的路径连接信息。在目标数据图中存在噪声数据时，通过现存的精确匹 配方法可能无法找出合理的匹配结果，而通过现存的近似匹配方法又无法保证 已获得的精确约束得到匹配。

与现有的图模式匹配方法相比，本方法同时利用了搜索方法(搜索器)与 索引查询(高速索引)方法，能够有效地平衡查询结果质量与执行效率。

本发明实施例提供的支持模糊约束关系的图模式匹配方法，可以适用于在 大规模目标数据图中，进行支持模糊约束关系与精确约束关系的混合查询，但 不仅限于此。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程， 是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于计算机 可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。 其中，所述的存储介质可为磁碟、光盘、只读存储记忆体(Read-OnlyMemory， ROM)或随机存储记忆体(RandomAccessMemory，RAM)等。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于 此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到 的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围 应该以权利要求的保护范围为准。