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

高圣巍,彭 超

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

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

高圣巍,彭 超

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

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

線性化壓縮算法;大數據;社會網絡;啟發式算法;Eulerian數據結構

1 概述

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

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

2 相關研究

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

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

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

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

3 MPK線性化算法

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

圖1 有向圖G

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

圖2 G對應的無向圖

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

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

3.1 MPk線性化定義

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

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

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

3.2 Eulerian數據結構

Eulerian數據結構用來保存對圖G的MP線性化序列L,它是一個數組,L的長度用|L|表示,設v(i)是出現在數組第i個位置的節點,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)節點指針:同一節點在序列中允許重復出現。節點指針指向節點下一次出現的位置。節點最后一次出現時,節點指針指向它首次出現的位置。

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

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

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

4 MPk線性化的改進

4.1 Eulerian數據結構的存儲冗余

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

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

4.2 改進的MPk線性化算法

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

最終,權值最大的節點優先加入數組L中。

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

輸入圖G,k

輸出G的線性化序列

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

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

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

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

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

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

4.4 MPk線性化的長度下界

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

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

5 實驗與結果分析

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

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

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

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

6 結束語

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

[1] 馬 帥,李 佳,劉旭東,等.大數據時代的圖搜索技術[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] 鄭翠芳.幾種常用無損數據壓縮算法研究[J].計算機技術與發展,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);上海市教育委員會科研創新基金資助項目(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.