8.2 隣接行列 | 情報数学入門

グラフを行列で表現すると、線形代数の道具が使える。隣接行列の累乗はパスの数を数え、固有ベクトルはネットワークの中心性を示す。GoogleのPageRankも、この行列の固有ベクトルである。グラフと線形代数の出会いがスペクトラルグラフ理論を生んだ。

隣接行列次数行列ラプラシアン PageRank

隣接行列

隣接行列（Adjacency Matrix）A

n×n 行列（n は頂点数）

Aᵢⱼ = 1 if 頂点iと頂点jが接続

Aᵢⱼ = 0 if 接続なし

無向グラフでは対称行列（A = Aᵀ）

3頂点のグラフ（1-2, 2-3 が接続）の隣接行列：

A = [[0,1,0], [1,0,1], [0,1,0]]

次数行列（Degree Matrix）D

対角行列。Dᵢᵢ = 頂点iの次数

グラフラプラシアン L

L = D - A

グラフの構造を捉える重要な行列。

固有値は連結性、固有ベクトルはクラスタリングに使用。

Webページの重要度を計算するアルゴリズム。

遷移行列 M の最大固有値に対応する固有ベクトルがPageRank。

「ランダムにリンクをたどるとき、各ページにいる確率」

正規化	式	用途
対称正規化	D⁻¹/²AD⁻¹/²	スペクトラルクラスタリング
ランダムウォーク	D⁻¹A	PageRank、GNN

リンク解析：サイト内リンク構造の分析。

影響力分析：SNSでの影響力のあるユーザーを特定。

到達可能性：ある状態から別の状態に遷移できるか。

GNN：隣接行列を使って近傍の情報を集約。

スペクトラルクラスタリング：ラプラシアンの固有ベクトルでクラスタリング。

グラフ埋め込み：Node2Vec、DeepWalk などの行列分解的手法。

GCN：正規化隣接行列による畳み込み。