DEIM Forum 2019 D2-5

自己遷移回数を減らした Metropolis-Hastings Random Walk
松村 俊樹†

首藤 一幸†† 東京工業大学 情報理工学院 数理・計算科学系〒 152-8552 東京都目黒区大岡山 2-12-1
あらまし Random Walk（RW）は，インターネットや SNS のような巨大なネットワークに対して有効なサンプリング手法の一つである．単純な RW は次数が高いノードを訪れやすいという特徴を持つのに対し，Metropolis-Hastings

Random Walk（MHRW）は訪れたノードが一様分布に従う ready-to-use 性を持つ．しかし，MHRW は自己遷移の回数が多くクローラーの拡がりが遅いため，十分な精度を確保するために多くのサンプル数を必要とする．本研究では，ready-to-use 性を保ちつつ、MHRW より自己遷移回数が少ない RW を提案する．ready-to-use 性は，MHRW の採択確率と隣接ノードの選択確率を適切に変えることで達成し，自己遷移の回数が MHRW よりも少なくなることを実験により示した．また，現実のネットワークへの適用も考え、コスト面の考察も行った．
キーワード

グラフ理論，グラフサンプリング，Metropolis-Hastings Random Walk

1. は じ め に提案手法は，MHRW の採択確率と隣接ノードの選択確率を適切に変えることで ready-to-use 性を満たすことを証明し，自グラフサンプリングはソーシャルネットワークや交通ネット

己遷移の回数が MHRW よりも少なくなることを 4 つのネット

ワーク等のグラフ構造を成すデータに対するサンプリング手法

ワークによる実験で示した．一方で，提案手法は 2 つ隣のノーである [1]．その手法は大きく分けて，ランダムサンプリングとドの情報を必要とするため，現実のネットワークでは適用し辛クローリングベースのサンプリングの 2 種類がある．ランダム

いという欠点を抱えている．この欠点を解消するために，まだサンプリングは，独立な確率でネットワークからノードやエッ訪問していないノードの次数をそのネットワークの平均次数でジを選択しサンプリングする手法であり，クローリングベース

近似することで，MHRW と同コストを達成した．ネットワーのサンプリングは，隣接しているノードやエッジを選択しサン

クの平均次数は初めの数十%ステップ走らせた MHRW による

プリングする手法である．特にクローリングベースのサンプリ

サンプルから推定し，残りのステップをその平均次数と提案手

ング手法は，セキュリティやプライバシ保護による制限によっ法を用いてサンプルノード列を生成する．平均次数を知るたてランダムサンプリングが難しい場合でも適用することができめの MHRW によるサンプルノード列も一様分布に従うため，るため，盛んに研究されている [2–6]．

MHRW と提案手法によるサンプルノード列を合わせて特徴量グラフサンプリングの目的は，計算の高速化やグラフの可の推定に使うことができる．

視化等多岐にわたるが，特徴量の正確な推定という目的のた

本論文の構成は以下のとおりである．2 章では本研究で用いめに最もよく用いられているのが Random Walk（RW）である言葉の定義や記法について述べ，3 章で我々の提案手法につる．RW は，次点の状態が現在の状態のみによって決まるといいて述べる．4 章では提案手法を現実のネットワークに適用すうマルコフ連鎖の一つであり，各ノードへの訪問割合が定常分る際のコストについて述べ，5 章では MHRW との比較実験を布に収束するという特徴を持つ．最も単純な RW の定常分布

行う．6 章では関連研究について述べ，7 章では本研究の貢献

は，各ノードの次数に比例するため，サンプルノード列が高次と今後の課題を述べる．

数のノードに偏ってしまう．その一方で，Metropolis-Hastings

Random Walk（MHRW）は定常分布が一様分布となるため，
サンプルノード列をそのまま解析した結果の期待値が母集団の特徴量と一致する ready-to-use 性を持つ．MHRW は，単純なRW と同様に隣接ノードを選択した後，ある採択確率によって

2. 準

備

本章では，本論文で扱う記法やグラフの前提について述べる．
また，いくつかの RW のアルゴリズムについて述べる．

2. 1 記法

そのノードに遷移するか，現在のノードに自己遷移するかを決

グラフ構造は，ノードとそれらを繋ぐエッジからなるデータ

める．MHRW は ready-to-use 性というメリットを持つ一方で，構造である．例えば，SNS ではユーザをノード，ユーザ同士の自己遷移によって同一ノードばかりをサンプリングしてしま

友達関係をエッジとし，グラフ構造として解析できる．本論文でい，ある程度の精度を達成するためのステップ数が多くなっては，グラフを G(V, E) で表す．V = {v1 , v2 , ..., vn } はノードのしまったり，遷移候補の次数を知るためのコストが無駄になっ集合で，E = {(vi , vj )|vi , vj ∈ V, i =| j} はエッジの集合である．

たりしてしまうデメリットを持つ．

ノード数 |V | とエッジ数 |E| はそれぞれ n, m とする．ノード

本研究では，MHRW のメリットである ready-to-use 性を保vi と隣接するノードの集合は N (vi ) = {vj ∈ V |(vi , vj ) ∈ E}

ちつつ、MHRW より自己遷移回数が少ない RW を提案する．

と定義し，ノード vi の次数を di = |N (vi )| とする．次数の総（ 2 ） 周期性を持たない（ 3 ） 状態数が有限

表 1 記法のまとめ

G(V, E)

重み無しの無向グラフ

V, E

ノードとエッジの集合

n

ノードの数

vi

G のノードdiD

ノード vi の次数∑n次数の総和
i=1 did平均次数 D/n
ノード vi の隣接ノード

N (vi )RW がエルゴード性を持てば，同時に定常分布 π が存在し，各ノードへの訪問確率はその定常分布へ収束する．例えば，

SRW による t ステップ後の各ノードへの訪問確率の分布 π ′(t)は，事象が起こる確率を P r とすると，π ′(t) = (P r[xt = 1]
，P r[xt = 2]，...，P r[xt = n]) と表すことができる．π ′(t) の i 番′(t)

目の要素を πi′(t)とすると πiは di /D に収束することが知ら

RW の定常分布

れている [7]．D は次数の総和であり定数である．つまり SRWb

サンプリングのコストにおいて各ノードへの訪問確率は次数に比例し，サンプルが高xk

ランダムウォークの k 番目のノードのインデックス

P

RW の遷移確率Q

RW の選択確率

A

RW の採択確率までに必要なステップ数を表す指標として mixing time があ

tmix

mixing time

る [8]．mixing time tmix は以下の式で表される．

π

H P (vi , vj )C P (vi )次数のノードに偏ってしまっている．
また，RW によるサンプルの分布が定常分布へと収束する

ノード vi からノード vj への到達時間

tmix (ϵ) := max{tmix (ϵ, vi )}ノード vi からの全訪問時間

vi′

和を D =′
tmix (ϵ, vi ) := min{|π − ei P t |1 <= ϵ, for all t >
= t}

∑n

i=1 vi とすると，握手の補題より D = 2E が成り立つ．また平均次数を d = D/n と記述する．本論文で扱うグt

ここで，| · |1 は全変動距離と呼ばれ，以下の式で表される．

|π − ej P t |1 :=多重辺を含まないものを仮定する．表記をまとめたものを表 1に示す．

1∑|πi − (ej P t )i |2 i=1n

ラフ G は，連結で重み無しの無向グラフであり，自己ループとtmix (ϵ) のパラメータ ϵ の値は，よく 1/4, 1/8 が用いられる．

2. 2 Random Walk (RW)

mixing time は，到達時間や全訪問時間だけではなく，推定値

グラフサンプリングは，出来るだけ少ないデータでグラフ全の精度の保証にも密接に関係した値であり，RW を比較する際

体の特徴を捉える手法である [1]．巨大で解析に多大のコストに重要な指標である [9–12]．

が掛かるグラフや，セキュリティやプライバシの問題でグラフ•の全トポロジ情報を得られないソーシャルネットワーク等のグ

β-RW は SRW の到達時間と全訪問時間を短くするために考ラフに有効である．グラフサンプリングの手法は大きく分けて，
ランダムサンプリングとクローリングによるサンプリングの 2
種類がある．本章では，クローリングベースのサンプリング手法の 1 つである RW について述べる．

RW は，初期ノードから隣接ノードの１つへ確率的に遷移しβ-Random Walk（β-RW）[13]

案された RW であり，遷移確率は以下のようになる．

d−β

j

 ∑
vj ∈ N (vi )−βvk ∈N (vi ) dk
Pij =




0
otherwiseてサンプルを収集していく手法であり，マルコフ連鎖の 1 つ

β が大きい程低次数のノードへ訪問しやすくなるため，高次である．遷移確率が一様ランダムである最も単純なランダム数のノードに訪問しやすい RW と比較すると，適切に β を定ウォークである Simple Random Walk（SRW）のノード vi かめたときにグラフ全体のノードを満遍なく訪れるようになるこ

らノード vj への遷移確率 Pij は次のように表される．
 1

vj ∈ N (vi )

di
Pij =


0
otherwiseとが期待できる．SRW の到達時間と全訪問時間の期待値が共遷移確率行列 P に従う RW において，ノード vi から出発してノード vj に到達するまでのステップ数の期待値を vi から vjへの到達時間と呼び，H P (vi , vj ) と記述する．また，ノード vi
から出発して全てのノードを訪問するまでのステップ数の期待値を全訪問時間と呼び，C P (vi ) と記述する．到達時間と全訪問時間は，RW の拡がりやすさを表したものであり，比較指標としてよく用いられる．

RW の最大の特徴は，以下に示す 3 つの条件を満たすとき，
エルゴード性を持つことである．
（ 1 ） 任意の状態から他の任意の状態へ到達可能に O(n3 ) であるのに対し，β-RW の到達時間と全訪問時間の期
待値は β = 1/2 のときにそれぞれ O(n2 )，O(n2 log n) を達成することが証明されている．

•

Metropolis-Hastings Random Walk（MHRW）

MHRW は，Metropolis-Hastings（MH）アルゴリズム [14]に基づいた RW であり，サンプルを任意の分布に収束させることができる．ほとんどの場合はサンプルが一様分布に従うものを指す．MHRW の遷移確率は次のように表される．

di
1


· min(1, ) = Qij · Aij vj ∈ N (vi )


d
d

i
j




∑
1−
Pik
i=j
Pij =


vk ∈N (vi )







0
otherwise②採択確率により遷移 or 滞在の決定①遷移候補を一様ランダムに選択

min 1,

1/2

𝑑𝑖
2
=
𝑑𝑗
3

1/2

図 1 MHRW によるサンプリングの例
1 と⃝2 を繰り返すことによってサンプル列を生成する．
⃝

Algorithm 1 MHRW

3. 1 遷 移 確 率

Input: n0 ：初期ノード，b：コスト提案する RW は，MHRW の選択確率を SRW のものから変Output: sample list：サンプル列

更する．それに伴い，付録 1 から ready-to-use 性を満たすよう

v i ← n0
sample list ← {n0 }k←1while k < b do
Choose node vj u.a.r. from N (vi )Generate p ∼ U (0, 1)
diif p <= min(1, d ) thenvi ← vjに採択確率を定める．遷移確率は以下のように表される．

Qij Aij
vj ∈ N (vi )





∑
Pij =
Pik
i=j
1−



vk ∈N (vi )0otherwisejappend vj to sample list
else
append vi to sample list

Q は選択確率，A は採択確率である．MHRW が自己遷移す
るのは，遷移候補として高次数のノードを選択した時であるため，提案手法では低次数のノード程選択されやすくなる選択確

end if率を用いる．自己遷移回数が減少した結果 mixing time の値

k ←k+1が小さくなり，ある程度の精度を保証するステップ数が短くな

end while

る．アルゴリズムは Algorithm 2 に示す．本論文では以下の 2

return sample list

種類の選択確率を検証する．

•

β-MHRW

Q と A はそれぞれ隣接ノードの選択確率と遷移するか留まる

β-MHRW は，MHRW の選択確率を β-RW のものに変更かを決める採択確率であり，Qij = 1/di , Aij = min(1, di /dj )したものである．β は到達時間と全訪問時間が最も小さくなるである．

MHRW は，SWR の遷移確率で隣接ノードを選んだ後，採択確率 A を用いて，遷移するか現在のノードへ自己遷移するか

1/2 を用い，選択確率と採択確率はそれぞれ以下のように表さ
れる．
−1/2

Qij = ∑

を決める．隣接ノードに遷移した場合はそのノードをサンプル−1/2
vk ∈N (vi ) dk

列に加え，自己遷移した場合は現在のノードを再びサンプル列が引き起こす推定精度の悪化や，遷移候補先の次数を取得したにもかかわらず遷移しない場合の追加コストを引き起こす．ア
ルゴリズムは Algorithm 1 に，具体的なサンプリングの流れは
図 1 に示す．

3. 提 案 手 法
MHRW は自己遷移により mixing time が大きくなってしまい，ある精度に達するまでに多くのサンプルを必要としてしまう．本章では，MHRW のメリットである ready-to-use 性を保ちつつ、MHRW より自己遷移回数が少ない RW を提案する．

，

Aij = min(1, Qji /Qij )に加える．自己遷移は MHRW の 1 つの特徴である一方で，同じノードを何度もサンプルすることによる mixing time の増加dj

次数の逆数に比例した β-RW の選択確率を用いることで自己遷移回数の減少が見込まれる．

•

Reselecting MHRW
Reselecting MHRW は，遷移候補を一様に選択した後，もう一度遷移候補を選択し，最終的に次数の小さい方を選択す
る．選択確率と採択確率はそれぞれ以下のように表される．

Qij =2 · #{dj < dk }k∈N (i) + #{dj = dk }k∈N (i)，d2i
Aij = min(1, Qji /Qij )Algorithm 2 提案手法

Algorithm 3 コスト削減提案手法

Input: n0 ：初期ノード，b：コスト

Input: n0 ：初期ノード，b：コスト，ϕ：MHRW の割合

Output: sample list：サンプル列

Output: sample list：サンプル列v i ← n0v i ← n0

sample list ← {n0 }sample list ← {n0 }k←1degree memory ← {n0 }：次数を取得したノードのリスト

while k < b dowhile length(degree memory) < ϕb do

Choose node vj Qij from N (vi )Choose node vj u.a.r. from N (vi )Generate p ∼ U (0, 1)
Qj
if p <) then= min(1,

if degree memory doesn’t contain vj thenvi ← vj

Qi

append vj to sample list
else
append vi to sample list
end ifk ←k+1end while
return sample list

append vj to degree memory
end ifGenerate p ∼ U (0, 1)
diif p <= min(1, ) thenvi ← vj

dj

append vj to sample list
else
append vi to sample list
end ifend while

3. 2 定 常 分 布
提案手法の遷移確率は，いずれの隣接ノードに対しても 0 で

average degree ← sample list 内のノードの次数の平均
while length(degree memory) < b do
Choose node vj Qij （degree memory 内に無いノードの次数はない．また，本研究では対象のグラフを連結無向グラフと仮は average degree として計算） from N (vi )定しているため，任意のノードから他の任意のノードへ到達可

if degree memory doesn’t contain vj then

能である．同様の理由から周期性を持たず，グラフの仮定からノード数が有限であることも明らかである．以上の 3 つの条件から，提案 RW はエルゴード性を持ち，同時に定常分布を持
つ．定常分布は付録 1 より一様分布である．

4. コストの考察

append vj to degree memory
end ifGenerate p ∼ U (0, 1)
Qji
if p <)（degree memory 内に無いノードの次数は= min(1,Qijaverage degree として計算） thenvi ← vj
append vj to sample list

サンプリングする際にはコストを考えることが重要である．

MHRW では，大きく分けて 2 種類のコストの捉え方がある．1
つ目はサンプルサイズをコストとする場合で，2 つ目は次数取得をコストとする場合である．本章では，それぞれがコストとして考えられる際の，提案手法の振る舞いについて述べる．

else
append vi to sample list
end ifend while
return sample list

4. 1 サンプルサイズがコストの場合取得するノード数を一定の数にしたい時や，ノードを保存ででも MHRW よりも提案手法の方が遥かにコストがかかる．提きるメモリに限りがある時に，サンプルサイズをコストとして案手法のコストを MHRW のコストまで減らすためには，2 つサンプリングを行うことが考えられる．提案手法は MHRW よ

隣までのノードの次数を推定する手法が考えられる．ノードのりも自己遷移回数が少ないため，サンプルサイズが同じならば次数が取得済みでメモリに保存されている場合は，コストをか提案手法の方が多くの種類のノードをサンプリングできている

けずに次数を知ることができるが，その他のノードの次数は知と考えられる．

ることができない．そのため本手法では，次数が未取得のノー

4. 2 次数取得がコストの場合

ドの次数を平均次数として提案手法を行う．十分なステップを

MHRW が採択確率を定めるために 1 つ隣のノードの次数を繰り返せば，次数を取得済みのノードが増えていき，サンプル

1 つ用いるのに対し，提案手法では 1 つ隣のノードと 2 つ隣のは一様分布に収束することが見込まれる．しかし，平均次数はノードの次数を全て用いる．SNS やインターネットなどの現実

グラフ全体の情報を知らずに正確に導出はできず，事前情報とのネットワークを考えると，API 制限や通信遅延の問題から，して与えられているとも考えにくい．そこで，コストの一部を

これらのノードの次数を全て得るコストは著しく大きくなると

用いて MHRW でサンプリングをし，そのサンプルを用いて平考えられる．そのため提案手法は，前提によっては全く現実的均次数を推定する．RW による関数 f の不偏推定量は以下のよな手法ではない可能性があり，コスト削減手法を考える必要がうに表される [15]．

ある．
次数の取得がコストとして考えられるとき，同じ 1 ステップ

Eπ (f ) :=

∑
vi ∈V

f (vi )πi(1)

π は RW の 定 常 分 布 で あ り，f : V → R は ノ ー ド を

表2

データセットの概要

引 数 と し て 実 数 を 返 す 関 数 で あ る ．MHRW の 定 常 分 布 は

Networknm

D/n

π = {1/n, ..., 1/n} であることから，(1) 式は以下のように

BA model10, 000

29, 991

5.998

Facebook

4, 03988, 234 43.691

表せる．

Eπ (f ) :=1 ∑f (vi )n v ∈V(2)

DBLP

317, 080 1, 049, 866

6.622

Amazon334, 863

5.530

925, 872if (vi ) = di とおけば，(2) 式は平均次数を表す．このようにして MHRW により平均次数を求める．
その後，その平均次数の推定値を用いてコストを削減した提案手法によるサンプリングを行う．最初の MHRW によるサンプルは ready-to-use 性を満たすため，平均次数を推定するためだけではなく，そのままサンプルとしても用いることができる．
アルゴリズムは Algorithm 3 に示す．
次数取得がコストの時，自己遷移回数の減少によるメリット
がもう一つ生まれる．MHRW は，採択確率を求める際に隣接ングさせたときの自己遷移回数を比べる．各ネットワークについて，総ノード数の 10%ステップ分のサンプリングを行う試行
を 1000 回行い，自己遷移回数の平均をとったものが図 2 である．この結果から，全てのネットワークについて提案手法の自己遷移回数が MHRW のものよりも少なくなっていることがわ
かる．また，提案手法のサンプルが一様分布であることを確かめるために L1 距離を用いる．L1 距離は以下の式で表され，0に近い程観測値の分布が想定した分布に近いことを表す．

ノードの次数を取得する．自己遷移をした場合は，遷移候補の

L1 距離

=

n
∑

|πi − πi′ |次数を取得したのにもかかわらず，そのノードには遷移しない．

i=1

すなわち，次数を取得したがサンプルには含まれていないノーπ は目標とする分布を指し，π ′ は実際に得られたサンプルのドが多く存在する．提案手法は，自己遷移回数を減らしたことによって，このようなコストの無駄を削減することができる．

5. 実

験

分布を指す．
各ネットワークについて，ステップ数に対する L1 距離の値
を 1000 回ずつ求め平均したものをプロットしたものが図 3 である．これを見ると，全てのネットワークで MHRW よりも本章では，提案手法の自己遷移回数が MHRW と比べて少な

常に提案手法の方が L1 距離の値が小さいため，提案手法はくなっていることを，様々なネットワークに対して実験するこ

ready-to-use 性を満たすだけではなく，MHRW よりも一様分とによって確かめる．また，MHRW の選択確率と採択確率を布に近いサンプルが得られていることがわかる．これは，自己変えたことによって提案手法の ready-to-use 性が失われていな

遷移回数を減らしたことによって同一ノードばかりサンプル

いかを確かめる．

するのを避け，クローラーが遠くへ拡がり，より多くの種類のまず初めに，MHRW と提案手法を同ステップだけクローリングさせたときの自己遷移回数を比べ，サンプルの分布が一様

ノードを集められるようになったことが要因だと考えられる．

5. 3 次数取得がコストである場合

分布へ収束することを確認する（5.2 節）．その後，現実のネッ

次に，現実のネットワークへの適用を考えてコストを削減しトワークへの適用を考え，MHRW と提案手法の次数取得コスた提案手法の実験を行う．ここでは，初めてノードの次数を取トを合わせた上で同じ実験を行う（5.3 節）．

得したときにコストがかかるものとする．取得したノードの

5. 1 データセット

次数はメモリに記憶しておく．コストを削減した提案手法で実験には，複雑ネットワークの生成モデルの一つである

は，パラメータ ϕ を用いて初めの何割のコストを平均次数をBarabási-Albert（BA）モデル [16] によるネットワークと，求めるための MHRW に割り当てるかを決める．今回の実験でStanford Network Analysis Project（SNAP）（注 1） のデータ

は，ϕ = 0.1, 0.3, 0.5 のときの自己遷移回数と L1 距離の値をセットで公開されている現実のネットワークのデータセットを

MHRW と比較する．ϕ = 1.0 のときは MHRW となる．図 4

用いる．Facebook は，実際に Facebook の SNS から得られたは，ϕ = 0.1, 0.3, 0.5 のときの自己遷移回数を MHRW と比べ

サブネットワークである．ノードはユーザ，エッジはフォロー関たものである．これを見ると MHRW の割合を減らす程，自己係を表す．DBLP は，DBLP computer science bibliography

遷移回数が減っていることがわかる．また図 5 は，固有ノードが提供する論文の共著関係を表したネットワークである．ノード数を比べたものであり，これを見ると同じコストでも MHRW

は論文の著者，エッジは共著関係を表す．Amazon は，Amazonの割合を減らす程，MHRW より提案手法の方が多くの種類ののウェブサイトをクローリングして得られた共購買ネットワー

ノードをサンプリングできていることがわかる．

クである．ノードは商品，エッジは頻繁に一緒に購入されていその一方で，MHRW の割合を減らすと平均次数の推定精度るかを表す共購買関係を表す．各ネットワークの特徴は表 2 にが悪くなり，提案手法の ready-to-use 性に悪影響を与える可能示す．

性がある．図 6 と図 7 は，各ネットワークについて，総ノード

5. 2 次数取得がコストでない場合

数の 2, 4, 6, 8, 10%コスト毎の L1 距離の値を 1000 回ずつ求まず初めに，MHRW と提案手法を同じステップ数クローリ

め平均しプロットしたものである．これを見ると，β-MHRW
はいずれの ϕ においても，全てのネットワークで MHRW より（注 1）：https://snap.stanford.edu/data/

L1 距離の値が小さいことがわかる．特に ϕ が小さい程，つま

200
100
0

140
120
100
80
60
40
20
0

Reselecting1
2
3
β-MH
MHRW
MH

DBLP

16000
14000
12000
10000
8000
6000
4000
2000
0

Reselecting1
2
3
β-MH
MHRW
MH

Amazon16000

the number of self-loop

300

the number of self-loop

400

Facebook160

the number of self-loop

the number of self-loop

BA model

500

14000

12000
10000
8000
6000
4000

2000
0

Reselecting1
2
3
β-MH
MHRW
MH

Reselecting1
2
3
β-MH
MHRW
MH

図 2 各ネットワークにおける提案手法と MHRW の自己遷移回数（ステップ数は総ノード数の 10%）

1.2
1
0.8
0.6

MHRW
Reselecting-MH
β-MH

1.4

L1 distance

L1 distance

1.6

MHRW
Reselecting-MH
β-MH

1.4

1.2

DBLP

2

1
0.8

0.6

1.8

MHRW
Reselecting-MH
β-MH

1.6

1.4
1.2
1
0.8

1.4

1.2
1
0.8

0.6

0.6

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0

0

0

100000200000 300000 400000

0

40000

80000

12000000

the number of step

the number of step

図3

MHRW
Reselecting-MH
β-MH

1.6

0.4

0

Amazon2
1.8

L1 distance

1.6

Facebook

1.8

L1 distance

BA model1.8

3000000

6000000

900000003000000

6000000

9000000

the number of step

the number of step

各グラフにおける L1 距離の推移（横軸は総ノード数に対するステップ数の割合）

り平均次数を知るための MHRW の割合が小さい程，提案手法が多くのサンプルを集められる．MD の遷移確率は以下で与えのサンプルは一様分布に近い．また，Reselect MHRW につい

られる．










1

ても，L 距離の値は MHRW と同等かそれ以下だと言える．これらは，平均次数の推定精度の悪さが提案手法の ready-to-use
性に与える影響が少ないことを示している．
以上の実験から，提案手法は ready-to-use 性を保ちつつ、

MHRW より自己遷移回数が少ない RW であると言える．さら

Pij =

1
dmax

di
1−

d

max





0

vj ∈ N (vi )i=jotherwiseに次数取得がコストだとしても，コストを削減する手法によって，前述のメリットをほとんど失うことなく MHRW と同コストを達成できることがわかった．

dmax = max{d1 , d2 , ..., dn } である．次数取得がコストの場合
は，MD の L1 距離が MHRW よりも小さくなることが示されている．一方で，その制限された状況下で dmax を知るための6. 関 連 研 究
Lee らは，本研究とは違うアプローチでの MHRW の改良案

コストを考察する必要があると思われる．

7. まとめと今後の課題

として MH algorithm with delayed acceptance (MHDA) を提案している [17]．本研究が MHRW の自己遷移確率を減らした

本研究では，MHRW の選択確率と採択確率を適切に変えるのに対し，MHDA は 1 つ前のノードに遷移する確率を減らしことで，ready-to-use 性を保ちつつ自己遷移回数の少ない RWている．遷移候補として 1 つ前のノードを選択してしまった場を提案した．提案手法は，次数が低いノード程遷移候補とし合，ある確率でもう一度遷移候補を選択しなおす．MHDA のて選ばれやすくなるような選択確率を用いることで，MHRW

自己遷移確率は MHRW のものと等しいため，本研究の手法とよりも少ない自己遷移回数を達成した．また，MH アルゴリ

組み合わせることでより拡がりの良い RW を作ることができる

ズムから定常分布が一様分布となるような採択確率を定め，と思われる．

ready-to-use 性も達成した．

Chierichetti らは，MHRW と比べて自己遷移回数が多くな選択確率と採択確率を定めるために，MHRW は隣のノード

る Maximum-degree sampling (MD) を提案した [18]．次数取を 1 つ，提案手法は 2 つ隣のノードの次数を全て用いるため，得がコストである場合，同じノードは何度もサンプリングしてSNS やインターネット等の現実のネットワークでは同等のコ

も 1 コストであるため，同コストならば自己遷移回数が多い方ストだとは言えない．そこでコストを合わせるため，まだ次数を取得していないノードの次数を平均次数として，選択確率と

1000
800
600
400
200
0

Facebook

500

β-MH

Reselecting-MH

400
300
200
100
0

MHRW
1
2
3
4
φ=0.3
φ=0.5
φ=0.1

DBLP

80000

β-MH

60000
40000
20000
0

MHRW

Amazon

60000

β-MH

Reselecting-MH

50000
40000
30000
20000
10000
0

MHRW

MHRW

1
2
3
4
φ=0.1
φ=0.3
φ=0.5
（φ=1.0）

1
2
3
4
φ=0.3
φ=0.5
φ=0.1
（φ=1.0）（φ=1.0）Reselecting-MH

the number of self-loop

Reselecting-MH

the number of self-loop

the number of self-loop

β-MH

the number of self-loop

BA model

1200

1
2
3
4
φ=0.3
φ=0.5
φ=0.1
（φ=1.0）

図 4 各ネットワークにおける提案手法と MHRW の自己遷移回数

Reselecting-MH

840
820
800
780
760
7400

MHRW

1
2
3
4
φ=0.3
φ=0.5
φ=0.1
（φ=1.0）Facebook

360

β-MH

Reselecting-MH

340
320
300
280
2600

MHRW

1
2
3
4
φ=0.3
φ=0.5
φ=0.1
（φ=1.0）

DBLP

27000

β-MH

Reselecting-MH

26800

26600
26400
26200
26000
0

MHRW

1
2
3
4
φ=0.3
φ=0.5
φ=0.1
（φ=1.0）the number of unique nodeβ-MH

the number of unique node

BA model860

the number of unique node

the number of unique node

（コストは総ノード数の 10%）

Amazon

27400

β-MH

Reselect-MH

27200
27000
26800

26600
26400
262000

MHRW

1
2
3
4
φ=0.3
φ=0.5
φ=0.1
（φ=1.0）

図 5 各ネットワークにおける提案手法と MHRW の固有ノード数（コストは総ノード数の 10%）

1.88
MHRW (φ=1.0)
φ=0.5
φ=0.3
φ=0.1

1.84

1.92

1.88
MHRW (φ=1.0)
φ=0.5
φ=0.3
φ=0.1

1.84

1.8

42

63

84

1.92
1.88
MHRW (φ=1.0)
φ=0.5
φ=0.3
φ=0.1

1.92
1.88

42

36

48

1.8
21

10 5 (%)

24

36

48

21

105 (%)

Percentage of cost to n

Percentage of cost to n

Percentage of cost to n

MHRW (φ=1.0)
φ=0.5
φ=0.3
φ=0.1

1.84

1.8

21

105 (%)

1.96

1.84

1.8

21

Amazon2

1.96

L1 distance

1.92

DBLP

2

1.96

L1 distance

1.96

L1 distance

Facebook

2

L1 distance

BA model

2

42

36

48

105 (%)

Percentage of cost to n

図 6 各グラフにおける MHRW と β-MHRW の L1 距離の推移（横軸は総ノード数に対する次数取得コストの割合）

1.85
MHRW (φ=1.0)
φ=0.5
φ=0.3
φ=0.1

1.8

21

1.9
1.85
1.8
1.75

42

63

MHRW (φ=1.0)
φ=0.5
φ=0.3
φ=0.1

48

Percentage of cost to n

105 (%)

21

42

36

1.96

1.92

1.92

1.88

1.88

MHRW(φ=1.0)
φ=0.5
φ=0.3
φ=0.1

1.84

48

Percentage of cost to n

10 5 (%)

Amazon2

1.96

L1 distance

1.9

DBLP

2

1.95

L1 distance

L1 distance

1.95

1.75

Facebook

2

L1 distance

BA model2

MHRW(φ=1.0)
φ=0.5
φ=0.3
φ=0.1

1.84

1.8

1.8

21

42

36

48

105 (%)

Percentage of cost to n

図 7 各グラフにおける MHRW と Reselecting MHRW の L1 距離の推移（横軸は総ノード数に対する次数取得コストの割合）

21

42

36

48

Percentage of cost to n

105 (%)

採択確率を定める方法を考案した．平均次数は，事前情報として与えられている状況はほとんどないと考えられるため，数十%のコストをかけて MHRW を走らせ推定し，残りのコストで提案手法を行う．この方法によって提案手法のコストを MHRWと同等まで削減した．
実験では，提案手法と MHRW の自己遷移回数と ready-to-use 性を 4 つのネットワークで比較した．それぞれの集めたサン
プルサイズをそろえた実験では，自己遷移回数と ready-to-use
性を表す指標の 1 つである L1 距離は共に，提案手法のほうが良い結果であった．また，コストを削減した提案手法と MHRWの比較も行った．コストを削減した提案手法は，初めの 10, 30,

50%を平均次数を知るためのコストとし，それぞれ自己遷移回
数と L1 距離の値を観察した．実験の結果から，コストをそろえた実験においても，提案手法の方が自己遷移回数が少なく，サンプルがより一様分布に近い手法であることを示した．
今回は，隣接ノードの選択確率を 2 つ用いたが，他にも選択
確率は考えられる．次数が小さい程選択されやすくなる選択確率であれば，自己遷移回数は MHRW よりも少なくなると考えられるため，よりよい選択確率を求めることが今後の目標と
なる．

謝

辞

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

[11] Jian Ding, James R Lee, and Yuval Peres. Cover times,
blanket times, and majorizing measures. In Proceedings ofthe forty-third annual ACM symposium on Theory of computing, pp. 61–70. ACM, 2011.
[12] Kai-Min Chung, Henry Lam, Zhenming Liu, and Michael
Mitzenmacher.
Chernoﬀ-hoeﬀding bounds for markov
chains: Generalized and simplified.
arXiv preprint
arXiv:1201.0559, 2012.
[13] Satoshi Ikeda, Izumi Kubo, and Masafumi Yamashita. The
hitting and cover times of random walks on finite graphs using local degree information. Theoretical Computer Science,Vol. 410, No. 1, pp. 94–100, 2009.
[14] Nicholas Metropolis, Arianna W Rosenbluth, Marshall N
Rosenbluth, Augusta H Teller, and Edward Teller. Equation of state calculations by fast computing machines. The
journal of chemical physics, Vol. 21, No. 6, pp. 1087–1092,
1953.
[15] Rong-Hua Li, Jeﬀrey Xu Yu, Lu Qin, Rui Mao, and Tan Jin.
On random walk based graph sampling. In 2015 IEEE 31st
International Conference on Data Engineering (ICDE), pp.
927–938. IEEE, 2015.
[16] Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics,
Vol. 74, No. 1, p. 47, 2002.
[17] 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.
[18] Flavio Chiericetti, Anirban Dasgupta, Ravi Kumar, Silvio Lattanzi, and Tamás Sarlós. On sampling nodes in a
network. In Proceedings of the 25th International Conference on World Wide Web, pp. 471–481. International World
Wide Web Conferences Steering Committee, 2016.

付
文

献[1] Pili Hu and Wing Cheong Lau. A survey and taxonomy ofgraph sampling. arXiv preprint arXiv:1308.5865, 2013.
[2] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos.
Graphs over time: densification laws, shrinking diametersand possible explanations. In Proceedings of the eleventh
ACM SIGKDD international conference on Knowledge discovery in data mining, pp. 177–187. ACM, 2005.
[3] 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.
[4] Leo A Goodman. Snowball sampling. The annals of mathematical statistics, pp. 148–170, 1961.
[5] Douglas D Heckathorn. Respondent-driven sampling: a new
approach to the study of hidden populations. Social problems, Vol. 44, No. 2, pp. 174–199, 1997.
[6] Matthew J Salganik and Douglas D Heckathorn. Sampling
and estimation in hidden populations using respondentdriven sampling. Sociological methodology, Vol. 34, No. 1,
pp. 193–240, 2004.
[7] David Aldous and Jim Fill. Reversible markov chains andrandom walks on graphs, 2002.
[8] David A Levin and Yuval Peres. Markov chains and mixing
times, Vol. 107. American Mathematical Soc., 2017.
[9] Yuval Peres and Perla Sousi. Mixing times are hitting timesof large sets. Journal of Theoretical Probability, Vol. 28,
No. 2, pp. 488–519, 2015.
[10] Roberto Oliveira, et al. Mixing and hitting times for finite
markov chains. Electronic Journal of Probability, Vol. 17, ,
2012.

録

1. MH アルゴリズム
ここでは，MH アルゴリズムから提案手法の採択確率をどのように定めたのかについて述べる．MH アルゴリズムは，マルコフ連鎖モンテカルロ法 (Markov chain Monte Carlo methods;

MCMC 法) の代表的な一つであり，いかなる確率分布からもサンプル列を構成することが目的である．この目的を達成する
ために，唯一の定常分布 π を持つマルコフ連鎖を用いる．定常分布を持つこととその唯一性は，エルゴ―ド性と以下の詳細つ
り合い条件を満たすことで保証される．

πi Pij = πj Pji(A·1)

定常分布が一様分布であることを目指すとき，(A-1) 式は

Pij = Pji となる．ここで，遷移確率 P を選択確率 Q と採択確率 A に分解する．Pij = Qij Aij である．このとき，(A-1) 式から以下の式を得る．

Aij
Qji
=
Aji
Qij

(A·2)

Aij = min(1, Qji /Qij ) とすると，これは (A-2) 式を満たす．これを Metropolis choice と呼ぶ．Qij = 1/di とすると

MHRW の遷移確率が得られる．提案手法は Q を β-RW の選
択確率，A を Metropolis choice による採択確率とすることで，ready-to-use 性を満たすことが保証される．