はじめに
データのつながりに着目した新たなデータ分析の手法を学ぶために，黒木裕鷹・保坂大樹 著 「データのつながりを活かす技術〜ネットワーク／グラフデータの機械学習から得られる新視点」を読むことにした。
本記事は，「第2章 ネットワークデータの発見・観測・構築」における，ネットワークの観測・入手に関する読書メモである。
- 本書の紹介ページ
2.3 ネットワークデータを観測・入手する
分析したいネットワークデータがなければ，新たなデータを取得する必要がある。本節では，ネットワークを抽出し観測するサンプリング手法について紹介している。
複数のノードを観測し，その間のエッジを見つける
誘導サンプリング
任意の複数のノードを観測し，それらノード間に存在するエッジもあわせて観測するサンプリング手法を誘導サンプリング(induced subgraph sampling)と呼ぶ。このようにして得られるネットワークを誘導部分グラフ(induced subgraph)と呼ぶ。
誘導サンプリングの注意点
ノードの抽出をランダムに行なう場合，抽出したネットワークにエッジがほとんど張られない可能性がある。他のノードとつながらないノードを孤立ノード(isolated node)と呼ぶ。
エッジがほとんどないような誘導部分グラフしか得られなければ，ネットワーク全体の構造が把握しづらくなる。
また誘導部分グラフが抽出されても，これがネットワーク全体を統計的に代表するわけではないことにも注意が必要である。
エッジを抽出し，つなぎ合わせる
エッジ誘導サンプリング
誘導サンプリング(ノードをまず選ぶ)とは反対に，はじめにエッジを観測し，続いてその両端にあるノードを観測する手法をエッジ誘導サンプリング(incident subgraph sampling)と呼ぶ。
| サンプリング手法 | 手順 |
|---|---|
| 誘導サンプリング | ノードを観測する⇒ノード間のエッジを観測する |
| エッジ誘導サンプリング | エッジを観測する⇒その両端にあるノードを観測する |
エッジ誘導サンプリングの注意点
エッジ誘導サンプリングは，つながりを多く有するノードが過剰に抽出されやすい，という点に注意する必要がある。エッジを軸として観測するので，結果として得られるネットワークは「中心的なノードの特徴」を過度に反映するものとなる。
任意のノードとその近傍ノードを抽出する
スターサンプリング
はじめに複数のノードを観測し，続いてそれらノードを起点とするエッジたどり，その先にある近傍ノードについても観測するサンプリング手法をスターサンプリング(star sampling)と呼ぶ。
サンプリング範囲が段階的に拡大していくことになり，雪玉が転がるにつれて大きくなるイメージにちなんでスノーボールサンプリング(snowball sampling)と呼ばれる。
経路を観測し，貼り合わせる
ノード集合(ソースノード)と，別のノード集合(ターゲットノード)をあらかじめ用意し，ソースからターゲットへ至る経路上にあるノードとエッジを抽出するサンプリング手法をリンクトレーシング(link tracing)と呼ぶ。
リンクトレーシングが有効に機能するのは，「特定の経路に関する情報は簡単に取得できるが，ネットワーク全体を把握するのは困難」という場面(物理的ななインターネットの通信経路の観測など)が典型的である。
まとめと感想
今回は，「第2章 ネットワークデータの発見・観測・構築」における，ネットワークデータの観測・入手についてまとめた。
ネットワークデータの作成方法は，ノードに着目する方法と，エッジに着目する方法がそれぞれ存在することが理解できた。
今回説明があった方法はそれぞれ特徴があったが，ノードやエッジといった局所的な特徴から，ネットワーク全体を捉えようとするのは，なかなか大変なことだと考える。各手法について，ネットワークの構築に関する性能の比較はいずれ試してみたい。
本記事を最後まで読んでくださり，どうもありがとうございました。
