近年来，越来越多的应用把它们的数据建模为图的形式，如XML数据库、社会网络、生物信息网络、交通网络等.随着这些应用的不断深入，使得这些数据的规模越来越大，如何高效地管理和挖掘这些数据，已经成为目前的热点研究问题之一.

距离查询^[1]，即回答图中任意两个结点间的距离，是图中最基本的操作之一.如在社会网络中可以判断两个用户间关系的亲近程度，在交通网络中则可以回答任意地点间的最短距离，其他很多应用中也大量涉及到距离计算.

由于实时在线查询和计算传递闭包两种极端方法或者在查询时间或者在索引存储无法满足可扩展性的要求，目前常用的方法是对原图创建压缩的索引.而相对于可达查询^{[1, 2, 3, 4]}，即关注任意两点之间是否存在路径，距离查询因为需要在所有可达路径中的计算最短距离，其难度更大.目前有关距离查询的研究焦点一般集中于两类图数据:一类是交通路网;另一类是复杂网络，如社会网络、生物信息网络等.对于前者，因为结构相对简单，目前出现了很多成功的研究成果^[5].而对于后者，目前仍然是很具挑战性的课题.虽然现在有一些处理复杂网络的方法，但是都面临着性能的瓶颈，即只能处理小规模图(结点数量在几千到几万之间)，而大多数算法在处理大规模图时，性能会急剧下降，甚至无法运行.

标签法^{[1, 3, 4, 6, 7, 8]}是在建立图数据索引时常用的一种方法，即为图中每个结点赋予一个标签，在进行可达查询或距离查询时，直接通过两个结点的标签集的join-查询即可快速获得结果.目前大部分的算法都是直接在原图上创建索引^{[6, 9]}，当图的规模增大到一定程度时，这些索引结构一般都无法具备良好的可扩展性.Jin等^[7]参考交通路网算法提出Highway标签结构，可以处理中等规模甚至大规模稀疏图，但不是所有的图都可以高效地提取出Highway结构.

文献^{[2, 10]}中提出利用创建通用查询子图的方法来提高其他算法的执行效率，即在原图中仅选取部分结点作为查询骨架，在进行可达查询或距离查询时，每个结点只需快速找到离自己最近的骨架结点，然后利用子图实现与目标结点信息的查询.这两个方法都具有一定的可扩展性，但是它们创建的查询子图本身对现有算法来说仍然可能过大而无法提高其效率.

总的来说，可扩展性已经成为影响距离查询效率的一个最重要障碍，目前急需解决的问题是当图的规模达到十几万甚至上百万结点的时候，如何建立一个高效的索引结构以实现高效查询.基于此，本文提出了利用社区划分的方法在原图中建立查询子图，称为查询主干，该主干保留了原图的所有拓扑信息，而且该算法可以递归进行，建立起一个多级标签索引结构，利用该结构既提高了查询速度，也大幅度降低了创建时间和索引大小.实验结果表明，本方法不仅适用于小规模的图数据，对于大型和超大型图数据也具有非常好的可扩展性.

本文研究建模为图的形式的网络数据，设G=(V,E)为有顶点集V和边集E的图，用符号n表示图的顶点数量|V|，m代表边的数量|E|.任意两点间的最短距离用d(u,v)表示，如果两点之间没有路径则d(u,v)= ∞.用N_ε(v)表示任意顶点v∈V的ε邻居，即N_ε(v)={d(u,v)≤ε|u∈V,(u,v)∈E}.

根据迪杰斯特拉最短路径算法思想，任意两点间的最短距离满足三角形不等式，对于图中任意三个连通结点u,v和s：

问题定义：给定一个图G，如何创建一个索引结构以高效回答任意两点间的距离.为了方便描述及与其他算法对比，本文主要讨论如何处理无向无权图，目前大多数的应用可以建模为这种形式，而且该方法也可以很容易地扩展到有权图或有向图的应用中.

直观地说，一个图的查询主干应该具备以下几个特征：1) 它的规模必须远远小于原图；2) 它必须保留原图所有的拓扑结构和距离信息；3) 原图中的任一结点都能在少数几步到达主干中的某一结点.

为了达到这个目标，本文引入了社区划分的概念.根据Milgram的小世界理论^{[11, 12]}，社区聚集是很多网状数据的共有现象，如图 1所示的一个社交网络，所有用户根据兴趣、职业等特征划分为若干个集合，在集合内部各结点联系紧密，而在集合之间联系则很少.本文利用了这个现象，首先将原图划分为若干个社区，其中每个社区包括一个与社区内所有结点连接的社区中心，而其他结点为该中心的ε邻居.

图 1(Figure 1)

Fig. 1

图 1 社交网络示意图Fig. 1 A real social network

综上，查询主干可定义如下：

定义1 给定一个图G=(V,E)和一个阈值ε，则它的查询主干为G^*=(V^*,E^*)，其中V^*∈V,E^*通常包括E中不存在的边，E^*中的权值为原图中两点最短距离.

查询主干中的结点应该具有如下性质：1) 原图中任意一个非主干结点都可以至多在2ε步内到达查询主干中的一个结点；2) 查询主干中的两个相邻结点的最大步长至多为2ε+1步.

图 2b为原图 2a的一个查询主干，从该例可以看出，查询主干的结点数量远远小于原图中结点的数量，该子图可以继续进行查询主干的创建操作，直至结点个数为1为止.

图 2(Figure 2)

Fig. 2

图 2 原图及其查询主干Fig. 2 The original graph anf query trunk (a)—原图； (b)—查询主干.

很显然，本问题的核心是如何在图中找到尽可能少的社区中心以覆盖原图中的所有结点，即创建尽可能小的索引，其定义如下：

定义2 最小查询主干(MQT，minimum query trunk)：给定图G=(V,E)，则必存在一个查询主干G^*=(V^*,E^*)，在所有的可能集合中|V^*|最小.

但是这个问题无法在多项式时间内解决，因为社区发现本身就是一个NP-hard问题，因此本文提出了一个简单但是非常有效的启发式算法，可以快速在一个图中建立查询主干并创建索引.

如果原图中的任意结点都可以在2ε步内到达主干T中的某一结点，则称T对原图完全覆盖.最理想情况下，先将原图划分为多个社区，然后再从各社区中确定社区中心建立查询子图，但这个方法本身也是NP-hard问题，所以本文提出一个基于度最大结点优先覆盖算法，其基本思想和原因如下：1)从图 1中可以发现，处于社区中心位置的结点往往是与其他结点关系最为紧密的，具体表现就是结点的度往往远大于其他普通结点；2) 如果先确定社区再确定中心，问题会非常复杂，而如果先确定中心再覆盖附近的邻居结点，则效率会明显提高.

利用这两点发现，本文提出了如算法1和算法2所示的基于度最大优先的启发式算法.这里还需给出一个有关有权图查询主干发现的定理.

定理1 给定一个边上权值为非负的无向图G=(V,E)，基于它的最小生成树生成的查询主干可以实现对图G的完全覆盖，证毕.

证明：根据最小生成树的定义，树中任意两个顶点的边都是原图中无环情况下权值最小的，因此计算G中任意两个顶点的距离所需步长一定小于或等于在树中两个顶点的步长，即通过最小生成树计算得到的查询主干可以实现对原图G的完全覆盖，证毕.

算法1给出了创建图G查询主干和为G中结点设置标签的过程.1) 如果G是原图，则直接对G中所有结点按度进行排序，否则根据算法1，首先生成G的最小生成树G′(3~5行)；2) 每次从当前未被访问集合中选择度最大的结点覆盖其周围所有ε邻居，直至所有结点都被访问为止(6~11行)；3) 依次从查询主干T中的每个顶点出发，在2ε+1的范围内进行宽度优先遍历(BFS)，对于该范围内的任一结点v，如果同为查询主干结点，则在E^*中增加该边(12~16行)；4) 如果u与v的步长为2ε+1但是v不是主干中结点，这种情况称为主干未完全覆盖原图，这将造成一些路径信息无法正确计算，为了避免这种情况发生，将这类结点也加入主干中，以实现完全覆盖(17~19行)；5) 对于其他非主干结点，则将该顶点u设为v的标签(20~21行).

算法2为递归生成查询子图，为G中所有结点设置标签的过程.它依次将当前生成的查询主干作为输入，循环生成查询子图，直至T中只剩一个结点为止.

在介绍利用可达主干进行可达查询之前，首先给出一个性质：给定图G=(V,E)，如果任意两个结点u，v(u∈V，v∈V)可达，则它们或者在2ε步内可达，或者通过某一级区域中心结点可达.

根据查询主干特点，该性质是显而易见的.

算法3给出了通过多级社区中心标签进行距离查询的基本框架.该过程主要包括两个基本步骤：1) 如果u和v有共同的社区中心，则两者的距离可以通过局部搜索或者与相同社区中心之和计算；2) 如果u和v没有共同社区中心，则可以逐级向上查找直至产生交集或者查找到最高级中心为止.

对于查询主干创建，主要时间代价为对图中结点的排序、临近结点的遍历及最小生成树的建立.其中排序时间代价为O(∑klgk)，其中k的初值为n，其他为各级查询主干结点个数，根据实验证明本算法收敛速度非常快，对于大型规模的图数据也仅需要运行少数几级即可创建所有结点的标签.对于临近结点遍历的代价为O(∑(k+e))，其中k为各级主干结点个数，初值为n；e为各级主干边的个数，初值为m.存储代价为O(kn)，其中k为各结点到达社区中心覆盖的个数，因为图数据的差异，无法确定k的规模，但是从实验结果看，绝大多数结点被覆盖的中心规模是可控的，对查询效果影响不大，尤其是稀疏图效果更明显.

对于查询效率，主要通过遍历查找结点标签以及计算两个结点标签集的交集实现距离计算.根据结点标签的性质，这种遍历类似于树的遍历，所以最坏情况下的时间复杂度为O(k+s)，k和s分别为两个结点各自生成的树状标签集的大小.

为了测试本算法的效率，利用一系列实验进行了验证，实验平台为一台高性能Windows服务器，处理器为Intel Xeon 2.10GHz ，主存为16GB.全部算法采用C++语言实现.在所有的实验中，统一限定ε值为2.

在实验中，重点测试3个重要指标:索引创建时间、索引大小和查询时间.对于查询时间，通过随机生成的1×10⁵次查询的合计时间来进行评价.为了测试算法的综合运行效率，利用随机生成的7组人工数据来对各算法进行综合对比，其结点数量从1×10³至2×10⁷.

本算法的参照对象是由Akiba提出的Pruned Landmark Labeling算法^[6](简称PLL)，该算法利用可剪枝的BFS来为原图的所有结点创建标签式索引，图 3和图 4给出了两个算法的索引创建时间和索引大小.从实验结果可以看出，本算法执行时间和索引规模都远远小于PLL算法，而当图结点规模大于2×10⁶时，PLL算法已经无法正常运行，而本算法仍然可以正常运行.

图 3(Figure 3)

Fig. 3

图 3 创建时间结果图Fig. 3 The results of construction time

图 4(Figure 4)

Fig. 4

图 4 索引大小结果图 Fig. 4 The results of index size

图 5给出算法的查询时间，当结点规模较小时，PLL的查询时间趋近于0，所以本文没有给出其查询时间实验结果.但从图中可以看出，虽然本文的算法没有实现常数时间查询，但是与极端算法BFS相比，大幅度降低了查询时间.

图 5(Figure 5)

Fig. 5

图 5 查询时间结果图 Fig. 5 The results of query time

有关ε取值问题，在实验中发现当ε=2时，原图结点的数量已经被压缩的非常可观，通常情况下，不建议设置ε>4.因为这样查询主干的规模虽然很小，但是会大幅度降低查询效率，在某些极端情况下，已经与BFS的查询效率相当.

从实验结果可以看出，本文算法在索引创建时间、索引大小和查询效率等方面比现有算法都有较大提高，并可以实现对大规模图数据的高效处理.

本文针对目前大规模图数据距离查询效率较低，现有方法可扩展性较差的问题，提出了多级社区中心标签的方法.该方法可以实现较低的创建时间、较少的存储代价和较高的查询效率，尤其对于大规模及超大规模图数据的处理，本文给出了一个比较可行的解决思路.另外，本算法的局部特性也非常适合分布式图数据的处理，今后将把研究重点放到这类数据的高效处理中.