こんにちは,DSOC 研究員の黒木裕鷹です. 今年の4月に新卒として入社しましたが,あっという間に半年経ってしまいました. 新しい環境にも慣れてきたのですが,同時に時間の速さに焦っています.
この連載では,私の学習や復習もかねて,ネットワーク構造を持ったデータ(グラフデータ)を対象とした統計解析を紹介しています. 第2回のテーマも前回に引き続き,ネットワークデータの標本調査です. 第1回で扱った,単純なノードやエッジの無作為抽出に加えて,第2回では少し凝った標本抽出を2つ紹介します. また,それらの標本抽出を使った,観測しきれないネットワーク全体の大きさ(ノードの数)を推定する取り組みを紹介します. それでは,やっていきます.
前回のおさらい
前回記事では,標本調査の初歩の初歩と,ネットワークの標本抽出を扱いました. ネットワークは構造をもつデータであるため,様々な標本抽出を考えることができます. 中でも最も単純なものである induced sampling と incident sampling を紹介しました. induced sampling はノード単位で,incident sampling はエッジ単位で無作為抽出をそれぞれ行い,それらに基づいた部分グラフを抽出します. それぞれのイメージを説明していきます.
いま,図1のようなネットワーク構造からの標本抽出を考えます. ここでは説明のため小さいネットワークを作りましたが,人間の交友関係やWorld Wide Web (WWW) のように,巨大なネットワークは通常その全貌を観測することができません. そこで,標本抽出と統計的な推論によってその性質を測ることになります.
induced sampling のイメージを図2に示しました. まず,ノードの無作為抽出により,黄色のノードが観測されたとします. 続いて,観測されたノード間のエッジ(太線)が観測されることになります.
incident sampling の例を図3に示しました. まず,エッジの無作為抽出により,太線のエッジが観測されたとします. 続いて,観測されたエッジに紐づいているノード(黄色)が観測されることになります.
その他の標本抽出
前回紹介した2つの単純な標本抽出に加え,新たに2つのネットワークの抽出,snowball sampling と link tracing を紹介します. これらはいずれも,ネットワークの構造を積極的に利用した抽出で,実際の調査で用いられることも多いです. snowball sampling におけるノードの包含確率など,より詳細な性質についてはネットワーク解析の代表的な教科書である "Statistical Analysis of Network Data" (Kolaczyk, 2009)などを参照ください.
snowball sampling
snowball sampling の手順を箇条書きで簡単に説明します. また,そのイメージを図4に示しました.
- seed とよばれる個の初期ノード(図では黄色)を無作為抽出し,その induced subgraph を観測します.
- 次に,seed の近傍のノード(オレンジ),seed との間のエッジ(太線)も観測し,を得ます.
- この作業を回繰り返し,得られたを観測ネットワークとします.
近傍,さらにその近傍,といったように,seed から雪玉のように大きく膨らませて抽出するため,snowball sampling という名前がついています. イメージではまでを示していますが,の snowball sampling を行えば,この例では母集団ネットワークの全貌を観測できることになります.
snowball sampling は,社会調査で頻繁に用いられます. たとえば違法薬物の使用者やホームレスなどは,研究者にとってアクセスするのが難しくなるでしょう. ある専門知識を持った集団などを対象とする場合も,その存在は稀有であるため,無作為抽出では観測することが困難です. しかし,このような隠れた母集団の構成員は互いに密接に関わっていることが想定されるため,snowball sampling が役に立ちます. 一方で,snowball sampling は seed の影響を強く受けてしまうことがデメリットとして挙げられます. これは,seed の属するコミュニティに偏った標本が観測されやすくなるためです.
link tracing
link tracing では,あるノード集合と別のノード集合を用意し,その経路上にあるノードとエッジを抽出します. 通常,経路には最短経路(のうちの1つ)が使われることが多いようです. 起点となるノード集合はソースノード,終点となるノード集合はターゲットノードとよばれます.
link tracing のイメージを図5に示しました. 図では,s1, s2 の2つのソースノード,t1, t2 の2つのターゲットノードがまず抽出され,続いてソースからターゲットまでの最短経路にあるエッジとノードを抽出しています.
link tracing が活躍するのは,ある現象の経路が簡単に手に入る場合です. たとえば,後ほど紹介する物理的なインターネットがその最たる例です. 一つ一つのルーターのルーティング機能は単純で,通信経路は簡単なコマンドで知ることができますが,世界中に広がった全体の構造や性質はもはや個人には知ることができません. 生き物などのエージェントの動きをトラッキングしている場合もそうでしょう.
ネットワークの大きさを推定する
前回記事では,母集団ネットワークの大きさは既知であるとしていました. たとえば日本人の交友関係に興味がある場合は,国勢調査などによりネットワークの大きさを予め知ることができます. そのため,ノードの包含確立や二次の包含確率さえ分かれば,様々な量について Horvitz-Thompson 推定量を考えることができるのでした. しかし WWW など,ネットワークの大きさが未知であったり,それ自体が興味の対象となることも多いでしょう.
この節では,母集団ネットワークの大きさを推定する取り組みを2つ紹介します. これらは Kolaczyk(2009) でも引用されている取り組みですが,せっかくなのでもう少し詳しく紹介したいと思います.
link tracing を用いた物理インターネットの大きさの推定 (Viger et al., 2007)
Viger et al. (2007) は,特にルータなどによって構成される物理的なインターネットの大きさを推定することを目的とし,link tracing に基づいた推定量を提案しています.
link tracing を利用するモチベーションに,Linux のtraceroute
コマンドがあります.
traceroute
では,指定したホストに到達するまでの経路を取得することができます.
コマンドを実行するIPをソースノードとし,指定したホストをターゲットノードとみなすと,これは link tracing そのものだとわかります.
つまり,この論文では,traceroute
を様々な端末から様々なホストに対して実行して得た標本ネットワークから,物理インターネットの大きさを推定することを目的としているのです.
論文で提案されている推定量は2つあり,Re Sampling (RS) estimator と Leave-One-Out (LOO) estimator です. どちらの推定量も,「ノードが重複して抽出される割合を用い,観測されたノードの数を膨らませる」というアイデアに基づいています.
Re-Sampling estimator
RS estimator では,標本ネットワークからさらに標本抽出を行いを得ることが, から が観測されることと同様の性質を持っていると仮定します. より具体的には,ネットワークの大きさをとすると,と,との関係が等しいと仮定し,
と整理できるため,次式で推定してやろうということです.
RS estimator で置かれている仮定はかなり厳しいものであると思います. がと同じ性質の構造になっているとは考えにくいでしょう. スケールフリーネットワークの部分グラフはスケールフリーにならない,という研究が Stumpf et al. (2005)などで行われていたりします. ましてや link tracing では,ハブとなるようなノードが抽出されやすく,得られる部分グラフは偏ったものと直感的に考えられます.
Leave-One-Out estimator
LOO estimator では,ターゲットノードが無作為抽出されていることを仮定します. そしてその名の通り,1つのターゲットノードを抜き出し,それが他のターゲットノードへの link tracing に含まれている割合を算出し,利用します,観測されたノードの数を膨らませます.
いま,ターゲットノードを除いた link tracing で得られるノード集合を,がに含まれないかどうかの指示関数を,他のに含まれないターゲットノードの数をで表すことにします. ターゲットノードはランダムに選ばれているため,他のターゲットノードへのlink tracingで観測される確率は次式のようになります. ここで,はソースノードの数,はターゲットノードの数,はの大きさです.
さらに和をとることで,の期待値を求めることができます.
これをについて整理すると次式のようになります.
このままでも良さそうですが,分母が0になると推定がおかしくなってしまうので,も直接推定し利用することを考え,論文では最終的に次の推定量が提案されています.
数値実験と,物理インターネットの大きさの推定
論文では,提案した推定量の良さを測るための数値実験が行われています. 性質が既知であるネットワーク生成モデルからたくさんのネットワークを適用し,そこからの link tracing により擬似的な標本ネットワークを得ます. 標本ネットワークからもとの大きさを推定し,の平均で評価を行っています. 生成モデルには,有名なBAモデルとERモデルが使われています(BAモデルやERモデルについては次回以降の記事で紹介することになると思います). その結果,ソースノードやターゲットノードの数が極端に少なくない限り,LOO estimator の性質が良いと結論付けられています.
たしかに,RS estimator はその仮定が怪しい感じもありますが,LOO estimator の方はターゲットノードさえ無作為抽出できる状況であれば良さそうですね.
最後に,物理インターネットの大きさの推定を実際に行っています.
推定量には数値実験で評価の良かったを使用し,結果として約7200万の推定値が算出されています.
実際に真の値を確かめることはできないのですが,より直感的な方法であるping
コマンドとの比較が行われています.
ping
は,指定したIPに疎通できるかどうかを調べるコマンドです.
さらに,IPの数は最大でも通りです.
そこで,論文では無作為に3726773個の IP に ping
を送信し,61246個の有効な応答 (1.64%) を得ています.
よって,ping
を使った方法では,物理インターネットの大きさは で,約7000万となり,と近い値が得られます.
このように,ターゲットノードさえ無作為抽出することさえできれば,link tracing で得られた標本ネットワークからは悪くない精度でその大きさが推定できそうです.
snowball sampling に基づいた,ネットワークの大きさの推定 (Frank and Snijders, 1994)
次に,もう少し古めの論文を紹介します.
Frank and Snijders (1994) では,snowball sampling によって抽出された標本ネットワークから,母集団ネットワークの大きさを推定する推定量をたくさん(なんと7個も)提案しています. それらは大きく
- Model-based な推定量
- Design-based な推定量
に分けられます. ここでは,そのうちいくつかを取り上げて紹介することにします.
Model-based estimation
Model-basedな推定量では,以下のような状況を仮定します. つまり,母集団にERモデルを仮定するという意味で model based になっています.
- snowball sampling の seed ノードが確率で無作為抽出されている
- 母集団ネットワークがランダムグラフであり,全てのノード間で確率でエッジが張られている
母集団ネットワークのノード集合をとし,ノードが抽出されたかどうかの指示関数をとします. また,エッジ集合をとし,エッジが抽出されたかどうかの指示関数をとします. さらに,seed 集合 の数を,seed 間のエッジ数をとすると,で条件付けしたは二項分布に従います. また,条件付けない場合の確率は次のようになります.
よって,の条件付き期待値や期待値は次のようになります.
次に,seedからwave1で観測されるノードに張られるエッジの数をとすると,先ほどと同様を条件付けたの確率は二項分布に従います. また, で条件付けない確率は次のようになります.
よって,の条件付き期待値や期待値は次のようになります.
ここまでの条件付き期待値による連立方程式を解き,を条件付けたときののモーメント推定量は次式のようになります.
同様に,を条件付けなかった場合は,のモーメント推定量は次式のようになります.
Design-based estimatior
母集団ネットワークにランダムグラフが仮定できる場合,つまり論文でいう Model-based estimator は非常に簡単でした. では,ランダムグラフが仮定できない場合はどうでしょうか. Design-based estimator では,seed が無作為抽出されることのみを仮定します.
Model-based estimatorで用意した数式に加えて,wave 1 で新たに観測されたノードの数をとします. また,母集団ネットワーク全体の弧(エッジの片割れ)の大きさをとします. の期待値はやを考えることで簡単に導出でき,次式のようになります. ここで,は,ノードと接続するノード集合で,はその大きさです.
上式からわかるように,統計量を使用すると,Model-basedのアプローチで導出された推定量が得られることになります. さらに,論文では少なくとも1つの他のseedと接続しているseedの数を導入し,別の推定量も導出しています. の期待値は次式のようになります.
であることを利用すると,次式の推定量を得ることができます.
数値実験
Frank and Snijders (1994) では,他にも Model-based の最尤推定量や,seedの抽出確率が既知であるときの Horvitz-Thompson 推定量なども提案されています. いくつかの推定量に対しては標準誤差の評価もされています.
これら多くの推定量を良さ測るためにa数値シミュレーションが行われています. 次の3つのモデルからネットワークを生成し,それに対し snowball sampling で標本ネットワークを得て,を推定します. 大きさは,seed の抽出確率はで,で,と設定されています.
- 定数モデル:全てのノードに対して,入次数が5であるような有向グラフ(接続はランダムに選択)
- ERモデル:ノード間にエッジが張られる確率があらゆるペアでであるような,ランダムグラフ
- 2-ブロックモデル:半分のノードの間では確率,もう半分のノードの間では確率,これらのグループ間では確率でエッジが張られるようなブロックモデル
論文は1994年に出版されているため,スケールフリーネットワーク(次回以降に紹介予定です)を用いた実験は行われていません. さらにが小さいこともあり,結果についてはここでは取りあげませんが,気になる方は元論文を参照ください.
おわりに
連載第2回の本記事では,より複雑なネットワーク標本抽出として,snowball sampling と link tracing を紹介しました. また,前回では既知としていた,ネットワークの大きさを推定する取り組みを2本ほど紹介しました. これらの論文では,link tracing のターゲットノードやsnowball sampling の seed を無作為抽出することを仮定していました. しかし,社会調査を目的としていない観察データなどを扱っていると,この仮定は非常に厳しいものでしょう. 実際に利用する際は,交絡因子を調整したりすることが望ましいと考えられます.
やや文量が多くなってしまいましたが今回の記事はここまでです. 標本抽出まわりは一旦これで終わりにし,次回からはネットワークの統計モデルに入っていきたいと思います.
参考文献
- Frank, O., & Snijders, T. (1994). Estimating the size of hidden populations using snowball sampling. Journal of Official Statistics, 10, 53-67.
- Kolaczyk, E. D. (2009). Statistical Analysis of Network Data. New York: Springer.
- Stumpf, M. P., Wiuf, C., & May, R. M. (2005). Subnets of scale-free networks are not scale-free: Sampling properties of networks. Proceedings of the National Academy of Sciences, 102(12), 4221-4224.
- Viger, F., Barrat, A., Dall’Asta, L., Zhang, C. H., & Kolaczyk, E. D. (2007). What is the real size of a sampled network? the case of the Internet. Physical Review E, 75(5), 056111.
▼これまでの記事