基于压缩的图的零漏包率割点求解算法

李发明　李建中　张冠男

摘 要：随着需求的增大，数据规模迅速增长。同样在图的应用方面，图的规模也成爆炸性增长，这样，图上的相关操作也因为图的规模巨大而变得异常艰难，这就需要研究者们提出新的方法来减少图上操作的难度。割点的查询是图的一个重要操作，提出了一种新的基于压缩的割点求解算法，在压缩的图上迅速确定原图上是否存在割点，若存在割点则返回全部可能割点，不会漏掉任何一个割点。同时，由于任何图应用中都会存在图的维护，提出一种在压缩图上进行增量维护的算法，避免了重新的计算，经过一次压缩后，压缩图可以永久使用。

关键字：割点；拓扑相似性； 压缩算法； 割点求解； 增量维护算法

中图分类号：TP311.13 文献标识码：A 文章编号：2095-2163（2014）02-

Cut-Vertex discovery on graph with 0-drain package based on compression

LI Faming， LI Jianzhong， ZHANG Guannan

（School of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，China）

Abstract： With the increasing of requirement， the size of data grows very fast. In the application of graph， the size of graph is growing explosively at the same time. So， the operation on graph becomes more and more difficult because of the large size. The researchers should come up with some new ways to reduce the difficulty of operation. The query of cut vertex is an important operation on graph， so the paper puts forward a new algorithm on discovering cut vertex. By using the compressing graph， the result can be confirmed whether there is cut vertices on the original graph quickly. If there are cut vertices， algorithm outputs all the possible cut vertices without dropping any cut vertices. It has been known that any application on graph exists the problem of maintenance. The paper also puts forward an algorithm maintaining the graph incrementally. The algorithm avoid recomputing . The graph can be used forever after compressing.

Keywords： Cut-vertex； Topology similarity； Compression algorithm； Cut-vertex discovery； Incremental maintenance algorithm

0 引 言

割点求解是图的重要操作，因为如果连通图中存在割点，这个图就会被该点分裂成多个连通分量，找出这样的点并且给予特别维护将会使图保持良好的连通性，这一过程在无线传感器网络和配电网络中具有重要作用[1]。传统的深度优先搜索树算法[2]可以在O（V + E）复杂度下求解割点，但是该算法处理的只是小规模图，同时算法有着一个重大缺陷，那就是每当图有所改变后就要重新运行，对于经常发生改变的图，传统算法将产生巨大的计算开销。

图压缩已经开展了大量研究[3-12]。其中，文献[3-5]利用web网络的url的字典序和相似网页的超链相似性进行合并压缩。文献[6]在加权图上压缩，如果顶点和边上的权值近似相等，则将顶点边合并，权值取平均值。文献[7-9]则利用邻居节点压缩无向图，但是这些算法并没有保持图的结构性质，类似聚类算法，如文献[10-11]中提出的相应聚类算法。文献[12]利用矩阵消除冗余的节点，但是该方法只针对稀疏图。

根据以上研究结果，本文提出了一种基于邻接顶点的相似性的压缩方法来压缩图，得到较小规模的图，在压缩图上求解割点，同时实现压缩图的增量维护算法，而无需在原图上进行更新后再压缩，避免重新计算的多余代价。

1 基本概念和拓扑相似性

定义1割点： 对于图G=（V，E），对于点u∈ V，u为割点当且仅当移除u点后，存在某两个点x，y∈V是不连通的。

定义2 拓扑相似性：对于图G=（V，E），u，v∈V，uv∈E，u和v的邻接顶点集合分别为U={u1，u2，u3 ...}-{v}和T={v1，v2，v3...}-{u}，S = U ∩ T，如果u和v满足下列性质，则u和v为拓扑相似点，其中a、b分别为u和v邻接顶点的下标，

（1）S=φ；

（2）若S≠φ，S=U=T；

（3）若S≠φ，S≠U≠T，S={s1，s2，s3…}，

对于所有的ua∈U-S，vb∈V-S，sc∈S，

（1） 若ua和sc邻接，则必存在vb和sc邻接；

（2） 若ua和sc不邻接，则必存在vb和sc不邻接；

上述拓扑相似定义可以分为两种：一种是U和T完全相同，可将其称为α1相似，直观上相似点的所有邻居节点完全相同，如上述条件2；另一种是U和T不完全相同或者完全不相同，可称为α2相似，直观上相似点的所有邻居节点不完全相同或完全不同，如上述条件3和1。

图1为一无线传感器网络图，可借助改图来解释已给出的相似性定义。

图1 无线传感器网络图

Fig.1 Wireless sensor network

由图1可见，两点满足相似性定义的（1），为α2相似，因为两者的邻接顶点没有交集；E、C满足相似性定义的3，为α2相似，因为E的邻接点U不和C邻接，C的邻接点中同样存在V、W、B不和E邻接；P、J满足相似性定义（2），为α1相似，因为P、J的邻居节点完全相同。

定义3 拓扑相似压缩： 对于图G=（V，E），u，v∈V，uv∈E，若u和v满足拓扑相似性，则将两个点合并为一个超级节点，和u、v邻接的点改为同超级节点邻接，该过程称为拓扑相似压缩。

定义4 超级结点的大小：超级结点内所含原始图中顶点的数目称为超级结点的大小。

此处需要注意的是，对于任意两个超级结点，如果这两个结点的大小相同，并且满足拓扑相似性，仍然可以继续进行拓扑相似压缩。

2 压缩算法

本文的压缩算法即基于上述提出的拓扑相似性。该算法运行中存在着预处理程序Pre，Pre就是将度为1的点x直接添加到Vr中，并添加一压缩过标记，因为和点x直接邻接的点y一定为割点，而点y则一定可将点x和图原图分离开，无需再做任何压缩。同时将点y放入割点结果集中，以便后边的割点求解。

由于相似的点的数目会随着算法的运行而逐渐减少，压缩效果也会逐渐降低。因而，可在算法中人为设置迭代压缩次数，通过人为设置的迭代次数来平衡压缩代价和压缩效果。

算法TC

输入：G=（V，E），迭代次数d；

输出：压缩图Gr = （Vr，Er）；

（1）While d --

（2） Vr =φ，Er =φ

（3） Pre（V，E）

（4） For 每一个没有被做过压缩标记的顶点v

（5） If v和其邻接节点u拓扑相似

（6） 合并vu为超级结点s，同时将v、u做 压缩过标记

（7） If v和u为α1相似

（8） s做α1相似标记

（9） Else

（10） s做α2相似标记

（11） Vr = s∪Vr

（12） Else

（13） 将v做压缩过标记

（14） Vr = v∪Vr

（15） For vc 、uc ∈Vr

（16） If p∈vc，q∈uc且pq∈E

（17） vc uc∈Er

（18） V= Vr，E=Er

（19） Return Gr = （Vr，Er）

3 割点求解

在压缩图上求解割点，会将所有割点求解出来，但是由于压缩过程中采用拓扑相似性会将割点和一些非割点判定为相似并压缩到一起，这样会将不是割点的点包含进来，在割点求解后这些点也将随同割点一起返回，这些点也同样需要重点维护，因其与割点直接相连，担当着同样重要的连接作用。

本文的算法虽然会将非割点返回，但是不会漏掉任何割点，不会出现任何漏包现象，所以我们的割点求解算法是0漏包算法。

算法CD

输入：压缩图Gr = （Vr，Er）；

输出：所有可能的割点的集合；

1. 采用传统深度优先搜索树算法得出压缩图上全部割点v1、v2 、v3……

2. 对于每个压缩图上割点v

3. If v的相似标记为α2

4. 输出v内全部结点

4 增量维护

由于已经得到了图的所有可能割点，其后就可以对图的割点进行重点维护，原始图上边和点的减少也会较难发生。但是实际的应用图经常会增加结点和边，如果采用传统深度优先搜索树算法就需要重新计算割点，相应地就增加了计算代价。基于这一问题，本文再次提出了增量维护算法，可以在压缩图上进行边和点的更新，同时可以在更新后的图上继续利用第3节提出的CD算法求解割点。

算法IM

输入：压缩图Gr = （Vr，Er），边更新pq；

输出：新的压缩图 = （ ， ）；

（1）查询p、q所在的超级结点P、Q（P、Q∈Vr）；

（2）If PQ∈Er

（3） 结束算法

（4）Else

（5） Er= PQ∪Er

（6） If P点和Q点拓扑相似

（7） 合并PQ作为超级结点，更新Vr 和Er

（8）算法结束；

上述算法处理边的更新，点的更新同边更新类似，只是相当于向压缩图中增加了多条边，处理过程同上。

5 实验

文中进行两组实验来验证提出算法的有效性，实验数据来自斯坦福大学的SNAP计划（http：//snap.stanford.edu/data/）。一个是本文的TC算法得到的压缩图的压缩比，分别给出不同迭代次数下的图的压缩效果；另一个是在图更新过程中，本文的算法同深度优先搜索树相比所节省的时间。

验证过程中，压缩比λ定义为：

λ = （1）

为在图中表示方便，采用百分数形式。

图2为进行递归压缩一次、两次和三次所得到的压缩比。

图2 不同迭代次数下的压缩比

Fig.2 The ratio of compression with different iterations

文中使用深度优先搜索树算法分别在压缩图和原始图上求解割点，图3三条曲线的纵轴为深度优先搜索树算法在压缩后的图上的割点求解时间和在原始图上的割点求解时间的相对比值，三条曲线分别对应压缩图一次、两次和三次所得到的压缩图。

图3 不同迭代次数下的运行时间比

Fig.3 The ratio of running time with different iterations

6 结束语

通过采用压缩方法，将原来大规模的图压缩到了较小的规模，得到了很好的压缩比。同时在压缩图上可以利用割点求解算法，得到所有可能的割点。压缩图还可以进行增量维护，无需如传统算法般重新在原始图上计算割点，只需要在维护后的图上继续计算割点，大大地节省了计算时间。

参考文献：

[1] XIONG S， LI J. An efficient algorithm for cut vertex detection in wireless sensor networks[C]//Distributed Computing Systems （ICDCS）， 2010 IEEE 30th International Conference on. IEEE， 2010： 368-377.

[2] CORMEN T H， LEISERSON C E， RIYEST R L， et al. “Introduction to Algorithms （Second Edition）”， The MIT Press， 2002

[3] BOLDI P， VIGNA S. The webgraph framework I： compression techniques[C]//Proceedings of the 13th international conference on World Wide Web. ACM， 2004： 595-602.

[4] RAGHAVAN S， GARCIA-MOLINA H. Representing web graphs[C]//Data Engineering， 2003. Proceedings. 19th International Conference on. IEEE， 2003： 405-416.

[5] SUEL T， YUAN J. Compressing the graph structure of the web[C]//Data Compression Conference， 2001. Proceedings. DCC 2001. IEEE， 2001： 213-222..

[6] TOIVONEN H， ZHOU F， HARTIKAINEN A， et al. Compression of weighted graphs[C]//Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2011： 965-973.

[7] GILBERT A C， LEVCHENKO K. Compressing network graphs[C]//Proceedings of the LinkKDD workshop at the 10th ACM Conference on KDD. 2004.

[8] ZHANG N， TIAN Y， PATEL J M. Discovery-driven graph summarization[C]//Data Engineering （ICDE）， 2010 IEEE 26th International Conference on. IEEE， 2010： 880-891.

[9] APOSTOLICO A， DROVANDI G. Graph compression by BFS[J]. Algorithms， 2009， 2（3）： 1031-1044.

[10] NAVLAKHA S， RASTOGI R， SHRIVASTAVA N. Graph summarization with bounded error[C]//Proceedings of the 2008 ACM SIGMOD international conference on Management of data. ACM， 2008： 419-432.

[11] ZHOU Y， CHENG H， YU J X. Graph clustering based on structural/attribute similarities[J]. Proceedings of the VLDB Endowment， 2009， 2（1）： 718-729.

[12] SUN J， BOLLT E M， BEN-AVRAHAM D. Graph compression—save information by exploiting redundancy[J]. Journal of Statistical Mechanics： Theory and Experiment， 2008， 2008（06）： P06001.