日本ソフトウェア科学会第 36 回大会 (2019 年度) 講演論文集

Watts-Strogatz モデルに基づく大規模ランダムグラ
フの分散並列生成
神野 薫

江本 健斗

近年，SNS や Web グラフなどの大規模なグラフに対して，解析処理を行うプログラムの開発の需要が高まってきている．そのようなプログラムの性能評価にあたっては，特定の特徴をもった様々なノード数のグラフが多く必要となる．しかし，逐次プログラムによる大規模な性能評価用グラフの生成は，非常に時間がかかってしまい，また，メ
モリ不足の可能性もあり，望ましくない．これらの問題点を解決するために，大規模グラフ生成の分散並列化が望まれる．
本研究では，現実世界の大規模グラフに似た特徴を持つ，よく知られたグラフモデルの一つである Watts-Strogatz
モデルに基づく生成の分散並列化を提案する．この際，分散並列環境として Hadoop MapReduce を用いる．分散並列化にあたっては，元の生成法に若干の制約を導入し，その効率化を図っている．そのため，提案手法が元のモデルに期待される特徴を保存していることも，理論的・実験的に証明する．

In recent years, there has been a growing demand for the development of programs that perform analysis on large-scale graphs such as SNS and Web graphs. In evaluating the performance of such programs,
we need a number of input graphs with the desired number of nodes and specific features such as thesmall-world property. However, the generation of large-scale random graphs by sequential programs is very
time-consuming, and may cause memory shortage. In order to solve this problem, distributed parallelizationof large-scale graph generation is desired.
In this research, we propose distributed parallelization of the random-graph generation based on WattsStrogatz model, which is one of well-known graph models that provide characteristics similar to large scalegraphs in the real world. We implemented our proposing distributed parallel algorithm by using Hadoop
MapReduce. In the distributed parallelization, some restrictions are introduced into the original generation
method to improve its eﬃciency. We have shown that the restrictions do not break the the characteristics
that the original model has.

大規模グラフを処理するプログラムやフレームワー

1 はじめにクの性能評価では，現実のグラフを対象としたベンチ

ソーシャルネットワークやタンパク質間相互作用にマークの他に，将来的な使用に対しての傾向を捉える

代表されるような，大量の「物」とその間の「関係」

ために，ランダム生成されたグラフを用いた評価が行とからなる巨大なデータの解析が広く行われるようにわれる．すなわち，現実のグラフと同様の特徴を持つなってきた．このような巨大データは，「物」を頂点，

指定サイズのグラフを生成できるモデルを用い，様々「関係」を辺とした大規模なグラフであると捉えられなサイズのグラフに対する処理時間等の測定を行う．

る．そのようなグラフの解析を行うプログラムの開発

それにより，例えば将来的に処理対象グラフのサイズ

や，その開発を支援するためのフレームワークの需要が大きくなったときにどの程度の計算時間となるのかが高まっている．

の知見が得られる．
大規模グラフ処理の評価に用いるべきランダム生

Distributed parallel generation of large-scale randomgraphs based on Watts-Strogatz model.
Kaoru Kamino, Kento Emoto, 九州工業大学, Kyushu
institute of technology.

成グラフは，当然ながら，大規模でなければ意味がない．しかし，大規模なランダムグラフの生成を 1 台の計算機で行うことは計算時間やメモリの制約から非現実的であり，ランダム生成モデル（アルゴリズム）の分散並列化が必要となる．

複を指摘するとともに，それを回避する分散並列化手法を提案する．続く第 4 節にて，提案手法が元の本研究は，様々なグラフ処理フレームワーク等の評

Watts-Strogatz モデルに期待される諸性質を保つこ

価によく用いられる，Watts-Strogatz モデル [10] のとを示す．そして，第 5 節にて，提案手法の Hadoop

分散並列化を提案する．WS モデルは，円状に並べ

Mapreduce による実装を導入し，PC クラスタにおられた n 個の頂点の各々が近隣の 2k 頂点と接続す

ける実験結果を示すとともに提案手法を評価する．最るリング状格子を初期グラフとし，各辺を確率 p で後に，第 6 節にて関連研究を述べ，第 7 にて本論文

未接続頂点に再接続させることでグラフを生成する．

をまとめる．

このモデルは，各頂点に自身に接続する辺の半分の再接続を実行させることで容易に並列化できそうに思

2 Watts-Strogatz モデル

えるが，単純な並列化では再接続辺の重複の問題が生

本節は，一般によく使われるランダムグラフの生成じてしまう．本研究は，この問題を再接続先頂点の選択に単純な制限を加えることで回避し，全体として頂モデルである Watts-Strogatz モデル [10] を導入する．このモデルは，単純 †1 な無向グラフを生成する．

点数程度の潜在的並列性を持つ生成アルゴリズムをWatts-Strogatz モデルで生成されるグラフは，平提案する．本研究の貢献は次のとおりである．

均経路長（全頂点間距離の平均）が短いという「ス• Watts-Strogatz モデル [10] に対し，潜在的並列

モールワールド性」を持つことや，高めのクラスタ係

度の高い分散並列化を提案する．本手法は，再接数（グラフ内の辺が三角形を構成している割合）を持

続辺重複問題を回避するために，辺の再接続先につことといった，現実のグラフとよく似た特徴を示

簡単な制約を追加する．この制約により，各頂点

す．そのため，現実のグラフを対象としたいグラフ解が自身に接続する辺を独立にかつ安全に再接続

析プログラム等の評価によく用いられる．

処理することが可能となり，単純なデータ並列の枠組みを用いてグラフの分散並列生成が可能となる．

2. 1 生成アルゴリズム
以下，Watts-Strogatz モデルでのグラフ生成の流• 提案手法で追加する再接続先の制約が，Watts-

れを説明する．生成は大きく二段階になっており，最Strogatz モデルに期待される諸性質を破壊しな

初に規則的なリング状格子を形成し，その後，辺の確いことを確認した．生成アルゴリズムの安易な率的な再接続を行ってその規則性を乱す．

改変は，生成されるグラフに期待される諸性質

Watts-Strogatz モデルは三つのパラメータを持つ：を破壊してしまい，望ましくない．本研究では，• N · · · グラフの頂点数

Watts-Strogatz モデルに関する既存の解析 [2] に• K · · · 平均次数の半分（すなわち，各頂点は平

基づき，そこで解析された諸性質が提案手法を用いた場合にも保たれることを示した．

• 提案する Watts-Strogatz モデルの分散並列化を

均で 2K 本の辺を持つ）• P · · · 辺の再接続確率（すなわち，グラフの乱れ具合）

Hadoop MapReduce [9] を用いて実装し，元の2. 1. 1 リング状格子の形成

生成アルゴリズムでは計算機一台では生成する

まず，N 個の頂点を円状に配置する．その後，各のが困難であるような，大規模なグラフの生成が頂点が片側 K 個ずつ，合計 2K 個の隣接頂点と接続

現実的に行えることを示した．

するよう辺を追加する．こうして得られるリング状の

本論文の以降の構成は次のとおりである．まず，第2 節にて，本研究で対象とする Watts-Strogatz モデ

規則的な格子（リング状格子）が Watts-Strogatz モ
デルの初期グラフとなる．

ルを導入する．次に，第 3 節にて，Watts-Strogatz
モデルの並列化における問題点である再接続辺の重†1 各頂点間に，辺は高々1 本しかない．

例として，N = 12，K = 2 としたリング状格子を

112

図 1 に示す.
このリング状格子は，隣接する頂点が三角形を多

2

11

3

く形成しているため，現実のグラフと同様にクラスタ係数が高い．しかし，反面，頂点間の平均的な距離

104は長く，N/K に比例する程度である．そのため，次9の段階として辺の確率的な再接続を行い，幾らかの「ショートカット」を導入することで平均経路長を小582. 1. 2 辺の再接続処理
第二段階の処理として，すべての辺について確率的

6
7

さくする．
図1

リング状格子の例（N = 12，K = 2）．頂点内の数
は，各頂点の番号である．

にその接続先を変更する再接続処理を行う．
再接続処理では，各頂点の各辺について順に，確率1
12P で接続先の変更を行う．この際，再接続先の頂点
は，その辺が起点としている頂点が接続したことのな

2

11

3

い頂点から選択する．
擬似コードとして表現した再接続処理は次のとおり

104である．ここで，全頂点は V = {1, . . . , N } であり，v9の担当する再接続処理対象の辺（すなわち v を起点とする辺）は E(v) = {(v, v + 1), (v, v + 2), . . . , (v, v +K)}†2 である．すなわち，各頂点は自身と自身以降の頂点を結ぶ K 本の辺を担当する．また，rand() を[0, 1] の一様ランダムな値を返す関数とする．
foreach v ∈ V

5
8

6
7

図2

再接続処理の例：頂点 1 と頂点 8 の辺（点線）が再接続（矢印）を行った．

foreach e ∈ E(v)「辺が重複して本数が減る」という事態が避けられて

if rand() > P thenいる．

e の終点を V ′ から一様ランダムに選択
where′

3 Watts-Strogatz モデルの分散並列化

V = V \ {v − K, . . . , v, . . . , v + K}

本節では， Watts-Strogatz モデルの単純な並列化\ { 再接続で v と繋がった頂点 }図 1 のグラフに対して再接続処理を行った例を図 2の直面する問題点を指摘した後に，その問題を解決しに示す．頂点 1 から頂点 3 に伸びていた辺に対して接続先の変更が起こり，その辺の終点が頂点 5 に変更された．同様に，頂点 8 から頂点 9 に伸びていた辺に対しても接続先の変更が起こり，その辺の終点が頂点 12 に変更された．いずれの辺についても，再接続
先はそれぞれの起点であった頂点が接続したことのなかった頂点であることが大事である．これにより，†2 簡潔な記述のため，N + 1 と 1 を同一視するなど，周期 N での同一視を行うとする．

た Watts-Strogatz モデルの分散並列化を提案する．

3. 1 単純な並列化とその問題点
前節で述べた Watts-Strogatz モデルの並列化は，一見，全頂点での再接続処理を並列に行えば簡単に実現できるように見える．しかし，この単純な並列化では「再接続辺の重複」の問題が生じる．
図 1 のリング状格子に対して再接続処理すること考える．ここで，全頂点が独立に並列に，その担当する辺の再接続処理を行ったとしよう．このとき，図 3

3. 2 提案手法：重複回避を伴う並列化

1
12

2

11

本研究は，前節で指摘した再接続辺重複の問題を，「重複辺を生成しない再接続先の選択方法」を導入す

3

ることにより解決する．
10

4

再接続辺の重複が起こるのは，二つの頂点が，互いに互いを再接続先に選んでしまったときである．よっ

9

5
8

6
7

図3

再接続処理の並列化時に発生し得る辺の重複：頂点

1 と頂点 5 が，互いを再接続先に選んでしまった状況．

て，再接続先頂点の選択に非対称性を導入し，「一方から他方は選べるが，その逆は不可能である」という状況を作れば良い．
上記のような非対称的な選択を行うひつの手法として，各頂点 v における再接続先を次のようにする
ことを提案する：に示すような状況が生じる．すなわち，頂点 1 が頂

v から円の中心を見て，左側の半円の頂点の点 3 に繋がっていた辺を頂点 8 に再接続し，同時に，

うち v と頂点番号の偶奇が一致する頂点と，頂点 8 が頂点 9 に繋がっていた辺を頂点 1 に再接続

同じく右半円のうち偶奇の異なる頂点．

するという状況が起こり得る．すなわち，再接続辺がすなわち，第 2 節に示した擬似コードにおいて，頂重複してしまうことが起こり得る．

点 v の再接続先候補集合 V ′ を次のようにすること

上記の再接続辺の重複は，いくつかの問題を生じる．まず，生成されるグラフは単純であるとしているを提案する．
V′ =ため，重複した二本の辺は一本に同一視され，グラ{v + K + i | i ∈ {1, 2, . . . , N/2}, K + i が偶数 }フ全体の辺の数が期待された数より小さくなってし∪ {v − K − i | i ∈ {1, 2, . . . , N/2}, K + i が奇数 }まう．また，グラフが単純であると想定しているプロ\ {v の再接続で v と繋がった頂点 }なお，N が偶数である場合，真反対の頂点とは接続

グラムに上記の重複辺をそのまま入力してしまえば，
思わぬ不正処理を発生させる事になりかねない．そして，既存の理論的な解析は重複辺の存在を仮定していないため，Watts-Strogatz モデルに期待される性質を破壊してしまう恐れもある．
以上のような理由により，各頂点を独立に並列に動かすという単純な並列化は望ましくなく，重複辺の発生を防ぐ仕組みを導入した並列化が望ましい．ひとつの方法として，「再接続時にロックを取る」などの排他制御を入れることも考えられるが，並列計算に用いる計算機が多い場合にはあまり現実的ではない．
また，「重複した際にやり直しをする」という手法も考えられるが，重複の有無の確認や再実行のコストが掛かるという問題がある．
本研究は，「重複辺が生じない選択しかできないよ
うにする」という手法よる解決を次節で提案する．

できないものとする．
再接続先候補に上記の偶奇制約を課すことで重複辺の生成を回避できることは自明である．最初のリング状格子で接続されていなかった頂点 u と v について考える．u が v の右半円に存在すると仮定しても一般性は失われない．このとき，v は u の左半円に存在することに注意する．u と v の偶奇が同じである場合，u から v に向けての再接続は可能である
が，逆に，v から u への再接続は上記の制約によって起こり得ない．同様に，u と v の偶奇が異なる場
合，v から u に向けての再接続は可能であるが，逆に，u から v への再接続は上記の制約によって起こり得ない．いずれにせよ，u から v へと v から u へとの両方の再接続は同時には起こり得ない．
図 4 と図 5 に，N = 12，K = 2 とした時の，頂点1 と頂点 8 に対する選択可能な再接続先頂点の様子を示す．まず，頂点 1 について，円の中心を見た際能となった．

1
12

2

11

4 諸性質の保存

3

前節で提案した「再接続先頂点選択への制約導入」
10

4の手法により，グラフ生成の安全且つ単純な分散並列化が実現できる．しかし，この制約の導入によって，958生成されるグラフに期待されていた性質が壊されてしまうようでは本末転倒である．

6
7

図4

本節では，前節の提案手法が，Watts-Strogatz モ

頂点 1 から接続可能な頂点ることを示す．具体的には，Watts-Strogatz モデルの解析を行いその性質を整理した研究 [2] に倣い，本112デルで生成されるグラフに期待される性質を保ってい2

11

提案手法で改変した生成方法について同様の解析を
行う．

3

10

4

4. 1 接続性の分布の保存
本節では，グラフの接続性，すなわち，頂点次数

9

5
8

6
7

図5

頂点 8 から接続可能な頂点の分布の保存の確認を行う．そのためにまず，元のWatts-Strogatz モデルで生成した場合の分布を計算し，その後，提案手法で改変された場合の分布を計算する．
以下，生成されたグラフにおいて，ある頂点が d 本の左半円にある頂点は 2，3，4，5，6 である．これの辺（隣接頂点）を持つ確率 P (d) を計算する．そのらのうち，実際に再接続先として選択可能なのは，最ためにまず，頂点の持つ辺を種類分けして整理する．

初のリング状格子で接続されておらず且つ偶奇の一生成されたグラフにおいて，頂点の持つ辺は，大致する頂点 5 のみとなる．同様に，右半円には 8，9，

きく二種類に分類される．一つは自身が再接続を行

10，11，12 の頂点があるが，これらのうち，最初のう K 本の辺であり，常に K 本存在する．もう一方

リング状格子で接続されておらず且つ偶奇の異なるは，他の頂点の再接続処理により変わる部分であり，頂点 8 と頂点 10 が接続先候補となる．総じて，頂ni = d − K 本存在する．後者はさらに，リング状格

点 1 の再接続先候補の頂点は 5，8，10 の三つであ子の段階で接続されていた辺 ni,1 本と，別の頂点のる．他方で，頂点 8 の再接続先候補の頂点は，3，5,

再接続処理によって繋げられた辺 ni,2 = ni − ni,1 本

12 となる．そのため，頂点 1 と頂点 8 の間に再接続とに分けられる．

辺が生じ得るとすれば，それは頂点 1 にしか行うこ

ここから，確率 P (d) の具体形を求めていく．ことができず，前節で指摘した再接続辺重複の問題は生こで，自身が再接続を行う K 本の辺は，確率に依じない．

存 せ ず 常 に K 本 存 在 す る こ と に 注 意 す る ．よっ

以上の「重複辺を生成しない再接続先の選択方法」て，P (d) は，ni = d − K の ni,1 と ni,2 への割の導入により，グラフの生成を安全に且つ単純に，頂り振りの全パタンを足し合わせたものとなり，前点毎に独立な計算として並列化することが可能となっ者に関する確率を P1 (ni,1 )，後者に関する確率をた．すなわち，第 2 節の擬似コードの最外の foreach

P2 (ni,2 ) = P2 (d − K − ni,1 ) と書けば，d ≥ K に対を，単純なデータ並列の形で分散並列化することが可して次式となる．
min(d−K,K)∑
Pp (d) =P1 (ni,1 )P2 (d − K − ni,1 )
ni,1 =0

リング状格子の段階で接続されていた辺が ni,1 本
残っている確率 Pは，次式で与えられる．
1 (ni,1 ) P1 (ni,1 ) = K (1 − P )ni,1 P K−ni,1ni,1すなわち，ni,1 本のそれぞれが 1 − P の確率で取り残された確率である．
他方，再接続処理により新しく v に接続されることとなった辺が ni,2 本となる確率は，ni,2 個の頂点が再接続先として v を選ぶという確率のことである．
そのような頂点の各々が v を再接続先に選ぶ確率は，
N ≫ K である場合 †3 ，KP/N である．すなわち，そのような頂点は K 回の再接続のチャンスが有り，各々の再接続は確率 P で成功するもので，さらに，
およそ N 個の再接続先から v を選ぶ確率は 1/N である．よって，そのような頂点が全体でおよそ N 個あることに注意すれば，次式を得る．

()ni,2 (
)N −ni,2
N
KP
KP


P2 (ni,2 ) =
1−
N
N
ni,2
さ ら に ，既 存 の 解 析 [2] と 同 様 に N を 大 き く
し た 際 の 極 限 を 取 れ ば ，上 記 の 二 項 分 布 が λ =N × (KP/N ) = KP のポアソン分布になり（例えば文献 [11] などを参照），次式を得る．
(KP )ni,2 −KP
P2 (ni,2 ) =eni,2 !
よって，以上から，元の Watts-Strogatz モデルでの生成における P (d) は，次式となる．ただし，d ≥ Kであることに注意する．min(d−K,K)∑K (1 − P )n P K−n
Pp (d) =nn=0(KP )d−K−n −KPe(d − K − n)!
次に，本研究の提案手法で改変した生成法に関す
×る P (d) を計算する．変更される点は，P2 の計算における以下の二点である．まず，各頂点が v に接続する確率が倍の 2KP/N になる．これは，再接続先の選択肢が，導入された偶奇制約により半分になるか
らである．次に，v に再接続することの出きる頂点の数が，同様の理由により半分の N/2 になる．よって，†3 既存研究 [2] と同様の仮定提案手法における ni,2 に関する確率 P2′ (ni,2 ) は，次式となる． P2′ (ni,2 ) = 


N
2



(

2KP
N

)ni,2 (2KP
1−N

) N −ni,22

ni,2
ここで，P2 と同様に N → ∞ の極限を取ってポア
ソン分布に近似することを考えると，λ = N/2 ×

2KP/N = KP となり，結果は P2′ (ni,2 ) = P2 (ni,2 )となる．導入した制約により影響を受け得るのは P2のみであるため，P (d) も一致する．
以上により，提案手法によるグラフ生成は，元のWatts-Strogatz モデルでの接続性を保存することが確認された．

4. 2 クラスタ係数の保存
次に，クラスタ係数の保存を確かめる．前節と同様，まずは既存の解析 [2] に従い元の Watts-Strogatz
モデルでのクラスタ係数を求め，その後，提案手法による生成での結果について述べる．なお，既存の解析では真のクラスタ係数ではなくその近似値を用いて解析を行っている．よって，本論文でも同じ近似値での比較を行う．
グラフのクラスタ係数 C は，そのグラフ内の三角形の割合のことであり，各頂点のクラスタ係数 cv の平均値で定義される：

C = E(cv )頂点 v について，その隣接頂点数を dv ，その隣接頂点間に存在する辺の本数を Nv とすると，頂点 v のクラスタ係数 cv は次式で定義される：
Nv
cv =dv (dv − 1)/2
すなわち，v の周辺について，存在し得る三角形の最大数 dv (dv − 1)/2 と，実際に存在している三角形の
数 Nv との比である．
まず，P = 0 のときを考える．すなわち，再接続が行われずリング状格子が生成結果となる場合を考える．このとき，v の左右には K 個ずつの隣接点がある．この隣接する頂点間にある辺の数 Nv は，頂点番号の低いほうを起点に辺を数え上げるとすると，次のようになる．まず，v より小さい K 個の頂点の各々を考えると，それらは v を抜いた K − 1 個の隣接頂点と接続している．よって，これらをまとめると

K(K − 1) 本の辺が存在する．次に，v より大きな頂点については，v の真横の頂点が K − 1 本，その隣が K − 2 本，……，などのように辺を持っている．これらをまとめれば，K(K − 1)/2 本の辺が存在する．
よって，これらの和を N̄ として，Nv は次式となる．
K(K − 1)3K(K − 1)
Nv = N̄ = K(K − 1) +=2
2
さらに，このとき，dv = 2K であるため，このときのクラスタ係数 C(0) は次式となる．
()
Nv
C(0) = E( cv (cv − 1)/2 )3K(K − 1)/2
= E
2K(2K − 1)/2
3(K − 1)=2(2K − 1)
次に，P > 0 の場合のクラスタ係数 C(P ) を考える．厳密に C(P ) を求めることは困難なため，既存の解析 [2] では期待値と演算の入れ替えを行った近似値による解析を行っている．以下，それに倣った解析てしまえば，E(ci ) = 2K より，最終的に次式を得る．
N̄ (1 − P )3
C̃(P ) ∼E(cv )E(cv − 1)/2
N̄ (1 − P )3=
2K(2K − 1)/2
= C(0)(1 − P )3
以上が，元の Watts-Strogatz モデルで期待されるクラスタ係数である．
次に，本研究で提案する手法について同様の値を計算する．導入した制約により変化し得る部分は，再接
続により新たな三角形が構成される部分である．しかし，上記の解析において，新たな三角形を構成しうる（v 以外の）2 頂点の選択の幅が半分になろうとも，再接続により互いが接続され得る確率が倍になろうとも，新たな三角形が構成される可能性が O(1/N )であることに変わりはない．よって，提案手法に関する解析も，上記の元の Watts-Strogatz モデルに関する解析と同じ結果を得る．

を行う．

P > 0 の場合の Nv の期待値を計算する．そのために，初期状態であるリング状格子（すなわち P = 0の状態）から再接続処理を行い，三角形の数がどの以上により，提案手法が元の Watts-Strogatz モデ
ルに期待されるクラスタ係数の特性を保存することが確認された．

ように変化するかを考える．まず，既存の三角形が保存される確率は，その三角形を構成している三本の辺全てが再接続されない確率に等しい．よって，保存される三角形の個数の期待値は，N̄ (1 − P )3 である．
次に，新しく三角形が構成される確率を考える．新たな三角形が構成されるには，v とは隣接していな
かった 2 頂点を考え，それら 3 点が互いに互いを接続先として再接続を行わなければならない．その確率は，O(N 2 ) × O((1/N )3 ) = O(1/N ) である．また，

v の隣接頂点と初期の辺を新たな三角形の一部とする可能性もあるが，その場合も同様に O(1/N ) である．
よって, P > 0 の時の Nv の期待値は，次式となる．
( )1
E(Nv ) = N̄ (1 − P )3 + O
N
ここで，O(1/N ) の項は N が十分に大きい時には無視できる．従って，P > 0 の時のクラスタ係数の近似値 C̃(P ) が次式となる．

E(Nv )
E(cv (cv − 1))/2
N̄ (1 − P )3=E(cv (cv − 1))/2
さらに，分母についても平均と演算の順序を入れ替え
C̃(P )=

4. 3 平均経路長の分布の保存
平均経路長とは，ノード間距離（経路長）のグラフ全体での平均の値のことである．Watts-Strogatz モ
デルの平均経路長の分布を理論的に解析することは困難であるため，既存の解析 [2] では，理論的な解析を諦めてその分布を実験的に測定して解析を行っている．本研究でもその手法を踏襲する．
既存の解析 [2] における平均経路長の分布の様子を図 6 に示した．この図は，N = 2000，K = 3 とし，P の値を 2−20 , 2−12 , 210 , 2−8 と変化させ，複数のグラフについて経路長ごとの割合を測定しプロットしたものである．P の値が小さいほどグラフが平坦であり，P が大きいほど山なりの部分が大きい．経路長の最大は 2K/N であり，P の値が大きくなるほど平均経路長が短くなる傾向がある．
図 7 に，同じパラメータに対して我々の提案手法で生成したグラフに関しての平均経路長をプロットした
図を示す．この図は，元の生成法に関する図 6 と同様の特徴を示している．

(c)

(d)

es of networks obtained by the procedure described in the text, for k = 2, N = 20. (a): p = 0, regular networks;
diate values of p; (d): p = 1.

ワークの一つに，Python で実装された NetworkX [8]6l(N,1)P(dij)

p=0.1
p=0.2
p=0.4
p=0.6
p=0.9
p=1

がある．提案手法と既存手法のフェアな比較のため，

5

同一言語での実装を行った．

4

なお，第 2 節のモデルの説明では初期のリング状

3
2

10

2

10

3

10

N

格子を明示的に作成するとしていたが，実際の実装で4はその必要がないことに注意する．すなわち，各頂点
k

2k

4

8

v は，2K 本の辺の分だけ [0, 1] 区間の一様乱数の生
c

12

16

0

dij

成を行い，各値が P 以下のときにはリング状格子でN/(2k)

ity distributions of the connectivity c for k = 3 Fig. 3. Probability distribution of the distance dij between two
es of p: c ≥ k, and the mean connectivity is vertices i and j of small-world graphs, for k = 3, N = 2000,
e symbols are obtained by numerical simula-図 p6= 2−20
(flat distribution), p = 2−12 , 2−10 and(curves
ノード間距離の割合（文献[2]2−8から引用）
orld networks (with N = 1000 vertices), and becoming more and more peaked as p grows), averaged overguide to the eye, joining points given by for- 500 samples for each p. The maximum value of dij is of course
circles show the probability distribution of the N/(2k). Inset: ℓ(N, 1) versus N for k = 3 and k = 5, together
or a random network of mean connectivity is with the ln(N)/ ln(2k − 1) straight lines.
n by (2k)c exp(−2k)/c!).

0.030

We first investigate this question by numerical simulations, to study the behaviour of ℓ(N, p) in a systematicway, varying N and p: we use values of N from 100 to
0.025
a
20
ore quite natural to ask if the change be- 20000, with p = 2 /2 , a = 0, · · · , 20, and we averageo behaviours occurs by a transition at a over 500 realizations of the disorder for each value of p.
0.020We have studied three diﬀerent values of the mean conritical value of p or if there is a crossover
any finite value of N , with a transition oc- nectivity: 2k = 4, 6 and 10.
p = 0. This last scenario was first proposed
0.015 In Figure 4, we plot ℓ(N, p)/ℓ(N, 0) for various values of N and k = 2. It is clear that ℓ(N, p) decreases

n, becomes more and more peaked aroundas p grows (see Fig. 3).

0.010の隣接点をその辺の接続先に設定し，そうでなければ再接続先頂点の選択ルールに従ってランダムに選ばれた頂点をその辺の接続先に設定する．
また，我々の提案手法の実装では，辺の再接続処理を逐次的に各頂点独立に行った後，改めて隣接リストの双方向化を行っている．すなわち，頂点の u の持
つ辺 (u, v) について，その接続先の頂点 v の隣接リストに u を入れるという処理を後で一斉に行う．

5. 1. 2 Hadoop MapReduce による実装
もう一つの実装は Hadoop MapReduce [4, 9] を用

0.005

いた分散並列実装である．こちらの実装言語は Java

0.000
0

50

100

150

200

250

300

350

である．以降，その実装の概略を説明する．

Map タスクは，入力として，そのタスクで処理を
図7

ノード間距離の割合（提案手法）

担当する頂点番号の範囲 [s, e) を受け取る．この他，モデルのパラメータ N , K, P を適切に受け取ってお以上のことから，本研究で提案した手法が平均経路

く．そして，各頂点 v ∈ [s, e) に対して，Python の長の分布に関する特徴も保存していることが確認さプログラムと同様，2K 本の辺の接続先を計算する．

れた．

そして，それらの各々の接続先 w について，(v, w)と (w, v) という key-value ペアを生成する．

5 実装と評価

Reduce タスクは，生成されるグラフの各頂点 v 毎

本節では，第 3 節で提案した手法の実装についてに存在する．先に説明した Map タスクの動きにより，簡単に述べ，その後，その実装を用いた提案手法の評

v に接続する頂点のリストを受け取ることになる．そ価について述べる．

のため，そのリストを後のプログラムに使いやすい形に整形して出力するなどを行うのみとなる．

5. 1 提案手法の実装
提案手法を大きく二つの枠組みで実装した．

5. 2 実験と評価

5. 1. 1 Python による実装

前節で説明した実装を用いて，提案手法の既存ルー

一つ目の実装は Python による逐次実装である．そチンとの性能比較や，分散並列実装時の性能を評価しの主な目的は，元の Watts-Strogatz モデルに基づくた．評価には，以下に示す環境の PC 16 台からなる

既存のランダムグラフ生成ルーチンと，提案手法に基クラスタを用いた．また，HDFS のチャンクサイズ

づく生成ルーチンとの性能比較である．

は 4MB とした．

グラフ処理のために広く利用されているフレーム

CPU：Intel(R) Core(TM) i5 6500 @ 3.20GHz
140

OS：Ubuntu 14.04.5 LTS

120

Java：Oracle JDK 1.8.0 131

100

Hadoop：1.2.1

80

Python：3.4.3
5. 2. 1 分散並列実行の評価

time[sec]

メモリ：16GB (8GB x2, PC4 17000)

K=2
K=4
K=8

60
40

まず，K = 4, P = 0.4 と，N = 100 万, 1000 万,20

1 億に対して，それぞれの実装でグラフを生成するの

0

0.2

0.4

N

にかかった時間を測定した．結果を表 1 に示す．なお，Hadoop 実装の Map タスクに与えられる入力の

図8

0.6

0.8

1.0
1e8

N だけを変化させたときの生成時間（P = 0.4）

範囲は [v, v + 1) とした．すなわち，一つの頂点について一つの Map タスクが生成される状況である．
まず，逐次実装である既存の NetworkX と提案手

180

法の Python 実装を比較する．結果より，提案手法の

160
140

方が 1.5 倍ほどの計算時間がかかることがわかる．こ間がかかっていることによると考えられる．双方向化

120time[sec]

れは，実装そのものが拙いことと，双方化の処理に時

100
80
60

の処理を再接続処理時にまとめて行うことで，処理時40間の差が縮まると考えられる．何れにせよ，提案手法

20による大幅な処理増加などがないことを確認できる．

0

次に，提案手法の Hadoop 実装と他の逐次実装とを比較する．

P = 0.2
P = 0.4
P = 0.8

図9

2.5

5.0

7.5

10.0

K

12.5

15.0

17.5

20.0

K だけを変化させたときの生成時間（N = 6000 万）

生成したいグラフサイズが小さい場合，Hadoop 実
装で十分なタスク分割が行われず（Map タスクへの以上の結果により，提案手法を用いることで，本研入力を記したファイルが分割されず），逐次実装のほ究の目的であった「一台の計算機では生成できないサ

うが速く生成可能である．実際，100 万頂点では計算

イズでの Watts-Strogatz モデルのランダムグラフ生機代数よりも少ない数のタスクしか生成されず，計算成」が達成されたことが確認された．

機台数を増やしても計算時間は短縮されない．
他 方 ，生 成 す る グ ラ フ サ イ ズ を 大 き く す る と ，Hadoop 実装の分散並列実行の効果が現れるよう

5. 2. 2 生成時間のモデルパラメータへの依存
次に，提案手法を用いた場合のグラフ生成時間の，モデルパラメータ N ，K ，P への依存を評価する．

になる．実際，1000 万頂点でも，タスク数による頭Hadoop 実装について，計算機を 16 台用いた際の，打ちはあるものの計算機代数を増やすにつれて計算時各パラメータ N ，K ，P だけを変化させた場合の計間が短縮され，明らかに逐次実装よりも速くグラフ生

算時間の変化を図 8 から図 10 に示す．

成を終えている．さらに，1 億頂点では，もはや逐次

まず，図 8 より，生成時間が N に比例しているこ

実装ではメモリ不足等によりグラフの生成自体が不とがわかる．また，図 9 より，生成時間が K にも比可能になっているのに対し，分散並列実装の Hadoop

例していることがわかる．提案手法の計算量は明ら

実装では，例え計算機１台であろうとも生成を正常にかに O(N K) であるので，これは期待通りの結果で終えることができ，また，投入する計算機台数に反比ある．

例する形で生成時間の短縮が達成できている．

次に，P の値の生成時間への影響を見る．図 10 よ

表1

NetworkX
頂点数

ランダムグラフ生成時間（秒）Python 実装（逐次実装） （逐次実装）

Hadoop 実装
1台

2台

4台

8台

16 台

100 万

6

9

19

17

16

16

17

1000 万

66

92

83

56

30

24

21

1億

–

–

833

414

213

139

78

表 2 より，生成すべきグラフサイズが大きい場合に90

は，ブロックサイズを大きくすることが望ましいとわ

80

かる．ただし，今回の実装では，入力とするブロック

70

を 1 行毎並べたファイルを MapReduce への入力とtime[sec]

60
N = 1,000,000
N = 10,000,000
N = 100,000,000

50
40
30

しているため，ブロックサイズが大きくなるにつれて入力ファイルが小さくなり，十分な Map タスクの生成ができず並列化効率が低下してしまっている．適切20

な Map タスクの生成が望ましい．なお，入力ファイ10

ル自体の生成にも多少の時間がかかる．入力ファイル

0

0.0

図 10

0.2

0.4

0.6

P

0.8

1.0

は N が変わる毎に必要となるが，ひとつの N に対P だけを変化させたときの生成時間（K = 4）

して複数のグラフを生成するであろうことを考えると，その生成時間は無視しても良い．実際，例えば，

表2各ブロックサイズにおけるグラフ生成時間（秒）生成頂点数

1 億頂点における入力ファイル生成時間は，ブロック
サイズが 1 の場合に 105 秒，ブロックサイズが 8 のブロックサイズ

1

2

4

8

10

100 万

12

14

13

17

16

1000 万

17

14

17

18

22

1億

82

62

48

47

55

場合に 13 秒程度である．

6 関連研究Watts-Strogatz モデル以外にも様々なランダムグ
ラフ生成モデルが知られている．

り，P の計算時間への影響は小さいが，P が大きく

Erdős-Rényi モデル [5] は，最も単純なランダムグ

なるにつれ，多少時間が伸びる傾向が観察される．こラフ生成モデルである．その生成法は単純で，各ノー

れは，P が大きくなると，単純なリング状格子の接ドが独立に，自分以外の各ノードに対し，与えられた

続に比べて接続先の決定が複雑となる再接続処理が確率 P で辺を張るというものである．言い換えれば，増えるためである．すなわち，予想される通りの結果

完全グラフの各辺について，確率 1 − P で削除を行である．

うというものである．生成法の単純さ故に用意に分散並列化が可能であるが，しかし，現実のグラフに見ら

5. 3 Map タスクへの入力と計算時間れるようなスケールフリー性や高いクラスタ係数な

我々の Hadoop 実装は，Map タスクへの入力区間どの性質を持つグラフは生成されない．このモデルに[s, e) のブロックサイズ e − s に処理時間が左右され基づくグラフの並列生成には，例えば GPU を用いる．以下，その影響を測定した結果を示す．

た生成システム PPreZER [3] も存在する．

使用計算機台数を 16 台に固定し，K = 2, P = 0.4

Barabáshi-Albert モデル [1] は，Watts-Strogatzとした際の，ブロックサイズに応じたグラフ生成時間

モデルに並んで広く認知されているランダムグラフ生の様子を表 2 に示す．

成モデルである．このモデルで生成されるグラフは，

膨大なリンクをもつ頂点（ハブ）が少数存在するよう入によって元の Watts-Strogatz モデルの備えていたな，スケールフリー性を備えることが知られている．

特徴を破壊していないことも確認した．さらに，提案

そのため，現実のグラフの良い模倣として利用でき

手法を Hadoop MapReduce を用いて実装し，分散る．このモデルでのグラフ生成は，基本的には頂点を並列実行による生成時間の短縮と，一台の計算機では一つずつ既存のグラフに追加していくことで行う．頂

対応できなかったサイズのグラフの生成が可能となっ点の追加の際には，既に多くの辺を持っている頂点にたことを確認した．

接続しやすくするため，頂点次数に比例した確率で接今後の課題として，提案手法のより効率的な実装

続先の選択を行う．残念ながら，この強く逐次的な生と，Watts-Strogatz モデルをベースとした派生モデ

成法は，並列化が容易ではない．難しい．

ルへの手法の適用などが考えられる．

Klemm-Eguı́luz モデルは [6]，Barabáshi-Albert
モデルを元にしたモデルで，Watts-Strogatz モデル

参 考 文 献が持つスモールワールド性と Barabáshi-Albert モデ[ 1 ] Barabáshi, A.-L. and Albert, R.:
Emergence of Scaling in Random Networks, Science,
No. 286(1999), pp. 509–512.
[ 2 ] Barrat, A. and Weigt, M.: On the propertiesof small-world network models, European PhysicalJournal B, Vol. 13, No. 3(2000), pp. 547–560.
[ 3 ] Bressan, S., Cuzzocrea, A., Karras, P., Lu, X.,
and Nobari, S. H.: An Eﬀective and Eﬃcient Parallel Approach for Random Graph Generation overGPUs, Journal of Parallel and Distributed Computing, Vol. 73, No. 3(2013), pp. 303–316.
[ 4 ] Dean, J. and Ghemawat, S.: MapReduce: Simplified data processing on large clusters, Communications of the ACM, Vol. 51, No. 1(2008), pp. 306–
318.
[ 5 ] Erdös, P. and Rényi, A.: On random graphs I,
Publicationes Mathmaticae Debrecen, Vol. 6(1959),
pp. 290–297.
[ 6 ] Klemm, K. and Eguı́luz, V. M.:
Highlyclustered scale-free networks, Physical Review E,
Vol. 65(2002), pp. 036123.
[ 7 ] Leskovec, J., Chakrabarti, D., Kleinberg,
J. M., Faloutsos, C., and Ghahramani, Z.: Kronecker Graphs: An Approach to Modeling Networks, The Journal of Machine Learning Research,
Vol. 11(2010), pp. 985–1042.
[ 8 ] NetworkX Developers: Overview of NetworkX.
https://networkx.github.io/documentation/stable/.
[ 9 ] The Apache Software Foundation: Apache
Hadoop. https://hadoop.apache.org/.
[10] Watts, D. J. and Strogatz, S. H.: Collective dynamics of ‘small-world’ networks, Nature,
No. 393(1998), pp. 440–442.
[11] 縄田和満: 基礎系 数学 確率・統計 I (東京大学工学教程), 丸善出版, 2013.

ルが持つスケールフリー性を両立するモデルである．
その生成法の改変は，Barabáshi-Albert モデルにおける新しい頂点の追加の際に，古い頂点の中から以降の接続に関与しない頂点を作るというものである．
これにより，Barabáshi-Albert モデルになかった性質を得られるものの，その生成法は依然として強く逐次的であるため，並列化は難しい．

Kronecker Graphs [7] は，クロネッカー積に基づいたランダムグラフ生成モデルであり，現実のグラフと同様の性質をもつグラフを生成できることが知られている．また，その生成の並列化も，Barabáshi-Albert
モデル等に比べて容易である．この生成モデルは，例
えば Graph500 の巨大な入力グラフの生成などに用いられている．

7 まとめ
本研究では, グラフ解析プログラム等の評価によく使われるランダムグラフ生成モデルである，Watts-

Strogatz モデルの分散並列化手法を提案した．その基本的アイデアは，並列化の際に問題となる再接続辺の重複を避けるために，再接続先選択に簡単な偶奇制約を導入するというものである．また，その制約の導