基于图谱和可达路径数的无向加权图的子图查询方法

摘要

本发明公开了一种基于图谱和可达路径数的无向加权图的子图查询方法，步骤1，计算查询图和已知图数据集中每个图的节点标记的编码、边带权重的邻接边标记的编码和可达路径数的编码；步骤2，生成查询图和已知图数据集中每个图的图谱；步骤3，用已知图数据集中每个图的节点标记的编码、边带权重的邻接边标记的编码、可达路径数的编码和图谱构建索引树；步骤4，将查询图与索引树节点图由上至下逐层进行比对，同时进行筛选，直至筛选到最底层，所得图即为与查询图相近的候选图。本发明更好地描述了图的拓扑信息。同时，对这些特征进行编码，不仅容易存储，而且操作简单，可以加快特征之间的比较，从而加快整个子图查询的速度。

说明书

技术领域

本发明属于计算机数据挖掘技术领域，具体涉及一种基于图谱和可达路径数的无向加权图的子图查询方法。

背景技术

近几年，包括计算机在内的许多领域，都应用到图这一数据结构去描述数据信息。例如，在化学中，分子或原子被建模成节点，它们之间的化学键被建模成边；在计算机网络中，个人计算机被建模成节点，而它们之间的路由关系被建模成边。图的广泛应用触发了图数据库的模式查询，其中，子图查询成为了最重要的研究方向之一。子图查询问题可以归结为：给出一个图数据集和一个查询图，找出所有包含查询图的数据图的集合，即使得查询图是这些数据图的子图，而这个过程中包含着子图同构的判定问题，也就是一个已被证明是NPC的问题。

目前，都采用过滤-验证框架去提高查询效率，即在查询处理时，查询图先经过索引进行过滤，产生少量的候选图，然后再对候选图进行子图同构的验证，得到最终的结果集。在这个过程中，找寻高效的索引特征和索引方法成为了工作重心。

现今方法中寻找高效的索引特征和索引方法各有优点和不足。例如，Graphgrep方法中，将指定大小的路提取出来进行索引建立，在查询时，对于那些不包含在查询图中的路的数据图将被视为FalsePositives而被过滤，再经过验证得到最终结果集。但是这种方法中，由于路包含的信息太简单，不足以表达出图的整个结构信息，导致效率非常低。另一类方法，gIndex，FG-Index，Treepi，Tree+delta，SwiftIndex等，利用现存图挖掘技术挖掘频繁子结构，再选取部分子结构创建索引。这类方法一定程度上提高了查询的效率，但是，有一个通病：过滤效率取决于提取的特征的质量。随着图数据库后面不断变化，不断地进行添加和删除等更新操作，这些方法都必须重新开始挖掘和创建索引，这部分得花费很多时间。最后一类算法，如Gcoding方法，是将提取的特征映射到数字空间生成编码，在编码的基础上构建一个索引树，这样可以很好地处理图数据库频繁更新的情况。因为编码方法是对每个数据图单独进行处理，所以在图数据库更新时，只需对变更的数据图进行编码处理，不用全部重新进行编码。但是Gcoding在计算特征值时，使用中间生成树的结构进行特征提取，而树的结构会丢失图中的部分结构信息，这样降低了方法的过滤效率，一定程度上影响了查询效率。

发明内容

本发明的目的是提供一种基于图谱和可达路径数的无向加权图的子图查询方法，解决了现有技术中存在的Gcoding索引方法中中间生成树的结构会丢失图的部分结构信息，降低了过滤效率，从而降低查询效率的问题。

本发明所采用的技术方案是,基于图谱和可达路径数的无向加权图的子图查询方法，其特征在于：具体包括以下步骤：

步骤1，计算查询图和已知图数据集中每个图的节点标记的编码、边带权重的邻接边标记的编码和可达路径数的编码；

步骤2，生成查询图和已知图数据集中每个图的图谱；

步骤3，用已知图数据集中每个图的节点标记的编码、边带权重的邻接边标记的编码、可达路径数的编码和图谱构建索引树；

步骤4，将查询图节点标记的编码、边带权重的邻接边标记的编码、可达路径数的编码、图谱与索引树节点图的节点标记的编码、边带权重的邻接边标记的编码、可达路径数的编码、图谱由上至下逐层进行比对，同时进行筛选，直至筛选到最底层，所得图即为与查询图相近的候选图。

步骤5，将候选图与查询图进行子图同构验证，得到结果图数据集。

本发明的特点还在于：

步骤1中，编码的生成过程为：

节点标记的编码生成方式为，构建节点标记的哈希函数，该哈希函数的产生方式为，以图中节点的种类数作为字符串长度，一类节点对应一组字符串，在每类节点对应的该组字符串中取一位用数字1进行标记，其余位为0，每类节点在字符串中标记的位置不重合，同类节点字符串相同，将每个节点对应的字符串相加，该结果即为该图的节点编码；

边带权重的邻接边标记的编码生成方式为，构建边带权重的邻接边标记的哈希函数，该哈希函数的产生方式为，将图中边的权重按照数量级划分为a级，字符串对应的分为a部分，从右到左，每部分依次表示边的权重的数量级为10ⁱ，i≤a；图中节点的种类数b为每部分字符串长度，每b位字符串从右到左依次表示第j类节点，j≤b，则该字符串共有(a×b)位；针对具体节点，找出其邻接边，一条边对应一组字符串；每组字符串的确定方法为，先确定具体边的边带权重的数量级，进而确定该数量级对应的b位字符串，从图中确定该边的另一端节点对应的种类，用数字1在该b位字符串中对应的位置进行标记，其余位为0；对每条边的字符串求和，得到的(a×b)位字符串即为上述节点的边带权重的邻接边标记的编码；

可达路径数的编码生成方式为，先构建图的可达路径数的哈希函数，该哈希函数的产生方式为，以图中节点的种类数作为字符串长度，一类节点对应一组字符串，在每类节点对应的该组字符串中取一位用数字1进行标记，其余位为0，每类节点在字符串中标记的位置不重合，同类节点字符串相同；计算图的邻接矩阵，邻接矩阵的阶数n与图中的节点数相同，第r行第s列元素表示第r个节点到第s节点的一步可达路径的数目，r≤n，s≤n；根据要求的图的c步可达路径数，求邻接矩阵的c次幂方阵；邻接矩阵c次幂方阵第w行第v列元素表示第w个节点到第v节点的c步可达路径的数目；按照节点种类将每条路径转化为上述哈希函数对应的字符串；对每个节点的字符串求和，该结果即为该图的可达路径数编码。

步骤2中，图谱的生成过程为：

步骤2.1，对于图中的每个节点先得到它的N层生成图，其中，N为任意自然数；

步骤2.2，求出每个节点N层生成图的邻接矩阵；

步骤2.3，根据公式x＝(x-c)/(d-c)，将邻接矩阵进行标准化，其中，x为邻接矩阵中的元素，c为邻接矩阵中的最小值，d为邻接矩阵中的最大值，计算标准化矩阵的特征值；

步骤2.4，将求得的每个节点的特征值进行递减排序，取出前2个特征值，即最大特征值和次大特征值；将所有节点的最大特征值进行递减排序，将所有节点的次大特征值进行递减排序；得到两个序列；该两个序列即为该图的两个图谱。

步骤2.1中，节点的N层生成图生成方法为，针对具体节点，将该节点外围的第N层节点及该节点到第N层节点之间的所有节点和边加入图中，该图即为该节点的N层生成图。

步骤3中，索引树的构建方法为，将已知图数据集中的图两两自由组合进行比较，将各编码中对应位数字大的提取出来形成新的节点图；重复上述过程，直至提取到只有一幅节点图为止；所述已知图数据集和依次形成的节点图共同构建为二叉树。

步骤4中，查询图与索引树节点图逐层进行比对，同时进行筛选，筛选条件为：

一、索引树节点图的节点标记的编码与查询图节点标记的编码对应位相等；

二、索引树节点图的边带权重的邻接边标记编码的每位数字大于等于查询图边带权重的邻接边标记编码对应位的值；

三、索引树节点图的可达路径数编码每位的数字大于等于查询图可达路径数编码对应位的值；

四、索引树节点图的图谱中选取出来的最大、次大特征值分别大于等于查询图图谱中选取出来的最大、次大特征值；

按照上述条件筛选出的索引树最底层的图即为与查询图相近的候选图。

本发明的有益效果是：

本发明选取的特征包括：节点标记、边带权重的邻接边标记、可达路径数和图谱。选取的节点标记和边带权重的邻接边标记记录了图的基本信息，可达路径数说明了路径的基本信息(路径的两个端点、路径的长度、路径的个数等)，图谱更好地描述了图的拓扑信息。因此，使用它们的组合信息较完整地记录了一张数据图的信息。同时，对这些特征进行编码，不仅容易存储，而且操作简单，可以加快特征之间的比较，从而加快整个子图查询的速度。

附图说明

图1是本发明基于图谱和可达路径数的无向加权图的子图查询方法所依据的过滤-验证框架图；

图2是本发明基于图谱和可达路径数的无向加权图的子图查询方法使用的测试数据图集和测试查询图；

图3是本发明基于图谱和可达路径数的无向加权图的子图查询方法节点标记的哈希函数；

图4是本发明基于图谱和可达路径数的无向加权图的子图查询方法测试数据图集和测试查询图生成的节点编码；

图5是本发明基于图谱和可达路径数的无向加权图的子图查询方法测试数据图集和测试查询图生成的边编码；

图6是本发明基于图谱和可达路径数的无向加权图的子图查询方法可达路径数的哈希函数；

图7是本发明基于图谱和可达路径数的无向加权图的子图查询方法测试查询图的节点对应的两层生成图；

图8为本发明基于图谱和可达路径数的无向加权图的子图查询方法测试数据图集构建的索引树；

图9是本发明基于图谱和可达路径数的无向加权图的子图查询方法得到的与测试查询图相似的候选图。

具体实施方式

下面结合附图和具体实施方式对本发明进行详细说明。

如图1所示，本发明基于图谱和可达路径数的无向加权图的子图查询方法，具体包括以下步骤：

步骤1，计算查询图和已知图数据集中每个图的节点标记的编码、边带权重的邻接边标记的编码和可达路径数的编码。

节点标记的编码生成方式为，构建节点标记的哈希函数，该哈希函数的产生方式为，以图中节点的种类数作为字符串长度，一类节点对应一组字符串，在每类节点对应的该组字符串中取一位用数字1进行标记，其余位为0，每类节点在字符串中标记的位置不重合，同类节点字符串相同，将每个节点对应的字符串相加，该结果即为该图的节点编码。

以图2所示的查询图(Q)为例，查询图(Q)包含了A，B，C，D四类节点，其中，A，C，D节点各一个，B节点两个。用上述方法生成查询图(Q)的节点哈希函数，A，B，C，D的节点标记编码如图3所示，A为0001，B为0010，C为0100，D为1000，将各节点编码相加，因B节点有两个，因此，B节点的编码0010加两次，得到查询图Q的节点编码为1121。按照上述方法，可生成图2所示的测试数据图集(G₁,G₂,G₃,G₄)的节点编码，如图4所示。

边带权重的邻接边标记的编码生成方式为，构建边带权重的邻接边标记的哈希函数，该哈希函数的产生方式为，将图中边的权重按照数量级划分为a级，字符串对应的分为a部分，从右到左，每部分依次表示边的权重的数量级为10ⁱ，i≤a；图中节点的种类数b为每部分字符串长度，每b位字符串从右到左依次表示第j类节点，j≤b，则该字符串共有(a×b)位；针对具体节点，找出其邻接边，一条边对应一组字符串；每组字符串的确定方法为，先确定具体边的边带权重的数量级，进而确定该数量级对应的b位字符串，从图中确定该边的另一端节点对应的种类，用数字1在该b位字符串中对应的位置进行标记，其余位为0；对每条边的字符串求和，得到的(a×b)位字符串即为上述节点的边带权重的邻接边标记的编码；

以图2所示的查询图(Q)为例，查询图Q的边权分别为30，60，150，1300，将边权按数量级进行划分，可分为10的1次幂，即30和60这两个边权；10的2次幂，即150这个边权；10的3次幂，即1300这个边权。根据划分的这三个数量级，将编码的计数器串对应的分为三部分，因查询图Q有A，B，C，D四类节点，因此，字符串的每部分为四位，因此，编码为(4×3)位。以查询图Q中的节点v₀为例，边编码的生成过程为，第一步，获得每个节点所有邻接边，节点v₀的邻接边包括一条以10的2次幂为边权，C为边的另一个节点，一条以10的1次幂为边权，D为边的另一个节点。因此，该节点的边编码为两组。第二步，通过上述方法生成边标记的哈希函数，这两条边对应的编码分别为0000>0的边编码0000>1，v₂，v₃，v₄的边编码，最后，将五个节点对应的五个字符串按位相加，即可得到查询图Q的边编码。按照同样方法可得到图2的测试数据图集(G₁,G₂,G₃,G₄)的边编码如图5所示。

可达路径数的编码生成方式为，先构建图的可达路径数的哈希函数，该哈希函数的产生方式为，以图中节点的种类数作为字符串长度，一类节点对应一组字符串，在每类节点对应的该组字符串中取一位用数字1进行标记，其余位为0，每类节点在字符串中标记的位置不重合，同类节点字符串相同；计算图的邻接矩阵，邻接矩阵的阶数n与图中的节点数相同，第r行第s列元素表示第r个节点到第s节点的一步可达路径的数目，r≤n，s≤n；根据要求的图的c步可达路径数，求邻接矩阵的c次幂方阵；邻接矩阵c次幂方阵第w行第v列元素表示第w个节点到第v节点的c步可达路径的数目；按照节点种类将每条路径转化为上述哈希函数对应的字符串；对每个节点的字符串求和，该结果即为该图的可达路径数编码。

即，邻接矩阵第一行第一列的元素表示第一个节点到第一个节点的一步可达路径的条数，有几条，就用对应的数字进行标记；邻接矩阵第一行第二列的元素表示第一个节点到第二个节点的一步可达路径的条数，有几条，就用对应的数字进行标记；以此类推，直到邻接矩阵第一行最后一列的元素，表示第一个节点到最后一个节点的一步可达路径的条数，有几条，就用对应的数字进行标记；如此，邻接矩阵第一行即确定；邻接矩阵第二行第一列的元素表示第二个节点到第一个节点的一步可达路径的条数，有几条，就用对应的数字进行标记；邻接矩阵第二行第二列的元素表示第二个节点到第二个节点的一步可达路径的条数，有几条，就用对应的数字进行标记；以此类推，直到邻接矩阵第二行最后一列的元素，表示第二个节点到最后一个节点的一步可达路径的条数，有几条，就用对应的数字进行标记；用上述方法确定邻接矩阵的第三行、第四行直到第n行；即确定出邻接矩阵；根据要求的图的c步可达路径数，求邻接矩阵的c次幂方阵；邻接矩阵的c次幂方阵的第一行第一列的元素即为第一个节点到第一个节点的c步可达路径的条数；邻接矩阵的c次幂方阵的第一行第二列的元素即为第第一个节点到第二个节点的c步可达路径的条数；以此类推，直到邻接矩阵的c次幂方阵的第一行第n列的元素即为第一个节点到第n个节点的c步可达路径的条数；邻接矩阵的c次幂方阵的第一行所有元素之和即为第一个节点的c步可达路径数；邻接矩阵的c次幂方阵的第二行第一列的元素即为第二个节点到第一个节点的c步可达路径的条数；邻接矩阵的c次幂方阵的第二行第二列的元素即为第二个节点到第二个节点的c步可达路径的条数；以此类推，直到邻接矩阵的c次幂方阵的第二行第n列的元素即为第二个节点到第n个节点的c步可达路径的条数；邻接矩阵的c次幂方阵的第二行所有元素之和即为第二个节点的c步可达路径数；以此类推，可以在邻接矩阵的c次幂方阵中查出第n个节点到其它节点的c步可达路径的条数；将每条路径转化为上述哈希函数对应的计数器串；即第n个节点是图中的哪类节点就对应于上述哈希函数中该类节点对应的计数器串；

以图2所示的查询图(Q)为例，确定查询图(Q)的两步可达路径数，按照上述方法生成查询图(Q)的邻接矩阵M_Q和邻接矩阵的二次幂方阵M_Q²为：

从邻接矩阵的二次幂方阵M_Q²中可以得出查询图Q中的节点v₁的两步可达路径数为四，也就是邻接矩阵的二次幂方阵M_Q²第二行元素之和，其中，三条路径＜*,V(v₁)＞和一条路径＜*,V(v₃)＞。然后，将节点v₁(在查询图(Q)中对应C类节点)的每条路径转化为哈希函数(如图6所示)表示的标记路径：即三条路径＜*,C＞，一条路径＜*,D＞，然后，根据用上述方法生成的哈希函数确定每条路径的编码：即三条0100，一条1000，将四条路径的编码按位相加得到编码1300，该编码即为查询图(Q)中节点v₁的两步可达路径数编码。用上述方法将查询图(Q)中其它节点的两步可达路径数编码计算出，然后，将查询图(Q)所有节点的两步可达路径数编码按位相加，即可得到查询图(Q)的两步可达路径数的编码。根据上述方法可得到图2的测试数据图集(G₁,G₂,G₃,G₄)的两步可达路径数的编码。

步骤2，生成查询图和已知图数据集中每个图的图谱；

步骤2的具体过程如下：

步骤2.1，对于图中的每个节点先得到它的N层生成图，其中，N为任意自然数；

步骤2.1的具体过程为，节点的N层生成图生成方法为，针对具体节点，将该节点外围的第N层节点及该节点到第N层节点之间的所有节点和边加入图中，该图即为该节点的N层生成图。即，针对某一节点，先找出它的邻接节点，以及上述节点到邻接节点之间的边，将这些点和边加入图中，即为该节点的一层生成图；然后，再找第一层生成图中节点的邻接节点，以及第一层生成图中节点到其邻接节点之间的边，将这些点和边也加入图中，即为该节点的二层生成图；以此类推，直到得到该节点的N层生成图。当图比较复杂时，N的取值相对取大一些；当图比较简单时，N的取值相对取小一些。

以图2所示的查询图(Q)为例，用上述方法求出查询图(Q)的五个节点对应的两层生成图如图7所示。

步骤2.2，按照步骤1.3中的方法求出每个节点N层生成图的邻接矩阵。步骤2.3，根据公式x＝(x-c)/(d-c)(x为邻接矩阵中的元素，c为邻接矩阵中的最小值，d为邻接矩阵中的最大值)，将邻接矩阵进行标准化，然后计算标准化矩阵的特征值。

步骤2.4，将求得的每个节点的特征值进行递减排序，取出前2个特征值，即最大特征值和次大特征值；将所有节点的最大特征值进行递减排序，将所有节点的次大特征值进行递减排序；得到两个序列；该两个序列即为该图的两个图谱。

步骤3，用已知图数据集中每个图的节点标记的编码、边带权重的邻接边标记的编码、可达路径数的编码和图谱构建索引树；

步骤3的具体过程如下：

索引树的构建方法为，将已知图数据集中的图两两自由组合进行比较，将各编码中对应位数字大的提取出来形成新的节点图；重复上述过程，直至提取到只有一幅节点图为止；所述已知图数据集和依次形成的节点图共同构建为二叉树。

即，索引树的构建方法为，将已知图数据集中的图两两自由组合进行比较，将对应位数字大的提出来形成新的节点，该新节点称为父节点，形成父节点的这两个自由组合进行比较的图即为叶子节点；再将父节点两两自由组合进行比较，将对应位数字大的提出来形成新的节点，也就是形成父节点的父节点；以此类推，即构建出一棵二叉树；其中，对于具有相同的节点标记的编码、边带权重的邻接边标记的编码、可达路径数的编码、图谱的两个图作为同一个叶子节点。

以图2所示的测试数据图集(G₁,G₂,G₃,G₄)和查询图(Q)为例，用上述方法构件的索引树如图8所示。其中，V表示节点标记编码，E表示边带权重的邻接边标记编码，N表示N层可达路径数编码，M表示图谱。

步骤4，将查询图节点标记的编码、边带权重的邻接边标记的编码、可达路径数的编码、图谱与索引树节点图的节点标记的编码、边带权重的邻接边标记的编码、可达路径数的编码、图谱由上至下逐层进行比对，同时进行筛选，直至筛选到最底层，所得图即为与查询图相近的候选图。

步骤4的具体过程如下：

查询图与索引树节点图逐层进行比对，同时进行筛选，筛选条件为：

一、索引树节点图的边带权重的邻接边标记编码的每位数字大于等于查询图边带权重的邻接边标记编码对应位的值；

二、索引树节点图的边带权重的邻接边标记编码的每位数字大于等于查询图边带权重的邻接边标记编码对应位的值；

三、索引树节点图的可达路径数编码每位的数字大于等于查询图可达路径数编码对应位的值；

四、索引树节点图的图谱中选取出来的最大、次大特征值分别大于等于查询图图谱中选取出来的最大、次大特征值；

照上述条件筛选出的索引树最底层的图即为与查询图相近的候选图。

以图2所示的测试数据图集(G₁,G₂,G₃,G₄)和查询图(Q)为例，用上述方法得到的候选图如图9所示。其中，V表示节点标记编码，E表示边带权重的邻接边标记编码，N表示N层可达路径数编码，M表示图谱。

步骤5，将候选图与查询图进行子图同构验证，得到结果图数据集。

本发明一种基于图谱和可达路径数的无向加权图的子图查询方法每一步所依据的原理如下：

(1)提取节点标记和边带权重的邻接边标记作为特征：

假如一个图G₁中存在的某个标记的节点和邻接边在另一个图G₂中不存在，那么G₁不可能是G₂的子图。

(2)提取可达路径数作为特征：

对于子图中两点间的路径，超图中对应节点肯定存在对应的路径。

(3)提取图谱作为特征：

给出一个图G，其邻接矩阵表示为M_G。M_G的所有特征值的序列称为图G的图谱。

(4)对于每个节点，求出它的N层生成图：

给出两个图G₁和G₂，两个节点v₁∈G₁和v₂∈G₂。如果G₁是G₂的子图，并且节点v₁对应的节点为v₂，那么，节点v₁的N层生成图LNSG(G₁,N,v₁)是节点v₂的N层生成图LNSG(G₂,N,v₂)的子图。