基于壓縮的圖的零漏包率割點(diǎn)求解算法

李發(fā)明　李建中　張冠男

摘 要：隨著需求的增大，數(shù)據(jù)規(guī)模迅速增長。同樣在圖的應(yīng)用方面，圖的規(guī)模也成爆炸性增長，這樣，圖上的相關(guān)操作也因?yàn)閳D的規(guī)模巨大而變得異常艱難，這就需要研究者們提出新的方法來減少圖上操作的難度。割點(diǎn)的查詢是圖的一個(gè)重要操作，提出了一種新的基于壓縮的割點(diǎn)求解算法，在壓縮的圖上迅速確定原圖上是否存在割點(diǎn)，若存在割點(diǎn)則返回全部可能割點(diǎn)，不會(huì)漏掉任何一個(gè)割點(diǎn)。同時(shí)，由于任何圖應(yīng)用中都會(huì)存在圖的維護(hù)，提出一種在壓縮圖上進(jìn)行增量維護(hù)的算法，避免了重新的計(jì)算，經(jīng)過一次壓縮后，壓縮圖可以永久使用。

關(guān)鍵字：割點(diǎn)；拓?fù)湎嗨菩裕?壓縮算法； 割點(diǎn)求解； 增量維護(hù)算法

中圖分類號(hào)：TP311.13 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引 言

割點(diǎn)求解是圖的重要操作，因?yàn)槿绻B通圖中存在割點(diǎn)，這個(gè)圖就會(huì)被該點(diǎn)分裂成多個(gè)連通分量，找出這樣的點(diǎn)并且給予特別維護(hù)將會(huì)使圖保持良好的連通性，這一過程在無線傳感器網(wǎng)絡(luò)和配電網(wǎng)絡(luò)中具有重要作用[1]。傳統(tǒng)的深度優(yōu)先搜索樹算法[2]可以在O（V + E）復(fù)雜度下求解割點(diǎn)，但是該算法處理的只是小規(guī)模圖，同時(shí)算法有著一個(gè)重大缺陷，那就是每當(dāng)圖有所改變后就要重新運(yùn)行，對(duì)于經(jīng)常發(fā)生改變的圖，傳統(tǒng)算法將產(chǎn)生巨大的計(jì)算開銷。

圖壓縮已經(jīng)開展了大量研究[3-12]。其中，文獻(xiàn)[3-5]利用web網(wǎng)絡(luò)的url的字典序和相似網(wǎng)頁的超鏈相似性進(jìn)行合并壓縮。文獻(xiàn)[6]在加權(quán)圖上壓縮，如果頂點(diǎn)和邊上的權(quán)值近似相等，則將頂點(diǎn)邊合并，權(quán)值取平均值。文獻(xiàn)[7-9]則利用鄰居節(jié)點(diǎn)壓縮無向圖，但是這些算法并沒有保持圖的結(jié)構(gòu)性質(zhì)，類似聚類算法，如文獻(xiàn)[10-11]中提出的相應(yīng)聚類算法。文獻(xiàn)[12]利用矩陣消除冗余的節(jié)點(diǎn)，但是該方法只針對(duì)稀疏圖。

根據(jù)以上研究結(jié)果，本文提出了一種基于鄰接頂點(diǎn)的相似性的壓縮方法來壓縮圖，得到較小規(guī)模的圖，在壓縮圖上求解割點(diǎn)，同時(shí)實(shí)現(xiàn)壓縮圖的增量維護(hù)算法，而無需在原圖上進(jìn)行更新后再壓縮，避免重新計(jì)算的多余代價(jià)。

1 基本概念和拓?fù)湎嗨菩?/p>

定義1割點(diǎn)： 對(duì)于圖G=（V，E），對(duì)于點(diǎn)u∈ V，u為割點(diǎn)當(dāng)且僅當(dāng)移除u點(diǎn)后，存在某兩個(gè)點(diǎn)x，y∈V是不連通的。

定義2 拓?fù)湎嗨菩裕簩?duì)于圖G=（V，E），u，v∈V，uv∈E，u和v的鄰接頂點(diǎn)集合分別為U={u1，u2，u3 ...}-{v}和T={v1，v2，v3...}-{u}，S = U ∩ T，如果u和v滿足下列性質(zhì)，則u和v為拓?fù)湎嗨泣c(diǎn)，其中a、b分別為u和v鄰接頂點(diǎn)的下標(biāo)，

（1）S=φ；

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

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

對(duì)于所有的ua∈U-S，vb∈V-S，sc∈S，

（1） 若ua和sc鄰接，則必存在vb和sc鄰接；

（2） 若ua和sc不鄰接，則必存在vb和sc不鄰接；

上述拓?fù)湎嗨贫x可以分為兩種：一種是U和T完全相同，可將其稱為α1相似，直觀上相似點(diǎn)的所有鄰居節(jié)點(diǎn)完全相同，如上述條件2；另一種是U和T不完全相同或者完全不相同，可稱為α2相似，直觀上相似點(diǎn)的所有鄰居節(jié)點(diǎn)不完全相同或完全不同，如上述條件3和1。

圖1為一無線傳感器網(wǎng)絡(luò)圖，可借助改圖來解釋已給出的相似性定義。

圖1 無線傳感器網(wǎng)絡(luò)圖

Fig.1 Wireless sensor network

由圖1可見，兩點(diǎn)滿足相似性定義的（1），為α2相似，因?yàn)閮烧叩泥徑禹旤c(diǎn)沒有交集；E、C滿足相似性定義的3，為α2相似，因?yàn)镋的鄰接點(diǎn)U不和C鄰接，C的鄰接點(diǎn)中同樣存在V、W、B不和E鄰接；P、J滿足相似性定義（2），為α1相似，因?yàn)镻、J的鄰居節(jié)點(diǎn)完全相同。

定義3 拓?fù)湎嗨茐嚎s： 對(duì)于圖G=（V，E），u，v∈V，uv∈E，若u和v滿足拓?fù)湎嗨菩裕瑒t將兩個(gè)點(diǎn)合并為一個(gè)超級(jí)節(jié)點(diǎn)，和u、v鄰接的點(diǎn)改為同超級(jí)節(jié)點(diǎn)鄰接，該過程稱為拓?fù)湎嗨茐嚎s。

定義4 超級(jí)結(jié)點(diǎn)的大小：超級(jí)結(jié)點(diǎn)內(nèi)所含原始圖中頂點(diǎn)的數(shù)目稱為超級(jí)結(jié)點(diǎn)的大小。

此處需要注意的是，對(duì)于任意兩個(gè)超級(jí)結(jié)點(diǎn)，如果這兩個(gè)結(jié)點(diǎn)的大小相同，并且滿足拓?fù)湎嗨菩裕匀豢梢岳^續(xù)進(jìn)行拓?fù)湎嗨茐嚎s。

2 壓縮算法

本文的壓縮算法即基于上述提出的拓?fù)湎嗨菩浴Ｔ撍惴ㄟ\(yùn)行中存在著預(yù)處理程序Pre，Pre就是將度為1的點(diǎn)x直接添加到Vr中，并添加一壓縮過標(biāo)記，因?yàn)楹忘c(diǎn)x直接鄰接的點(diǎn)y一定為割點(diǎn)，而點(diǎn)y則一定可將點(diǎn)x和圖原圖分離開，無需再做任何壓縮。同時(shí)將點(diǎn)y放入割點(diǎn)結(jié)果集中，以便后邊的割點(diǎn)求解。

由于相似的點(diǎn)的數(shù)目會(huì)隨著算法的運(yùn)行而逐漸減少，壓縮效果也會(huì)逐漸降低。因而，可在算法中人為設(shè)置迭代壓縮次數(shù)，通過人為設(shè)置的迭代次數(shù)來平衡壓縮代價(jià)和壓縮效果。

算法TC

輸入：G=（V，E），迭代次數(shù)d；

輸出：壓縮圖Gr = （Vr，Er）；

（1）While d --

（2） Vr =φ，Er =φ

（3） Pre（V，E）

（4） For 每一個(gè)沒有被做過壓縮標(biāo)記的頂點(diǎn)v

（5） If v和其鄰接節(jié)點(diǎn)u拓?fù)湎嗨?/p>

（6） 合并vu為超級(jí)結(jié)點(diǎn)s，同時(shí)將v、u做 壓縮過標(biāo)記

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

（8） s做α1相似標(biāo)記

（9） Else

（10） s做α2相似標(biāo)記

（11） Vr = s∪Vr

（12） Else

（13） 將v做壓縮過標(biāo)記

（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 割點(diǎn)求解

在壓縮圖上求解割點(diǎn)，會(huì)將所有割點(diǎn)求解出來，但是由于壓縮過程中采用拓?fù)湎嗨菩詴?huì)將割點(diǎn)和一些非割點(diǎn)判定為相似并壓縮到一起，這樣會(huì)將不是割點(diǎn)的點(diǎn)包含進(jìn)來，在割點(diǎn)求解后這些點(diǎn)也將隨同割點(diǎn)一起返回，這些點(diǎn)也同樣需要重點(diǎn)維護(hù)，因其與割點(diǎn)直接相連，擔(dān)當(dāng)著同樣重要的連接作用。

本文的算法雖然會(huì)將非割點(diǎn)返回，但是不會(huì)漏掉任何割點(diǎn)，不會(huì)出現(xiàn)任何漏包現(xiàn)象，所以我們的割點(diǎn)求解算法是0漏包算法。

算法CD

輸入：壓縮圖Gr = （Vr，Er）；

輸出：所有可能的割點(diǎn)的集合；

1. 采用傳統(tǒng)深度優(yōu)先搜索樹算法得出壓縮圖上全部割點(diǎn)v1、v2 、v3……

2. 對(duì)于每個(gè)壓縮圖上割點(diǎn)v

3. If v的相似標(biāo)記為α2

4. 輸出v內(nèi)全部結(jié)點(diǎn)

4 增量維護(hù)

由于已經(jīng)得到了圖的所有可能割點(diǎn)，其后就可以對(duì)圖的割點(diǎn)進(jìn)行重點(diǎn)維護(hù)，原始圖上邊和點(diǎn)的減少也會(huì)較難發(fā)生。但是實(shí)際的應(yīng)用圖經(jīng)常會(huì)增加結(jié)點(diǎn)和邊，如果采用傳統(tǒng)深度優(yōu)先搜索樹算法就需要重新計(jì)算割點(diǎn)，相應(yīng)地就增加了計(jì)算代價(jià)。基于這一問題，本文再次提出了增量維護(hù)算法，可以在壓縮圖上進(jìn)行邊和點(diǎn)的更新，同時(shí)可以在更新后的圖上繼續(xù)利用第3節(jié)提出的CD算法求解割點(diǎn)。

算法IM

輸入：壓縮圖Gr = （Vr，Er），邊更新pq；

輸出：新的壓縮圖 = （ ， ）；

（1）查詢p、q所在的超級(jí)結(jié)點(diǎn)P、Q（P、Q∈Vr）；

（2）If PQ∈Er

（3） 結(jié)束算法

（4）Else

（5） Er= PQ∪Er

（6） If P點(diǎn)和Q點(diǎn)拓?fù)湎嗨?/p>

（7） 合并PQ作為超級(jí)結(jié)點(diǎn)，更新Vr 和Er

（8）算法結(jié)束；

上述算法處理邊的更新，點(diǎn)的更新同邊更新類似，只是相當(dāng)于向壓縮圖中增加了多條邊，處理過程同上。

5 實(shí)驗(yàn)

文中進(jìn)行兩組實(shí)驗(yàn)來驗(yàn)證提出算法的有效性，實(shí)驗(yàn)數(shù)據(jù)來自斯坦福大學(xué)的SNAP計(jì)劃（http：//snap.stanford.edu/data/）。一個(gè)是本文的TC算法得到的壓縮圖的壓縮比，分別給出不同迭代次數(shù)下的圖的壓縮效果；另一個(gè)是在圖更新過程中，本文的算法同深度優(yōu)先搜索樹相比所節(jié)省的時(shí)間。

驗(yàn)證過程中，壓縮比λ定義為：

λ = （1）

為在圖中表示方便，采用百分?jǐn)?shù)形式。

圖2為進(jìn)行遞歸壓縮一次、兩次和三次所得到的壓縮比。

圖2 不同迭代次數(shù)下的壓縮比

Fig.2 The ratio of compression with different iterations

文中使用深度優(yōu)先搜索樹算法分別在壓縮圖和原始圖上求解割點(diǎn)，圖3三條曲線的縱軸為深度優(yōu)先搜索樹算法在壓縮后的圖上的割點(diǎn)求解時(shí)間和在原始圖上的割點(diǎn)求解時(shí)間的相對(duì)比值，三條曲線分別對(duì)應(yīng)壓縮圖一次、兩次和三次所得到的壓縮圖。

圖3 不同迭代次數(shù)下的運(yùn)行時(shí)間比

Fig.3 The ratio of running time with different iterations

6 結(jié)束語

通過采用壓縮方法，將原來大規(guī)模的圖壓縮到了較小的規(guī)模，得到了很好的壓縮比。同時(shí)在壓縮圖上可以利用割點(diǎn)求解算法，得到所有可能的割點(diǎn)。壓縮圖還可以進(jìn)行增量維護(hù)，無需如傳統(tǒng)算法般重新在原始圖上計(jì)算割點(diǎn)，只需要在維護(hù)后的圖上繼續(xù)計(jì)算割點(diǎn)，大大地節(jié)省了計(jì)算時(shí)間。

參考文獻(xiàn)：

[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.