一種改進的鄰接關系可查詢壓縮算法

高圣巍,彭 超

(華東師范大學軟件學院,上海200062)

一種改進的鄰接關系可查詢壓縮算法

高圣巍,彭 超

(華東師范大學軟件學院,上海200062)

目前多數(shù)數(shù)據(jù)壓縮算法不能直接在壓縮結果上進行數(shù)據(jù)查詢,大數(shù)據(jù)的線性化壓縮算法雖然可直接在壓縮后的數(shù)據(jù)上進行鄰接關系查詢,但壓縮率較低。針對該問題,對線性化壓縮的實現(xiàn)原理進行研究,分析MPk線性化算法在不同社會網(wǎng)絡樣本下的壓縮效率,發(fā)現(xiàn)線性化壓縮結果中存在冗余信息,并針對該情況設計改進算法,刪去原有數(shù)據(jù)結構中的冗余部分,進一步提高壓縮率。實驗結果證明,改進算法的時間復雜度與原算法相同,壓縮率平均提升23%。

線性化壓縮算法;大數(shù)據(jù);社會網(wǎng)絡;啟發(fā)式算法;Eulerian數(shù)據(jù)結構

1 概述

近些年來,由于在生物、天文、經(jīng)濟和社會網(wǎng)絡等諸多領域的應用,超大規(guī)模復雜圖的相關研究受到廣泛重視。這當中社會網(wǎng)絡尤為突出,其能幫助人們發(fā)現(xiàn)潛在問題,做出決策,管理人際關系、組織機構乃至國家社會。社會網(wǎng)絡通常被建模為超大圖,成員對應圖的節(jié)點,而成員間的關系則為圖的邊。這些關系可以是友誼、血緣、貿(mào)易或沖突等,是研究的重點對象。因此,在分析社會網(wǎng)絡時,查詢鄰居節(jié)點是最頻繁也最重要的工作之一[1]。

社會網(wǎng)絡一般都由上百萬的節(jié)點和邊組成,存儲社會網(wǎng)絡需要很大的空間。問題也隨之而來:如何壓縮網(wǎng)絡數(shù)據(jù)以節(jié)省空間?好的算法會利用社會網(wǎng)絡的一些特性來獲得高壓縮率,比如節(jié)點通常會以簇的形式出現(xiàn)在社會網(wǎng)絡中。在以往,人們在查詢社會網(wǎng)絡時,都會將其圖數(shù)據(jù)解壓縮。如果查詢操作能直接在壓縮數(shù)據(jù)上進行,將可以大量節(jié)省解壓縮的時間。本文利用線性化壓縮的特性,提出一種改進的線性化壓縮算法。該算法不需要解壓即可查詢,通過計算節(jié)點間的關聯(lián)度,調(diào)整節(jié)點在壓縮結果中的排放位置,從而提高線性化壓縮的壓縮率。

2 相關研究

在大規(guī)模復雜網(wǎng)絡數(shù)據(jù)的壓縮方面,國內(nèi)外已經(jīng)有一些相關研究工作。例如:文獻[2]將壓縮問題轉(zhuǎn)化為在有向圖中尋找最小生成樹的過程;文獻[3]通過廣度優(yōu)先遍歷的方法壓縮圖,并優(yōu)化了壓縮圖的編碼方式;文獻[4]介紹了幾種常用無損數(shù)據(jù)壓縮算法。

針對海量社會網(wǎng)絡數(shù)據(jù),要獲得高壓縮率,首先,圖中頂點出現(xiàn)的順序十分重要,文獻[5]說明了節(jié)點的排列對壓縮實際帶來的影響。其次,設計良好的數(shù)據(jù)結構來存儲數(shù)據(jù)十分重要。文獻[6-7]中總結了一些壓縮社會圖的方法,主要有記錄鄰接表、記錄間距、引用壓縮和差量壓縮,并且設計了通用的圖壓縮框架。在后續(xù)的工作中,Paolo Boldi采用Task Decomposition技術[8],將壓縮框架擴展為在多核架構上運行,提高壓縮速度。文獻[9]分析了社會網(wǎng)絡不同于普通圖的特性,提出通過找出具有相似鄰居的節(jié)點進行壓縮的方法。這些壓縮方法都有著較好的壓縮率,但在社會網(wǎng)絡上做查詢操作前,都要先將壓縮的圖解壓。

文獻[10]提出了一種“線性化”技術,這種技術將社會網(wǎng)絡中的節(jié)點表示成一個序列,序列中的每個節(jié)點僅存儲序列中相鄰節(jié)點的鄰居關系,雖然這樣壓縮率與其他壓縮算法稍有降低,但這種技術使得查詢可以直接在壓縮后的結果上進行。尋找這樣一種序列基本上被認為是NP完全的問題,因此一般來說不存在有效的多項式時間算法,文獻[11]對此作了闡述。

本文對線性化壓縮的實現(xiàn)原理進行研究,分析線性化方法在不同社會網(wǎng)絡樣本下的壓縮效率,發(fā)現(xiàn)線性化壓縮結果中存在的冗余信息,并針對該情況提出一種改進算法。

3 MPK線性化算法

一個社會網(wǎng)絡可以用一個有向圖G(V,E)表示,其中,V表示圖中點的集合;E表示圖中邊的集合,即E∈V×V,本文假定網(wǎng)絡是簡單的(即沒有自環(huán)),源節(jié)點到目的節(jié)點最多只有一條邊。有向圖的邊用e=(u,v)表示,其中,u為源節(jié)點;v為目的節(jié)點,且(u,v)≠(v,u)。圖1是一個有向圖示例。

圖1 有向圖G

定義有向圖對應的無向圖,無向圖存在邊,當且僅當(u,v)∈E(G)或(v,u)∈E(G)。圖2是圖1中有向圖G對應的無向圖。

圖2 G對應的無向圖

定義有向圖對應的轉(zhuǎn)置圖GT,轉(zhuǎn)置圖存在邊(u,v)∈E(GT),當且僅當(v,u)∈E(G)。

對有向圖G的查詢分為2種:查詢節(jié)點u指向的所有鄰點{v|(u,v)∈G};查詢所有指向節(jié)點u的鄰點{v|(v,u)∈G}。為有效支持這2種查詢,多數(shù)壓縮算法需要存儲圖G和轉(zhuǎn)置圖GT。而線性化算法將圖G進行編碼,節(jié)省了大量的空間,同時支持在已編碼的結果上直接作查詢。下文將給出MPk的定義和用 MPk于存儲圖G的編碼的數(shù)據(jù)結構——Eulerian結構。

3.1 MPk線性化定義

定義1設S=(vi1,vi2,…,vim)是由圖G的節(jié)點組成的序列,如果G中所有的節(jié)點在S中至少出現(xiàn)一次,則稱S覆蓋了圖G,這里請注意S中前后相鄰出現(xiàn)的點不一定在G中存在鄰接邊。

定義2給定一個覆蓋圖G的序列S,dist(u,v)表示序列S中節(jié)點u和節(jié)點v最相近的距離。

定義3給定一個覆蓋圖G的序列S,如果對于圖G中所有的邊(u,v)∈E(G),在S中都有dist(u,v)≤k,則稱S是圖G的MPk階線性化序列。圖G中的節(jié)點允許在S中重復出現(xiàn)。

3.2 Eulerian數(shù)據(jù)結構

Eulerian數(shù)據(jù)結構用來保存對圖G的MP線性化序列L,它是一個數(shù)組,L的長度用|L|表示,設v(i)是出現(xiàn)在數(shù)組第i個位置的節(jié)點,v(i)保存2個信息:

(1)鄰居信息:對于MP1線性化序列,鄰居信息占2 bit,分別記錄有向邊(v(i),v(i+1))和(v(i+1),v(i))是否屬于E(G)。對于MPk線性化,每個元素需要一個2kbit的比特串保存鄰居信息,其中,第2j-1個和第2j個比特分別記錄有向邊(v(i),v(i+j))和(v(i+j),v(i))是否屬于E(G)。

(2)節(jié)點指針:同一節(jié)點在序列中允許重復出現(xiàn)。節(jié)點指針指向節(jié)點下一次出現(xiàn)的位置。節(jié)點最后一次出現(xiàn)時,節(jié)點指針指向它首次出現(xiàn)的位置。

圖G的MP1和MP1線性化序列的Eulerian表示如圖3和圖4所示。

圖3 圖G的MP1線性化序列的Eulerian表示

圖4 圖G的MP2線性化序列的Eulerian表示

4 MPk線性化的改進

4.1 Eulerian數(shù)據(jù)結構的存儲冗余

在稀疏圖中,節(jié)點的出入度都較小,在k比較大的情況下進行MPk壓縮,會導致Eulerian數(shù)據(jù)結構中的鄰居信息存儲著大量的不連續(xù)的0 bit(表示節(jié)點之間沒有邊相連)。假設圖G的MPk序列的某一段如下排列:a,u1,v1,u2,v2,…,uk/2,vk/2,其中,,則節(jié)點a的鄰居信息表示為:001100110011…(共2kbit)。如果變換節(jié)點出現(xiàn)的順序為a,u1,u2,…,uk/2,v1,v2,vk/2,同時保證序列仍然符合MPk的定義,則節(jié)點a的鄰居信息變?yōu)?0000…01111…1(0 bit與1 bit各k個),可以省去開始的k個0 bit,從第1個1 bit開始記錄鄰居信息。由于鄰居信息的長度不再固定為2k,因此需要增加lbk個比特記錄鄰居信息的比特串長度。通常lbk遠小于k,所以,整體壓縮率仍然是提高的。

改進的Eulerian數(shù)據(jù)結構除了保存圖G的節(jié)點外,還保存著一個二元組(NI,δN),其中,δN表示鄰居信息比特串的長度;NI表示鄰居信息。

4.2 改進的MPk線性化算法

本文通過算法調(diào)整序列中節(jié)點出現(xiàn)的順序。用數(shù)組L來記錄線性化序列中的節(jié)點,初始時L長度為0,此時隨機選擇一個節(jié)點加入到L。當向L加入新節(jié)點時,計算每個候選節(jié)點u與L中最后k個節(jié)點的關聯(lián)度,稱之為權值。設當前L的長度為|L|,權值C的計算方法如下:

最終,權值最大的節(jié)點優(yōu)先加入數(shù)組L中。

結合上述的分析,本文對MPk算法進行了重新設計,并使用改進的Eulerian數(shù)據(jù)結構,稱為IMPk算法。算法描述如下:

輸入圖G,k

輸出G的線性化序列

4.3 MPk與IMPk的計算復雜度對比

在構造線性化序列時,IMPk算法與MPk算法的主要區(qū)別在于選擇新加入節(jié)點時的策略不同,MPk算法選擇與X集合有最多相連邊的節(jié)點優(yōu)先加入序列,完成這個過程的步驟如下:

(1)找出X集合中節(jié)點的所有鄰居,最多有個鄰居;

(2)對于X集合的每個鄰居v,判斷v與X集合共有多少邊相連,復雜度為c1×K,其中,c1為判斷兩節(jié)點之間是否有邊的開銷。因此,MPk算法完成整個選擇的復雜度為:

而IMPk算法在上述第(2)步加入了權值計算,對于X集合的每個鄰居v,判斷其權值的復雜度為(c1+c2)×K,其中,c2表示計算v與X中節(jié)點的距離所花費的開銷,完成整個選擇的復雜度為:(c1+c2)×K×

由于X集合每次更新一個節(jié)點,根據(jù)其中節(jié)點順序可以快速計算到v的距離,c2的值比c1小很多。因此,IMPk算法計算復雜度與MPk算法復雜度基本相當。

4.4 MPk線性化的長度下界

設MPk線性化序列L的長度為|L|,L中的每個節(jié)點需要lb|L|個比特保存節(jié)點指針,2k個比特保存鄰居信息,整個序列需要保存。本文用圖G中每條有向邊,在壓縮結果中占用的bit數(shù)來衡量壓縮率,稱為BPE(Bits Per Edge),其值為:

本文給出改進MPk線性化序列長度的下界,設v∈V(G),L中每個節(jié)點鄰居信息占用2kbit,在最好情況下,只能記錄它的k個鄰居,所以,v在最終序列L中至少出現(xiàn)「deg(v)/k?次,deg(v)為節(jié)點v的度數(shù)。則L的長度至少為:

5 實驗與結果分析

本文使用C++實現(xiàn)了改進的算法,并用網(wǎng)站http://snap.stanford.edu/data中提供的社會網(wǎng)絡圖數(shù)據(jù)作為輸入,分別取k=10,k=15,k=20,k=30為參數(shù)進行實驗。實驗結果如表1和表2所示,表中數(shù)據(jù)為原 MPk算法與 IMPk算法運行結果的BPE值。

表1 MP10,MP15與IMP10,IMP15序列壓縮結果比較

表2 MP20,MP30與IMP20,IMP30序列壓縮結果比較

可以看出,改進后的IMPk算法之平均壓縮效率比原MPk算法平均高出大約23%。本文對實驗結果作進一步分析后發(fā)現(xiàn),社會網(wǎng)絡的聚合度對壓縮效率有很大的影響。在這些社會網(wǎng)絡中,web-Standford圖中的節(jié)點都以簇的形式分布[12],簇內(nèi)的節(jié)點連接緊密,而與其他簇連接較少,因此該網(wǎng)絡的壓縮效率最好,達到6.37 bits/edge,比原MPk算法效果提升38%。在email-EuAll圖中,各節(jié)點的鄰居分布比較隨機,使得算法在執(zhí)行時,加入了許多隨機節(jié)點(即跳至外層while循環(huán),選擇隨機節(jié)點)來保證序列符合MPk定義。最終,改進算法仍比原算法有2%的效率提升。

6 結束語

本文改進社會網(wǎng)絡的線性化壓縮算法,通過計算權值,優(yōu)化最終序列中的節(jié)點順序和Eulerian數(shù)據(jù)結構。實驗結果證明,改進后的壓縮算法的壓縮率相比原算法平均提高了23%。下一步工作是深入分析社會網(wǎng)絡的聚合程度對算法的影響,改進算法以適應社會網(wǎng)絡的不同特征。

[1] 馬 帥,李 佳,劉旭東,等.大數(shù)據(jù)時代的圖搜索技術[J].信息通信技術,2013,(6):44-51.

[2] Adler M,Mitzenmacher M.Towards Compressing Web Graphs[C]//Proceedings of 2001 Data Compression Conference.Snowbird,USA:IEEE Press,2001:202-213.

[3] Apostolico A,DrovandiG.Graph Compression by BFS[J].Algorithms,2009,2(3):1031-1044.

[4] 鄭翠芳.幾種常用無損數(shù)據(jù)壓縮算法研究[J].計算機技術與發(fā)展,2011,21(9):73-76.

[5] Boldi P,Santini M,Vigna S.Permuting Web Graphs, Algorithms and Models for the Web-Graph[M].Berlin, Germany:Springer,2009:116-126.

[6] Boldi P,Vigna S.The WebGraph Framework I: Compression Techniques[C]//Proceedings of the 13th International Conference on World Wide Web.New York, USA:ACM Press,2004:595-602.

[7] Boldi P,Vigna S.The WebGraph Framework II:Codes for the World-wide Web[C]//Proceedings of 2004 Data Compression Conference.Snowbird,USA:IEEE Press, 2004:528.

[8] Boldi P,Rosa M,Santini M,et al.Layered Label Propagation:A Multiresolution Coordinate-free Ordering for Compressing Social Networks[C]//Proceedings of the 20th International Conference on World Wide Web. Hyderabad,India[s.n.],2011:587-596.

[9] Chierichetti F,Kumar R,Lattanzi S,et al.On Compressing Social Networks[C]//Proceedings of the 15th ACM SIGKDD InternationalConference on Knowledge Discovery and Data Mining.Paris,France: ACM Press,2009:219-228.

[10] Maserrat H,Pei J.Neighbor Query Friendly Compression of Social Networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington D.C.,USA: [s.n.]:2010:533-542.

[11] Papadimitriou C H.The NP-completeness of the Bandwidth Minimization Problem[J].Computing,1976,16(3): 263-270.

[12] Easley D,Kleinberg J.Networks,Crowds,and Markets[M]. Cambridge,UK:Cambridge University Press,2010.

編輯 金胡考

An Improved Compression Algorithm Supporting Neighbor Query

GAO Shengwei,PENG Chao
(Software Engineering Institute,East China Normal University,Shanghai 200062,China)

Nowadays,most data compression algorithms do not support performing query directly on compressed data. Though the compression algorithm can perform query neighbor relations on compressed result,the compression ratio is relatively low.To solve the problem,this paper does some research on the principle of linearization compression algorithm.It analyzes the compression ratio of MPkalgorithm in different sample social network and finds the redundant information in compressed result.To eliminate these redundant information,it improves the original data structure, removes the unnecessary bits and improves the compression ratio.Experiments show that the proposed algorithm has same time complexity compared with primal algorithm,but the compression ratio can be increased by 23%in average.

linearization compression algorithm;big data;social network;heuristic algorithm;Eulerian data structure

1000-3428(2015)01-0061-04

A

TP312

10.3969/j.issn.1000-3428.2015.01.011

國家自然科學基金資助項目(91118008,61232006);國家“863”計劃基金資助重點項目(SQ2010AA0101016001);上海市教育委員會科研創(chuàng)新基金資助項目(44440590)。

高圣巍(1989-),男,碩士研究生,主研方向:移動路由算法;彭 超,副教授。

2014-01-20

2014-03-15 E-mail:51111500026@ecnu.cn

中文引用格式:高圣巍,彭 超.一種改進的鄰接關系可查詢壓縮算法[J].計算機工程,2015,41(1):61-64.

英文引用格式:Gao Shengwei,Peng Chao.An Improved Compression Algorithm Supporting Neighbor Query[J]. Computer Engineering,2015,41(1):61-64.