@uminchu987さんと輪読会を開催したので、資料の内容をまとめました。
1章 ネットワークデータの基礎
1.1.ネットワークとは？
ネットワークとは
ノード（点）とエッジ（線）からなるつながりの構造
ネットワークの分析対象
-
ノード
- 分析対象を表す点。
-
エッジ
- ノードをつなぐ線。
ネットワークから何がわかる？
- どこが中心的な役割を担っているのか
- 共通のつながりを持つグループが存在するか
- 最も遠い位置にいるのは何か
ネットワークの特徴
- データ形式の制約が緩い。
- 様々な事象をネットワークで表現できる。
- 表データ, テキストデータなどは、制約が固定化されているケースが多い
1.2.さまざまなネットワーク
つながりの方向
-
有向ネットワーク
- エッジが方向を持つ
- 例）Xのフォロー/フォロワー、Webページのリンク構造
-
無向ネットワーク
- エッジが方向を持たない
- 例）LINEの友だち関係、電車の路線図
つながりの重み
-
重み付きネットワーク
- エッジが重み（つながりの強さ）をもつネットワーク
- 例）「連絡回数」をエッジの重みとしたLINEの友だち関係
-
重みなしネットワーク
- エッジが重み（つながりの強さ）を持たないネットワーク
- 例）↑を考慮しないケース
主体・つながりの種別
-
同種ネットワーク
- 同じ種類のノード、エッジにより構成されるネットワーク
- 例）LINEの友だち関係（ノードは全てユーザー）
-
異種ネットワーク
- 異なる種類のノード、エッジにより構成されるネットワーク
- 例）ECサイトの購買情報（ノードは顧客と商品、エッジは購買）
-
二部ネットワーク
- 2種類のノード集合とノード集合間にのみ同種のエッジが張られるネットワーク
- 例）ECサイトの購買情報（ノードは顧客と商品、エッジは購買）
- 「射影」によって分析しやすくなる
-
知識グラフ
- 特定の観点で体系化された知識をエンティティ（ノード）とリレーション（エッジ）で表現したネットワーク
主体・つながりの付属情報
-
特徴量
- ノードやエッジに付随された情報
- 例）年齢、性別、プロフィール文
時間変化の考慮
-
動的ネットワーク
- 時間経過に伴い構造が変化するネットワーク
-
静的ネットワーク
- 時間経過に伴い構造が変化しないネットワーク
柔軟性が高く様々な要素を組み込めるため、まずはシンプルなネットワークを作って必要だと判断した時点で情報を付け加えていくとよい。
1.3 ネットワークデータの表現方法
数式による表現
-
ネットワーク $G=(V,E)$
- ノードの集合$V$と、エッジの集合$E$からなるネットワーク
-
エッジ$E$の要素$e$
- 異なるノードである$u,v$の順序のないペア$e=\lbrace{u,n\rbrace}$で表現される
-
隣接
- 2つのノード$u,v$を結ぶエッジが存在し、${u,v}\in{E}$である場合、2つのノードは隣接しているという
-
次数
- ノードの数$N_V=|V|$とエッジの数$N_E=|E|$は、次数と呼ばれることがある
隣接行列
- ネットワーク$G$を分析する際には行列でよく表現される
- 隣接行列$A$は$N_V \times N_V$の対象行列で表現できる
$$
A = [A_{i,j}]
$$
$$
a_{ij} =
\begin{cases}
1 & \text{if } {i, j} \in E \
0 & \text{otherwise}
\end{cases}
$$
- 隣接行列のほとんどが要素0となる場合の行列をネットワークは 疎(sparse) と呼ばれる。
- $N_V \times N_V$の体格行列を$D$としたとき、$L=D-A$で表現される行列$L$をグラフラプラシアンと呼ぶ
- グラフラプラシアンはノードの埋め込みやGNNなどでよく使われる。