DEIM Forum 2019 B8-4

ロードバランス重視のグラフ分割手法
袁

沛霖†

真†

鬼塚

佐々木勇和†† 大阪大学大学院情報科学研究科 〒 565-0871 大阪府吹田市山田丘１−５
E-mail: †{yuan.peilin,onizuka,sasaki}@ist.osaka-u.ac.jp
あらまし

近年，数億ノードから構成される大規模なグラフが登場し，より高効率のグラフ計算をできる分散グラフ処理は重要になりつつある．分散グラフ処理ではグラフをいかに分割するかは現在注目されている課題の 1 つである．
既存研究では Neighbor-Expansion と呼ばれるエッジのクラスタ成長策略を用いた分割手法が提案されている．しかし既存手法ではクラスタ内のノード数を均等に分割することが難しいためロードバランスが悪くなり，その結果，各マシンの利用率が低くなるという問題が存在する．そこで本稿では既存手法を改良し，よりロードバランスの取れる手法を提案する．提案手法では，常に最も小さいクラスタを拡張することによってロードバランスを維持する．実験
では，本稿の提案手法が常に既存手法より優れたロードバランスを取れることを確認した．そして，処理時間がノードのバランスに依存するアルゴリズムを実行する際の処理時間の短縮も観察された．
キーワード 分散グラフ処理，グラフ分割，ロードバランス
手法も提案されているが [4], [31], [32], 高速に処理できるグラフ

1 はじめに現在，大規模なグラフが世の中に多く存在している．例えば，
インターネット上のサービスから得られる Twitter や Facebookのようなソーシャルグラフ，ウエブページの間のリンク関係を表すウェブグラフ，各種の道路の空間的な分布状態を表現する
道路網やセンサネットワークによって構成される IoT(Internetof Things) からなるネットワークグラフなど様々なグラフ構造
データが実世界に存在する．そして，これらのグラフの大規模化が進んでいるだけではなく，そのペースは早くなっている．
特にソーシャルグラフにおいて，そのノード数が既に数億を超えていることは決して少なくない，Facebook の全世界アクティ
ブユーザ数は 10 億以上である [1]．豊かかつ有用な情報がグラ
フデータの中に含まれているが，それは顕在的な情報と潜在的な情報の二種類がある．顕在的な情報とは，グラフの形や構造から見るだけで理解できる情報のことを指す．例えば，ソーシャルグラフの中のスーパーノードを見つけることで有名人特定するという問題がある．一方，潜在的な情報はグラフデータ
を一定な分析パターンによって分析しなければ発見できないものである．もしこれらのグラフデータをデータマイニングアル
ゴリズムによって適切に扱えば，貴重なデータを手に入れることができる．一例として，Google が提案したウェブページの重要度を評価する PageRank アルゴリズムによって検索エンジンでのウェブページランキング問題を解決し，最もユーザーに役立ちそうなページを優先的に検索結果に表示することができた [2], [3], [22]．しかし，グラフノード数の増加に伴って，このようなグラフにおける必要となる計算時間も相当増加している．
従って，グラフ計算の更なる高速化技術への需要が高まっている [33]．
現在数多くの分散グラフ処理高速化の研究が行われている [18], [19], [20], [21], [23]. シングルマシンでグラフを処理する

データ規模の上限があるため，より注目されているのは分散処理技術を利用した手法である．これは定められたルールに従ってグ
ラフ計算を複数のマシンに分割して実行し，マシン間の通信でやり取りしながら結果を求める技術である．本稿では，各マシンに割り当てられるグラフをオリジナルグラフの部分グラフと呼ぶ．
分散処理技術が発展することで高速な大規模グラフ計算が可能になり，いくつかの分散グラフ処理エンジンが既に提案されている．例えば，Graphlab [5], Pregel [6], PEGASUS [7], [8], Pow-

erGraph [11], PowerLyra [34], Spark GraphX [24], Chaos [25]などがある．
分散グラフ処理効率に影響を与える要因にはマシン間の通信コストと各部分グラフのエッジ数とノード数のロードバランスがある [9], [10]．ロードバランスが悪い場合は，処理が速いマシンは最も遅いマシンを待つ必要があるため，マシンの利用率が低い．通信コストが大きい場合は，通信待ちで計算が止まってしまう．更に，マシン間通信は一般的に遅いため，通信回数が多ければ多いほど分散処理の効率が悪くなる．これまでこの 2つの要因を改善するためのグラフ分割手法に関する議論が様々ある [15], [16]．
本研究では従来手法を踏まえて新しいグラフ分割手法を提案する．提案手法はロードバランスを重視し，Neighbor Expan-

sion と呼ばれるクラスタ拡張手法に基づいている [17]．この手
法は常にノードの core 集合と boundary 集合を維持し，1 つの boundary 集合の中にいるノードとノード間のエッジが 1 つのクラスタを構成する．boundary 集合の中の特定の条件に満たすノードを core 集合に移動すると同時にこのノードに繋がる一部のエッジをクラスタの中に追加する．既存の Neighbor

Expansion を利用したグラフ分割手法では，個々のクラスタを順次成長させるため実験によりクラスタ間でのノードのバラン
スが悪い欠点があることが分かった．提案手法はノード数とエッジ数のロードバランスを重視するよう，Neighbor Expansion

を拡張するため，複数のクラスタを徐々に成長させるという戦

HDRF や Obilivious と比べてみるとその利点はグラフの構造

略を取る．提案手法を多様なグラフデータに適用することで，の全体を考えできることである．しかし欠点として，Sheep を提案手法の方がより均等にエッジとノードを各クラスタに割り用いる際に良いパフォーマンスを発揮できるのは木構造に近い当てることを確認した．また，処理時間がノードのバランスに

グラフのみである．

依存するグラフ分析アルゴリズムを実行する際の処理時間の短縮も観察された．

前述したのは代表的な vertex-cut 手法であるが，いずれもグラフの構造を活用できないので，結果として高い replication

本稿の構成は，次の通りである．2 章で既存研究について述

factor となる欠点がある．また， edge-cut 手法の中で一番注べる．3 章において提案手法の事前準備に関して詳説する．4

目されていた METIS [29] アルゴリズムも vertex-cut をできる

章で既存手法の問題点を分析し提案手法の詳細について説明すように拡張された [30]．この手法はグラフ全体の構造を重視し，る．5 章において提案手法の評価と分析を行う．6 章で本稿をメモリの中でグラフの分割を行う．確かにこれによってグラフ

まとめる．

を分割して得られる replication factor は他の vertex-cut 手法
より優るが，大規模グラフには通用できないという欠点がある．

2 既存研究既存のグラフ分割手法はノードを一意に割り当てる edge-cutとエッジを一意に割り当てる vertex-cut という大きく二種類の手法があるが，Power-law に従うグラフを対象とする場合
は，vertex-cut を適用する方針が計算効率が良いことが確認されている．生成したノードのコピー数の期待値から考えると，既存の vertex-cut 手法の中では最も良い分割結果を出せるのは Neighbor Expansion [17] と呼ばれるアルゴリズムを利用した順次にエッジのクラスタを拡張する手法である． 3 章がそれについて詳しく分析する．

3 事前準備edge-cut によるノードのコピー数を g とすると，vertex-cut に

前述した既存手法を説明するためまず Neighbor Expansion

よるノードのコピー数は g より小さくかつ厳密なる上限があアルゴリズムを説明する [17]．Neighbor Expansion は一定なる [11]．続いて vertex-cut に関する既存研究について説明する．

ルールに従ってクラスタの中に吸収するノードを選び，持つChaos [25] は RAND と呼ばれる手法を用いて高いネットワー

エッジ数が上限数に達するまでノードの選択を繰り返し実行すク帯域幅を活用しランダムにエッジを各部分グラフに割り当て

るアルゴリズムである．Neighbor Expansion アルゴリズムでる．このような処理は非常に速いスピードを保証することがでは．ノード吸収のルールを実現するためノードの core 集合 C

きるが，その代わりにグラフの構造を無視して高いノードのと boundary 集合 S が事前に定義され，以下の関係に従う．

replication factor をもたらす．replication factor が高ければC = ∅, S = ∅高いほどノードがより多く切断されていることを意味する．切
断回数が多くなると，グラフ処理で計算する必要があるノードも多くなり， 処理時間が長引いてしまう．

DBH [26] はエッジの密度を主なパラメータとするハッシュ関数に基づくグラフ分割手法である．この手法は最初に全てのノードをランダムに割り当て，そしてエッジ集合 E をトラ
バースし，任意のエッジ (i, j) に関してその時点で degree(i)と degree(j) のどっちが小さいかを判断し，次数が小さい方が存在する部分グラフに割り当てられる．DBH は power-law グ
ラフのノード次数分布を利用しているが，RAND と同様にグラフの構造を活用していないため，ノードの replication factor
はまだ高い．

C ⊆ S が常に成立する
初期化する際，オリジナルグラフデータからランダムにノードを選び，S と C の中に一緒に追加され，そしてこの node の全ての隣接ノードも S の中に追加される．もし S の中ではエッジによって繋がっている 2 つのノードが存在するなら，このエッジをエッジのクラスタに割り当てる．それと同時に，オリジナルグラフからこのエッジを削除する．
続いて Neighbor Expansion ではエッジのクラスタを拡張するためのループが始まる．本稿は 図 1 を用いてこのループを説明する．

Oblivious [11] は 1 つのエッジをどの部分グラフに送るかを決める際に既に各部分グラフに割り当てられたエッジを考慮す

Step. 1S

S
C

C

るストリーミングアルゴリズムである．実行する際，1 つの部分グラフに割り当てようとしているエッジは常により多くのノードを共有するエッジを持つ部分グラフに割り当てる．

HDRF [27] は Oblivious を拡張したストリーミングアルゴリ

S
CS

Step. 3C

ズムであり，DBH のように更に power-law グラフのノード次数分布を活用している．HDRF も Oblivious もエッジを割り当てる際に既に割り当てられたエッジにしか依存していないため，グラフの構造の一部のみを活用している．

Sheep [28] は分割統治法を用いたグラフ分割手法である．

図 1 Neighbor Expansion の例（緑色のノードは今回選ばれた C に追加するノード，実線はクラスタに吸収されたエッジ， 点線はまだオリジナルグラフに存在るエッジ）ループは大きく 3 つのステップに分けられている．

隣接ノードが選択されて C の中に追加されたら，自然に隣接しStep.1 において，S − C に属する任意のノード n を探索し，ているスーパーノードが S の中に追加される．スーパーノード

n の隣接ノードであり，S に属さないノードの件数を集計する．

の次数がアルゴリズムの実行と伴って減っていくが，順次拡張

そして，この数が一番小さいノードを選出する．もし S − C がする際，特に一番目や二番目に拡張されるクラスタに対して，∅ であれば，オリジナルグラフからノードをランダムに選出しスーパーノードの次数はまだ大きい．この場合ではスーパーて C と S に追加する． 図 1 では，最初 S − C に属する 2 つ

ノードが S の中に入っても次数が小さくなるまで C の中に追のノードに対して，上のオレンジ色のノードが持つ S に属さな加されることは難しい．一方，1 つのノードが S に追加されるいノードの数は 3 であり，下の緑色のノードが持つ S に属さな手段として，ランダムに選択される以外は隣接ノードが C にいノードの数は 1 である．緑色のノードの方が小さいため，こ追加されるのを待つしかない．つまり，スーパーノードと隣接のノードは選ばれる．

している次数が小さいノードにとって，スーパーノードが C に

Step.2 では，C が先に Step.1 で選ばれたノードを追加する．

追加されるまで S に追加されない可能性は高い．従って，スーそして，C に追加されたノードに対して，その S に属さない

パーノードと繋がるノードの次数は小さければ小さいほど順次

ノードは全て S − C に追加される． 図 1 では，選ばれた緑色

拡張の最後のクラスタに残される可能性が高い．特にスーパーのノードが C に追加される．このノードの隣接ノードは 1 つ

ノードと繋がる次数が 1 のノードは確実に最後に残される（ラしかないかつ S − C に属されていないので，隣接ノードは S

ンダムに選択された次数が 1 のノードを除く）．

に追加される.

ここでは問題が発生する．次数が小さいノードが S に追加さ

Step.3 はループ最後のステップである．このステップではれる際，既に S の中にされた隣接ノードの数も少ないので，新Step.2 において新しく S − C の中に入った全てのノードを探しくクラスタに吸収されるエッジの数も少ない．例えば，一番索する．もしあるノードの隣接ノードが既に S に属しているな

最後に残されやすい次数が 1 のノードにとって，S に追加されら，このノードと S に属する隣接ノードをつなぐエッジは拡張

たら新しくクラスタに吸収されるエッジの数も 1 である．逆に，されているエッジのクラスタに追加される．同時に，オリジナ

順次拡張において優先に拡張されるクラスタでは S に追加されルグラフからエッジを削除する．これによってオリジナルでのるノードに対して，S に追加されると同時にクラスタに吸収さ削除されたエッジと関わるノードの次数が小さくなる．ここで，れるエッジの数は比較的に多い．従って，Neighbor-Expansion

i を拡張されているエッジのクラスタの番号として，クラスタ

では拡張されるクラスタがエッジ数の上限を持っているので，を Ci と定義する． 図 1 では，前述した条件を満たすエッジは

拡張順番が後ろのクラスタ内のエッジ数は設定されたエッジ数２本であり，Ci に吸収されたので点線から実線に変化した．

上限に達するまで吸収するノード数は比較的に多いだと思われオリジナルグラフを p 個に分割する場合，このグラフ分割手る，クラスタ間のノードのアンバランスが避けられない．

法は C1 から Cp まで順次にエッジのクラスタを拡張する．拡

この仮説を確認するため，実際に live-journal [14] と com-

張する際，クラスタの中のエッジの数が α ∗ |E|に達するまでporkut [13] という 2 つのソーシャルグラフを利用して確認した

前述した Neighbor Expansion アルゴリズムのループが実行さところ，ノードのアンバランスな状況が 2 つのデータで 図 2れる．ここで，α はクラスタのエッジの数の上限をコントローと図 3 の状況になったことを確認した．赤い線はトレンドライ

ルするためのユーザーが定義できる変量である．クラスタの拡ンであり，クラスタの中のノードの数の変化の傾向を表す．既張が全部終了すると，得られた各クラスタはオリジナルグラフ

存手法によって分割されたグラフではノードのバランスが悪い，から切り離した部分グラフである．

より先に拡張されたクラスタではより少ないノードを持つ傾向があることが分かった．このような現象をもたらす主な原因と4 提案手法本章では既存手法の問題点を分析し，解決手法を提案する．

4. 1 既存手法の問題点

してはスーパーノードに繋がる低次数のノード，特に次数が１のノードは最後のクラスタにより集中的に吸収されることである．
数多くの分散グラフ計算は分割後エッジとノード両方のロー3 章で述べた通り，Neighbor-Expansion のループにおいてドバランスと関わっている．ノードのバランスが悪い場合は，

core ノード集合 C の中に追加されるのは boundary ノード集

前述したような分散グラフ計算では処理が速いマシンは最も遅合 S に属するノードであり，且つ S に属さない隣接ノードのいマシンを待つ必要があるため，マシンの利用率が低い．従っ数がもっとも少ないノードである．この手法より C に追加するて，いかにノードのロードバランスを取るかが本研究の課題にノードを選んだ後，新しく S に追加するノードは少ないため，なる．

Neighbor Expansion によって新しくクラスタに追加するエッジも少ない．エッジ数が増えないように制御できる．しかし，Power-law グラフの特徴として全てのノードの次数の分布が冪級数分布になり，スーパーノードと呼ばれる次数が他のノードを遥かに超えているノードが存在する．もしスーパーノードの4. 2 ロードバランス重視のグラフ分割
既存手法の問題を改善するため本研究ではクラスタの拡張順
番を変える. 既存手法のような 1 つのクラスタがエッジ数の上限まで拡張されたら次のクラスタの拡張操作を始めるのではな
く，本研究では常に一番少ないエッジを持つクラスタから拡張

Algorithm 1 ロードバランスを重視する順位付き拡張手法

live-journal-20

1: {C1 , ..., Cp } = {∅, ..., ∅}6000002: while E =| ∅ do3:z ∈ arg min edgesize(Cm )4:

E = N eighbor Expansion(Cz )

1<
= m<
=p

node

4000005: end while
200000

クラスタにエッジの吸収が終わったら，今回の Neighbor Ex-

pansion を終了し，提案手法最初のクラスタ選択のステップに

0
1

2

3

4

5

6

7

8

9

10 11 12 13 14 15 16 17 18 19 20

戻す．

クラスタ番号

図 2 live-journal を 20 個に分割した時のノード数分布

上記のような手法により，グラフ分割する際に各クラスタ内のエッジ数のバランスを取ることができるだけではなく，最後に

com-orkut-20

残された元々スーパーノードと繋がった低次数ノードも各クラ

500000スタに分散することができる．従って，エッジとノード両方の400000

バランスを取れる．

node

3000005 実験・評価

2000005. 1 実 験 目 的

1000001，ロードバランス重視のグラフ分割は良いノードバランス

0
1

2

3

4

5

6

7

8

9

10 11 12 13 14 15 16 17 18 19 20
クラスタ番号

図 3 com-orkut を 20 個に分割した時のノード数分布を取れるかどうかを確認する．

2，提案手法は既存手法のように良いエッジバランスを維持するかどうかを確認する．

3，提案手法によって処理時間がノードバランスに依存する
するロードバランス重視の順位付き拡張手法を提案する．理由
としては 2 つある．1 つ目はこうするとエッジのバランスが取りやすいこと，2 つ目は拡張するクラスタの切り替えを頻繁に行うことによってスーパーノードに繋がる低次数ノードを各ク

分散グラフ処理が速くなれるかどうかを確認する．

5. 2 実験環境とグラフデータ
本研究では Amazon Web Service を利用して実験を行う．使
用した環境についてを 表 1 に示す．

ラスタに分散できる．
提案手法では分割数と同じ数のクラスタを初期化して任意の

表 1 AWS の実験環境

クラスタから Neighbor Expansion の単一ループ処理を実行し，Amazon マ シ ン イ メ ー ジ

新しいエッジがクラスタに入る度に次に拡張するクラスタを再(AMI)
インスタンスタイプ

選択する．この手法の擬似コードを Algorithm 1 に示す．

m4.xlarge

ルートデバイスタイプ

ロードバランスを重視する順位付き拡張手法•

ami-b9206089

グラフを p 個に分割する際，p 個のクラスタを一挙に初

ebs

cpu

Intel Xeon E5-2676v3

cpu 数

4

マシン台数

5 ∼ 30期化する．そして Neighbor Expansion のノードやエッジを吸動作周波数 (GHz)2.40

収するループを開始し，持つエッジの数が一番少ないクラスタ

メモリ (GB)から拡張というルールに従って次に拡張するクラスタを選ぶ．

OS

もしこのようなクラスタが 2 つ以上存在するなら，ランダムにネットワークパフォーマンス

16
Ubuntu 14.04
高い

拡張するクラスタを選択する．

•

Neighbor Expansion の単一ループ処理によってクラス

また，実験で使用されたグラフデータを 表 2 に示す．

タを拡張する．初期 node がスーパーノードである場合を考慮
し，既存手法と同じく各クラスタのエッジ数の上限を α ∗ |E|pに設定する． 推奨設定としては，α は 1 である．この設定によって分割結果でのクラスタ間のエッジのバランスは既存手法と同じぐらい取ることができる．

•

新たなノードが boundary ノード集合 S に追加されて

表 2 実験用のグラフデータ
名称

グラフ種類

ノード数

california [14]道路網

1,965,206

エッジ数5,533,214

cit-patent [12]

引用関係グラフ

3,774,768

16,518,948

com-Orkut [13]ソーシャルグラフ

3,072,441 117,185,083

cit-patent

1.5

ne-ori-1.1

提案手法

0.5

node-balancenode-balancene-ori-1
1

com-orkut

2

ne-ori-1.1

提案手法
1
0.5

0

2

ne-ori-1

1.5

node-balancecalifornia

20

25

ne-ori-1
提案手法

1
0.5

0
15

ne-ori-1.1

1.5

0

30

15

20

分割数

25

30

15

20

分割数

25

30

分割数

図 4 node balance の実験結果

cit-patent

1.25

ne-ori-1.1
ne-ori-1
提案手法

0.75
0.5
0.25

ne-ori-1.1

提案手法

0.75
0.5
0.25

0

1.25

ne-ori-1

1edge-balanceedge-balance1

com-orkut

1.25

20

25

ne-ori-1
提案手法

0.75
0.5
0.25

0
15

ne-ori-1.1

1edge-balancecalifornia

0

30

15

20

分割数

25

30

15

20

分割数

25

30

分割数

図 5 edge balance の実験結果

california

cit-patent

115

ne-ori-1.1

com-orkut

5ne-ori-1.1

ne-ori-1

5ne-ori-1.1

ne-ori-1
4

提案手法

ne-ori-1
4

提案手法

提案手法

105

処理時間(s)

処理時間(s)

処理時間(s)

110
3
2
1
100
20

25

30

分割数

2
1

0
15

3

0
15

20

25

30

分割数

15

20

25

30

分割数

図 6 SSSP の実験結果

5. 3 実験結果と分析
本研究の提案手法はロードバランス重視なので，分割後部分
グラフ間の既存手法より優れたノードバランス及びエッジバラ

ance の値に関しては，提案手法の方が 1 により近い．つまり，提案手法がより均等にノードを各部分グラフに割り当てられることは確認された．

ンスを取ることが目標である．ノードバランスとエッジバラン

SSSP の実行に要する処理時間に関しては，提案手法の方がスを良いか悪いかを評判するため，本研究では node balance

既存手法より短いことも観察された．従って，ノードバランスと edge balance を使う．定義として部分グラフのノードあるに依存するグラフ計算を実行する際に提案手法の有効性が確認

いはエッジの最大値と期待値の商を意味する．具体的に言うされた．

と，まず分割後の各部分グラフのノードの総数及びエッジの総数を求め，分割数で割って各部分グラフのノードとエッジの期待値を計算する．node balance は各部分グラフの中の一番多いノード数を期待値で割って得られた値である．同じように，

edge balance は各部分グラフの中の一番多いエッジ数を期待値で割って得られた値である．
この 2 つの値をロードバランスを評価する指標として使う
理由は分散処理では毎回の同期処理の時間は一番遅いマシンによって決定されるためである．1 つの部分グラフが 1 台のマシンに割り当てられ，部分グラフのノード数やエッジ数は多ければ多いほど処理時間が長引いてしまう．従って，上記 2 つの値
は 1 に近ければ近いほど良いバランスを取ったことを意味す

6 ま と め
本稿では，分散グラフ処理高速化のための Neighbor Expan-

sion と呼ばれるエッジのクラスタの拡張法を元に既存グラフ分
割手法の改良案を提案した．
既存手法はクラスタを順次に拡張し，その結果としてクラス
タの番号の増加に伴ってクラスタ内のノード数も増える傾向があり，ノードのバランスが悪い．そこで本稿は常に一番少ない
エッジを持つクラスタから拡張を始める手法を提案する．実験によって提案手法は既存手法より均等にノードを各クラスタに割り当てれることが証明された．また，提案手法によりノードの次数分布が Power-law を満たすグラフを分割した後，SSSP

る．また，本研究の実験も時間計算量 O(V 2 ) の Single Sourceのような処理時間がノードバランスに依存するグラフ計算を実Shortest Path(SSSP) の実行に必要な時間を記録した．図 4，

行する際の時間が既存手法より短いことも観察された．

図 5，図 6 に実験結果を示す．
実験によると，edge balance の値に関して既存手法 (α = 1)と提案手法両方も限りなく期待値の 1 に近い．だが，node bal-

今後の課題として，Neighbor Expansion を実行する際の初期ノードの選択が分割結果に与える影響を考察するのを考えら
れる．

文

献

[1] Christopher Sibona and Jae Hoon Choi. Factors Aﬀecting
EndUser Satisfaction on Facebook. In Proceedings of the
6th International AAAI Conference on Weblogs and Social
Media (ICWSM 2012). AAAI Press, 2012.
[2] Kamvar S, Haveliwala T, Golub G. Adaptive methods forthe computation of PageRank[J]. Linear Algebra & Its Applications, 2004, 386(2):51-65.
[3] Jeh G, Widom J. Scaling personalized web search[C]. International Conference on World Wide Web. ACM, 2003:271279.
[4] Kyrola A, Blelloch G, Guestrin C. GraphChi: large-scalegraph computation on just a PC[C]. Usenix Conference on
Operating Systems Design and Implementation. 2014:31-46.
[5] Low Y, Gonzalez J, Kyrola A, et al. GraphLab: A Distributed Framework for Machine Learning in the Cloud[J].
Eprint Arxiv, 2011.
[6] Malewicz G, Austern M H, Bik A J C, et al. Pregel: asystem for large-scale graph processing[C]. ACM SIGMODInternational Conference on Management of Data. ACM,
2010:135-146.
[7] Kang U, Tsourakakis C E, Faloutsos C. PEGASUS: A PetaScale Graph Mining System Implementation and Observations[C]. Ninth IEEE International Conference on Data
Mining. IEEE Computer Society, 2009:229-238.
[8] Han M, Daudjee K, Ammar K, et al. An experimental comparison of pregel-like graph processing systems[J]. Proceedings of the Vldb Endowment, 2014, 7(12):1047-1058.
[9] Shiokawa H, Fujiwara Y, Onizuka M. Fast algorithm
for modularity-based graph clustering[C]. Twenty-Seventh
AAAI Conference on Artificial Intelligence. AAAI Press,
2013:1170-1176.
[10] Rahimian F, Payberah A H, Girdzijauskas S, et al. JA-BEJA: A Distributed Algorithm for Balanced Graph Partitioning[C]. IEEE, International Conference on Self-Adaptive
and Self-Organizing Systems. IEEE Computer Society,2013:51-60.
[11] Gonzalez J E, Low Y, Gu H, et al. PowerGraph: distributedgraph-parallel computation on natural graphs[C]. Usenix
Conference on Operating Systems Design and Implementation. USENIX Association, 2012:17-30.
[12] J. Leskovec, J. Kleinberg and C. Faloutsos. Graphs over
Time: Densification Laws, Shrinking Diameters and Possible Explanations. ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining (KDD), 2005.
[13] J. Yang and J. Leskovec. Defining and Evaluating Network
Communities based on Ground-truth. ICDM, 2012.
[14] J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney. Community Structure in Large Networks: Natural Cluster Sizes
and the Absence of Large Well-Defined Clusters. Internet
Mathematics 6(1) 29–123, 2009.
[15] Sun R, Zhang L, Chen Z, et al. A Balanced Vertex Cut Partition Method in Distributed Graph Computing[C]. Revised
Selected Papers. Springer-Verlag New York, Inc. 2015:43-54.
[16] Lang K. Finding good nearly balanced cuts in Power-law
graphs[J]. Preprint, 2004.
[17] Chenzi Zhang, Fan Wei, Qin Liu, Zhihao Gavin Tang, andZhenguo Li. 2017. Graph Edge Partitioning via Neighborhood Heuristic. In Proceedings of the 23rd ACM SIGKDDInternational Conference on Knowledge Discovery and Data
Mining (KDD ’17). ACM, New York, NY, USA, 605-614.
[18] Boldi P, Rosa M, Santini M, et al. Layered label propagation:a multiresolution coordinate-free ordering for compressing social networks[C] J Acoust Soc Am, 2011:587-596.
[19] Power R, Li J. Piccolo: building fast, distributed programswith partitioned tables[C]. Usenix Symposium on Operating Systems Design and Implementation, OSDI 2010, Octo-

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

ber 4-6, 2010, Vancouver, Bc, Canada, Proceedings. DBLP,
2010:293-306.
Gregor D, Lumsdaine A. The Parallel BGL: A generic library for distributed graph computations[J]. In Parallel
Object-Oriented Scientific Computing. POOSC, 2005.
Ekanayake J, Li H, Zhang B, et al. Twister: a runtime
for iterative MapReduce[C]. ACM International Symposium
on High PERFORMANCE Distributed Computing. ACM,
2010:810-818.
Guo, Tao, et al. Distributed Algorithms on Exact Personalized PageRank. Proceedings of the 2017 ACM International
Conference on Management of Data. ACM, 2017.
LUO, Xinyuan, et al. Tuning the granularity of parallelism
for distributed graph processing. Distributed and Parallel
Databases, 2017: 1-32.
GONZALEZ, Joseph E., et al. GraphX: Graph Processing
in a Distributed Dataflow Framework. In: OSDI. 2014. p.
599-613.
ROY, Amitabha, et al. Chaos: Scale-out graph processing
from secondary storage. In: Proceedings of the 25th Symposium on Operating Systems Principles. ACM, 2015. p.
410-424.
XIE, Cong, et al. Distributed power-law graph computing:
Theoretical and empirical analysis. In: Advances in Neural
Information Processing Systems. 2014. p. 1673-1681.
PETRONI, Fabio, et al. Hdrf: Stream-based partitioning
for power-law graphs. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge
Management. ACM, 2015. p. 243-252.
Daniel Margo and Margo Seltzer. 2015. A scalable distributed graph partitioner. Proc. VLDB Endow. 8, 12 (August 2015), 1478-1489.
KARYPIS, George; KUMAR, Vipin. A fast and high quality
multilevel scheme for partitioning irregular graphs. SIAM
Journal on scientific Computing, 1998, 20.1: 359-392.
BOURSE, Florian; LELARGE, Marc; VOJNOVIC, Milan.
Balanced graph edge partition. In: Proceedings of the 20th
ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014. p. 1456-1465.
Wang K, Hussain A, Zuo Z, et al. Graspan: A Singlemachine Disk-based Graph System for Interprocedural
Static Analyses of Large-scale Systems Code[J]. Acm Sigplan Notices, 2017, 51(2):389-404.
Maass S, Min C, Kashyap S, et al. Mosaic: Processing a
Trillion-Edge Graph on a Single Machine[C]. Twelfth European Conference on Computer Systems. ACM, 2017:527543.
Xie C, Chen R, Guan H, et al. SYNC or ASYNC: time
to fuse for distributed graph-parallel computation[C] ACM
Sigplan Symposium on Principles and Practice of Parallel
Programming. ACM, 2015:194-204.
Chen R, Shi J, Chen Y, et al. PowerLyra: diﬀerentiatedgraph computation and partitioning on skewed graphs[C]//
Tenth European Conference on Computer Systems. ACM,
2015:1.