DEIM Forum 2013 E9-5

一様独立サンプリングとランダムウォークを組み合わせたグラフのサンプリング手法

宇都宮健太†

首藤一幸 ††† , †† 東京工業大学 大学院情報理工学研究科 数理・計算科学専攻〒 152-8550 東京都目黒区大岡山 2-12-1-W8-43
E-mail: †utsunomiya.k.aa@m.titech.ac.jp, ††shudo@is.titech.ac.jp
あらまし ソーシャルグラフ等，大規模なグラフを対象としてグラフの特徴量を得るためのサンプリング手法として，ランダムウォーク（RW）と一様独立サンプリング（UIS）がある．一般的に UIS はノード ID が既知であることなどを前提とするために適用できないケースが多く，RW の方が現実的であると考えられている．しかし，ノード ID が既知でなくともある程度密であれば，存在する ID を一定の成功率で推測することは可能である．以下，存在する ID の推測成功率が低いために UIS を効率的に行えない状況を想定する．そこで我々は，UIS と RW を組み合わせるサンプリング手法を提案する．これにより，ある種の特徴量をより正確に算出できるという UIS の利点と，ノード ID が既知でなくともよいという RW の利点を両立させる．また，UIS と RW の混合割合によって，トレードオフの関係にある特徴量の正確さとサンプリング効率がどうなるかを調べる．
キーワード

ノードサンプリング ，ソーシャルグラフ

A Graph Sampling Technique
combining Random Walk and Uniform Independent Sampling

Kenta UTSUNOMIYA† and Kazuyuki SHUDO ††† , †† Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology
2-12-1-W8-43 Ookayama, Meguro, Tokyo, 152-8552 Japan
E-mail: †utsunomiya.k.aa@m.titech.ac.jp, ††shudo@is.titech.ac.jp
Key words Node sampling, social graph

1. 導入ランダムウォーク（RW）と一様独立サンプリング（UniformIndependent Sampling，UIS）がある．

グラフ解析の対象は、インターネット、航空網などから Face-

ランダムウォークはあるノードから隣接する他のノードへとbook、Twitter といった SNS まで、より大規模なものとなっ次々とノードをたどっていく抽出手法である．ランダムウォーてきた。しかしながらそういった巨大なグラフ全体を直接詳細

クは各ノードがどのノードと連結しているかという情報さえあに解析することは，莫大なコストがかかりすぎるため非常に困ればよく，ノード ID を知る必要がないため，サンプリングが難である．そのため，現在はグラフ全体を直接解析するのではしやすいという利点がある．また解析対象のグラフが連結でななく，グラフ全体から部分グラフを抽出し，その部分グラフをかった場合は，抽出されないノードが必ず存在してしまうため，解析する手法を用いる．このような方法はグラフサンプリング

グラフ全体にわたる特徴を見つけることは困難である．と呼ばれる．

一方，UIS は全ノードからランダムに，ノードを選択していグラフサンプリングでは大規模なグラフからどのノードく抽出手法である．UIS では各ノードの ID を知る必要があるを抽出するかが特に重要であり，代表的な抽出方針としてにためサンプリングは比較的難しい．しかし各ノードが選択される確率は全ノードで等しいため，平均次数といった特徴量はラ （ 1 ） G0 =（V 0 , E 0 ）：サンプリングされた部分グラフ
ンダムウォークと比べて正確になるという利点がある．しかし，（ 2 ） C ：サンプルノードの衝突回数
UIS で求めた部分グラフは連結でない可能性が高いためクラスタ係数といったノード同士のつながりに関する特徴量の計算には向かない．
そこで我々はある種の特徴量をより正確に算出できるというアルゴリズム：（ 1 ） count[v] = 0 for all v ∈ V

UIS の利点と，ノード ID が既知でなくともよいという RW のV0 =φ

利点を両立させるため，ランダムウォークと UIS を組み合わせ

E 0 = φ と初期化たグラフのサンプリング手法を提案する．そして，その手法によって各ノードが選択される確率を算出する．さらに，この手 （ 2 ） グラフ内のノードを一つ選択し now node とする
法を実際のソーシャルグラフのデータセットに適用し，グラフのサイズや次数分布といったグラフの特徴量ををどれだけ正確に算出できるかを評価した．また RW と UIS の比をチューニ（ 3 ） 以下の作業（a, b, c, d）を r 回繰り返す（ a ） 次のノードへジャンプする．

ングすることでサンプリング全体に対して，どのような作用が起こるかどうかということも考察した．

2. 関 連 研 究•

確率 c でグラフ内の別のノードへジャンプする•

確率（1 − c）で now node と隣接しているノードへジャンプする（ b ） ジャンプ先のノード v に対し count[vi ]+ = 1

Metropolized Random Walk (MRW) [] はランダムウォーク
で遷移先の各ノードに重みを設定し重みが軽い方が遷移する確率が高くなるランダムウォークを行なっている．そのため，各（ c ） v を V 0 に加える．また v と隣接しているエッジを全て E 0 に加える．
（ d ） now node = v0

ランダムウォークの遷移手順では入次数の高いノードへ遷移する確率は低く抑えることができる．

（4）

C = 12|V |∑（count[vi ] ×（count[vi ] − 1））を計算

i=1

ForestFire 法 [] は UIS と幅優先探索を組み合わせた手法で0ある．幅優先探索を一定の確率で別スタート地点から行うこと （ 5 ） G , C を出力して終了
で，様々な部分のサンプルを取得することができる．
グラフの特徴量を導出する際に，グラフのノード数が必要にこのアルゴリズムでは，c = 0 の場合は単一始点ランダムウォー
クとなり，c = 1 の場合は UIS となる．

なってくることがある．グラフのサンプリングにおいてグラフ入力パラメータ c については，連続してランダムウォークで全体のサイズを求める手法は，Katzir [] がランダムウォーク中選択される数は幾何分布に従うため，以下のように決めることにサンプルノードが衝突する回数を利用してノード数 N をもできる

Ψ・Ψ−1
N=2C
•Ψ•C•

サンプルノードの入次数の和Ψ•c=−11kk：ランダムウォークで連続してノードがサンプリングされる個数の平均サンプルノードの入次数の逆数の和

4. 特徴量分析
サンプルノードの衝突回数

4. 1 ノード選択確率として概算できるとした．

3. RW と UIS を組み合わせたサンプリング手法

ランダムウォークにおいて各ノードが選択される確率はノードの入次数に比例する．UIS ではノードの入次数にかかわらず全ノードで一定である．そのため，UIS において各ノードが選

我々の提案手法では UIS が高い確率で可能であるという仮定択される確率は以下のようになる．の下で，UIS でサンプリングするノード数と RW でサンプリンdc
P（deg（v ）= d ）= （1 − c ）+DN

グするノード数の比を最初にパラメータとして与える．
入力：（ 1 ） G =（V, E ）サンプリング対象のグラフ（2） r

サンプリング回数（3） c

サンプルノードのうち UIS で選択するノードの割合

出力：

•D

全ノードの入次数の和•dノードの入次数•N

グラフのノード数表1

各データセットのグラフの詳細

orkut LiveJournal

Facebook

ノード数3,072,441

総エッジ数117,185,083

最大次数33,313

20,3334,929

α1.60.75

2.434,847,575

1,567,931

42,851,240 117,185,083

1orkutLive Journal
Facebook

0.1
0.010.001
図 1 Induced Subgraph Sampling (左) と Star Sampling (右)0.0001
1e-05

ノードが選択される確率を求めるにはグラフ全体のサイズと1e-06全体の入次数の和を知る必要がある．

Katzir の手法 [] を用いると，グラフサンプリング中のノード1e-07
1数は各ノードが選択される確率がノードに比例する．そのためこの手法はランダムウォークにおいてにしか成り立たない．そ10100

1000 10000 100000

図 2 各 データセット全体の次数分布のため，ランダムジャンプを含む我々の提案手法でノードのサイズの概算を行う場合は以下の式となる．

N=1（ΨΨ−1（1 − c）+ cr 2 ）2Cの二つがある

Star Sampling はサンプリングされた部分グラフのエッジのみに注目し, サンプリングされていないノードは一切含めな本研究では解析するグラフの対象を複雑ネットワークに限定い方法である．この方法では，サンプルグラフのノード同士がしている．そのため次数に関しては，複雑ネットワーク特有のつながっていることが正確にわかる．しかし，部分グラフのサ性質であるスケールフリー性を利用して解析を行う事ができる．

イズはサンプルノード数以下となる．

スケールフリー性とは，ノードの入次数の確率分布がべき乗則に比例するという性質である．

Induced Subgraph Sampling はサンプリングされたノードだけではなく，サンプルノードに直接連結しているノードとつまり，次数の分布が以下のようになるということである．

その間のエッジまで含める方法である．この方法を用いると，p(deg(v ) = k ) ∝ k−α

サンプリングされたグラフはサンプルノード数よりも大きくなる．

この事実を利用して，次数の和や次数分布の概算ができる．次5. 実数の和の概算値は以下の通りである．

∑提案手法がどれだけ正確に特徴量を算出できるかを，実際のdmax

D∼=Nk−α+1

ソーシャルグラフを用いて検証した．

5. 1 実 験 内 容

k=1dmax∑

本実験ではウェブページ [5] で提供されている orkut のソーk−αk=1

一般的なスケールフリーネットワークでは 0.5 <= 3 であ=α<る．定数倍の誤差を許容することになるが，仮に α = 2 とすると辺の本数は以下のように概算できる．

D∼=N

験

6 ln dmaxπ2

またサンプリングの際に，より正確な α も求めるならばサンプリングされたノードの次数分布に対して非線形回帰分析を行うことで，α を求めることができる．

4. 2 部分グラフの構築手法

シャルグラフと，Facebook のグラフと LiveJournal のグラフを用いた．各特徴量の真値は表 である．
各データセットの友人関係のソーシャルグラフは無向グラフであり，入次数と出次数が一致するため，出次数に関してのみ次数分析を行えば十分である．
提案手法の評価のためにジャンプ確率 c を変えてノードのサンプリング行った．このとき，c = 0 の場合はランダムウォー
クになり，c = 1 の場合は UIS となる．サンプル数のサイズはNN<r<= 100
10000 =

でグラフのサンプリングを行いサンプリングされたグラフにおいて以下の特徴量を求め，正しい値との比較を行った

サンプリングされたノードから部分グラフを構築する方法
として, Star Sampling と Induced Subgraph Sampling•

ノードサイズの概算

50

c=0
c=0.001c=0.01
c=0.1

c=0
c=0.1
c=0.01c=0.00140
error(%)

error (%)

201816141210864200.01

30
20
100.1

00.01

10.1

sampling rate (%)
図3

図5ノード数の概算 (Facebook)20

c=0c=0.001
c=0.01c=0.1

c=0c=0.001
c=0.01c=0.1

15error (%)

40error (%)

sampling rate(%)

ノード数の概算

50

130
2010
51000.01

0.1

00.01

10.1

sampling rate (%)

sampling rate (%)

図 4 ノード数の概算 (LiveJournal)

グラフ次数の和の概算•

ノード次数分布50て概算を行い，以下の式を利用して評価を行った．

|x̄ − x|xx：真値

•x̄：概算値

c=0c=0.001
c=0.01c=0.140

グラフ次数の和の概算は計算を簡略化するため α = 2 と仮定し•

図 6 次数和のの概算 (orkut)

error (%)

•1302010

またノードの次数分布については Star Sampling と Induced

00.010.11

sampling rate (%)

Subgraph Sampling の２種類の部分グラフでの評価を行った．
図75. 2 実 験 結 果

次数和のの概算 (LliveJournal)

5. 2. 1 ノードサイズの概算
orkut グラフと LiveJournal のグラフでは，グラフのサイズ対して Facebook のサンプルでは他のものと比較してグラフが十分でないときの誤差は大きかったが，c=0.1 の場合が最ものサイズが小さいにもかかわらず，正確な値を取得するに至っ誤差が小さくなっている部分があった．しかし，サンプルのサていない．

イズが 0.1%を超えたあたりから c = 0 のときを除いて誤差が5. 2. 2 グラフの次数の和の概算極端に大きくなっている．このデータセットにおいて，サンプ次数和の精度はノードサイズの精度と相関があるが，α の値ルサイズが大きな時に誤差はが大きくなる原因は，c = 0 の時の取り方によって定数倍の誤差が生じる．そのためノードサイ2を除いて概算値の r の項の影響が大きくなってしまうためだと思われる．

ズの概算よりも誤差が大きくなっている．

5040error(%)

7. ま と め

c=0c=0.1
c=0.01c=0.001

本研究では UIS と RW を組み合わせた手法を提案し, その手法で各ノードが選択される確率を算出した．また, 提案手法を用いて実際のソーシャルグラフの特徴量を求め, 真値との比較30を行った．次数分布を求めることにおいては，本研究では非線20形回帰を用いて概算を行った．その結果 RW も UIS も適切に計算を行えば，どちらも同程度の精度でグラフの特徴量を求め10られることがわかった．しかしながら，データセットの性質によって精度の違いが露呈することもわかった．データセットの00.010.1

図81sampling rate(%)とする．

次数和のの概算 (Facebook)

謝表 2 InducedSubgraphSampling での α の概算値の平均
真値

orkut

性質によらず常に正確な値を得る評価手法の提案を今後の課題

c=0 c=0.001 c=0.01 c=0.1

1.6 0.71

0.65

0.530.41

LiveJournal 0.75 0.41

0.44

0.42

0.44

1.65

1.340.9

Facebook 2.43

1.8

辞

本研究は科研費 (24650025) および独立行政法人情報通信機構（NICT）委託研究「新世代ネットワークを支えるネットワー
ク仮想化基盤技術の研究開発」の助成を受けたものである．

表 3 StarSampling での α の概算値の平均
真値

orkut

c=0 c=0.001 c=0.01 c=0.1

1.6 1.54

1.60

1.55

LiveJournal 0.75 0.71

0.63

1.43

1.56
1.1

Facebook 2.43 1.86

1.21

1.53

1.435. 2. 3 次 数 分 布
各分布において回帰分析を行い，α の値を概算したところ表2, 3 の通りになった．
何れのサンプルも c の値によらず Induced Subgraph Sam-pling にでは α の値はやや低めに出てしまっている.
Star Sampling では次数の低いノードの部分は確率分布はほぼ一致しているのに対して，次数の高いノードが極端に少ない．
しかしながら，InducedSubgraphSampling よりも正確な α の値を得ることができている．

6. 考察

orkut, LiveJournal, Facebook のデータセットといった複雑ネットワークにおいてグラフのサイズといった特徴量分析を行った．その結果，orkut と LiveJournal のデータセットでは，0.1%程度のサンプル数で最も正確な値を得られることができた．しかし Facebook のデータセットでは，最もノード数が少ないにもかかわらず，正確な値を得るにはより多くのノードをサンプリングする必要がある．
次数分布の解析においては Induced Subgraph Sampling はサンプルサイズに対して多くのノードを部分グラフの中に構築することができる．しかし，サンプリングされていないノードが大量に部分グラフに残ってしまうため次数分布においてはStarSampling と比べて精度が劣っている．

文献[1] W. Hastings , Monte Carlo Sampling Methods Using
Markov Chains and Their Applications , Biometrika, 1970.
[2] J Leskovec ，C Faloutsos , Sampling from Large Graphs ,Proc. KDD’06, 2006.
[3] Liran Katzir, Edo Liberty, Oren Somekh, Estimating Sizesof Social Networks via Biased Sampling, Proc. WWW’11,
2011.
[4] Stanford Large Network Dataset Collection,
http://konect.uni-koblenz.de/networks/orkut-links[5] orkut Network Dataset-KONECT,
http://snap.stanford.edu/data/index.html