グラフ圧縮アルゴリズムの概要

この作業では、主にソーシャル（ソーシャルネットワーク上のユーザー間のリンクのグラフ）およびWebグラフ（サイト間のリンクのグラフ）を圧縮する方法について説明します。



ほとんどのグラフアルゴリズムは十分に研究されており、グラフ要素へのランダムアクセスが可能であるという前提で設計されています。現時点では、ソーシャルグラフのサイズは平均的なマシンのRAMのサイズを超えていますが、同時にハードディスクに簡単に収まります。 妥協点は、特定のクエリにすばやくアクセスできる機能を備えたデータ圧縮です。 2つに焦点を当てます。



a）特定の頂点のエッジのリストを取得します

b）2つの頂点が接続されているかどうかを調べます。



最新のアルゴリズムを使用すると、リンクごとに最大1〜5ビットのデータを圧縮できるため、平均的なマシンで同様のベースで作業できます。 この記事を書きたいのは、vkontakte friendsデータベースを32GBのRAMに収めるきっかけになりました。現在、約3億のアカウントがあり、平均最高度が約100であるため、非常に現実的です。 これに基づいて実験を行います。



興味のあるグラフの一般的なプロパティは次のとおりです。

a）それらが大きい、1 6〜1 9以上のトップおよび約1 9エッジであるという事実-それらをメモリ内で直接操作することは不可能になりますが、1つのハードドライブ上でも簡単に保存できます。 サイトlaw.di.unimi.it/datasets.phpは、このようなデータベースの膨大な範囲全体を提示します。

b）頂点の次数の分布。実際、すべての重要な周波数特性は、べき法則によって（少なくとも漸近的に）記述されます。

c）それらはまばらです。 ピークの平均次数は100〜1000です。

d）頂点が類似している-共通の友人がいる確率は、接続された頂点の方が多くなります。

ボルディとヴィグナ。

このペーパーでは、「自然な」非圧縮形式のグラフはリストの配列で表されます。

node1 -> link11,link12,link13... node2 -> link21,link22,link23.... ....  link[i,j] < link[i,j+1].
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

トップ	頂点度	リブ
15	11	13,15,16,17,18,19,23,24,203,315,1034
16	10	15,16,17,22,23,24,315,316,317,3041
17	0
18	5	13,15,16,17,50

表1.グラフの自然なコーディング。 （例は[2]から取られています）



2つのリンクのインデックス間の差を「ギャップ」と呼びます。

 Gap[i,j] = link[i,j-1] - link[i,j]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

圧縮アルゴリズムの最初のファミリーは、次の2つの基本的なアプローチを使用する方法です。

a）頂点の局所性の活用。 ピークは、多くの場合、「遠い」ピークよりも「近い」ピークを指します。

b）頂点の類似性の活用。 「近い」ピークは同じピークを指します。



これらの2つのステートメントには逆説があります。ピークの「近接」という用語は、類似性によって説明することもできます。その場合、ステートメントは真実になります。 「近接」の概念を説明する上で、私がテストしたアルゴリズムには主な違いがあります。



この主題に関する最初の研究は、明らかにK.ランドール[1]です。 まだ残っているAltavistaのWebグラフを調べたところ、グラフ上のリンクのほとんど（80％）がローカルであり、多数の共通リンクを持っていることがわかり、次の参照コーディングを使用することが提案されました。

-新しい頂点は、「類似」+追加と削除のリストへのリンクとしてエンコードされ、ギャップとニブルコーディングでエンコードされます。

連中はaltavistaをリンクごとに5ビットに圧縮しました（作業中に最悪の圧縮結果を出すようにします）。 このアプローチは、Paolo BoldiとSebastiano Vignaによって大きく開発されました。



彼らは、表2に示すより複雑な参照コーディング方法を提案しました。各頂点は1つの「類似」リンクを持つことができ、RefNrは現在の頂点とそれとの差をエンコードします。 コピーリストは、参照によって取得される頂点をエンコードするビットリストです。対応するコピーリストビットが1の場合、この頂点もエンコードされたものに属します。 次に、Copylistも同様のアルゴリズムでRLEによってエンコードされ、CopyBlocksに変わります。

 01110011010 -> 0,0,2,1,1,0,0
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

長さ-各繰り返しブロックの1 +最初のブロックの値（1または0）を記録します。最後に残っているゼロは破棄できます。



残りの頂点はギャップに変換され、ゼロは個別にコーディングされ（ここではウェブグラフの特別なプロパティが使用されます。これについては以下で説明します）、残りのギャップ（残差）はデジタルコードの1つ（ Golomb 、 Elias Gamma 、およびハフマン極値）でエンコードされます。



表2からわかるように、このエンコードはマルチレベルにすることができます。このマルチレベルの次数はエンコーダーLのパラメーターの1つであり、 Lが大きいとエンコードおよびデコード速度は低下しますが、圧縮率は増加します。

トップ	頂点度	RefNr	コピーブロック数	ブロックをコピー	間隔の数	間隔（相対左インデックス）	間隔の長さ	残差
...	...	...	...	...	...	...	...	...
15	11	0			2	0.2	3.0	5,189,11,718
16	10	1	7	0,0,2,1,1,0,0	1	600	0	12,3018
17	0
18	5	3	1	4	0			50
...	...	...	...	...	...	...	...	...

表2.表1のデータに対してBoldiとVignaが提案した参照符号化方法[2]



クローラーデータベースのギャップの分布もPower-Lawの対象です。





図1. .ukサイトのスナップショットでの「ギャップ」の分布-1850万ペー​​ジ



これにより、Webクローラーからの順序付けられたデータの形で、上から「クローズ」アカウントが与えられていると言えます。 そして、上記の2つの方向で作業を開発します。前の頂点の1つを修正してエッジのリストをエンコードし（参照コーディング）、「ギャップ」の形式でエッジのリストを保存します（ギャップ[i、0] =ノード[i]-リンク[i、 0]）-そして、上記の周波数応答を使用して、このリストを多くの整数コードの1つでエンコードします。 リンクごとに2〜5ビット[4]のように、かなりうまくいったと言わざるを得ません。 [2]および[3]では、データを小さなブロックにエンコードする、より単純な参照符号化方法であるLMおよびSSLが提案されました。 結果は、BVアルゴリズムよりも優れているか、かなり同等です。 ギャップのある単純なコーディングでもWebベースで同等の結果が得られると同時に、ローカルの「類似性」を使用するすべての方法がソーシャルベースで顕著に受け継がれることを、私自身に付け加えたいと思います。



ソーシャルグラフでは、この効果は観察されていないようです。図2は、vkontakteデータベースのさまざまな部分でのギャップの分布を示しています。 興味深いことに、最初の100万のログ/ログアカウントについて、ギャップ法が実際に実施されています。 しかし、データ量の増加に伴い。 ギャップの分布はますます「白」になりつつあります。

サンプル50k。	10万サンプル	2Mサンプル。

図2. vkontakte friendsデータベースによるギャップ分布。





図3.グラフvkontakteの隣接行列。





図4.クラスタリングの前後の隣接行列。 10万人のユーザー。



図3は、フレンドグラフの隣接行列を対数形式で示しています。 彼女はまた、この種の圧縮に大きな希望を抱かせていません。 何らかの方法でグラフを事前にクラスター化すると、データはさらに興味深いものになります。 図4は、MCL（ マルコフクラスターアルゴリズム ）クラスター化器を通過した後の隣接行列を示しています。 対応行列はほぼ対角線になります（カラーマップは対数なので、明るい黄色は要素間の接続が数桁多いことを意味します）-WebGraphおよび他の多くのアルゴリズムは、そのようなデータの圧縮にすでに優れています。 （現在、浅野[7]は、圧縮に関して知っている限りでは最高ですが、データへのアクセスが最も遅くなっています）。



しかし問題は、最悪の場合、MCLが時間的にキュービックであり、メモリ内で2次であるということです（http://micans.org/mcl/man/mclfaq.html#howfast）。 人生では、すべてが対称グラフ（ソーシャルグラフとほぼ同じ）にとってそれほど悪くはありませんが、線形性とはまったく同じです。 さらに大きな問題は、グラフがメモリに収まらず、分散クラスタリング手法を考え出す必要があることです。これはまったく別の話です。 この問題に対する中間的な解決策は、Alberto ApostolicoとGuido Drovandiによって考案されました[1]-幅優先探索（BFS-search）を使用して単純にグラフの番号を変更します。 したがって、相互に参照しているノードの一部が近いインデックスを持つことが保証されます。 彼らの仕事では、彼らはGAPコーディングを残し、エンコードされたリンクごとに1〜3ビットを受信する、かなり複雑な参照コーディングのモデルに置き換えました。 実際、BFSが頂点を正しく構成する直観はあまり明確ではありませんが、この方法は機能します-VKontakteデータベースに対してこのコーディングを行い、ギャップによるヒストグラムを見ました（図5）-非常に有望です。 また、BFSの代わりにDeep First Searchを使用する提案や、シングルオーダーなどのより複雑な再インデックススキーム[7]があり、同様の増加をもたらします。 BFSの再インデックス付けが機能する/機能する理由はもう1つあります。WebArchiveデータベースは十分にエンコードされており、ライブインターネットグラフの順次インデックス付けによって取得されます。





図5. BFSインデックス作成後のvkontakte friendsデータベースによるギャップ分布。 100kサンプリング

ギャップ	数量	共有する
1	83812263	7.69％
2	12872795	1.18％
3	10643810	0.98％
4	9097025	0.83％
5	7938058	0.73％
6	7032620	0.65％
7	6322451	0.58％
8	5733866	0.53％
9	5230160	0.48％
10	4837242	0.44％
top10	153520290	14.09％

表2. BFSインデックス作成後のvkontakte friendsデータベースによるギャップ分布。 1Mサンプル



Boldi and Vigna [5]の2番目の作業は、ギャップのリストをさまざまなデジタルコードでコーディングし、それらを上限としてハフマンコーディングと比較することの理論的な正当化に当てられます。 基本は、エンコードされた値がZipfの法則に従って配布されるという事実です。 さまざまなアルファパラメーターの圧縮上限は、リンクごとに4〜13ビットでした。 VKontakteデータベースの場合、このエンコード方式はリンクごとに18ビットを提供しました。 もちろん、これは悪くなく、ベース全体をRAMに収めることができますが、作品で与えられた領土の推定からはほど遠いです。 図5は、BFSインデックス作成後のギャップの分布と、実際のデータ（アルファ= 1.15）に可能な限り近いzipfの分布の比較を示しています。 図6は、BFSの再インデックス付け後のグラフの隣接行列を示しています。これは、圧縮率が低い理由をよく反映しています。対角線はよく描かれていますが、全体的なノイズはクラスター化行列に比べて非常に大きくなっています。 これらの「悪い」結果は、[6]でも確認されています。





図6. vkontakteベースの隣接行列。 BFSのインデックス再作成後。

ビクリク

特別な注意に値する別の方法があります-グラフのプロパティの活用。 つまり、2部グラフの選択と、サブグラフの2つの部分を接続する仮想頂点の生成。 これにより、2部グラフの各辺の頂点リストの長さが短くなります。 通常、このタスクはNP完全ですが、2部構成のサブグラフを見つけるには多くの優れたヒューリスティックがあります。 この方法は[9]で提案され、BVアルゴリズムが他の多くの[10-11]を生み出したように、より詳細な検討に値します。 図6は、彼の主なアイデアのみを説明しています。

A1-> A2 B2 C2 D3 B1-> A2 B2 C2 D4 C1-> A2 B2 C2 D5	A1-> V D3 B1-> V D4 C1-> V D5 V- > A2 B2 C2

図6. Biklikコーディング。

文学

1. A. AlbertoおよびG. Drovandi：BFSによるグラフ圧縮。
2. Sz。 GrabowskiとW. Bieniecki：タイトでシンプルなWebグラフ圧縮。
3. Sz。 GrabowskiとW. Bieniecki効率的なWebグラフ圧縮のための隣接リストのマージ
4. P.ボルディとS.ヴィグナ：ウェブグラフフレームワークI：圧縮技術。
5. P. BoldiとS. Vigna：ウェブグラフフレームワークII：World-Wide-Webのコード。 WebGraphII.pdf
6. P.ボルディとS.ヴィグナ。 Webおよびソーシャルグラフの置換。
7. フラビオ・キエリチェッティ、ラヴィ・クマール。 ソーシャルネットワークの圧縮について。
8. 浅野、宮脇、西関：Webグラフの効率的な圧縮。
9. グレゴリー・ビューラー、クマール・シェラピラ。 コミュニティによるWebグラフ圧縮へのスケーラブルなパターンマイニングアプローチ
10. セシリア・ヘルナンデス、ゴンサロ・ナバロ。 Webおよびソーシャルグラフの圧縮表現。
11. F. ClaudeとG. Navarro：高速でコンパクトなWebグラフ表現。