带权大图上的K步可达性查询算法.pdf

第 卷第 期计算机应用与软件 年 月 带权大图上的 步可达性查询算法李文华李盛恩（山东建筑大学计算机科学与技术学院山东 济南 ）收稿日期：。李文华，硕士生，主研领域：图数据管理。李盛恩，教授。摘要可达性查询作为图中最常用的基本操作，在生物信息学、智慧交通等领域应用广泛，但在一些现实问题中，仅仅进行可达性查询并不能满足人们对距离信息的需求，步可达性查询应运而生。目前已有的 步可达性查询的处理对象为有向无环图，无法充分反映顶点间的距离信息，并且无环图并不符合交通网络等实际应用情况。针对以上问题，提出一种针对带权有向图的 步可达性查询算法。通过求解近似最小顶点覆盖集，分别构建了顶点覆盖集内索引和顶点覆盖集外的双向最短路径索引，有效避免了查询时的 操作，提高了查询效率。在 个数据集上进行对比实验，并通过比较索引构建时间、索引规模、查询时间等指标证明了该算法的高效性。关键词带权大图步可达性顶点覆盖图数据库知识图谱中图分类号 文献标志码 ：（，），引言随着移动智能终端和移动互联网的普及，越来越多的业务和互联网紧密结合起来。从社交网络到智慧政务，从餐饮娱乐到智能交通，人们在享受互联网 带来的无限便利的同时，每天也产生了海量的数据。这些数据具有以下特点：（）数据量大，存储单位从过去的 、级到现在的 乃至 级别。（）数据结构多样，大量数据为无结构化数据、半结构数据。（）数据产生速度快，对网络传输的性能要求高，有些数据需要实时处理，对服务器的计算处理能力要求高。（）数据价值密度低 。面对这些数据，传统的关系型数据库在处理时显得力不从心。为了更好地存储和管理这些数据，各种新型数据库应时而生。以 为代表的图数据库就是其中的一类，它以属性图作为逻辑存储模型，凭借图的独特构造，在存储和管理如社交网络、生物信息网络、智能交通网络等数据时发挥了重要作用。在数据库系统中，快速准确地进行查询是用户的第 期李文华，等：带权大图上的 步可达性查询算法 一项基本需求，为了满足用户的这一需求，传统数据库的设计和开发者为数据建立了各式各样的索引，极大提高了查询效率，现在已经非常成熟。而图数据中的查询种类众多，包括可达性查询、最短路径查询、关键字查询、匹配查询等，近年来，针对这些查询的研究得到了更多学者的关注。可达性查询研究的是图中两个顶点之间是否存在可达路径，作为图数据管理中使用最频繁的操作，可达性查询在子图匹配查询、生物信息学、社交网络等领域中应用广泛 。但是对于一些现实中的问题，仅仅进行可达查询并不能满足用户的需求，如在无线传感器网络、互联网、电信网以及社交网络中，顶点 对顶点 的影响力受制于从 到 的路径长度（例如无线传感器网络的广播消息可能在传输过程中的任何一步丢失，其他顶点接收到的概率会随着路径长度的增加以指数级速度衰减），因此针对 步可达性查询的研究逐渐增多。步可达性查询是在可达性查询的基础上，对两顶点间的路径长度限制至 ，即回到两点间是否存在一条长度不超过 的路径。步可达性查询相比可达性查询，不仅能反映顶点间是否存在影响，还能反映顶点间的影响程度，可以提供更多有用信息，在无线传感器网络、互联网、电信网以及社交网络等实际应用中应用广泛，具有较高的实用价值。近年来，随着研究的深入，已有多个 步可达性查询算法先后被提出，但是这些算法的研究对象均为无权图。而在一些现实问题中，我们要处理的往往是带权重的图数据，如前文提到的传感器网络、社交网络、交通网络等，在这些网络中，权重可以表示传感器间的距离、功率损耗，社交网络中人与人之间的亲密程度，交通网络中两城市间的距离、油耗等。此外，有些算法的研究对象限定为有向无环图，如果图数据中存在环，则通过压缩强连通分量构造为有向无环图，这在步可达性查询中并不合理；有些算法在构建索引时需提前指定查询步数 ，且针对每个 构建的索引只适合 步以内的查询，在查询时不能灵活地更改查询步数 。针对以上问题，本文提出了一种针对带权有向图的 步可达性查询算法，能在常数时间内完成大部分步可达性查询。具体来说，本文的贡献如下：（）根据现实问题，提出了带权有向图上的 步可达性查询，以双向最短路径索引和 索引为基础设计了高效索引，能在常数时间完成大部分 步可达性查询。（）研究对象不再局限于有向无环图，对于带环图也可以正常处理；构建索引时，不需要提前指定查询步数 ，并且在查询时可以灵活改变查询步数 。（）基于多个真实图数据进行测试，通过与无权图上的 步可达性查询算法对比，实验结果表明本文算法高效可行。背景知识和相关工作 背景知识本文的研究对象为带权有向图 （，），其中 是 的顶点集合，中的顶点用 、等小写英文字母表示，是 的有向边集，中的有向边用（，）表示，其含义是从 到 的一条有向边，为边上权重。（）表示指向顶点 的顶点集，（）表示顶点 指向的顶点集，（，）表示从 到 的路径长度，即从 到 所经过边的权重之和。本文要处理 步可达性查询，即查询给定的图 中的两个顶点 和 ，是否存在一条从 到 且长度不超过 的路径，若存在，则称 步可达 ，用 表示。若不存在，则称 步不可达 ，用 表示。相关工作根据索引类型进行分类，可将目前已有的 步可达性查询算法分为两类。第一类是基于可达性的 步可达性查询算法，该类方法的基本思想是以可达性查询结果作为否定剪枝条件，如果通过可达性查询判断出两顶点 和 不可达，则两顶点一定 步不可达；如果可达性查询结果为可达，则结合辅助索引做进一步判断。第二类基于顶点覆盖集的 步索引方法，其基本思想是首先求出原图的一个顶点覆盖集，然后根据原图中的可达性，在顶点覆盖集上建立 步可达索引。在查询时，根据顶点 和 是否属于顶点覆盖集，将查询分为四种情况，再利用建立的索引实现快速查询。基于可达性的 步可达性查询算法基于可达性的 步可达性查询算法以可达性查询为基础，在构建索引时，首先通过压缩强连通分支，将原图转换为有向无环图，然后在有向无环图上构建可达性查询索引和一些辅助索引。在查询时，该类方法以可达性查询结果作为否定剪枝条件，首先通过可达性查询判断出两顶点 和 是否可达，如果不可达，则两顶点一定 步不可达；若可达，则利用辅助索引进一步判断，若通过辅助索引的查询结果为不可达，则两顶点一定 步不可达，若辅助索引的结论果仍为可达，则依次判断以顶点 的为弧尾的相邻顶点集中的点是否 步内可达以顶点 为弧首的相邻顶点集中的点，若是，则 可以 步可达 ，否则 不可 步可达 。该类方法的典型代表有 算法 、算法 、计算机应用与软件 年 算法 、算法 。算法以著名的可达性算法 ，为基础，其基本思想是：首先对有向无环图分别进行从左到右和从右到左的后根遍历，每个顶点两次后根遍历的次序分别作为其两个区间的上界 ，而区间的下界为其子节点区间的下界的最小值 ，若该顶点为叶子节点，则其区间下界和上界相等，这样就构建起单向双区间的可达性索引。为了加速查询，该算法索引中还包含了每个顶点的双向广度层数和双向拓扑层数。在查询时，首先根据可达性查询判断两点是否可达，如果不可达，则得出结论，两点 步不可达，否则，利用双向广度层数和双向拓扑层数进行判断，若仍不能判断出结果，则递归地从两顶点出度或入度较小的一侧向另一侧查找，递归结束的条件是递归次数达到 或查到另一个顶点。算法以 算法 为基础，其基本思想是为部分度大的顶点构建双向最短路径索引。首先选取部分度大的顶点（这些点称为 点），根据实验，当一幅图中选择的度大的节点数达到 个时，要么这些节点维护的可达性信息已经足够多，要么再增加节点也不会显著增加可达性信息。然后利用广度优先遍历为这些 顶点分别建立两个标签 和 （），前者存储图中可达 的顶点及其到 的路径长度，后者存储 可达的顶点及其路径长度。为了快速判断不可达，本文在索引中为非 点添加了正反互逆拓扑号。在查询时，对于给定的点 和 ，如果至少有一个为 点，则直接查找其与另一个点的路径长度，判断路径长度是否小于或等于 ，若是则两点 步可达，否则 步不可达；若两点均不为 点，则利用正反互逆拓扑号进行判断，若判断结果为不可达，则说明两点 步不可达，否则借助原图递归地从两顶点出度或入度较小的一侧向另一侧查找，直到递归次数达到 或查到另一个顶点。算法以 和 算法为基础，首先利用可达性算法构建 索引，然后将原图生成广度优先森林，对广度优先森林中的每一个棵树进行后根遍历，构建 间隔标签索引，最后对每棵树进行广度优先遍历，得到每一个顶点的全局广度层数。在查询时，对给定的两点 和 ，步长 ，先利用 索引进行可达性查询，如果查询结果为两点不可达，则得到两点一定 步不可达，否则利用 索引的包含关系进行判断；如果点 的 间隔标签包含点 的标签，则判断 的全局广度层数减点 得到的值是否小于步长 ，如果是，则两点 步可达，否则不可达；如果点 的 间隔标签不包含点 的标签，则从点 的出度和点 的入度两者中小的一侧进行递归的搜索，直到得出结论。算法同样以可达性算法 为基础，结合文献 中的算法。在构建索引时，首先对有向无环图进行从左到右的后根遍历，为每个顶点构建一个区间，然后将有向无环图反向再进行一次从左到右的后根遍历，为每个顶点再构建一个区间，这样就构建起了双向双区间标签索引。在查询时，对于给定的两点 和 ，仍然是先根据可达性查询判断两点是否可达，如果不可达，则一定 步不可达，否则递归地判断 的子节点是否 步可达 直到得到结果。基于可达性的 步可达性查询算法，充分利用可达性查询，巧妙地结合一些剪枝策略，算法简明清晰，然而在实际中，顶点之间或多或少存在某种联系，可达性查询大多会返回肯定的结果 ，因此剪枝效果并不理想。并且其研究对象为有向无环图，这并不符合实际应用情况，在可达性查询中，因为强连通分支内顶点都是相互可达的，可以通过压缩强连通分量，将普通有向图转为有向无环图，但在 步可达性查询中，压缩强连通分支变得不合理，比如在 步可达性查询中重要应用交通路网中，如果假设路网为有向无环图，那么意味着从一个城市出发即再也无法回到该城市，这显然不符合常理。基于顶点覆盖集的 步索引方法文献 提出了基于顶点覆盖集的 步索引方法 ，该方法的基本依据是一条边的两个顶点，至少有一个在顶点覆盖集中。在构建索引时，该方法首先要确定查询步数 ，然后对给定的图 求近似最小顶点覆盖集 ，求出顶点覆盖集 中顶点在原图中的所有路径及长度，将路径长度不超过 的路径和路径长度作为带权有向边，保存为索引，此外索引中还包含近似最小顶点覆盖集 ，所以该方法的索引由顶点集 和带权有向边集构成。在查询时，对于给定的两个顶点 和 是否在顶点覆盖集 中，将查询分为四种情况，当 和 均属于顶点覆盖集 时，直接查询 ，的路径长度并与 值进行大小比较，若路径长度小于或等于 值，则 可以 步可达 ，否则 不可 步可达 ；当 属于顶点覆盖集 ，但 不属于 时，依次取 （）中的顶点 ，因为 不属于 ，所以 一定属于顶点覆盖集 ，所以直接查询 ，的路径长度并与 进行大小比较，若路径长度小于或等于 ，则 可以 步可达 ，否则 不可 步可达 ；当 不属于顶点覆盖集 ，但 属于 时，依次取 （）中的顶点 ，因为 不属于 ，所以 一定属于顶点覆盖集 ，所以直接查询 ，的路径长度并与 进行第 期李文华，等：带权大图上的 步可达性查询算法 大小比较，若路径长度小于或等于 ，则 可以 步可达 ，否则 不可 步可达 ；当 和 均不属于顶点覆盖集 时，依次取 （）中的顶点 和 （）中的顶点 ，查询 ，的路径长度并与 进行大小比较，若路径长度小于或等于 ，则 可以 步可达，否则 不可 步可达 。方法的研究对象不再局限于有向无环图，利用指定 值构造出来的索引，也能提供较好的查询效率，但是其仍不能解决带权图上的 步可达性查询，同时构造索引时需要提前指定 值，查询时 值不能灵活更改等问题使得该算法难以在实践中应用。基本思想和算法描述 索引构建算法本文提出的针对带权有向图的 步可达性查询算法，首先求解给定图的近似最小顶点覆盖集，然后基于顶点覆盖集构建索引，类似于文献 提出的算法，与之不同的是，本文的研究对象由简单有向图变为带权有向图，在构建索引时也不需要提前指定 值。除了顶点覆盖集上的索引外，为了避免在查询过程中的 操作，提高查询效率，本文还构建了顶点覆盖集外的双向最短路径索引。求解近似最小顶点覆盖集根据文献 的证明，最小顶点覆盖问题属于 类问题，通常一个问题若被证明为 类，人们认为该问题不能在多项式时间内解答。虽然无法准确求解图的最小顶点覆盖集，但是可以在多项时间内求解图的近似最小顶点覆盖集。文献 给出了一个求解近似最小顶点覆盖集的朴素算法，即从边集中任选一边 ，将该边的两顶点 、依次加入到顶点覆盖集 中，然后将顶点 或 能覆盖到的边从边集中全部删除，重复上述过程，直到边集为空，这样就得到了一个顶点覆盖集。该算法简单易懂，但得到的顶点覆盖集往往规模偏大。本文采用贪心算法来求解近似最小顶点覆盖集，首先计算图中各顶点的度，选出度最大的顶点，然后将该顶点加入到顶点覆盖集中，并将该顶点覆盖到的边从边集中全部删除，在删除过程中，对相关顶点的度进行调整，重复上述过程，直到边集为空。具体如算法 所示。算法 近似最小顶点覆盖集算法输入：带权有向图 （，）输出：近似最小顶点覆盖集 初始化各顶点的度 （）求近似最小顶点覆盖集 （）（）（，）需要说明的是，在求解近似最小顶点覆盖集的过程中，因为边的方向和权重不起作用，我们可以将其暂时忽略。如图 所示，最小顶点覆盖集由灰色顶点构成。本文采用的求解近似最小的顶点覆盖集的贪心算法的时间复杂度为 （），不如文献 给出的朴素算法时间复杂度 （），但该算法求解的顶点覆盖集更小，有利于保证接下来的索引构建过程的时间和空间效率。图 带权有向图 （灰色点构成顶点覆盖集 ）构建索引基于上一节得到的近似最小顶点覆盖集，进行索引构建，具体如算法 所示。最终构建的索引由三部分构成，分别是近似最小顶点覆盖集 、内索引和 外索引。其中近似最小顶点覆盖集 已经求出，可直接加入到索引中。算法 索引构建算法输入：带权有向图 （，）。输出：（，）。求近似最小顶点覆盖集 求 内顶点间的最短路径 （，），（，）（，）求 外的索引 （）（，）（）（，）内索引实际上就是 内各顶点间的最短路径，计算机应用与软件 年该部分是整个索引的核心部分，在构建过程中，对 内每一个顶点 ，在原图中执行广度优先遍历，对遍历到的每一个顶点 ，如果 属于 ，则将（，）加入到索引中，其中 表示从 到 的路径长度，这样就得到由带权边构成索引，如表 所示。内索引的构建过程，需要对 内每一个顶点执行广度优先遍历，但每个点遍历得到的个数并不确定，所以其时间复杂度可表示为，表示 可达点的数量。表 顶点覆盖集 内索引 ，外索引类似于 算法中的双向最短路径索引，具体构建过程如下，对 外的每一个顶点 ，依次访问 （）或 （）内顶点 ，因为 不属于 ，所以 一定属于 ，将（，）加入到 外索引的 （，）或 （，）中。最终构建的 外索引如表 所示。外是该索引的重要组成部分，借助该部分，本算法可以实现在不访问原图的情况下，完成 步可达查询操作。虽然该部分索引在一定程度上增大了索引的规模，但是有效避免了 操作，大幅提高了查询效率。通过分析易知，其时间复杂度为 （），（）。表 顶点覆盖集 外索引节点 （，）（，）（，）（，）（，）（，）（，），（，）查询处理对于给定的两顶点 、和路径长度 ，根据 和 是否属于近似最小顶点覆盖集 ，将查询分为四种情况：（）若 和 均属于 ，则直接查询 内索引得到 （，），若 （，），则 步可达 ，否则 步不可达 。（）若 属于近似最小顶点覆盖集 ，而 不属于 ，则首先判断 外索引中的 的入边顶点集 （）是否为空，若 （）为空，则 步不可达 ，否则依次遍历顶点 的入边顶点集 （）中的点 ，判断是否存在 使得 （，）（），若存在这样的点 ，则 步可达 ，否则 步不可达 。（）若 不属于近似最小顶点覆盖集 ，而 属于 ，同样首先判断 外索引中的 的出边顶点集 （）是否为空，若 （）为空，则 步不可达 ，否则依次遍历顶点 的出边顶点集 （）中的点 ，判断是否存在 使得 （，）（），若存在这样的点 ，则 步可达 ，否则 步不可达 。（）若 和 均不属于顶点覆盖集 ，则首先判断 外索引中的 的出边顶点集 （）或 的入边顶点集 （）是否为空，若二者任意一个为空，则 步不可达 ，否则依次遍历顶点 的出边顶点集 （）中的点 和顶点 的入边顶点集 （）中的点 ，判断是否存在点 和点 使得 （）（，）（），若存在这样的点 和 ，则 步可达 ，否则 步不可达 。具体如算法 所示。算法 查询算法输入：（，）；顶点 和 ，步长 。输出：。顶点 均属于 （）（，）（）顶点 属于 ，不属于 （）（）（）（，）（）（）顶点 不属于 ，属于 （）（）（）（，）（）（）顶点 和 均不属于 （）（）（）书书书第 期李文华，等：带权大图上的 步可达性查询算法 （）（）（）（，）（）（）在查询过程中，判断顶点 和 是否属于近似最小顶点覆盖集 在 （）内即可完成，从索引中查找路径长度则与顶点的度有关系，对于查询最复杂的第四种情况，其时间复杂度为 （）（）（），并且因为使用优先选择度大顶点贪心算法来构建最小顶点覆盖集，所以绝大部分度大顶点已在顶点覆盖集中，顶点覆盖集外顶点的度一般不会太大。例如要查询图 中的顶点 和 是否 步内可达，因为顶点 不在顶点覆盖集中，而顶点 在，所以首先判断顶点 的出边顶点集是否为空，发现顶点 的出边顶点集不为空且由顶点 构成，所以根据 外索引得到 （），根据 内索引得到 （，），两者求和得到的路径长度为 ，与给定的步长相等，所以顶点 ，步可达顶点 。实验 实验环境和实验数据本实验所用的计算机配置为 （）处理器，主频 ，内存，机械硬盘，教育版操作系统。本实验所用算法均由 语言实现，版本为 。本文选取了 步可达性查询中常用的 个数据集，用于性能测试，包括 、，这些数据全部来自科布伦茨网络数据集（：），其中 、是航空路网，、是引用网络，、是社交网络，是人类蛋白质网络。、网络中存在回路。、为平均度超过 的稠密图。和 网络中自带权重信息，其他网络中权重由本文利用随机函数添加。各数据集的统计信息如表 所示，其中 代表图中顶点数，代表边数，为各顶点的平均度数。表 数据集统计信息数据集 因为目前还没有针对带权有向图上的 步可达性查询算法，同时考虑到大部分已有算法的处理对象为有向无环图，可比性不强，本文选择与可以处理带环有向图的 算法进行比较，其中参数 设为 ，通过索引构建时间、索引规模、查询时间三个指标进行性能评价。本文所列出的所有数据均为算法执行 次的平均值并通过四舍五入保留到小数点后两位，表中 为本文中提出的算法。索引构建时间和规模表 给出了两种算法所求的顶点覆盖集规模，通过比较发现，采用优先选择度大顶点的贪心算法求解得到的顶点覆盖集规模明显小于朴素算法得到的顶点覆盖集规模，平均降低约 。表 顶点覆盖集规模数据集 表 给出了两种算法的索引构建时间，从索引构建时间可以发现，在稀疏图上，算法与 的相比略占上风，但差别不大。但在稠密图上，算法的优势比较明显，索引构建时间平均降低约 。这主要得益于 算法在求解近似最小顶 计算机应用与软件 年点覆盖集时采用了优先选择度大顶点加入顶点覆盖集的贪心算法，有效降低了顶点覆盖集中顶点数量，从而减少了构造比较费时的顶点覆盖集内索引规模，提高了索引构建效率。表 索引构建时间单位：数据集 表 给出了两种算法构造的索引规模，从索引规模来看，两种算法不相上下，算法整体具有一定优势，主要是因为随着顶点覆盖集内索引规模的减少，顶点覆盖集外索引规模逐渐上升，所以索引总规模保持相对稳定。表 索引规模数据集 查询时间表 给出了两种算法在步长 时，随机生成万个顶点对进行查询的结果，表中数据为 万次查询时间之和。可以发现，在查询时间方面，两种算法效率相当，虽然 算法在查询过程中需要计算路径长度，但有限次的简单算术计算并不影响算法整体查询效率。表 查询时间单位：数据集 表 给出了 算法在 值分别为 、时的查询时间，可以发现 值的变化对于算法的查询时间影响不大，这是因为 算法在顶点覆盖集上构建的索引与 值无关，不论 值如何变化，查询操作不会变化。表 不同 值的查询时间单位：数据集 结语本文针对 步可达性查询在实际应用中存在的问题，吸收已有 步可达性查询算法 算法和 算法的优势，提出了带权有向图上的 步可达性查询算法 ，并通过实验验证了算法的高效性。带权有向图上的 步可达性查询因为涉及到权重，需要额外空间进行存储，索引规模相对较大，如何在保证查询效率的前提下，尽可能压缩索引空间，值得进一步研究。参考文献刘凯悦 大数据综述 计算机科学与应用，第 期李文华，等：带权大图上的 步可达性查询算法（）：陈子阳，陈伟，李娜，等 面向大图的可达性查询处理算法 计算机学报，（）：，（）：周军锋，陈伟，费春苹，等 ：一种处理 步可达性查的双向搜索算法 通讯学报，（）：杨静 基于混合标签的可达性查询算法研究 秦皇岛：燕山大学，杜明，杨安平，周军锋，等 面向大图的 步可达查询优化算法 计算机应用，（）：，：，：宋亚青，武优西，刘靖宇，等 基于双向双区间标签实现 步可达查询 计算机科学，（）：，：，（）：，：，：，（）：，：，：，：，：，：杨柳，刘同勇，胡志刚，等 向无环图的可达性查询方法、系统及可读存储介质：，：，：，：，（）：，（）：朱大铭，马少汉 算法设计与分析 北京：高等教育出版社，：（上接第 页），：，：，：，：，：，：，：，：，：，：，：史志成，周宇 代码特征自动提取方法 计算机科学与探索，（）：胡海生 一种基于白名单机制的电力监控主机恶意代码防御方案 计算机应用与软件，（）：，：，