DEIM Forum 2017 I6-2

ランダムウォークを用いたソーシャルネットワークの平均距離推定
松村 俊樹†

岩崎 謙汰†

首藤 一幸†† 東京工業大学 情報理工学研究科 〒 152-8552 東京都目黒区大岡山 2-12-1
E-mail: †matsumura.t.ac@m.titech.ac.jp
あらまし ネットワークのスモールワールド性を示す指標として平均距離がある．平均距離を厳密に求めるためには，ネットワークの任意の 2 ノード間の最短距離を測る必要がある．しかし，現実のソーシャルネットワークは，セキュリティやプライバシ保護による制限のため，ネットワーク全体を得ることが難しい．そのため，ネットワークの一部をサンプリングして特徴量を推定する方法が有効である．本研究では，クローリングによるサンプリング手法の 1 つであるランダムウォークを用いて，平均距離を推定する手法を提案する.
キーワード

ソーシャルネットワーク，複雑ネットワーク，グラフサンプリング，平均距離
ランダムノードサブグラフサンプリング（RVS），ランダムエッ

1. は じ め に

ジサブグラフサンプリング（RES），ランダムノードサンプリ

ソーシャルネットワーキングサービス（SNS）の利用者は年々増加の一途を辿っている．例えば，Facebook（注 1）

ング（RV）の 4 つのサンプリング手法を用いて平均距離の推定の利用者はを行っているが，BFS 以外の手法はランダムサンプリングの一2016 年時点で 15 億人を超えており，このような巨大なソー種であり，現実のソーシャルネットワークに適用することが困シャルネットワークを解析することの関心が高まっている．具難である．また，BFS はクローリング手法の 1 つであるが，サ体的には，SNS の利用者をノード，利用者間の関係をエッジンプルが初期ノード周りに偏ってしまう性質から，ネットワーとしたグラフの構造を解析する方法がある．人間関係のネットク全体の特徴を正確に推定できない．一方でランダムウォークワークのような巨大で複雑なネットワークは複雑ネットワークによるグラフサンプリング手法は，各ノードへの訪問割合が数と呼ばれ，ほとんどのソーシャルネットワークのグラフ構造は学的に算出できるため，サンプル列を上手く解析すればグラフ複雑ネットワークを成している．

全体の特徴量を偏りなく推定できそうである．そこで我々は，複雑ネットワークにおいて，ネットワークのスモールワールクローリングによるグラフサンプリング手法の 1 つであるランド性を示す指標として平均距離がある．平均距離は，ネットダムウォークによってネットワークの平均距離を推定する手法

ワークの任意の 2 ノード間の最短距離の平均であり，一般的にを提案する．提案手法では，遷移確率が一様である最も単純な「世間は狭い」とは平均距離が小さいことを指す．平均距離をランダムウォークを用いる．

厳密に算出するには，ネットワークの任意の 2 ノード間の最短本論文の構成は以下のとおりである．2 章では本研究で用い距離を全て求める必要があるが，ソーシャルネットワークではる言葉の定義や記法について述べ，3 章で我々の提案手法につ非現実的である．なぜなら，セキュリティやプライバシ保護にいて述べる．4 章では様々なネットワークについて既存手法とよる制限によって全ノードの情報が得られないためである．そ提案手法の比較実験及び考察を行い．5 章では本研究の貢献とのため，ネットワークの一部のみを用いてネットワークの特徴今後の課題を述べる．

量を推定するグラフサンプリング手法が有効である [1]．
グラフサンプリングは大きく分けて，ランダムサンプリング

2. 準備とクローリングによるサンプリングの 2 種類がある．ランダム

本章では，今まで研究されてきたグラフサンプリング手法やサンプリングは，独立な確率でネットワークからノードやエッ平均距離について述べる． 記法については適宜説明を述べ，表ジを選択しサンプリングする手法であるが，実社会のソーシャ

1 にまとめた．

ルネットワークは，運営が保持しているネットワーク全ての情

2. 1 グラフサンプリング手法

報が事前に得られないことがほとんどであり，実現することはグラフサンプリングとは，出来るだけ少ないデータでグラフ困難である [2, 3]．一方でクローリングによるサンプリングは，全体の特徴を推定する手法である．巨大で解析に多大のコスト隣接しているノードやエッジを選択しサンプリングしていくが掛かるグラフや，セキュリティやプライバシの問題でグラフ手法であり，事前情報を必要としないため，ソーシャルネットの全トポロジ情報が与えられていないソーシャルネットワークワークに適用することができる．

等のグラフに有効である．グラフサンプリングの手法は大きく

グラフサンプリングによる平均距離推定は，過去に Qi Ye らによって実験されている．そこでは幅優先サンプリング（BFS），分けて 2 種類に分類される．ランダムサンプリングとクローリングによるサンプリングである．

2. 1. 1 ランダムサンプリング（注 1）：http://www.facebook.com/

ランダムサンプリングは，ネットワークから隣接関係を一切考慮せずに，ランダムにノードやエッジを選択して情報を収集していくサンプリング手法である．各ノードやエッジが選択さランダムウォークで訪れたノードれる確率は任意であり，最も単純なランダムサンプリングであ観測できるノードる一様独立サンプリング（UIS）では，総ノード数 n に対し各観測できないノードノードが選択される確率は 1/n と等しいため，偏りのない正確辿ることのできるエッジ辿ることのできないエッジな値を推定することが可能である．しかし，各ノードやエッジをランダムに選択するには，ネットワーク全体の情報を事前に知っている必要があるので実現は困難である [2, 3]．また，クラ図1

ランダムウォークによるグラフサンプリングの例
色付きのノードと太いエッジからなるサブグラフを G′ と表す．

スタ係数や平均距離等の，ノード間やエッジ間の繋がりを示す特徴量の推定には不向きであるという欠点もある.

G(V ，E)

重み無しの無向グラフ

2. 1. 2 クローリングによるサンプリング

V ，E

ノードとエッジの集合

ランダムサンプリングを実社会のネットワークに適用するこnノードの数とは困難であるため，隣接関係を辿っていくクローリングによvi

G のノードるサンプリングが現実的な手法である．クローリング手法は大diきく分けて 2 種類に分類される．走査ベースの手法とランダムウォークベースの手法である.

ノード vi の次数∑ni=1 di次数の総和

D

ノード vi の隣接ノード

N (vi )

ランダムウォークの定常分布πa ) 走査ベースr

サンプリングのコスト

走査ベースのサンプリングは，幅優先サンプリング（BFS）

xk

ランダムウォークの k 番目のノードのインデックスや深さ優先サンプリング（DFS），スノーボールサンプリングG′

ランダムウォークのサンプルノードとその隣接ノード群から生成したサブグラフが有名である [4]．BFS やスノーボールサンプリングは，あるノードの周りの情報を集めるという点で特定のコミュニティや集団の解析において広く使われているが，ネットワーク全体の特徴量を正確に推定する場合には不向きである [5]．また，各V2同一ノードを除いたノードの組の集合

Svi ,vj

ノード vi からノード vj への最短ステップ数L

G の平均距離L̂L の推定値

ノードにどのような割合で訪れるのか分析することが出来な

表 1 記法のまとめいため，推定値がどの値に収束するか不明であるという欠点もある．

T (ϵ) = max min{t : |π − π (i) P t |1 < ϵ}b ) ランダムウォークベースi

ランダムウォークは，初期ノードから隣接ノードの１つへ確

π はランダムウォークの定常分布である． P t は t ステップ後の遷率的に遷移してノードの情報を収集していく手法である．遷移移確率行列であり，|・|1 は全変動距離を指す．全変動距離とは，確率が一様ランダムである最も単純なランダムウォークのことを Simple random walk（SRW）と呼ぶこととする．SRW のノード vi からノード vj への遷移確率を Pvi ,vj とすると，

度 P ，Q とある事象 A に対して |P ，Q|1 = sup |P (A) − Q(A)|と定義される．mixing time のオーダーは O(log2 n) 程度であり，ランダムウォークによる同一サンプル列内のノードの組

Pvi ,vj =2 つの確率分布の間で同事象の確率の差の最大値であり，確率測

1dvi

 0

でも，mixing time 以上インデックスが離れていれば，ネットvj ∈ N (vi )ワークからランダムサンプリングしたものと見なせることが分

otherwise

かっている [8]．と表せる．dvi と N (vi ) はそれぞれノード vi の次数と隣接ノー

2. 2 平 均 距 離
平均距離は，スモールワールド性を示す指標であり，ネットドである．
ランダムウォークの最大の利点は，各ノードへの訪問確率ワーク内の全ノード間の最短距離の平均である．本研究においが数学的に証明されていることである．例えば，SRW によるて，対象にするグラフは重み無しのグラフを仮定するため，最′t ステップ後の各ノードへの訪問確率の分布 π は，事象が起短距離のことを最短ステップ数とも呼ぶ．Svi ,vj をノード vi かこる確率を P r とすると，π ′ = (P r[xt = 1]，P r[xt = 2]，...

らノード vj への最短ステップ数とすると，平均距離 L は′，P r[xt = n]) と表すことができる．π の i 番目の要素を πとすると π′(i)′(i)は dvi /D に収束することが知られている [6]．Dは次数の総和であり定数である．つまり SRW において，各ノードへの訪問確率は次数に比例する．

L=∑2
Sv ,vn(n − 1) 1<i<j <n i j==と定義される．ネットワークの総ノード数 n が増加した際に，訪問確率が定常分布に収束するまでのステップ数 T のことをL が高々 log n 程度の増加幅である時，このネットワークはスmixing time と呼び，パラメータ ϵ を用いて次のように定義さモールワールド性を満たすという．本論文では，この平均距離れている [7]．

をグラフサンプリングによって推定する．

2. 3 前

提2𝑣2

既存のグラフサンプリング手法の中には実社会の SNS での運用を前提にしていないものもある．本研究は，実社会の SNSに適用できる平均距離推定手法を目指しているため，いくつかの前提を考える必要がある．本節では，グラフサンプリングを行うにあたっていくつかの前提条件を述べる．

a ) ネットワークの構造

m=2𝑣4

14𝑣6𝑣1𝑣3

クローリングによるグラフサンプリング手法はその性質上，

𝑣5

1234𝑣1𝑣2𝑣5𝑣63

図 2 I の要素の例

初期ノードから連結した部分の特徴量しか求めることはできず，孤立したノードやクラスタまで加味することはできない．そのため，対象にするネットワークは基本的に連結であるものとする．孤立したノードやクラスタが存在する場合は無視する．

b ) クローリング中のネットワークの状態
実社会のソーシャルネットワークはノードの参加や離脱が頻繁に起こっている．しかし Gjoka らは，Facebook においてクローリングする時間に対する総ノード数の変化は微々たるものと述べている [9]．そのため本研究では，ネットワークは静的なものと仮定する．

c ) 未知の情報
実社会のソーシャルネットワークにおいて，ノード間の最短ステップ数が与えられていることはほとんどないため，ノードvi とノード vj 間の最短ステップ数 Svi ,vj は未知の値とする．
d ) サンプリングの際に取得する情報
本研究では，ノードの次数の情報を用いる．実社会のソーシャルネットワークにおいて，隣接ノードの ID を取得することは多くの場合容易であるため，「ノードをサンプリングする」とは SNS の API へアクセスし，そのノードの ID と隣接ノードの ID を取得し保持することとする．

i ) サンプリング
SRW を用いてグラフ G(V ，E) からコスト r 分ノードのサンプル列を取得する．本研究ではランダムウォークのステップ数をコストと呼ぶこととする．我々はサンプリングしたノード IDとその隣接ノードの ID を情報として取得する．

ii ) ノードペアの選択
最短ステップ数を求めるために，サンプル列からノードペアを選択する．しかし，サンプル列内のインデックスが近いノードペアは強い相関関係にある．例えば，サンプル列内の i 番目のノードと i + 1 番目のノード間の最短ステップ数は必ず 1 であるように，インデックスが近いノードの組はその間の最短ステップ数が小さい傾向がある．そのため，本手法では SRW で集めたサンプル列内の「ある程度離れた」ノードの組を用いる．
この条件は，組内のノードが SRW の定常分布に従ってグラフからランダムに選択したものであること，つまりランダムサンプリングされたものであることを保証するために必要である．

SRW によるサンプル列 (vx1 ，vx2 ，..．
，vxr ) について，mixingtime 以上のある閾値 m 以上離れた異なるノードの組の集合 Iを次のように定義する．

e) コ ス ト
複数のグラフサンプリング手法を比較する際には，サンプリ

I = {(vxi ，vxj )|m <| xj }=j−i∧ 1<=i<j<= r，xi =ングのコストを合わせて実験を行う必要がある．コストの定義は以下の 2 種類が考えられる．

•クローリングの総ステップ数: クローラがノードに遷移する度に増やしていく．

•SNS の API へのアクセス回数: 本研究では，サンプリングしたノード ID とその隣接ノード群の ID を保持すると定これが解析に使用するノードの組である．例えば，図 2 の右図のようなサンプル列が取得された際，m = 2 とすると，サンプルとして用いるノードの組は列内のインデックスが 2 以上離れた {(v1 ，v5 )，(v1 ，v6 )，(v2 ，v6 )} の 3 つとなる．

iii ) 平均距離 L の推定値 L̂ の計算義しているため，1 度訪れたノードへ再び遷移した際に API へ

I 内のノードの組における Svi ,vj の平均が求める値であるのアクセスを行わない．未知のノードへ遷移したときのみアクが，Svi ,vj は事前に G 全体のトポロジ情報を得ていないと算セス数を増やす．
本研究ではクローリングの総ステップ数をサンプリングのコストとする．

3. 提 案 手 法
本章では，ランダムウォークを用いたグラフサンプリングによってネットワークの平均距離を推定する手法を提案する．真値よりも大きな値に推定値が収束することを利用した抑え込み手法について述べる．

3. 1 平均距離推定手法の流れ
提案手法は，ネットワークから SRW でサンプリングを行った後にサンプル列を解析するという流れを取る．

出することは不可能である．そこで，保持している情報のみでの最短ステップ数を求める．具体的には，ランダムウォークで訪れたノードとその隣接ノード群から形成される G′ について，Sv′ i ,vj を求め，その平均をとる．例えば図 1 において G′ は色付きのノードと太いエッジからなるサブグラフである．Sv′ i ,vj′
は Svi ,vj <= Svi ,vj の関係を満たす．

ϕ(ω) を I 内のノードの組における Sv′ i ,vj に重み ω をかけたものの平均，ψ をサンプル列内の 1/dvi の平均とすると

ϕ(ω) =

ψ =

∑1
|I|

3. 3 m の決定方法

ωSv′ i ,vj

mixing time は用いるランダムウォークの手法や対象にする(vi ,vj ) ∈ I

ネットワークによって変動する値であるので，事前に知ること

r∑1
1
r i=1 dviは困難である．m が mixing time よりも小さいと，独立でないノードの組，つまり比較的短いステップ数で繋がったノードとなり，その期待値はの組を多くサンプリングしてしまうので推定値が想定より小さな値に収束してしまう．一方で m が大きすぎると，I の要素がE[ϕ(ω)] = E[ωSv′ i ,vj ]∑=ωSv′ i ,vj π (i) π (j)=1<|=i<j <=n，i=j

E[ψ] = E[dv dvj
ωSv′ i ,vj i
D D=を行い，値の変化を見る手法を用いる．

4. 実

験

本章では，3 章で述べた m の決定手法について実験し，その1]dvim を用いて，提案手法による推定値を評価する．比較対象は，

r
∑
1 (i)
=πdvi
i=1=いので，分散が大きくなってしまう．そこで，ランダムウォー
クのサンプル列について逐次的に m を増やして平均距離推定

1<|=i<j <=n，i=j∑

減ってしまい，少ないサンプルで推定値を求めなければいけな

BFS による平均距離推定手法と，SRW によるサブグラフの平均距離を求める手法を用いる．

r∑1 dvidvi D
i=1OSnD

メモリ

4GB RAM

言語

Python2.7

Microsoft Windows 8.1

プロセッサ Intel (R) Core (TM) i5-3230M CPU @ 2.60GHz

表2

実験環境となる．推定値 L̂ を次のように定義すると

L̂ =ϕ( dv 1dv )i

実 験 に は 複 雑 ネット ワ ー ク の 生 成 モ デ ル の 1 つ で あ るψ2′Svi ,vj <= Svi ,vj となることにより

E[L̂] =1n2∑

Barabasi-Albert モデル（BA モデル）で作成したネットワー
ク，ランダムネットワーク，Stanford Network Analysis Project（SNAP）のデータセット [10] で公開されている現実社会のネッ

Sv′ i ,vj

トワークのデータセットを用いた．また，各ネットワークの特1<|=i,j <=n，i=j∑2n−1
Sv′ ,v=n n(n − 1) 1<i<j <n i j=n−1
2>= n n(n − 1)

4. 1 ネットワークのデータセットj=∑Svi ,vj

1<=i<j <=nn−1
L=nとなる．つまり，推定値 L̂ は n−1
L 以上の値に収束する．
nSNS において n は十分に大きいので， n−1L ≃ L と見なせる．
n徴を表 3 にまとめた．
NetworknD/nBA model

L100000

9.99950

4.2989Random Network 100000

9.99245.2631

Gnutella

62581

4.727485.9355

DBLP

3170806.622096.7815

表3データセットの概要

4. 2 予 備 実 験
本節では，3 章で述べた m の決定手法について各ネットワー

また，SRW によるサンプル数 r を増やすほど，Sv′ i ,vj は Svi ,vj

クで実験を行う．具体的には，総ノード数 n の 5% の分だけへと収束するので，推定値 L̂ は L に近づく．

SRW によりノードをサンプリングし，m を変動させて値の変3. 2 Svi ,vj と Sv′ i ,vj
最短経路はそのネットワークのハブであるノードを含んでいることが多い．複雑ネットワークを対象に考えると，G のサブグラフ G′ は SRW が次数の高いノードへ訪れやすいという性質を持っているため，ハブとなるノードを多く含んでいる．つまり，G′ での最短経路と G での最短経路の間に極端に大きな化を観察する．その結果を図 3 に示す．
この結果を見ると，いずれも m を増加させるとある時点で値が収束し始めていることがわかる．例えば図 3 の Gnutellaネットワークを見ると，m が 50 あたりで値が収束し始めていることが分かる．つまり Gnutella ネットワークにおいて SRWの mixing time はおおよそ 50 であり，仮に m を 100 等とす違いは見られないと考えられる．一方で，スケールフリー性れば十分独立なノードペアが選択できていると見なせる．このを満たさないランダムネットワークや交通ネットワーク等ではようにして各ネットワークにおいて m を定める．

Svi ,vj と Sv′ i ,vj の間に大きな差が出てしまうことが予想できる．

Barabasi-AlbertRandom Network

4.446

7.542

7.54

4.445

Average Path Length

Average Path Length

4.44554.44454.444
4.44354.443

4.4425
4.442

7.538

7.536
7.534

7.532
7.53

4.4415

7.528

4.441
0

100

200

300

400

0500

100

200

400

500

1250

1500

DBLP

Gnutella
7.605

7.1

7.6

Average Path Length

7

Average Path Length

300mm

6.9
6.8
6.7
6.6

6.5

7.595
7.59
7.585
7.58
7.575
7.57
7.565
7.56

6.4

050

100

150

200

250

300

0250

500

1000mm
図3750

各ネットワークにおいて m を動かしたときの L̂ の変容

4. 3 平均距離の推定実験
本節では，3 章で述べた L̂ の変化をサンプル率を変化させて観察する．図 4 は，それぞれのネットワークについて L̂ の推移を表したものである．m は 4.2 節で述べたように定める．

5. まとめと今後の課題
本研究では，ランダムサンプリングが難しいソーシャルネッ
トワークに対して，ランダムウォークを用いたグラフサンプリ

4. 4 実 験 結 果

ングで平均距離を推定する手法を提案した．提案手法は，ク

提案手法は，サンプル率を増やしていくにつれて真値よりローリングによるグラフサンプリング手法を用いているため現も大きな値から徐々に近づいていく動向を見せ，サンプル率が実社会の SNS に適用可能である．さらに提案手法は，スケー5%の段階ではランダムネットワーク以外の 3 つのネットワークルフリーネットワークに有効な手法であると言える．

において，比較手法よりも精度が良い手法であることがわかっ

また本論文では，サンプル率を各ネットワークで一律 5%また．これは 3.2 節で述べたように，次数が一様で大きなハブがでと定めて実験を行った．しかし，実際に現実社会の SNS に存在しないランダムネットワークでは Svi ,vj と Sv′ i ,vj の間にグラフサンプリングを適用する場合は，例えばランダムウォー大きな差が生まれてしまっていることが要因だと考えられる．

クがネットワークをクローリングする時間を 1 週間等と定め，実際に，Svi ,vj と Sv′ i ,vj の完全一致率を示したものが図 5 であ

そこで得られたサンプルで特徴量を推定する方法が望まれる．

る．これを見ると，スケールフリーネットワークに対して完全最後に，提案手法はネットワークの一部の情報のみを用いて一致率が 8 割から 9 割を達成している一方で，ランダムネットいるものの，計算時間は最も単純な Dijkstra 法を用いて，サンワークの完全一致率は極端に低いことがわかる．しかし現実社

プル数 r に対して O(r 3 ) かかってしまう．これを解決するため

会のソーシャルネットワークは，有名人等が極端に多くの交友に，アルゴリズムの効率化を考える必要がある．例えば，SRW関係を有していることが多く，スケールフリーネットワークでによるサンプル列から m ステップ以上離れたノードペアを選あることがほとんどである．そのため，提案手法は現実社会の択するところを，ちょうど m ステップ離れたノードペアを選SNS に対して有効な手法と言える．

択するようにすれば，多少精度は悪くなるものの最短距離の計算回数が減ることが見込まれる．このトレードオフの評価も今Barabasi-Albert

612Average Path Length

5Average Path Length

Random Network

14104321提案手法

G'のAPL

BFS

真値

8642G'のAPL

BFS

真値

000123405123sampling rate (%)

sampling rate (%)

Gnutella

1045DBLP

108

Average Path Length

8Average Path Length

提案手法

642提案手法
BFS

G'のAPL
真値

642提案手法

G'のAPL

BFS

真値

00012345012sampling rate (%)
図4

図 5 最短距離の完全一致率後の課題とする．

辞本研究は JSPS 科研費 25700008 および 16K12406 の助成を受けたものです．本研究の一部は，国立研究開発法人新エネル
ギー・産業技術総合開発機構（NEDO）の委託業務として行われました．

4各グラフにおけるサンプル率に対する L̂ の変容

文

謝

3

sampling rate (%)

献[1] Pili Hu and Wing Cheong Lau. A survey and taxonomy ofgraph sampling. arXiv preprint arXiv:1308.5865, 2013.
[2] Minas Gjoka, Maciej Kurant, Carter T Butts, and Athina
Markopoulou. Practical recommendations on crawling online social networks. IEEE Journal on Selected Areas inCommunications, Vol. 29, No. 9, pp. 1872–1892, 2011.
[3] Shaozhi Ye, Juan Lang, and Felix Wu. Crawling onlinesocial graphs. In Web Conference (APWEB), 2010 12th
International Asia-Pacific, pp. 236–242. IEEE, 2010.
[4] Maciej Kurant, Athina Markopoulou, and Patrick Thiran.
Towards unbiased bfs sampling. IEEE Journal on Selected
Areas in Communications, Vol. 29, No. 9, pp. 1799–1809,
2011.
[5] Maciej Kurant, Athina Markopoulou, and Patrick Thiran.
Towards unbiased bfs sampling. IEEE Journal on Selected
Areas in Communications, Vol. 29, No. 9, pp. 1799–1809,
2011.
[6] David Aldous and Jim Fill. Reversible markov chains andrandom walks on graphs, 2002.
[7] Abedelaziz Mohaisen, Aaram Yun, and Yongdae Kim. Measuring the mixing time of social graphs. In Proceedings ofthe 10th ACM SIGCOMM conference on Internet measurement, pp. 383–389. ACM, 2010.
[8] Stephen J Hardiman and Liran Katzir. Estimating clustering coeﬃcients and size of social networks via randomwalk. In Proceedings of the 22nd international conferenceon World Wide Web, pp. 539–550. ACM, 2013.

5

[9] Minas Gjoka, Maciej Kurant, Carter T Butts, and AthinaMarkopoulou. Practical recommendations on crawling online social networks. IEEE Journal on Selected Areas inCommunications, Vol. 29, No. 9, pp. 1872–1892, 2011.
[10] Stanford large network dataset collection. https://snap.
stanford.edu/data/.