DEIM Forum 2016 D2-7

ソーシャルグラフ向けクラスタ係数推定手法の効率化
岩崎

謙汰†

華井

雅俊††

首藤 一幸††† 東京工業大学 理学部 情報科学科†† 東京工業大学 大学院情報理工学研究科 数理・計算科学専攻〒 152-8552 東京都目黒区大岡山 2-12-1-W8-43
E-mail: †iwasaki.k.ah@m.titech.ac.jp
あらましソーシャルネットワーク全体の特徴はクラスタ係数といった指標で表すことができる．現実のソーシャル

ネットワークサービスでは，グラフ全体を入手することは現実的ではないため，オンラインでサンプリングした一部分から指標を算出する他ない．オンラインでのサンプリングでは，頂点や辺の収集はグラフをクロールして行うこととなる．特にクラスタ係数の推定ではランダムウォークベースの手法が有効である．現在最も精度が高いクラスタ係数推定手法は，Hardiman らが提案した Simple random walk (SRW) を利用した手法である．しかし SRW では一つ前のノード戻る遷移が精度を下げる原因となる．本研究では既存手法の問題点に着目し，一つ前のノードに戻らないラ
ンダムウォーク Non-backtracking random walk (NBRW) を利用したクラスタ係数推定手法を提案した．そして実験により提案手法が既存手法より効率的かつ高精度であることを示した．
キーワード

ソーシャルネットワーク，グラフサンプリング，クラスタ係数
立に選択しサンプリングする手法は現実的ではない [7]．した

1. は じ め にがって隣接ノードの情報を元にノードの隣接関係を辿っていく

ソーシャルネットワークの利用者は増加を続け，例えば Face（注 1）

クローリングによるグラフサンプリング手法を考える必要があ．利用者が増えるに従い，

る [6, 8]．現実のソーシャルネットワークでも，幅優先サンプリ

ソーシャルネットワークをグラフ構造として分析することの関

ング (BFS) やランダムウォークなどのクローリングによるグ心が高まっている．例えばユーザをノード，ユーザの友達関係

ラフサンプリング手法が実際に使われている [1–3, 9–11]．

book の利用者は 10 億人に達したをエッジとするグラフが考えられる．

我々が知る限り，グラフサンプリングによるクラスタ係数推ソーシャルネットワークの分析において，複雑ネットワーク

定手法で最も効率的かつ高精度な手法は Hardiman ら [12] が提の特徴の一つであるグラフのクラスタ係数は重要な指標の一つ

案した Simple random walk (SRW) を行いながら三角形を数えである．クラスタ係数は特定の一つのノードに対して定義できる手法である [13]．しかし，SRW は一つ前に訪問したノードる値であり，隣接ノード間に辺が張られている割合によって表に遷移する可能性があるため，三角形を数える計算に無駄が生される指標である．グラフの全ノードのクラスタ係数の平均がじ推定精度を下げる原因となる．したがって一つ前に訪問した

高いほどそのネットワークは密であると言える．クラスタ係数

ノードに戻らないランダムウォークである Non-backtracking

はネットワークの分析に盛んに使用されている [1–3]．

random walk (NBRW) によって三角形を数える手法が有効で

しかし大規模なソーシャルネットワークに対して，計算量のあると考えられる．また NBRW はその性質から SRW よりも問題から平均クラスタ係数を厳密に計算することは困難である．

一定のノード数をサンプルするのに必要なステップ数が少なく

具体的には頂点数 n に対して O(n3 ) の計算量 [4] がかかる．そなることが期待できる．

のため，グラフの全体から一部分のノードとエッジを取得し特

本研究は NBRW をしながら三角形を数えるクラスタ係数推徴を抽出するグラフサンプリングによってクラスタ係数を推定定手法を提案した．そして実験結果から既存手法より効率的かする手法が盛んに研究されてきた．

つ高精度なクラスタ係数推定手法であることを示した．

ソーシャルネットワークに対するグラフサンプリング手法を

本論文の構成は以下の通りである．2 章では関連研究を紹介考える場合には，グラフデータを保有する企業がプライバシー

する．3 章では本論文で使用する表記や数式の定義，サンプリに関する規律や法律を定めているため，ネットワークのトポロ

ング手法の紹介を行う．4 章では我々の提案手法を述べる．5 章

ジ情報が事前に与えられないことがあることを考慮しなければでは提案手法の評価実験を行う．6 章では本研究のまとめと今ならない．同様の理由でネットワークの全ての情報にアクセス

後の課題について述べる．

することもできない．例えばネットワークの全体のノード数すら事前に知ることができないソーシャルネットワークがほとんどである [5]．それゆえ [6] で紹介されている，ノードを一様独

2. 背

景

本章では，既存のクローリングによるサンプリング手法とク
ラスタ係数推定手法について述べる．

（注 1）：http://www.adweek.com/socialtimes/3q-2014-earnings/438899

2. 1 クローリングによるサンプリング手法
クローリングによるグラフサンプリング手法は大きく分けてに 2 種類に分類できる．走査ベースによるサンプリング手
法 [6, 8, 14] とランダムウォークベースによるサンプリング手
法 [15, 16] である．

2. 1. 1 走査ベースのグラフサンプリング
走 査 ベ ー ス の サ ン プ リ ン グ 手 法 は ，幅 優 先 サ ン プ リ ン
グ (BFS) ，深さ優先サンプリング (DFS) ，などが挙げられる．特に BFS は基礎的であり最も広く使われている手法である [1–3]．一つの理由として，BFS はグラフの特定の部分を全
図 1 エゴネットワークて収集してくれる点にある．しかし，BFS は次数が高いノードに収集が偏りやすいことがわかっている [17]．さらに，どのよ
うに収集するノードの偏るのか分析できないため，クラスタ係

つエッジの情報が必要なためである [2]．したがってランダム数や次数分布などのグラフの構造的特徴を求める場合には不向ウォークのステップ数以上の情報が必要となり，取得情報量がきである [5, 18]．

制限されているソーシャルネットワークの条件下では推定精度

2. 1. 2 ランダムウォークベースのグラフサンプリングが低下する．例えば図 1 を見ると，ランダムウォークによってランダムウォークとは，まず最初に一つもしくは複数のノーのみ見えている情報はノードが 2 個エッジが 5 本だが，エゴドを恣意的に選択し，現在いるノードから隣接しているノード

ネットワークの範囲も含めると見えている情報はノードが 4 個に対して確率的に一つのノードを選択し次のノードとして移動

エッジが 7 本と増えているのが分かる．

する動作を繰り返すことによってノードを収集する手法のこと

これに対し Hardiman ら [12] は SRW によるノードの収集である．次のノードを選ぶ時に一様ランダムに選択するランダを行った後，エゴネットワークの情報を使用せずにクラスタ係

ムウォークを Simple random walk (SRW) と呼ぶ．SRW は最数を推定する手法を提案した．この手法はランダムウォークをも基本的なランダムウォークである．SRW は BFS 同様次数がしながら 1 ステップ前と 1 ステップ後のノードが繋がってる場

高いノードに収集が偏りやすいサンプリング手法である．しか合の数をカウントする．つまり三角形を数えることでクラスタ

しマルコフ連鎖による解析から，ノードの訪問確率はそのノー係数を推定する手法である．しかし，SRW では次のノードにドの次数に比例することが解明されている [19]．それに対し移動する時に一つ前に訪問したノードに遷移する可能性があり，Metropolis-Hasting (MH) [20] アルゴリズムを使用し，定常分

その場合三角形を数えることにおいて無駄なステップを踏むこ

布が一様分布になるようにノード選択の確率を調整したランダとになる．また同様の理由で訪問するノードの範囲が狭まり，

ムウォークが Metropolis-Hasting random walk (MHRW) で偏ったサンプリング結果を引き起こす可能性がある．

ある．MHRW は一様にサンプリングするので理想的と思える

第 6 章では，我々の NBRW による提案手法と Hardiman

が，ノード遷移を行う時に次数が高いノードを選択した場合はら [12] のクラスタ係数推定手法を比較する．Ribeiro ら [22]

遷移を拒否する可能性があり，SRW より多くのグラフ情報をの手法と Gjoka ら [2] の手法との比較は [12] の論文により，取得しなければならないという欠点がある [21] [13]．

Hardiman ら [12] の手法の方が精度が高いことが判明している

Non-backtracking random walk (NBRW) は次のノードに遷移する時に，一つ前に訪問したノード以外の隣接ノードから一様ランダムにノードを選択するランダムウォークである．NBRW

ため，本論文では比較しない．

3. 準

備

は一つ前のステップのノードに遷移確率が依存するため，ノー本章では，数式やグラフの表現の定義と本論文で使用するサ

ドの状態空間ではマルコフ連鎖ではない．しかしエッジの状態

ンプリング手法について述べる．この章に記した定義は表 1 に空間とするとマルコフ連鎖を作ることができるため，NBRW

まとめた．

による推定手法が可能となる [21]．その定常分布は SRW と同

3. 1 表じである．また NBRW による推定は SRW による推定より分

本論文ではネットワークを無向グラフ G(V, E) で表す．グラ散が小さくなる [21]．

記

フ G はセルフループが存在しない，エッジは重みを持たない，

2. 2 クラスタ係数推定手法

多重辺を持たないと仮定する．V = {v1 , v2 , ..., vn } はノード

クローリングによるクラスタ係数推定手法は [2, 22] で提案（頂点）の集合であり，全ノード数を n = |V | とする．E はエッされている．Ribeiro ら [22] は SRW によるノード収集を行い，ジの集合である．頂点 v ∈ V と隣接しているノードの集合を

Gjoka ら [2] は MHRW によるノード収集を行う手法を提案しN (v) = {w ∈ V : (v, w) ∈ E} とする．頂点 vi の次数を diた．これらの手法はノード収集を行った後にクラスタ係数を推定するためにさらにエゴネットワークにあたるノードとエッジ

または kvi と表すとする．di = kvi = |N (vi )| である．全てのdef ∑nノードの次数の総和を D =i=1 di = 2|E| とする．グラフも収集する必要がある．これは一つのノードに対するクラス

G の n × n 隣接行列を A とする．すなわちノード vi と vk の間タ係数を求めるために，隣接ノードに加えて隣接ノードが持にエッジが存在すれば Ai,k = Ak,i = 1 であり，エッジが存在

def

しなければ Ai,k = Ak,i = 0 である．
［定義 3.1］ 3 つのノードの組 (vj , vi , vk ) に対して，j < k のとき vj と vi ，vi と vk 間のエッジが存在することを「(vj , vi , vk ) は連結」と定義する．隣接行列で表すと j < k の時 Aj,i = 1, Ai,k = 1
である．
［定義 3.2］ 3 つのノードの組 (vj , vi , vk ) に対して (vj , vi , vk ) が

図 2 SRW の遷移確率

連結していて，vj と vk の間にエッジが存在する時，「(vj , vi , vk ) は三角形」と定義する．隣接行列で表すと Aj,k = 1 である．

3 つノードの組 (vj , vi , vk ) が連結であるとは Aj,i Ai,k = 1(j <k) と同義である．3 つノードの組 (vj , vi , vk ) が三角形であるとは Ai,j Ai,k Aj,k = 1 (j < k) と同義である．特定のノード vi に対∑して連結している (vj , vi , vk ) の数は j<k Aj,i Ai,k と表すこと∑ができ， j<k Aj,i Ai,k = di (di − 1)/2 である．特定のノード vi
def ∑を含む (vj , vi , vk ) の三角形の数を li =j<k Ai,j Ai,k Aj,k と定義する．これは vi の隣接ノード間のエッジの数に等しい．

図 3 ノード v からノード w へ遷移した直後の NBRW の遷移確率

π = (Pr[xr = 1], Pr[xr = 2], ..., Pr[xr = n])
十 分 多 く ラ ン ダ ム ウォー ク の ス テップ 数 を 重 ね た 後 の 確

3. 2 クラスタ係数［定義 3.3］ vi に対するクラスタ係数 [23] を ci と表し

率 P r[xr = i] をπ(i) と定義し，SRWの場合π(i) = di /D に収束する [19]．ベクトル π = (π(1), π(2), ..., π(n)) はグラフ G の



 0
ci =




定常分布と呼ばれる．SRWでは次数が高いノードに訪れやすい

di = 0 または di = 12li

di (di − 1)ci ∈ [0, 1]
otherwise．例えば他のノードに比べて次数が 2 倍のノードは訪れる確率
も 2 倍になる．

3. 3. 2 Non-backtracking random walk(NBRW)と す る ．こ れ は 連 結 し て い る (vj , vi , vk ) の 数 に 対 する (vj , vi , vk ) の三角形の数の割合を意味する．

R′ = (x1 , x2 , ..., xr ) を NBRW によって訪れたノードのイ
ンデックスの列とする．NBRW は次のノードを選択する時に一様ランダムに一つ選択する点は SRW と同じだが，一つ［定義 3.4］ 平均クラスタ係数を C と表し

1∑
ci
n i=1
n

C=

前に訪れたノードを選択しないのが特徴である．すなわち

xt+1 =| xt−1 (t >= 1) を満たす．ただし現在いるのノード v に対して次数 kv =1 の場合は一つ前のノードしか遷移先がないた
め，例外となる．また最初のノードから次のノードを選択すると定義する．本研究で推定するのはこのグラフの平均クラスタ係数である．

時は，一つ前のノードが存在しないため 1/dx1 の確率で遷移す
る．SRW と NBRW の遷移確率の違いを図 2 図 3 に示した．

3. 3 グラフサンプリング手法
本論文の実験のために実装したランダムウォークベースのグ
ラフサンプリングアルゴリズムを二つ紹介する．

3. 3. 1 Simple random walkR = (x1 , x2 , ..., xr ) を SRW によって訪れたノードのイン

3. 4 Hardiman らのクラスタ係数推定手法
Hardiman ら [12] は SRW をしながら三角形の数えるクラス
タ係数推定手法を提案した．その概要について述べる．

SRW によるランダムウォーク R = (x1 , x2 , ..., xr ) に対して新しい変数 ϕk を定義する．

デックスの列とする．r は合計ステップ回数である．最初にランダムに選ばれたノード vx1 からスタートし，隣接ノード
から一様ランダムに一つノードを選択し移動する．これを繰り返す．SRW は既約なマルコフ連鎖である．遷移確率行列を

P = {P (v, w)}v,w∈V とすると P (v, w) は{P (v, w) =def

ϕk = Axk−1 Axk+1 (2 <= r − 1).
= ∀k <(1)

ランダムウォークの k − 1 ステップ目のノードと k + 1 ステッ
プ目のノード間にエッジが存在する場合 ϕk = 1 となり，存在しない場合は 0 となる．例えば図 4 のように x1 , x2 , x3 , x4 の

1kv

w ∈ N (v)

順番にランダムウォークした場合，x2 の前後である x1 と x3 は0otherwise

隣接しているので ϕ2 = 1．x3 の前後である x2 と x4 は隣接していないので ϕ3 = 0 となる．これはランダムウォークしながと表される．事象 A が起きる確率を Pr[A] と表すとすると，r回ステップ後の SRW による分布は次のように表すことができる．

ら三角形を数えることになる．そしてクラスタ係数の推定値を次のように定義する．ステップ数を r として

(3)(4) の式の分子の 2li は (vj , vi , vk ) の三角形の数とそれを反転させた (vk , vi , vj ) の数を足した数である．それぞれの分母は連結している (vj , vi , vk ) の数のうち (xk−1 , vi , xk+1 ) が選ばれる場合の数である．NBRW は一つ前のノードに戻らない分だ
け出て行く場合の数が di − 1 となっている．また ϕ′k の期待値
は vxk のクラスタ係数の ci と一致するため，SRW より精度が良くなると予想できる．
続いてネットワークのクラスタ係数 C を推定するために次の二つの変数を導入する．

図 4 ϕk の計算例

1

∑r−1

k=2 ϕk /(dxk − 1)r

1 ∑ ′ 1
ϕk
r−2
dxk
r−1

Ĉ = r−2 1 ∑r

(2)

k=1 1/dxk

Φ =

k=2

n
1∑ 1
Ψ =
.
r
dxk

とした．

k=1

表 1 定義のまとめ

G

無向グラフ

n

グラフのノード数A

G の隣接行列そして推定値 Ĉ を次のように定義する．

vi

G のノードN (v)ノード v の隣接ノードの集合

di

ノード vi の次数D

全てのノードの次数の総和

Φ
Ψ

def

Ĉ =

推定値がステップ数を増やしていくと真値のクラスタ係数 Cに収束することを示す．大数の法則より期待値と真値が一致す∑nることを示せば良い．

i=1 dir

ランダムウォークの全ステップ数

Φ の期待値は

xk

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

SRW によるランダムウォーク

E[Φ] = E[ϕ′kR′

NBRW によるランダムウォーク

π

定常分布

li

vi の隣接ノード間のエッジの数

ci

ノード vi に対するクラスタ係数

C

ネットワークのクラスタ係数

Ĉ

C の推定量

=

n
∑

1
]
dxk

π ′ (i)E[ϕk | xk = i]

i=1

=

n
∑
di

D
i=1

ci

1
.
di

1 ∑
ci
D i=1
n

=

4. 提 案 手 法となり，Ψ の期待値は既存手法の Hardiman ら [12] では SRW を使用してクラス

E[Ψ] = E[

タ係数を推定する．しかし SRW ではひとつ前のノードに戻る=

場合無駄が生じる．提案手法では三角形の数えるアイデアと=数推定の精度の向上を目指した．本章では，提案手法の概要に=した．

NBRW によるランダムウォーク R (x1 , x2 , ..., xr ) に対して新しい変数 ϕ′k を定義する．

n
∑
di 1

D di

1
di
.

n
D

def

E[Φ]
1∑
ci =
n i=1
E[Ψ]
n

C=

ϕ′k = Axk−1 Axk+1 (2 <= r − 1).
= ∀k <(5)

ここで π ′ は NBRW の定常分布であるが [21] より，π ′ (i) =これは式 (1) と同じ定義である．違いは SRW か NBRW による
ものかである．次に ϕk とϕ′k の vxk = vi の時の期待値を求める．

2li
= ci
di (di − 1)

π ′ (i)従って，′

E[ϕ′k | xk = i] =

n
∑

i=1

ついて述べる．また，実装のアルゴリズムを Algorithm1 に示

4. 1 クラスタ係数推定

1
]
dxk

i=1

NBRW を組み合わせた新しい推定手法を提案し，クラスタ係

2li
E[ϕk | xk = i] = 2
di

1
di

(3)
(4)

π(i) = di /D であることがわかっている．この証明は付録 1.
に示した．(5) より推定値 Ĉ が真値 C に収束することが示された．

5. 実験・評価
提案手法のクラスタ係数推定の精度を評価するために，複数Algorithm 1 提案手法

トワークである．このネットワークは購入者がどの商品とどのRequire: 無向グラフ G(V, E), ステップ数 r

商品が一緒に買われやすいかに注目している．ノードは商品でEnsure: グラフ G のクラスタ係数の近似値あり，頻繁に一緒に購入される商品（ノード）に対しては無向v ← 最初のノード

エッジが張られる．

w1 ← v

5. 1. 2 DBLP ネットワーク

i←1

Dblp computer science bibliography （注 2） が提供する，コン

t1 ← 0t2 ← 1/kv

ピュータ科学の研究論文の共著者ネットワークである．ノード

while i < r do

は論文の著者であり，一度でも共著関係になると無向エッジがv の隣接ノードから一様ランダムにノード w を選ぶ
if i == 1 then

張られる．

5. 1. 3 Gowalla ネットワークv←w

Gowalla は位置情報サービスを利用したソーシャルネット

i←i+1

ワーク Web サイトで，ユーザはチェックインを行うことで自分

wi ← v

がいる場所を共有する．公開 API によって友達関係のネット

t2 ← t2 + 1/kv

ワークを集めることができる．しかし 2016 年 1 月 20 日現在

else

サービスは終了している．

if kv <
| wi−1 then
= 1 or w =v←w

5. 1. 4 LiveJournal ネットワーク

i←i+1

LiveJournal（注 3） は他のユーザと友達関係を持つことができwi ← v
if i >= 3 then

るオンラインブログコミュニティである．

5. 2 実 験 環 境

if wi−2 ∈ N (wi ) then

既存手法と提案手法を Python と NetworkX（注 4） を用いて

t1 ← t1 + 1/kwi−1

実装した．本実験は MacBook Pro (Retina, 13-inch，Early

end ifend if2015)，プロセッサ 3.1 GHz Intel Core i7，メモリ 16 GB で

t2 ← t2 + 1/kv

行った．

5. 3 実 験 内 容else
ノード v に滞在する与えられたグラフに対して既存手法と提案手法を適用し誤差

end ifを計測する．既存手法には Hardiman ら [12] の SRW による手

end if法を与える．他の手法と比較しないのは [12, 13] より，他の既end while

存の手法より優れていることが実験によりすでに示されている

t1 ← t1/(r − 2)からである．

t2 ← t2/r

まず予備実験として，既存手法と提案手法で 10000 ノードサ

return t1/t2

ンプルするのに必要なステップ数を計測し，10 回測定した平均のネットワークに対して既存手法と提案手法で計算機実験を行った．ここでの既存手法とは，Hardiman らが提案した SRW
によるクラスタ係数推定手法である．

値を求めた．その結果を表 3 に記した．
続いて誤差についての実験について説明する．10000 ノー
ドサンプルするまでランダムウォークを続けさせ，各手法のクラスタ係数推定値を 1000 回測定し，その正規化平均二乗誤

5. 1 データセット
Stanford Network Analysis Project (SNAP) のデータセッ
ト [24] で公開されているソーシャルネットワーク・引用ネット
ワークを用いて実験を行った．表 2 に各データセットの概要を示す．

差 (NBRSE) [21] を計算した．その結果を図 5，6，7，8 に示した．

5. 4 実 験 結 果
表 3 と正規化平均二乗誤差の実験から，提案手法が既存手法
よりステップ数が少ないのにも関わらず高い精度でクラスタ係

表 2 データセット
ネットワーク

全ノード数 n 平均次数数を推定できていることがわかる．ゆえに提案手法の方が既存
平均クラスタ係数

Amazon334,8635.530

0.3967

DBLP

317,080

6.622

0.6324

Gowalla196,591

9.668

0.2367

Live Journal

3,997,962

17.35

0.2843

手法より優位といえる．

6. まとめと今後の課題
本論文では，NBRW と三角形の数えるアイデアを組み合わせた手法を提案した．実験から既存手法より効率的かつ高精度であり，クラスタ係数の推定手法として優れていることがわか

5. 1. 1 Amazon ネットワーク
Amazon Web サイト（注 1）をクローリングして集められたネッ（注 2）：http://dblp.uni-trier.de/（注 3）：http://www.livejournal.com/（注 1）：http://www.amazon.co.jp/（注 4）：https://networkx.github.io/表 3 10000 ノード収集するのに必要なステップ数の平均
ネットワーク

既存手法

提案手法

Amazon

20308

14981

DBLP

16144

14232

Gowalla

14758

13406

Live Journal

11417

10616

図 8 LiveJournal ネットワーク

定量的に評価することとする．
謝辞
本研究は JSPS 科研費 25700008，26540161 の助成を受けたも
図 5 Amazon ネットワーク

のである．

文

図 6 DBLP ネットワーク

図 7 Gowalla ネットワーク

る．その理由として，NBRW が SRW の一つ前のノードに遷移する可能性があるためサンプリング結果に偏りが出やすいという欠点を解決できている点と，式 (4) から NBRW と三角形の数え上げのアイデアによるクラスタ係数推定が相性が良いという点が考えられる．今後の課題として，提案手法が既存手法
よりステップ数が少ないのにも関わらず精度が良くなる理由を

献[1] Yong-Yeol Ahn, Seungyeop Han, Haewoon Kwak, Sue
Moon, and Hawoong Jeong. Analysis of topological characteristics of huge online social networking services. In
Proceedings of the 16th international conference on World
Wide Web, pp. 835–844. ACM, 2007.
[2] Minas Gjoka, Maciej Kurant, Carter T Butts, and Athina
Markopoulou. Walking in facebook: A case study of unbiased sampling of osns. In INFOCOM, 2010 Proceedings
IEEE, pp. 1–9. IEEE, 2010.
[3] Alan Mislove, Massimiliano Marcon, Krishna P Gummadi,Peter Druschel, and Bobby Bhattacharjee. Measurement
and analysis of online social networks. In Proceedings of the
7th ACM SIGCOMM conference on Internet measurement,
pp. 29–42. ACM, 2007.
[4] Thomas Schank and Dorothea Wagner. Approximatingclustering-coeﬃcient and transitivity. Universität Karlsruhe, Fakultät für Informatik, 2004.
[5] Minas Gjoka, Maciej Kurant, Carter T Butts, and Athina
Markopoulou. Practical recommendations on crawling online social networks. Selected Areas in Communications,
IEEE Journal on, Vol. 29, No. 9, pp. 1872–1892, 2011.
[6] Jure Leskovec and Christos Faloutsos. Sampling from large
graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining,pp. 631–636. ACM, 2006.
[7] Shaozhi Ye, Juan Lang, and Felix Wu. Crawling onlinesocial graphs. In Web Conference (APWEB), 2010 12th
International Asia-Pacific, pp. 236–242. IEEE, 2010.
[8] Maciej Kurant, Athina Markopoulou, and Patrick Thiran.
Towards unbiased BFS sampling. Selected Areas in Communications, IEEE Journal on, Vol. 29, No. 9, pp. 1799–
1809, 2011.
[9] Daniel Stutzbach, Reza Rejaie, Nick Duﬃeld, SubhabrataSen, and Walter Willinger. On unbiased sampling for unstructured peer-to-peer networks. IEEE/ACM Transactions on Networking (TON), Vol. 17, No. 2, pp. 377–390,
2009.
[10] Amir H Rasti, Mojtaba Torkjazi, Reza Rejaie, andD Stutzbach. Evaluating sampling techniques for large dynamic graphs. Univ. Oregon, Tech. Rep. CIS-TR-08, Vol. 1,

, 2008.
[11] Balachander Krishnamurthy, Phillipa Gill, and Martin Arlitt. A few chirps about twitter. In Proceedings of the firstworkshop on Online social networks, pp. 19–24. ACM, 2008.
[12] Stephen J Hardiman and Liran Katzir. Estimating clustering coeﬃcients and size of social networks via random
walk. In Proceedings of the 22nd international conferenceon World Wide Web, pp. 539–550. International World
Wide Web Conferences Steering Committee, 2013.
[13] Rong-Hua Li, Jeﬀrey Xu Yu, Lu Qin, Rui Mao, and Tan
Jin. On random walk based graph sampling. In Data Engineering (ICDE), 2015 IEEE 31st International Conferenceon, pp. 927–938. IEEE, 2015.
[14] Yong-Yeol Ahn, Seungyeop Han, Haewoon Kwak, Sue
Moon, and Hawoong Jeong. Analysis of topological characteristics of huge online social networking services. In
Proceedings of the 16th international conference on World
Wide Web, pp. 835–844. ACM, 2007.
[15] Tianyi Wang, Yang Chen, Zengbin Zhang, Tianyin Xu,
Long Jin, Pan Hui, Beixing Deng, and Xing Li. Understanding graph sampling algorithms for social network analysis.
In Distributed Computing Systems Workshops (ICDCSW),
2011 31st International Conference on, pp. 123–128. IEEE,
2011.
[16] Ziv Bar-Yossef, Alexander Berg, Steve Chien, Jittat
Fakcharoenphol, and Dror Weitz. Approximating aggregate
queries about web pages via random walks. 2000.
[17] Sang Hoon Lee, Pan-Jun Kim, and Hawoong Jeong. Statistical properties of sampled networks. Physical Review E,
Vol. 73, No. 1, p. 016102, 2006.
[18] Maciej Kurant, Minas Gjoka, Carter T Butts, and Athina
Markopoulou. Walking on a graph with a magnifying glass:stratified sampling via weighted random walks. In Proceedings of the ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems,
pp. 281–292. ACM, 2011.
[19] David Aldous and Jim Fill. Reversible markov chains andrandom walks on graphs, 2002.
[20] Minas Gjoka. Measurement of Online Social Networks. PhD
thesis, UNIVERSITY OF CALIFORNIA, 2010.
[21] 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.
[22] 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.
[23] 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.
[24] Stanford large network dataset collection.
https://
snap.stanford.edu/data/.
[25] Galin L Jones, et al. On the markov chain central limit
theorem. Probability surveys, Vol. 1, pp. 299–320, 2004.

付

録

1∑
f (Xs )
t s=1
t

def

µˆt (f ) =定常分布 π に関する関数 f の期待値は次のように与えられる．
∑
def
Eπ (f ) =π(i)f (i).
i∈V[25] では {Xt } が定常分布 π の有限で既約なマルコフ連鎖であるとき，任意の初期分布 P{X0 = v}, v ∈ V, ( t → ∞) に対してµˆt (f ) → Eπ (f ) almost surely (a.s.)が成立つ．ただし Eπ (|f |) < ∞ とする．
この可逆なマルコフ連鎖から，NBRW によるランダムウォー
ク，つまり同じ定常分布 π の非可逆で既約な有限マルコフ連鎖を作る [21]．

NBRW によるランダムウォークを {Xt′ ∈ V, t = 0, 1...} とす′る．現在のノードが Xt′ のとき，次のノード Xt+1の決定のさ′れ方は現在のノード Xt′ だけでなく，一つ前のノード Xt−1にも依存する．このため，{Xt′ }t>
自体は V の状態空間ではマ=0
ルコフ連鎖になり得ない．したがって，マルコフ連鎖を作れる
ように次のような状態空間を定義する．
defΩ = {(i, j) : i, v ∈ V s.t. P (i, j) > 0}⊂=V × Vdef′|Ω| < ∞ であり，Zt′ = (Xt−1, Xt′ ) ∈ Ω (t >= 1) とする．簡単に表記するために 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)P (i, j) = π(j), ∀j ∈ Vi∈V :eij ∈Ω

i∈V

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

j∈V i∈Vf (j)π(j) = Eπ (f )j∈V

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

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

すなわち，

∑t

定量である．

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