基于图数据的关键字覆盖集合问题

文/刘慧娟

任何一个企业的组成或者结构都可以看成一个大的数据图，那么这个问题就可以定义为：给定有向无环图G，关键字的集合覆盖问题主要回答找到k关键字，使k个关键字能够覆盖给定的属性集合，并且这k个关键字的影响力最大，这是多种数据管理应用中的核心操作之一，如XML和RDF数据库以及社交网络和生物信息网络等，是研究者广泛关注的热点问题。如日常生活中普遍存在的工程设计问题，在电网企业中人员调动、通信网络安全、资源分配、电路设计、信息通信管理、运输车辆路径安排等领域有广泛的应用，多年来吸引了众多计算机科学家、运筹学研究人员的研究兴趣。对这一问题，相继有很多学者利用不同的思想提出了很多不同的算法。现有求解关键字覆盖集合的方法主要分为四类，基于分数的贪心算法、基于鸽子洞的贪心算法、基于划分的算法、基于划分的优质算法。

1 背景知识及相关工作

本文用G=(V,E)表示有向无环图，其中V表示G中的顶点集合，E表示G中有向边的集合，|V|表示G中顶点的个数，|E|表示G中边的个数。若(u,v)∈E，则说明G中有一条从u到v的边，反之不存在。w(u,v)是从节点u到节点v概率，取值范围是(0,1]。

在社交网络G中，节点v的属性集合用A(v)表示，如果属性ai∈A(v)，那么节点v覆盖属性ai，否则就认为节点v没有覆盖属性ai。节点集合覆盖属性集合A={a1, a2,…, am}当且仅当任意的属性ai∈A，至少有一个节点v(v∈V´)覆盖属性ai。用V(A)表示节点集合，在集合中的每一个节点都能覆盖属性集A。集合属性的划分是基于覆盖组的概念进行划分的，设一个属性集合Q和Q的一种局部划分P={A1, A2, …, Am}令ri=|Ai|(i∈[1,m])是属性Ai集合中元素的个数。集合R={r1, r2, …, rm}是P的覆盖组。

2 PICS-IN方法

本节首先介绍索引结构，在每次查询覆盖特定属性m的节点时，直接查找属性m的倒排表即可，减少了时间代价来减少需要访问的顶点数量，简称PICS-IN，然后介绍基于阈值的高效的剪枝策略，并将其应用于PICS-IN算法来提升系统性能。

2.1 离线索引结构

本文方法所使用的集合划分策略是根据覆盖组的方法进行划分组合，覆盖组，当判断节点u的属性是否能覆盖属性某一属性m时，PICS-IN的基本思想是：首先根据图1中节点集合中包含的所有不重复的属性集合，建立属性集合的倒排索引，选择符合条件的节点集合。

给定一个属性集合Q，一个正整数k，一个社交网络G=(V, E, w, A)。图中的每个节点都有属性标签，每个节点的属性标签的个数不同，其中也有的节点的属性个数为0，图1中，节点1到节点23之间每个节点的属性标签个数不一定相同，同一个属性a可能会出现在多个节点中，例如节点1的属性标签集合是{a, b, c, d}，节点2的属性集合是{a, b, c, e}，重复的属性是{a, b, c}三个。建立的索引结构是关于节点的不重复的属性集合A(V)和节点的索引，属于离线索引。建立离线索引需要三步，首先遍历节点集合V，然后对于每个节点v，遍历节点v的属性集合中任意的属性a，最后把节点v放到属性a的倒排表中，当遍历完节点集合中的节点，以及节点集合中每个节点的属性集合，那么就建立了属性的倒排表。图1中，节点集合为V={1, 2, 3, 4, …,23}，节点集合V中所有节点的不重复的属性是{a, b, c, d, e, f}，把包含属性集合中任一属性的节点存放到属性的倒排表中，遍历节点集合V，访问1号节点时，1号节点的属性集合是{a, b, c, d}，那么就把1号节点分别添加到属性a，b，c，d的倒排表中，建立的索引结构如图2所示，那么建立的倒排索引中，属性a的倒排表中是包含属性a的节点，其他属性也一样。由图1得到的属性索引结构如上的表1所示。

2.2 高效的阈值剪枝策略

定理1(新生成组合的判断条件)给定一个链表集合L1，L2，…，Lm，一个组合集合C，链表Li在第d层元组用表示，如果新生成的组合至少满足以下条件之一，则直接把这个组合进行删除，不再和集合C中其他的组合结合在一起产生新的组合，条件如下：

首先在已经构建的倒排索引中，找到前k个能够覆盖给定的属性集合Q中的属性，并且有最大影响力的节点；其次，对于属性集合Q每一个覆盖组R，从已经选择的节点集合中取前k-|R|个节点作为自由集的解，并在已经划分的覆盖组中除去已经被自由集中的节点覆盖的属性；最后，根据PICS+算法中构建在线索引链表的方法，构建索引链表，即把覆盖相同属性个数的节点放在同一链表中，并把节点组合成元组的形式，如图2所示，构建的在线的索引链表如表2所示。然后把链表中不同列的元组进行组合，利用取上界的Upperbound算法求出能够覆盖这些属性并且影响力最大的节点，最后得到的这些节点就是受约束集Sp，最后返回的k个节点就是由自由集中的节点和受约束集中节点组成的并集。

3 结论

通过实验对比现有的几种算法和本文提出的PICS-IN算法的索引大小、创建索引的时间、查询节点的时间以及实验中需要访问的顶点数量，通过几种性能的对比，验证了本文提出算法的结果的准确性和时间的高效性。最后对PICS-IN算法在取不同k值时，不同|Q|值时的查询处理性能进行了实验对比，进一步验证了本文提出的PICS-IN算法的扩展性。

表1：属性的索引结构

表2：覆盖组的链表

集合覆盖方法对企业物资的调度、电路的设计等起到了良好的推动作用，并通过数据分析，可以得出最优的、最合理的解，也就是实际问题的解决办法，集合覆盖技术的研究将将大大的减少人工核算的人员和资源的浪费，为电网的发展提供更加合理化、数据化的理论支撑，更加准确、有效的推进企业规划中的资源配置和部署。

图1：有向无环图G及顶点属性标签图

图2：有向图G及节点的属性标签图