DEIM Forum 2019 D2-4

プライベートなノードを含むソーシャルネットワークの統計量推定
中嶋一貴†

首藤 一幸†† 東京工業大学 情報理工学院 数理・計算科学系
あらまし

本研究では，プライベートなノードを含むソーシャルネットワークに対する，ランダムウォークを用いた統計量推定アルゴリズムを議論する．近年では，ランダムウォークを用いた，ソーシャルネットワークの統計量の効率的な推定アルゴリズムが多く提案されている．現実のソーシャルネットワークは隣接ノードが非公開であるプライ
ベートなノードが一定の割合で存在するが，既存の推定アルゴリズムはこれらの存在を考慮していない．特に，平均次数とノード数に対する既存の推定アルゴリズムは，グラフ内のプライベートなノードの割合 p が増加するにつれて，推定値の誤差が増加する問題点がある．本論文では p にほぼ依存しない，グラフの平均次数とノード数の推定アルゴ
リズムをそれぞれ提案する．我々はサンプルされた各ノードに既存の推定アルゴリズムと異なる重みをかけることで，p に対して頑健な推定アルゴリズムを実現する．実験では，提案アルゴリズムが p にほぼ依存せずに，高い精度で平均次数とノード数を推定できることを示す．
キーワード ソーシャルネットワーク，グラフサンプリング，ランダムウォーク，プライバシていたと報告した [16]．本論文では隣接ノード集合を公開・非

1 はじめに近年，Online Social Networks (OSNs) の解析を目的とする研究が盛んに行われている．OSNs の解析は平均次数やノード数などのグラフの統計量や，中心性などのノードの統計量を推定することである [1–4]．しかし，ほとんどの OSN はそのグラ
フデータへのアクセスを制限しており，推定することは容易ではない．巨大な OSN の全てのグラフデータを取得して統計量を厳密計算することはほぼ不可能であり，また事前にノードの分布を知ることもできないためランダムサンプリングに基づく
推定アルゴリズムを適用することも難しい [5, 6]．
この問題を打開するために，ランダムウォークを用いた統計量推定アルゴリズムが多く提案されてきた [7–14]．多くの

OSN のアプリケーション・プログラミング・インターフェー
ス (API) は，クエリを実行したノードの隣接ノード情報を提供する．API から提供された隣接ノードのインデックスをランダ
ムに 1 つ選び遷移することを繰り返すことで，OSN 上でラン
ダムウォークを実行してインデックスなどのグラフデータのサンプリングが可能である．また，ランダムウォークのマルコフ性から各ノードのサンプルの分布を計算できるため，サンプルノードに適切な重み付けを行うことで不偏な推定量を求めることができる [6, 4, 15]．既存の統計量推定アルゴリズムは，ごく限られた API へのクエリ回数で統計量を高精度に推定することを目標として設計されてきた．

OSN に既存の統計量推定アルゴリズムを適用する上で，ユー
ザのプライバシ保護によるランダムウォークの制限は無視できない問題である．ほとんどの OSN では，各ユーザは友人リス
トの公開・非公開を設定することができる．Dey らは，ニューヨークの Facebook ユーザの 52.6%が友人リストを非公開にし公開にするノードをそれぞれパブリック・プライベートなノードと呼ぶ．ランダムウォークでプライベートなノードに遷移した場合は，API がその隣接ノードを提供しないためアルゴリズ
ムを続行できない．

Gjoka らは，実際に Facebook 上でランダムウォークを実行したとき，パブリックな隣接ノードに遷移する対処をとった [4]．
このランダムウォークは，グラフ全体ではなく，グラフ内のパブリックなノードのみから成る連結な部分グラフ上で実行されている．このため，Gjoka らのランダムウォークを既存の統計量推定アルゴリズムに適用すると，その部分グラフの統計量を推定することになる．
平均次数とノード数に対する既存の推定アルゴリズムは，プライベートなノードの割合 p が増加するにつれて推定値の誤差が大きくなる問題点がある．これは，ランダムウォークが実行される部分グラフの平均次数とノード数が，p が増加するにつれて真値との誤差が大きくなるためである．
本研究の貢献は，p に対して頑健な，平均次数とノード数の推定アルゴリズムを提案することである．まず，Gjoka らのランダムウォーク [4] の定常分布を導出し，各ノードがそのパブリックな隣接ノード数に比例した分布でサンプルされることを示す．各ノードのサンプルの分布を計算することで，各サンプ
ルノードへの適切な重み付けを議論することが可能になる．そして我々は，各サンプルノードに既存の推定アルゴリズムと異なる重みをかけることで，p に対して頑健な推定を可能にする．
本研究では，OSN の API が提供する隣接ノード情報の 2 つのモデルを考え，それぞれのモデルでクエリ回数を考慮した推定
アルゴリズムを設計する．実際の OSN のグラフに対する実験
では，いずれのモデルに対しても，提案アルゴリズムが p にほぼ依存せずに，ごく限られたクエリ回数で平均次数とノード数を高精度に推定できることを示す．

This is an unrefereed paper.

3 プライベートなノードを考慮したランダムウ
ォーク
プライベートなノードを含むグラフ上のランダムウォークを議論する．ランダムウォークは，あるノードの隣接ノードから(a) API が隣接ノードのプライバシ (b) API が隣接ノードのプライバ
シ情報を提供しないモデル．

情報を提供するモデル．

図 1 パブリックなノード vi にクエリを実行したとき，API が提供

ランダムに 1 つのノードを選択して遷移することを繰り返し，遷移したノードのインデックスをはじめとする情報をサンプリングする．プライベートなノードに遷移した場合はその隣接する隣接ノード情報の，2 つのモデル: 青色のノードはパブリッ

ノードの情報が取得できないため，ランダムウォークを続行す

ク，赤色のノードはプライベート，白色のノードはプライバシ情ることができない．

報が不明なノードを示す．

このため，Gjoka らが提案したパブリックな隣接ノードをランダムに選び遷移するランダムウォークが適切である [4]: ラ
ンダムウォークの i ステップ目のパブリックなサンプルノード

2 準

備

vxi の隣接ノード集合からランダムに 1 つ選んだノード vxi+1

本研究では無向で連結なグラフ G = (V, E) を扱う．ソー
シャルネットワークでは，ノードはユーザ，エッジはユーザ間の関係を表す．グラフ G はセルフループと多重辺を持たず辺に重みはないとする．ノード数 n = |V |, エッジ数 m = |E| とし，グラフ G のノード集合を V = {v1 , v2 , ..., vn }, エッジ集合
を E ，ノード vi の次数を di と表記する．グラフ G の平均次数は以下のように定義される:∑

定義 1. davg =vi ∈V di

n

= 2m
.
n

研究対象とするネットワークはランダムウォークモデル [9]を満たすとする．事前にグラフの情報は持たず，OSN の API
が提供する隣接ノード情報を辿ってサンプリングを行う．また，推定アルゴリズムを実行している間，グラフは静的であるとする．
グラフ G の各ノード vi はパブリックまたはプライベートののプライバシ情報を確認し，vxi+1 がパブリックなノードであればそのノードに遷移し，プライベートなノードであれば vxiの隣接ノードを選択し直す．API が隣接ノードのプライバシ情報を提供しないモデルでは，vxi+1 にクエリを実行してその出力からプライバシ情報を判別する．

Gjoka らのランダムウォークは，元のグラフ G からプライ
ベートなノードを削除してできるいくつか部分グラフのうち，初期ノードが属する部分グラフ上で実行される．グラフ G から全てのプライベートなノードとそれに接続するエッジを削除したあとに分割される k 個の連結な部分グラフを Ci とする．
それぞれの部分グラフ Ci をクラスタと呼ぶ [19, 20]．この中でノード数が最大のクラスタを C ∗ = (V ∗ , E ∗ ) とする．C ∗ に対して n∗ = |V ∗ |, m∗ = |E ∗ | とおく．最大クラスタ C ∗ の平均次数を以下のように定義する:
定義 2. d∗avg =∑∗vi ∈V ∗ di
n∗

∗

= 2m
.
n∗

いずれかのラベルを持つ．ノード vi に対してクエリを実行し本研究ではランダムウォークの初期ノードは最大クラスタ

たとき，vi がパブリックであれば，その隣接ノード情報を取得に属するノードを選ぶとする．ほとんどの OSN はスケールフ

でき，vi がプライベートであれば，その隣接ノード情報は取得

リーネットワークに分類され [1–4]，スケールフリーネットワー

できないとする 1： ．
本研究では，図 1 のように，OSN の API が提供する隣接ノー

クはランダムなノードの除去に対して頑健であることが知られている [19, 20]. すなわち，グラフにプライベートなノードがラド情報の 2 つのモデルを考える．Gjoka らが Facebook 上でランダムに分布していると仮定すると，ほとんどのパブリックなンダムウォークを実行した事例は，図 1(a) のモデルに該当す

ノードは最大クラスタに属される．このため，既存研究でも最る [4]．しかし，図 1(b) のように，隣接ノードのインデックス

大クラスタでサンプリングが可能であった [1–4]．

のみ提供される場合も考えられる．
ランダムウォークを用いた推定アルゴリズムの目標は，少3. 1 最大クラスタ上のランダムウォーク

ないクエリ回数で OSN のグラフの統計量を推定することであ最大クラスタ上のランダムウォークでは，各ノードはそのパ

る [5, 17]．一度クエリを実行したノードの隣接ノードの情報はブリックな隣接ノード数に比例した分布でサンプルされる．こ保存する．

れは最大クラスタ上のランダムウォークの定常分布を導出する

P = {pij }i,j∈S を有限な状態空間 S におけるマルコフ連鎖

ことでわかる．C ∗ 上のランダムウォークは有限な状態空間 V ∗の遷移確率行列とする．P の定常分布について以下の定理が成におけるマルコフ連鎖でありエルゴード性を満たす．よって，り立つ．

定理 1 より定常分布 π ∗ が一意に存在する．C ∗ における各ノー定理 1. [18]P がエルゴード的であるとき，その定常分布 π が一意に存在する．
1：出力はエラーメッセージや空集合など，OSN の API に依存する．

ド vi ∈ V ∗ の次数を d∗i と表す．C ∗ の各ノードの次数は，そのノードの G におけるパブリックな隣接ノード数である．ここで V ∗ の各ノードの添字集合を I = {i1 , i2 , ..., in∗ } とおく．C ∗∗ とする上のランダムウォークの定常分布を π ∗ = {πj∗ }1<=j <=nE[dˆ∗xi ] = d∗xi

証明. i ステップ目のサンプルノードの隣接ノードを 1 つランd∗xダムに選んだとき，確率 dxi でパブリックな隣接ノードを選択i

図 2 プライベートなノードを含むグラフの例．青色のノードはパブ∗

dx
する．よって，E[dˆ∗xi ] = dxi dxi = d∗xi が成り立つ．
i

リック，赤色のノードはプライベートなノードである．

と，各ノード vij ∈ V ∗ に対して以下が成り立つ:

πj∗ =

d∗ij
2m∗

5 プライベートなノードを考慮した統計量推定
本論文ではグラフ G の平均次数 davg とノード数 n を推定す.

例えば図 2 のグラフで vi = i (0 <= 9) とする．以下の 3=i<
つのクラスタ C1 , C2 , C3 に分割され，最大クラスタは C ∗ = C1である:•C1 = ({3, 4, 5, 6, 8}, {(3, 4), (4, 5), (4, 6), (4, 8)})•C2 = ({7, 9}, {(7, 9)})•C3 = ({2}, {}).

るアルゴリズムを議論する．グラフのノード数とエッジ数は最も基本的なグラフの統計量である．定義 1 よりノード数と平均次数の推定値からエッジ数の推定値を求めることができる．
既存の推定アルゴリズムは C ∗ の平均次数とノード数を推定しており，p が増加するにつれて推定値の誤差が増加する問題
点がある．提案アルゴリズムは，既存アルゴリズムのサンプル
ノードへの重みを変更することで，p の増加に対する推定値の誤差の増加を大幅に小さくする．

添字集合 I = {i1 , i2 , i3 , i4 , i5 } を i1 = 3, i2 = 4, i3 = 5, i4 =6, i5 = 8 とすると，d∗3 = 1, d∗4 = 4, d∗5 = 1, d∗6 = 1, d∗8 = 1
で あ る ．よ っ て C

π

∗

∗

上のランダムウォークの定常分布は= ( 81 , 12 , 18 , 18 , 18 ) である．

5. 1 平均次数の推定
Dasgupta らはグラフの平均次数を推定するアルゴリズム
Smooth を提案した [9]．Smooth は，入力として平均次数の大まかな推定値 c を与え，それより正確な推定値 dSmoothを出avg

4 パブリックな隣接ノード数の計算
平均次数とノード数の推定において，各サンプルノード vxiに重み付けをするために，そのパブリックな隣接ノード数 d∗xiを計算する必要がある．API が提供する隣接ノード情報のそれ
ぞれのモデル (図 1) に対して，クエリ数を考慮した計算方法を述べる．

力する．ランダムウォークで遷移した各ノードにセルフループ
を c 本追加して次の遷移先のノードを選択する．
本研究ではグラフの事前知識が無いことを仮定するため c = 0とする．入力として与える定数 c は平均次数に対する大まかな近似値とされるが，グラフに対する事前知識が無い場合はその近似値を求めることにクエリの追加実行を必要とする．Dasgupta
らは定数 c=0, 1, 5, 50 に対して推定精度の評価実験をしてお4. 1 API が隣接ノードのプライバシ情報が提供するモデル
API が vxi の隣接ノードのプライバシ情報を提供する場合，
d∗xi を厳密に計算できる．実際に，Gjoka らが Facebook 上でランダムウォークを実行した事例では，このモデルに該当す

り，0 や 1 の小さい値が望ましいとしている [9]．特に c = 0 の場合は Gjoka らが Facebook の平均次数を推定したアルゴリズ
ムと一致する [4]．

C ∗ 上で Smooth を適用すれば推定値は以下のように計算される:

る [4]．

dSmooth= ∑ravg

4. 2 API が隣接ノードのプライバシ情報が提供するモデル
この場合，d∗xi の厳密値を計算するには vxi の全ての隣接ノードに対してクエリを実行する必要があり，現実的ではない．このため，ランダムウォークでサンプルした各ノードに対して，
パブリックな隣接ノードを選択できた割合から近似計算する方法を提案する．各サンプルノード vxi に対して，パブリックな
隣接ノードを選択した合計回数を axi ，隣接ノードを選択した
合計回数を bxi とする．各サンプルノード vxi のパブリックな
隣接ノード数 d∗x の近似値 dˆ∗x を以下のように定義する:
idˆ∗xi =idx axi
d

i bx

xi

i

r

1
i=1 d∗xi

定理 3. 推定値 dSmoothは d∗avg に収束する．
avg

R は有限な状態空間 V ∗ におけるエルゴード的なマルコ∑フ連鎖であるから，定常分布 π ∗ を持つ．ΦSmooth= r1 ri=1 d∗1
avg

証明.

xi

とおく．E[ΦSmooth] = d∗1
avg

を示す．

avg

E[ΦSmooth
]
avg

∑ ∗
1
1
= E[ ∗ ] =πi E[ ∗ |xk = i]
d xk
d
xk
v ∈V ∗i∑| 0)(bxi =

d∗i 1
1
=
= ∗
∗ d∗
2m
d
avg
i
∗
v ∈V
i

(otherwise)

定理 2. 近似値 dˆ∗xi の期待値は真値 d∗xi に等しい．

1 つ目の等号は期待値の線型性より，2 つ目の等号は繰り1
返し期待値の法則より成り立つ．d∗avg = E[ΦSmooth
である．
]
avg

は期待値に収束するので dSmoothは d∗avg に収束す
ΦSmoothavg
avg

一つ目の等号は期待値の線型性より成り立つ．2 つ目の等号はる．

xk = j ，xl = j である確率がともに 2|Ej∗ | であり，インデック

本論文では各サンプルノード vi にかける重みを d1i に変更した推定アルゴリズムを提案する．提案アルゴリズムによる davgの推定値 dˆavg を以下のように定義する:

rdˆavg = ∑r

d∗スが m だけ離れていることでそれぞれの事象は独立に起こることより成り立つ．
∗
次に E[ΨKHn ] = nE[ΨKHn ] = E[1i=1 dxi∗d∗ivi ∈V ∗ di

定理 4. dˆavg は d˜avg = ∑ 2m
証明.

Φ̂avg = r1

∑r1
i=1 dxi= n∗に収束する．

∑
vj

∈V ∗

d∗j

( d∗ )2j

2|E ∗ |を示す．

∑ ∑ (d∗j )2 d∗i(d∗xk )2
d∗j
]=
∗
∗
∗
dxl
di 2|E | 2|E ∗ |v ∈V ∗ v ∈V ∗
∑

d∗j

(

vj ∈V ∗

i

j

)2
d∗j
2|E ∗ |

とおく．定理 3 の証明と同様にして，E[ΨKH ]

KHnである．ΦKH
は期待値に収束するのでn∗ = E[ΦKH
n , Ψn
]

∑

d∗i 1
1
E[Φ̂avg ] =
=
∗ d
˜
2m
i
davg
v ∈V ∗

nnKH は n∗ に収束する．

id˜avg = E[Φ̂1 ] である．Φ̂avg は期待値に収束するので dˆavg はavg
d˜avg に収束する．

我々は ΦKHと ΨKHの重み付けを変更した Φ̂n と Ψ̂n からnn推定値を求める．

Φ̂n =5. 2 ノード数の推定(k,l)∈I

Katzir と Hardiman はサンプルノードの衝突に基づく，グΨ̂n =ラフのノード数を推定するアルゴリズムを提案した [7]．この

1 ∑ (dxk )2|I|d∗xl(k,l)∈I

推定アルゴリズムは，ランダムウォークでサンプルしたノード
集合 R = {v1 , v2 , ..., vr } に対してある定数 m 以上離れたイン1 ∑dxk ϕk,l|I|

ノード数の推定値 n̂ を以下のように定義する．

デックスのペアの集合 I を調べる:n̂ =I = {(k, l) | m <= |k − l| ∧ 1 <= k, l <= r}
インデックスを m だけ離すことで，それぞれのノードが定常定理 6. n̂ は ñ =証明.

定理 5 の証明と同様にして以下が示される．

そうでなければ 0 を返す変数 ϕk,l を定義する:

E[Φ̂n ] =E[Ψ̂n ] = n∗

ここで各ノードペア (vxk , vxl ) ∈ I に対して重み付けした∗に定義する:

xl

(
dj

∑

d∗j
2|E ∗ |d∗j

vj ∈V ∗

2

(

)2

dj
2|E ∗ |

)2のそれぞれの平均値 ΦKH
ΨKHを以下のようn ，nΨ̂n ]ñ = E[である．Φ̂n , Ψ̂n は期待値に収束するので n̂ は ñ にE[Φ̂ ]
n

収束する．

1 ∑ ∗
ΦKH
=
dxk ϕk,ln|I|

API が隣接ノードのプライバシ情報を提供しないモデルで(k,l)∈I∗ 2
1 ∑ (dxk )
ΨKH
=
n
|I|
d∗xl

は，それぞれの推定アルゴリズムにおける各サンプルノード
vx の重みに用いる厳密値 d∗x の代わりに近似値 dˆ∗x を用いる．

(k,l)∈Ii

C ∗ 上で Katzir と Hardiman の推定アルゴリズムを適用すれば，その推定値 nKH は以下のように定義される:

nKH =

ΨKH
n
ΦKH
n

まず E[ΦKH
n ] =

∑
vj

∈V ∗

ΦKH
= E[d∗xk ϕk,l ] =
n

d∗j

i

i

dˆ∗xi は 4 章に基づいて近似計算する．このモデルでも，定理 2より，定理 4 と定理 6 が成り立つ．

6 実

験

実際の OSN のグラフを用いて提案アルゴリズムを評価する．

定理 5. nKH は n∗ に収束する．
証明.

∑
vj ∈V ∗

ϕk,l = 1{xk =xl }(dx )d∗xk ϕk,l と d∗k∑2n∗ v ∈V ∗ d∗j (dj )
∑ jに収束する．
∗
2v ∈V ∗ dj (dj )j

分布 π ∗ から独立にサンプルしたとみなすことができる [7]．
各ノードペア (vxk , vxl ) に対して vxk = vxl のとき 1 を返し

Ψ̂n
Φ̂n

( d∗ )2j
2|E ∗ |∑
vj ∈V ∗d∗j(

対象とするグラフが有向グラフであれば反対向きのエッジを追を示す．

加することで無向グラフとし，非連結なグラフはそのグラフの)2

最大連結成分を扱った．また，セルフループと多重辺は削除し

d∗j
2|E ∗ |

た．本論文で扱う各グラフのノード数，平均次数を表 6 に示す．

API が提供する隣接ノード情報のそれぞれのモデル (図 1)

Network

収束値

相対誤差

n

davg

LiveMocha [21]10410342.13

Smooth

19.49

0.287

douban [21]154908

4.22

Ours

28.31

0.0362

gowalla [21]196591

9.67

KH1080278

0.338

academia [21]200167

10.22

Ours

1627218 0.00342

Pokec [22]1632803 27.32
表 2 Pokec におけるそれぞれの推定アルゴリズムの収束値

表 1 データセット

NRMSE が高くなっている．また，p が 0.0 から 0.2 まででは
において，提案アルゴリズムの頑健性の評価と，実際にプライ

Ours の NRMSE は KH より高いが，p が 0.2 から 0.3 まで

ベートなノードを含む Pokec グラフ [24] における推定精度のでは Ours の NRMSE は KH より低い．一方で，クエリ数を評価を行う．推定精度の評価に正規化平方二乗誤差 (NRMSE)5%としたとき NRMSE に顕著な差が見られる．平均次数推定を用いる．NRMSE は推定値の誤差と分散を評価できる指標でと同様に，提案アルゴリズムの NRMSE は p の増加に対してあり，関連する多くの研究で用いられている [15, 7, 11, 23]．

ほとんど増加していない．

6. 1 提案アルゴリズムの頑健性提案アルゴリズムの頑健性を評価する．グラフ内のプライ
ベートなノードの割合が増加したとしても，NRMSE の増加が小さいことが望ましい．グラフ内のプライベートなノードの割合を増加させた時のそれぞれの推定アルゴリズムの NRMSE を比較する．一方で，プライバシ保護などの観点からプライベート

図 7 は LiveMocha における，API が隣接ノードのプライバ
シ情報を提供しないモデルにおける結果を示す．この場合も，提案アルゴリズムは既存アルゴリズムと比較して p が増加しても NRMSE はほとんど増加していない．Douban, gowalla,

academia でも同様の結果が得られた．
6. 2 Pokec グラフにおける提案アルゴリズムの推定精度なノードを含む公開データセットは我々の知る限り Pokec のみ

実際にプライベートなノードを含むソーシャルネットワークであった [24]．このため本論文では 4 つのグラフ LiveMocha,

である Pokec グラフにおいて，提案アルゴリズムの推定精度を

douban, gowalla, academia に対してパラメータ p を与えて，割評価する．Pokec グラフは Takac らがプライベートなノードを

合 p のノードをランダムに選びそれらをプライベートなノード含む当時の全グラフデータを取得し，各ノードのプライバシ情とする前処理を行った．そして，その最大クラスタからランダ報も付与されている [22, 24]．プライベートなノードは 552525

ムに選んだ初期ノードとクエリ数を与えてランダムウォークを

ノード (約 33.8%) 存在する．

実行し，それぞれの推定値を計算する．上記のシミュレーショ

Pokec グラフに対して，その最大クラスタからランダムに選ンを独立に 1000 回行い，それぞれのアルゴリズムの NRMSE

んだ初期ノードとクエリ数を与えてランダムウォークを実行を比較する．パラメータ p は 0.0 から 0.30 まで 0.01 ごとにし，それぞれの推定値を計算する．このシミュレーションを独変化させた．p = 0.0 のときそれぞれのアルゴリズムは等しい

立に 1000 回行い，それぞれのアルゴリズムの NRMSE を比較

NRMSE を持つ．また，ノード数推定アルゴリズムにおける定する．クエリ数はノード数の 0.5%から 5%まで 0.25%ごとに変数 m は，サンプル列の長さの 2.5%と設定した．

化させた．

まず，API が隣接ノードのプライバシ情報を提供するモデ

図 8 は，API が隣接ノードのプライバシ情報を提供するモデ

ルにおける提案アルゴリズムの頑健性を議論する．平均次数のルにおける，Pokec の平均次数とノード数推定における既存ア

推定アルゴリズムの頑健性を評価する．図 3 と図 4 は各グラ

ルゴリズム (Smooth,KH) と提案アルゴリズム (Ours) のク

フにおけるそれぞれクエリ数をノード数の 1%，5%とした時のエリ数に対する NRMSE を示す．既存アルゴリズムの NRMSE

Dasgupta らのアルゴリズム (Smooth) [9] と提案アルゴリズ

は，クエリ数が増加してもほとんど減少していない．一方で提ム (Ours) のパラメータ p に対する NRMSE を示す．いずれ

案アルゴリズムはクエリ数が増加するにつれて NRMSE が減少のクエリ数に対しても，全てのグラフにおいて Smooth はパしている．表 2 は定理 3,4,5,6 を用いてそれぞれの推定アルゴ

ラメータ p が増加するにつれて NRMSE が増加している．一リズムの収束値と真値との相対誤差を計算したものである．提方で，Ours の NRMSE は p が増加してもほとんど増加してい案アルゴリズムの収束値の相対誤差は既存アルゴリズムと比較ない．

して非常に小さいことがわかる．いずれの推定においても，提ノード数の推定アルゴリズムの頑健性を評価する．図 5 と図案アルゴリズムによる推定値は既存アルゴリズムより総じて低

6 はそれぞれクエリ数をノード数の 1%，5%とした時の Katzir

い NRMSE を示している．1%未満のクエリ数でのノード数推と Hardiman のアルゴリズム (KH) [7] と提案アルゴリズム

定では提案アルゴリズムの推定値の誤差が大きくなっており，(Ours) のパラメータ p に対する NRMSE を示す．ノード数衝

この改善は今後の課題である．図 9 は API が隣接ノードのプ突に基づくアルゴリズムはクエリ数が極端に少ない場合，サン

ライバシ情報を提供しないモデルにおける結果を示す．この場

プル内のノードの衝突がほとんど生じないため推定精度が低く合も，提案アルゴリズムは総じて低い NRMSE を示している．

なる．このため，クエリ数が 1%のとき両方のアルゴリズムの(a) LiveMocha(b) douban(c) gowalla(d) academia

図 3 p に対する平均次数の推定値の NRMSE (API が隣接ノードのプライバシ情報を提供する
モデル，クエリ数: 0.01n)(a) LiveMocha(b) douban(c) gowalla(d) academia

図 4 p に対する平均次数の推定値の NRMSE (API が隣接ノードのプライバシ情報を提供する
モデル，クエリ数: 0.05n)(a) LiveMocha(b) douban(c) gowalla(d) academia

図 5 p に対するノード数の推定値の NRMSE (API が隣接ノードのプライバシ情報を提供する
モデル，クエリ数: 0.01n)(a) LiveMocha(b) douban(c) gowalla

図 6 p に対するノード数の推定値の NRMSE (API が隣接ノードのプライバシ情報を提供する
モデル，クエリ数: 0.05n)(d) academia

(a) 平均次数推定, クエリ数: 0.01n (b) 平均次数推定, クエリ数: 0.05n (c) ノード数推定, クエリ数: 0.01n (d) ノード数推定, クエリ数: 0.05n
図 7 LiveMocha における p に対する推定値の NRMSE (API が隣接ノードのプライバシ情報を提供しないモデル)

た [25]．各ユーザの友人のうちわずか 8 ユーザが公開されているだけで，その部分グラフ上のノードの次数や媒介中心性，コミュニティ検出などの統計量を十分に近似できることを実験的に示した．しかし，ランダムウォークを用いて統計量を推定す
る本研究とは異なる．Ye らは OSN のプライベートなノードがクローリングに与える影響を言及している [26]．実際の OSNsのデータセットに対して 10 万ノードをランダムにプライベー
トなノードとしてクローリングで取得できるノード数とエッジ数の減少率を調べており，大きな減少は見られないとしている．
(a) 平均次数推定(b) ノード数推定

しかし，この研究は統計量推定におけるプライベートなノードの影響は論じていない．Chierichetti らはソーシャルネット

図 8 Pokec におけるクエリ数に対する推定値の NRMSE (API が隣接ノードのプライバシ情報を提供するモデル)

ワークにおける public-private model を提案した [27]．このモ
デルでは全体のグラフ G をパブリックなグラフと呼び，パブリックなグラフに属する各ノード u はプライベートなグラフ

Gu を持つ．パブリックなグラフはどのノードからでも見えるグラフであり，プライベートなグラフ Gu はノード u のみが見えるグラフである．各ノード u に対して G ∪ Gu の統計量を効率よく計算するアルゴリズムを提案している．しかし，この研究はグラフの全データにアクセスできることを前提にしている
ため本研究とは異なる．

8 ま と め本研究ではプライベートなノードを含むソーシャルネット
(a) 平均次数推定(b) ノード数推定

ワークに対する，ランダムウォークを用いた統計量推定アルゴ
リズムを議論した．まず，Gjoka らのパブリックなノードのみ

図 9 Pokec におけるクエリ数に対する推定値の NRMSE (API が隣接ノードのプライバシ情報を提供しないモデル)を遷移するランダムウォークの定常分布を導出し，各サンプル
ノードはそのパブリックな隣接ノード数に比例した分布でサンプルされることを示した．平均次数とノード数に対する既存の推定アルゴリズムは，プライベートなノードの割合が増加するにつれて推定値の誤差が大きくなる問題点があった．我々は，

7 関連研究既存アルゴリズムのサンプルノードへの重みを変更すること
で，プライベートなノードの割合に対して頑健な推定を可能に

オンラインソーシャルネットワークのプライバシを考慮しした．本研究では，OSN の API が提供する隣接ノード情報のた研究はいくつかある [25–27]．Bonneau らは Facebook の公

2 つのモデルを考え，それぞれのモデルにおける実験で，提案開されている隣接関係に基づくグラフ統計量の近似を議論しアルゴリズムがプライベートなノードの割合にほぼ依存せず，

高精度に平均次数とノード数を推定できることを示した．今後
は，統計量の推定精度の向上だけでなく，プライベートなノードの割合に対して頑健な推定を達成するアルゴリズムを設計するべきである．

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

文

献[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] 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.
[3] Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue
Moon. What is twitter, a social network or a news media? In Proceedings of the 19th international conference on
World wide web, pp. 591–600. AcM, 2010.
[4] 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.
[5] 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.
[6] 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.
[7] Liran Katzir and Stephen J Hardiman. Estimating clustering coeﬃcients and size of social networks via random walk.
ACM Transactions on the Web (TWEB), Vol. 9, No. 4,
p. 19, 2015.
[8] Liran Katzir, Edo Liberty, Oren Somekh, and Ioana A
Cosma. Estimating sizes of social networks via biased sampling. Internet Mathematics, Vol. 10, No. 3-4, pp. 335–359,
2014.
[9] Anirban Dasgupta, Ravi Kumar, and Tamas Sarlos. On
estimating the average degree. In Proceedings of the 23rd
international conference on World wide web, pp. 795–806.
ACM, 2014.
[10] Bruno Ribeiro and Don Towsley. On the estimation accuracy of degree distributions from graph sampling. In Decision and Control (CDC), 2012 IEEE 51st Annual Conference on, pp. 5240–5247. IEEE, 2012.
[11] Xiaowei Chen, Yongkun Li, Pinghui Wang, and John Lui. A
general framework for estimating graphlet statistics via random walk. Proceedings of the VLDB Endowment, Vol. 10,
No. 3, pp. 253–264, 2016.
[12] Kenta Iwasaki and Kazuyuki Shudo. Estimating the clustering coeﬃcient of a social network by a non-backtracking
random walk. In Big Data and Smart Computing (BigComp), 2018 IEEE International Conference on, pp. 114–
118. IEEE, 2018.

[13] Toshiki Matsumura, Kenta Iwasaki, and Kazuyuki Shudo.
Average path length estimation of social networks by random walk. In Big Data and Smart Computing (BigComp), 2018 IEEE International Conference on, pp. 611–
614. IEEE, 2018.
[14] Kazuki Nakajima, Kenta Iwasaki, Toshiki Matsumura, andKazuyuki Shudo. Estimating top-k betweenness centrality nodes in online social networks. In Proceedings of theIEEE ISPA-IUCC-BDCloud-SocialCom-SustainCom 2018,
pp. 1128–1135. IEEE, 2018.
[15] 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.
[16] Ratan Dey, Zubin Jelveh, and Keith Ross. Facebook
users have become much more private: A large-scale study.
In Pervasive Computing and Communications Workshops(PERCOM Workshops), 2012 IEEE International Conference on, pp. 346–352. IEEE, 2012.
[17] Kenta Iwasaki and Kazuyuki Shudo. Comparing graphsampling methods based on the number of queries. In
Proceedings of the IEEE ISPA-IUCC-BDCloud-SocialComSustainCom 2018, pp. 1136–1143. IEEE, 2018.
[18] David A Levin and Yuval Peres. Markov chains and mixing
times, Vol. 107. American Mathematical Soc., 2017.
[19] Réka Albert, Hawoong Jeong, and Albert-László Barabási.
Error and attack tolerance of complex networks. nature,
Vol. 406, No. 6794, p. 378, 2000.
[20] Reuven Cohen, Keren Erez, Daniel Ben-Avraham, andShlomo Havlin. Resilience of the internet to random breakdowns. Physical review letters, Vol. 85, No. 21, p. 4626,
2000.
[21] Ryan A. Rossi and Nesreen K. Ahmed. The network datarepository with interactive graph analytics and visualization. In Proceedings of the Twenty-Ninth AAAI Conferenceon Artificial Intelligence, 2015.
[22] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford
large network dataset collection. http://snap.stanford.
edu/data, June 2014.
[23] Pinghui Wang, John Lui, Bruno Ribeiro, Don Towsley, Junzhou Zhao, and Xiaohong Guan. Eﬃciently estimating
motif statistics of large networks. ACM Transactions on
Knowledge Discovery from Data (TKDD), Vol. 9, No. 2,
p. 8, 2014.
[24] Lubos Takac and Michal Zabovsky. Data analysis in public social networks. In International Scientific Conference
and International Workshop Present Day Trends of Innovations, 2012.
[25] Joseph Bonneau, Jonathan Anderson, Ross Anderson, andFrank Stajano. Eight friends are enough: social graph approximation via public listings. In Proceedings of the Second
ACM EuroSys Workshop on Social Network Systems, pp.
13–18. ACM, 2009.
[26] Shaozhi Ye, Juan Lang, and Felix Wu. Crawling onlinesocial graphs. In Web Conference (APWEB), 2010 12th
International Asia-Pacific, pp. 236–242. IEEE, 2010.
[27] Flavio Chierichetti, Alessandro Epasto, Ravi Kumar, Silvio Lattanzi, and Vahab Mirrokni. Eﬃcient algorithms
for public-private social networks. In Proceedings of the21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 139–148. ACM, 2015.