DEIM Forum 2017 I6-5

後戻りなし Metropolis-Hastings Random Walk によるソーシャルネットワークのグラフサンプリング
岩崎 謙汰†

首藤 一幸†† 東京工業大学 情報理工学院 数理・計算科学系
E-mail: †iwasaki.k.ah@m.titech.ac.jp
あらましランダムウォークによるグラフサンプリング手法は，実際のソーシャルネットワークの情報取得の制限下でも複雑ネットワークの様々な性質を推定するため有用である．特に Metropolis-Hastings Random Walk は定常分布が一様分布であるため，サンプルした結果をそのまま推定に使用できるという利点を持つ．しかし，次数が低いノードに留まりやすいため，広範囲にサンプルするのに多くのステップ数が必要となり，推定の精度を下げる原因となっている．本研究では，これらの問題点を解決した後戻りなし Metropolis-Hastings Random Walk を提案する．提案手法は，少ないステップ数で広範囲にサンプリングを行うことが可能であり，既存手法よりもネットワークの特徴の推定の精度が高い．本論文ではこのことを実験により示した．
キーワード

ソーシャルネットワーク，グラフサンプリング，ランダムウォーク

1. は じ め に
昨 今 ，Online Social Networks (OSNs) や Peer-to-peer(P2P) ネットワーク，world wide web (WWW) などの複雑

表 1 RWRW と MHRW の比較

RWRWMHRW

サンプリング後の処理

必要

ready-to-use

サンプル範囲大きい

小さい

ネットワークのノードおよびトポロジの特徴量を推定する研究が注目されている. ネットワークの特徴量の具体例としては，この性質を ready-to-use 性と呼ぶこととする．ready-to-use 性

次数分布やクラスタ係数などが挙げられる．しかし，これらのは，データの使い勝手がいいだけでなく，他人にサンプルノーネットワークの全体情報は一般的に公開されておらず，ネットドデータを配布しやすいといった利点を持つ．これに対し通常ワークの特徴量を推定することは簡単ではない．例えば，ノーのランダムウォークの場合，次数が高いノードに偏ったサンプドを一様独立に選択し直接取得する一様独立サンプリングのよリングが行われるため，サンプル後の特徴量推定時にノードのうな手法を，このようなノード ID が未知のネットワークに適次数の偏りを排除するような重み付け計算を行わなければ正し用することは実現不可能である．現実的には，ソーシャルネッ

い推定を行うことができない．この場合，多次元スケーリング

トワークの API やスクライピングなどを繰り返し使用するこや階層的クラスタリングなど，複雑なデータ分析の場面では適とでサンプリングを行うため，クローリングによるグラフサン用困難といった欠点を持つ [1]．

プリング手法を考える必要がある．この時，ノードのサンプル

MHRW の短所は，通常のランダムウォークに比べて，広範集合に偏りが生じてはいけないため，マルコフ連鎖によって不囲のサンプリングを行うために非常に多くのステップ数が必要偏サンプリングを達成できるランダムウォークベースの手法がとなる点である．MHRW は高次数ノードへの訪問の偏りを無有用だとされている [1]．

くすために受理確率に応じて訪問拒否を行っており，その結果ランダムウォークによる不偏サンプリング手法には 2 つの次数が低いノードに対してサンプルが重複する確率が高く，広代表的な手法が存在する．通常のランダムウォークによって範囲へのサンプリングが遅くなってしまう．ネットワークデーノードをサンプルした後，事後処理を行うことで特徴量を推タの単位時間あたりの取得量に制限があることを考えると，少定する Random Walk Re-Weighting (RWRW) と Metropolis-ないステップ数かつ高い精度でネットワークの特徴量を推定でHastings (MH) アルゴリズムによって一様にノードをサンプルきる方が望ましい．広範囲にノードサンプリングすることで推することで不偏サンプリングを達成する Metropolis-Hastings

定値の分散が小さくなり，高精度の推定を達成できる．本研究

Random Walk (MHRW) である．この 2 手法の関係はトレードの提案手法は，既存の MHRW より広範囲にサンプリングできオフの関係であることが [1] で考察されている．トレードオフるようにすることで推定精度の向上を試みる．の関係を簡単にまとめたのが表 1 である．本論文では MHRW

本論文では，一つ前のサンプルノードには遷移しないといに着目し，MHRW の長所である ready-to-use 性を残しつつ，うルールを MHRW に追加することで，MHRW の長所である短所であるサンプル範囲の狭さを改善した手法を提案する．

ready-to-use 性を保ったまま，MHRW よりも広範囲にサンプリ

MHRW の長所は，定常分布が一様分布であるためサンプルングすることで推定の精度を向上させる手法を提案する．これをしたノードを計算時にそのまま使用することができる点である．

後戻りなし Metropolis-Hastings Random Walk (NBMHRW)

と呼ぶことする．一つ前のサンプルノードには遷移しないことによって，次数が低いノードに何度も留まる可能性を排除している．本論文では，後戻りしないルールを MHRW のアルゴリズムを設計し，MHRW よりも広範囲にサンプリングができていることを実験によって示した．また特徴量の推定の精度の比較実験を行い，良いサンプルノード集合を取得できていること

図 1 ノード v での MHRW の遷移確率を示した．特徴量の推定では ready-to-use 性を保っていることも確認する．最後に付録で，ready-to-use 性が保てていることを数学による証明によって示した．

2. 準

備

本章では，提案手法のベースとなる MHRW について説明する．

図 2 実装上の MHRW の手順

2. 1 定義・前提
本論文ではソーシャルネットワークをグラフ G(V, E) で表す．

V = {v1 , v2 , ..., vn } はノード（頂点）の集合であり，全ノード数を n = |V | とする．E はエッジの集合である．頂点 v ∈ V と隣接def

しているノードの集合を N (v) = {w ∈ V : (v, w) ∈ E} とする．

目標としている一様分布と同じである．しかし，遷移確率を算出するためには，滞在しているノードの次数と全ての隣接ノードの次数を知る必要があるため，クエリ数が膨大に増えてしまう．したがって，実装上では次のような Algorithm1 によって頂点 vi の次数を di または kvi と表すとする．di = kvi = |N (vi )|def ∑nである．全てのノードの次数の総和を D =i=1 di = 2|E| とMHRW の遷移確率による遷移を表現することができる．

する．

Algorithm 1 MHRW

我々は，グラフ G に対して次のような前提を置いて議論を進める．

sample list に now node を追加•

G は重みなしの無向グラフである．

•G は連結グラフである．

•ノード ID のクエリによりそのノードの隣接ノードリス

while 停止条件を満たしていない doトを取得することができる．

•sample list ← 空のリスト
now node ← 最初のノードクローリングによって取得できる情報は，初期ノードとクエリによって得られる情報のみである．

neighbor list ← now node の隣接リスト
next node ← neighbor list から一様ランダムに選択する
p ← 一様分布 U (0, 1) から乱数を生成する
know node
if p <then=knext node

now node ← next node

2. 2 Metropolis-Hastings Random Walk (MHRW)
一般的なランダムウォークによるサンプリング処理の順序は，まず最初のノードを選択し，その後は反復的に処理を行う．反
復的な操作では，滞在しているノードの全ての隣接ノードを取得する．そして決められた遷移確率によって次に遷移するノー

sample list に now node を追加
else
now node に滞在する
sample list に now node を追加
end ifend while

ドを隣接ノードリストから決める．
任意のノードの定常分布が一様分布に収束するように遷移確率を調整したのが MHRW である．Metropolis-Hastings アルゴリズムは，直接サンプルするのが難しい確率分布 µ からサンプルするための一般的なマルコフ連鎖モンテカルロ法 (MCMC)である．今回の場合では，一様分布 µv = |V1 | からノードをサンプルするのが目標である．なぜなら，一様分布でサンプルすることによって ready-to-use 性を保つことができるからである．
これは次のような遷移確率で達成できることが知られている．

1, 1 )kv kw
 min(∑MHMHPv,w =1 − y=v| Pv,y 0MHRW の毎回の反復では図 2 のような処理が行われる．現在ノード v にいる時，隣接ノード w を一様ランダムに選択し，v
受理確率 min(1, kkw) によって受理または拒否を決定し，受理の場合遷移を行う．拒否の場合は，現在のノード v を再びサンプルする．MHRW は現在のノードより次数が小さいノードを選択した場合，必ず受理され遷移する．逆に現在のノードより次数が高いノードを選択した場合，拒否される場合がある．これによって，高次数へのサンプルの偏りを排除している．
しかし，MHRW はランダムウォークに比べてサンプル範囲w ∈ N (v)w=vが小さいという欠点を持つ．なぜなら遷移を拒否する場合，現(1)otherwise

具体的な遷移確率の例を図 1 に示した．
この遷移確率による定常分布は πvM H = |V1 | であり，我々が在滞在しているノードをサンプルするからである．さらに滞在しているノードの次数が低いほど遷移の受理確率が低くなり，何度も同じノードをサンプルする場合が起こりうる．

図 5 ノード v に滞在した後の ノード v での NBMHRW の遷移確率
図 3 始点 ノード w での NBMHRW の遷移確率

図 6 実装上の NBMHRW の手順
図 4 ノード w から遷移した後の ノード v での NBMHRW の遷移確率

Algorithm 2 NBMHRW
sample list ← 空のリスト
now node ← 最初のノード

3. 後戻りなし
Metropolis-Hastings Random Walk
本 章 で は ，提 案 手 法 で あ る NBMHRW に つ い て 述 べ る ．

NBMHRW は一つ前にサンプルしたノードを避けてサンプリングを行うことで，MHRW のサンプル範囲が小さいという欠点を克服した MHRW である．一つ前にサンプルしたノード

sample list に now node を追加
neighborl ist ← now node の隣接リスト
next node ← neighbor list から一様ランダムに選択する
p ← 一様分布 U (0, 1) から乱数を生成する
pre node ← now node
know node
if p <
then=knext node

now node ← next nodeend ifは，必ずすでにサンプルしたことがあるノードであるため，そsample list に now node を追加のノードを避けることによってまだ訪れたことがないノードを

while 停止条件を満たしていない doサンプルする可能性が高くなり，広範囲のサンプリングを実現

neighbor list ← now node の隣接リストしやすくなると予想した．

pre node ← sample list の後ろから 2 番目のノード

3. 1 NBMHRW の遷移確率

while next node == pre node donext node ← neighbor list から一様ランダムに選択する

NBMHRW の遷移確率は基本的には MHRW と同じである．

p ← 一様分布 U (0, 1) から乱数を生成する

違いは，一つ前に訪れたノードを記憶し，MHRW の遷移確率

if p ≧ kknow node thennext node

でそのノードが選択された場合，もう一度 MHRW の遷移確率

next node ← now nodeで選び直す点である．しかし，最初のステップの時は例外であend if

る．なぜなら，最初のステップ時は一つ前のノードが存在しな

end while

いからである．この時は通常の MHRW の遷移確率から次のnow node ← next nodeノードを選択する．
図 3 で最初のステップ時の NBMHRW 遷移確率を示し，図sample list に now node を追加
end while

4 でノード w から遷移した後のノード v での NBMHRW の遷移確率の例を示した．

4. 1 データセット

しかし，MHRW 同様に遷移確率を算出するためには，全てStanford Network Analysis Project (SNAP)（注 1） のデータの隣接ノードの次数を知る必要があるため膨大なクエリ数が必セットで公開されているソーシャルネットワーク・引用ネット

要となり実用的でない．したがって実装上では図 6 のような手ワークを用いて実験を行った．表 2 に各データセットの概要順で次のノードを決定する．そのアルゴリズムを Algorithm2を示す．実用的にグラフサンプリングが行われるケースは，対に示した．

象となるソーシャルネットワークは未知であるが，実験では全4. 実験・評価
本論文では，提案手法を評価するために既存手法であるMHRW との比較を行う．

体像を知っているグラフデータに対して，シミュレーションを行う．

4. 1. 1 Amazon ネットワーク
Amazon Web サイトをクローリングして集められたネットワークである．このネットワークは購入者がどの商品とどの商（注 1）：https://snap.stanford.edu/data/表 2 データセット
ネットワーク

全ノード数 n 平均次数 平均クラスタ係数

Amazon334,863

5.530

0.3967

DBLP

317,080

6.622

0.6324

品が一緒に買われやすいかに注目している．ノードは商品であり，頻繁に一緒に購入される商品（ノード）に対しては無向エッジが張られる．

4. 1. 2 DBLP ネットワーク
DBLP computer science bibliography が提供する，コン

図 7 10000 クエリ当たりの重複ありサンプル数

ピュータ科学の研究論文の共著者ネットワークである．ノードは論文の著者であり，一度でも共著関係になると無向エッジが張られる．

4. 2 実 験 環 境
既存手法と提案手法を Python と NetworkX（注 2） を用いて実装した．本実験は MacBook Pro (Retina, 13-inch，Early2015)，プロセッサ 3.1 GHz Intel Core i7，メモリ 16 GB で行った．

4. 3 実 験 内 容
本論文の実験では，Amazon，DBLP のそれぞれのソーシャル

図 8 10000 クエリ当たりサンプルの固有ノード数

ネットワークに対して，MHRW と提案手法である NBMHRWの 2 手法を用いて 10000 クエリを上限としノード ID のサンプリングを行った．それを 1000 回行い，そのノード ID 集合について分析を行った．始点ノードについては，始点ノード集合を 1000 個一様ランダムに選び，各々のサンプリング手法の始点ノードとした．現実にはネットワークが未知であるため，始点を一様ランダムに選択することは不可能だが，最初の方の十分多くのサンプリングノードを破棄する burn-in を行うことでクローリングでも一様ランダムに始点ノードを選択することは

図 9 平均クラスタ係数推定の正規化平均二乗誤差可能である [1]．
図 7 は 2 手法のサンプル集合の重複ありのサンプル数の平均ことで，2 手法のサンプル集合がグラフ全体の特徴を捉えていを表している．MHRW は 2 クエリで 1 サンプルを取得するたるかどうかと，ready-to-use 性を持っているかどうかを示した．

め，10000 クエリでは半分の 5000 サンプル取得している．一誤差の評価は正規化平均二乗誤差 [3] を用いた．正規化平均二方で NBMHRW は一つ前のノードを選択した場合，拒否を行乗誤差が小さいほど特徴量推定の精度が高く，良いサンプル集

いもう一度サンプルをやり直すため MHRW よりサンプル数が合を集められていることがわかる．結果を見ると，NBMHRW少なくなっていることがわかる．それに対し，図 8 では，2 手の方が正規化平均二乗誤差が小さく，NBMHRW が MHRW よ法のサンプル集合の固有ノード数の平均を表している．つまり，り優位であることがわかる．

この値が大きいほど，広範囲にサンプリングしていると言える．
一般的にサンプル数が大きければ固有ノード数も大きくなるた

5. まとめと今後の課題

め，MHRW の方が固有ノード数が大きくなることが予想され本論文では，後戻りなし Metropolis-Hastings Random Walk

るが，実際は NBMHRW の方が固有ノード数が大きくなってによるソーシャルネットワークのグラフサンプリング手法を提いる．これは，MHRW が同じノードを何度もサンプルしてし案した．既存研究との差分として，ready-to-use 性を保ちつつ，まう可能性が高いのに対し，NBMHRW はまだ訪れていない

広範囲にサンプリングできる手法であることを理論と実験によノードに遷移しやすいためである．結果 NBMHRW の方が広り示した．今回の実験では，平均クラスタ係数という一つの特範囲にサンプリングできていることがわかる．

徴量のみ推定となったが，あらゆる特徴量について実験を行う

図 9 では，2 手法のサンプル集合を用いた，グラフの特徴量推定の誤差を表している．今回は平均クラスタ係数という複雑こと，そして RWRW や他の MHRW の改良手法との比較実験を行うことを今後の課題とする．

ネットワークの密さを表す指標を用いた [2]．この実験を行う
文（注 2）：https://networkx.github.io/

献[1] Minas Gjoka, Maciej Kurant, Carter T Butts, and Athina

[2]

[3]

[4][5]

Markopoulou. Practical recommendations on crawling online social networks. Selected Areas in Communications,
IEEE Journal on, Vol. 29, No. 9, pp. 1872–1892, 2011.
L da F Costa, Francisco A Rodrigues, Gonzalo Travieso, andPaulino Ribeiro Villas Boas. Characterization of complex
networks: A survey of measurements. Advances in Physics,
Vol. 56, No. 1, pp. 167–242, 2007.
Bruno Ribeiro and Don Towsley. Estimating and samplinggraphs with multidimensional random walks. In Proceedings of the 10th ACM SIGCOMM conference on Internet
measurement, pp. 390–403. ACM, 2010.
Galin L Jones, et al. On the markov chain central limit
theorem. Probability surveys, Vol. 1, pp. 299–320, 2004.
Chul-Ho Lee, Xin Xu, and Do Young Eun. Beyond random
walk and metropolis-hastings samplers: why you should not
backtrack for unbiased graph sampling. In ACM SIGMETRICS Performance Evaluation Review, Vol. 40, pp. 319–330. ACM, 2012.

付録

1. 不可逆なマルコフ連鎖の生成
付録では，NBMHRW による不偏サンプリングが MHRW と同じ定常分布で達成できることを数学的証明によって示す．順
序としては，MHRW が可逆性のある既約な有限マルコフ連鎖であることを示し，次に可逆性のある既約な有限マルコフ連鎖から，同じ定常分布 π の非可逆で既約な有限マルコフ連鎖を作ることができることを示す [5]．
扱うネットワークの仮定から，既約性と有限性は自明である．
ここでは MHRW の可逆性を示す．
可逆性を示すためには，詳細釣り合い条件が成立つことを証明すれば良い．つまり，MHMHπv Pv,w= πw Pw,v(v, w ∈ V )であることを示せれば良い．これは MHRW の定常分布がMH
πv M H = |V1 | であることと，式 (1) で紹介した πv Pv,wの定義から容易に証明することができる．ゆえに MHRW は可逆性をが成立つ．ただし Eπ (|f |) < ∞ とする．
この可逆なマルコフ連鎖から，後戻り無しのランダムウォー
ク，つまり同じ定常分布 π の非可逆で既約な有限マルコフ連鎖を作る [5]．

NBRW によるランダムウォークを {Xt′ ∈ V, t = 0, 1...} とす′
る．現在のノードが Xt′ のとき，次のノード Xt+1の決定のさ′れ方は現在のノード Xt′ だけでなく，一つ前のノード Xt−1にも依存する．このため，{Xt′ }t>
自体は V の状態空間ではマ=0ルコフ連鎖になり得ない．したがって，マルコフ連鎖を作れるように次のような状態空間を定義する．

Ω = {(i, j) : i, v ∈ V s.t. P (i, j) > 0}⊂=V × V
def′|Ω| < ∞ であり，Zt′ = (Xt−1, Xt′ ) ∈ Ω (t >= 1) とする．簡単
defに表記するために eij は状態 (i, j) ∈ Ω を表すとする．ただし

eij =| eji である．P′ = {P ′ (eij , elk )}eij ,elk ∈Ω を状態空間 Ω 上
defの既約なマルコフ連鎖 {Zt′ ∈ Ω, t = 1, 2, ...} の遷移確率行列とする．この時定義より P ′ (eij , elk ) = 0 (∀j =| l) ．マルコフ連鎖{Zt′ } の定常分布 π ′ = [π ′ (eij ), eij ∈ Ω] が次のように与えらdefれたとする．

π ′ (eij ) = π(i)P (i, j), eij ∈ Ω
この時元のランダムウォーク {Xt } の可逆性から π ′ (eij ) =π ′ (eji ) である．また，定常状態中のノード j にいる NBRW によるランダムウォーク {Xt′ } の確率は，元の可逆マルコフ連鎖{Xt } の定常分布の π(j) (∀j ∈ V ) と同じである．
∑π ′ (eij ) =i∈V :eij ∈Ω

最初の等号は，P (v, w) = 0, ∀(v, w) ̸∈ Ω によって導かれる．特に任意の関数 f : V → R に対して，もう一つの関数 g : Ω → R，g(eij ) = f (j) としたとき，∑eij ∈Ω

次に，可逆なマルコフ連鎖から非可逆なマルコフ連鎖を生成できることを示す [5]．つまり，後戻りなしのランダムウォーク=

一 般 的 な 可 逆 性 の あ る 既 約 な 有 限 マ ル コ フ 連 鎖 {Xt ∈V, t = 0, 1...} は遷移確率行列 P = {P (i, j)}i,j∈V ，定常分
布 π = [π(i), i ∈ V ] とする．任意の関数 f : V → R に対して次のような推定量を定義する．

1∑µˆt (f ) =f (Xs )t s=1tdef

定常分布 π に関する関数 f の期待値は次のように与えられる．
def

Eπ (f ) =∑π(i)f (i).

i∈V[4] では {Xt } が定常分布 π の有限で既約なマルコフ連鎖であるとき，任意の初期分布 P{X0 = v}, v ∈ V, ( t → ∞) に対してµˆt (f ) → Eπ (f ) almost surely (a.s.)∑g(eij )π ′ (eij ) =∑∑f (i)π(i)P (i, j)j∈V i∈Vf (j)π(j) = Eπ (f )j∈Vにしても特徴量推定の時には同じ定常分布を使用できることを示し，ready-to-use 性を保っていることを証明する．

π(i)P (i, j) = π(j), ∀j ∈ Vi∈VEπ′ (g) =持つ．

∑大数の法則より
tt
1∑
1∑g(Zs′ ) =f (Xs′ ) → Eπ′ (g) = Eπ (f ) a.s.,t s=1t s=1

すなわち，∑t

定量である．

∑t′′s=1 g(Zs )/t =s=1 f (Xs )/t は Eπ (f ) の不偏推