第1章：グラフとグラフ表現学習の基礎

グラフ理論の基礎、グラフ表現、特徴量抽出、グラフ埋め込み手法の理解

📖 読了時間: 30-35分 📊 難易度: 初級〜中級 💻 コード例: 12個 📝 演習問題: 6問

学習目標

この章を読むことで、以下を習得できます：

1.1 グラフ理論の基礎

グラフとは何か

グラフは、オブジェクト間の関係を表現する数学的構造です。ソーシャルネットワーク、分子構造、道路網、知識グラフなど、現実世界の多くの問題をグラフで表現できます。

「グラフ $G$ は、ノード（頂点）の集合 $V$ とエッジ（辺）の集合 $E$ で定義される：$G = (V, E)$」

基本用語

グラフの種類

グラフの種類定義具体例
木（Tree）閉路を持たない連結グラフファイルシステム、組織図
DAG有向閉路を持たない有向グラフタスクの依存関係、因果グラフ
完全グラフ全ノード間にエッジが存在完全に接続されたネットワーク
二部グラフノードが2つのグループに分割可能推薦システム（ユーザー-アイテム）
サイクルグラフ単一の閉路を形成循環参照、リング構造
正則グラフ全ノードの次数が等しい結晶格子、トーラスグラフ
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

print("=== NetworkX によるグラフの基本操作 ===\n")

# 1. 無向グラフの作成
G_undirected = nx.Graph()
G_undirected.add_edges_from([
    ('A', 'B'), ('A', 'C'), ('A', 'D'),
    ('B', 'C'), ('C', 'D')
])

print("無向グラフ:")
print(f"  ノード数: {G_undirected.number_of_nodes()}")
print(f"  エッジ数: {G_undirected.number_of_edges()}")
print(f"  ノード: {list(G_undirected.nodes())}")
print(f"  エッジ: {list(G_undirected.edges())}\n")

# 2. 有向グラフの作成
G_directed = nx.DiGraph()
G_directed.add_edges_from([
    ('A', 'B'), ('B', 'C'), ('C', 'A'),
    ('A', 'D'), ('D', 'B')
])

print("有向グラフ:")
print(f"  ノード数: {G_directed.number_of_nodes()}")
print(f"  エッジ数: {G_directed.number_of_edges()}")
print(f"  ノードAの出次数: {G_directed.out_degree('A')}")
print(f"  ノードAの入次数: {G_directed.in_degree('A')}\n")

# 3. 重み付きグラフの作成
G_weighted = nx.Graph()
G_weighted.add_weighted_edges_from([
    ('Tokyo', 'Osaka', 400),
    ('Tokyo', 'Nagoya', 350),
    ('Osaka', 'Nagoya', 180),
    ('Osaka', 'Fukuoka', 500)
])

print("重み付きグラフ（都市間距離）:")
for u, v, weight in G_weighted.edges(data='weight'):
    print(f"  {u} - {v}: {weight}km")

# 4. 特殊なグラフの生成
print("\n=== 特殊なグラフの生成 ===\n")

# 完全グラフ（K5: 5ノードの完全グラフ）
G_complete = nx.complete_graph(5)
print(f"完全グラフ K5:")
print(f"  ノード数: {G_complete.number_of_nodes()}")
print(f"  エッジ数: {G_complete.number_of_edges()} (理論値: n(n-1)/2 = 10)\n")

# 木（二分木）
G_tree = nx.balanced_tree(r=2, h=3)  # r=分岐数, h=深さ
print(f"二分木 (深さ3):")
print(f"  ノード数: {G_tree.number_of_nodes()}")
print(f"  エッジ数: {G_tree.number_of_edges()}")
print(f"  木構造か: {nx.is_tree(G_tree)}\n")

# 二部グラフ
G_bipartite = nx.complete_bipartite_graph(3, 4)
print(f"完全二部グラフ K(3,4):")
print(f"  ノード数: {G_bipartite.number_of_nodes()}")
print(f"  エッジ数: {G_bipartite.number_of_edges()}")
print(f"  二部グラフか: {nx.is_bipartite(G_bipartite)}\n")

# グラフの可視化
fig, axes = plt.subplots(2, 3, figsize=(15, 10))

# 無向グラフ
nx.draw(G_undirected, ax=axes[0, 0], with_labels=True,
        node_color='lightblue', node_size=800, font_size=12)
axes[0, 0].set_title('無向グラフ', fontsize=14)

# 有向グラフ
nx.draw(G_directed, ax=axes[0, 1], with_labels=True,
        node_color='lightcoral', node_size=800, font_size=12,
        arrows=True, arrowsize=20)
axes[0, 1].set_title('有向グラフ', fontsize=14)

# 重み付きグラフ
pos = nx.spring_layout(G_weighted, seed=42)
nx.draw(G_weighted, pos, ax=axes[0, 2], with_labels=True,
        node_color='lightgreen', node_size=1000, font_size=10)
edge_labels = nx.get_edge_attributes(G_weighted, 'weight')
nx.draw_networkx_edge_labels(G_weighted, pos, edge_labels, ax=axes[0, 2])
axes[0, 2].set_title('重み付きグラフ', fontsize=14)

# 完全グラフ
nx.draw(G_complete, ax=axes[1, 0], with_labels=True,
        node_color='lightyellow', node_size=800)
axes[1, 0].set_title('完全グラフ K5', fontsize=14)

# 木
nx.draw(G_tree, ax=axes[1, 1], with_labels=True,
        node_color='lavender', node_size=600, font_size=8)
axes[1, 1].set_title('二分木 (深さ3)', fontsize=14)

# 二部グラフ
nx.draw(G_bipartite, ax=axes[1, 2], with_labels=True,
        node_color='peachpuff', node_size=600)
axes[1, 2].set_title('完全二部グラフ K(3,4)', fontsize=14)

plt.tight_layout()
plt.savefig('graph_types.png', dpi=150, bbox_inches='tight')
print("グラフを 'graph_types.png' に保存しました。")

実行結果の例

=== NetworkX によるグラフの基本操作 ===

無向グラフ:
  ノード数: 4
  エッジ数: 5
  ノード: ['A', 'B', 'C', 'D']
  エッジ: [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('C', 'D')]

有向グラフ:
  ノード数: 4
  エッジ数: 5
  ノードAの出次数: 2
  ノードAの入次数: 1

重み付きグラフ（都市間距離）:
  Tokyo - Osaka: 400km
  Tokyo - Nagoya: 350km
  Osaka - Nagoya: 180km
  Osaka - Fukuoka: 500km

=== 特殊なグラフの生成 ===

完全グラフ K5:
  ノード数: 5
  エッジ数: 10 (理論値: n(n-1)/2 = 10)

二分木 (深さ3):
  ノード数: 15
  エッジ数: 14
  木構造か: True

完全二部グラフ K(3,4):
  ノード数: 7
  エッジ数: 12
  二部グラフか: True

1.2 グラフの表現方法

3つの主要な表現形式

グラフをコンピュータで扱うには、適切なデータ構造で表現する必要があります。主な表現方法は以下の3つです：

1. 隣接行列（Adjacency Matrix）

$n$ 個のノードを持つグラフに対して、$n \times n$ の行列 $A$ で表現します：

$$ A_{ij} = \begin{cases} 1 & \text{if } (i, j) \in E \\ 0 & \text{otherwise} \end{cases} $$

特徴 ：

2. 隣接リスト（Adjacency List）

各ノードについて、隣接するノードのリストを保持します：

特徴 ：

3. エッジリスト（Edge List）

単純にエッジの集合として表現：$E = \{(u_1, v_1), (u_2, v_2), \ldots\}$

特徴 ：

操作隣接行列隣接リストエッジリスト
エッジの存在確認$O(1)$$O(d)$$O(m)$
隣接ノードの取得$O(n)$$O(d)$$O(m)$
全エッジの走査$O(n^2)$$O(n+m)$$O(m)$
メモリ使用量$O(n^2)$$O(n+m)$$O(m)$

※ $d$ はノードの次数、$m$ はエッジ数、$n$ はノード数

import networkx as nx
import numpy as np
import pandas as pd

print("=== グラフの表現方法の比較 ===\n")

# サンプルグラフの作成
G = nx.Graph()
edges = [
    ('A', 'B'), ('A', 'C'), ('A', 'D'),
    ('B', 'C'), ('C', 'D')
]
G.add_edges_from(edges)

print("グラフ構造:")
print(f"  ノード: {list(G.nodes())}")
print(f"  エッジ: {list(G.edges())}\n")

# 1. 隣接行列（Adjacency Matrix）
print("1. 隣接行列（Adjacency Matrix）")
print("-" * 40)
adj_matrix = nx.adjacency_matrix(G).todense()
node_list = sorted(G.nodes())

print("行列形式:")
df_adj = pd.DataFrame(adj_matrix, index=node_list, columns=node_list)
print(df_adj)

print("\nNumPy配列形式:")
print(adj_matrix)

# 隣接行列の性質
print(f"\n対称行列か: {np.allclose(adj_matrix, adj_matrix.T)}")
print(f"メモリ使用量: O(n²) = O({len(G.nodes())}²) = {len(G.nodes())**2} 要素")

# 2. 隣接リスト（Adjacency List）
print("\n2. 隣接リスト（Adjacency List）")
print("-" * 40)
adj_list = {node: list(G.neighbors(node)) for node in G.nodes()}
for node, neighbors in sorted(adj_list.items()):
    print(f"  {node}: {neighbors}")

print(f"\nメモリ使用量: O(n+m) = O({len(G.nodes())}+{len(G.edges())}) "
      f"= {len(G.nodes()) + len(G.edges())} 要素")

# 3. エッジリスト（Edge List）
print("\n3. エッジリスト（Edge List）")
print("-" * 40)
edge_list = list(G.edges())
for edge in edge_list:
    print(f"  {edge}")

print(f"\nメモリ使用量: O(m) = O({len(G.edges())}) = {len(G.edges())} エッジ")

# 4. 各表現での操作の比較
print("\n" + "=" * 50)
print("各表現での基本操作")
print("=" * 50)

# エッジの存在確認
print("\n【エッジの存在確認】")
u, v = 'A', 'C'
print(f"エッジ ({u}, {v}) は存在するか?\n")

# 隣接行列での確認
u_idx = node_list.index(u)
v_idx = node_list.index(v)
exists_matrix = adj_matrix[u_idx, v_idx] == 1
print(f"  隣接行列: {exists_matrix} (O(1) 時間)")

# 隣接リストでの確認
exists_list = v in adj_list[u]
print(f"  隣接リスト: {exists_list} (O(d) 時間)")

# エッジリストでの確認
exists_edges = (u, v) in edge_list or (v, u) in edge_list
print(f"  エッジリスト: {exists_edges} (O(m) 時間)")

# 隣接ノードの取得
print(f"\n【ノード {u} の隣接ノード】\n")

# 隣接行列から取得
neighbors_matrix = [node_list[i] for i in range(len(node_list))
                   if adj_matrix[u_idx, i] == 1]
print(f"  隣接行列: {neighbors_matrix} (O(n) 時間)")

# 隣接リストから取得
neighbors_list = adj_list[u]
print(f"  隣接リスト: {neighbors_list} (O(d) 時間)")

# エッジリストから取得
neighbors_edges = list(set([v for (s, t) in edge_list
                           for v in [s, t] if (s == u or t == u) and v != u]))
print(f"  エッジリスト: {neighbors_edges} (O(m) 時間)")

# 5. 有向グラフと重み付きグラフの表現
print("\n" + "=" * 50)
print("有向グラフと重み付きグラフの表現")
print("=" * 50)

# 有向グラフ
G_directed = nx.DiGraph()
G_directed.add_edges_from([('A', 'B'), ('B', 'C'), ('C', 'A')])

print("\n有向グラフの隣接行列:")
adj_directed = nx.adjacency_matrix(G_directed).todense()
print(pd.DataFrame(adj_directed,
                  index=sorted(G_directed.nodes()),
                  columns=sorted(G_directed.nodes())))
print(f"対称行列か: {np.allclose(adj_directed, adj_directed.T)}")

# 重み付きグラフ
G_weighted = nx.Graph()
G_weighted.add_weighted_edges_from([
    ('A', 'B', 0.5),
    ('A', 'C', 1.2),
    ('B', 'C', 0.8)
])

print("\n重み付きグラフの隣接行列:")
adj_weighted = nx.adjacency_matrix(G_weighted).todense()
print(pd.DataFrame(adj_weighted,
                  index=sorted(G_weighted.nodes()),
                  columns=sorted(G_weighted.nodes())))

print("\n重みを含む隣接リスト:")
for node in sorted(G_weighted.nodes()):
    neighbors_with_weight = [(neighbor, G_weighted[node][neighbor]['weight'])
                            for neighbor in G_weighted.neighbors(node)]
    print(f"  {node}: {neighbors_with_weight}")

実行結果の例

=== グラフの表現方法の比較 ===

グラフ構造:
  ノード: ['A', 'B', 'C', 'D']
  エッジ: [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('C', 'D')]

1. 隣接行列（Adjacency Matrix）
----------------------------------------
行列形式:
   A  B  C  D
A  0  1  1  1
B  1  0  1  0
C  1  1  0  1
D  1  0  1  0

対称行列か: True
メモリ使用量: O(n²) = O(4²) = 16 要素

2. 隣接リスト（Adjacency List）
----------------------------------------
  A: ['B', 'C', 'D']
  B: ['A', 'C']
  C: ['A', 'B', 'D']
  D: ['A', 'C']

メモリ使用量: O(n+m) = O(4+5) = 9 要素

3. エッジリスト（Edge List）
----------------------------------------
  ('A', 'B')
  ('A', 'C')
  ('A', 'D')
  ('B', 'C')
  ('C', 'D')

メモリ使用量: O(m) = O(5) = 5 エッジ

1.3 グラフの特徴量

ノードレベルの特徴量

グラフニューラルネットワークでは、ノードやエッジの特徴量が重要です。以下は代表的な特徴量です：

1. 次数（Degree）

ノード $v$ に接続されているエッジの数：

$$ d(v) = |\{u \in V : (v, u) \in E\}| $$

2. クラスタリング係数（Clustering Coefficient）

ノードの近傍がどれだけ密に接続されているかを示す指標：

$$ C(v) = \frac{2 \cdot |\{(u, w) : u, w \in N(v), (u, w) \in E\}|}{d(v) \cdot (d(v) - 1)} $$

$N(v)$ はノード $v$ の近傍ノード集合。値は $[0, 1]$ の範囲で、1に近いほど近傍が密に接続されています。

3. 中心性指標（Centrality Measures）

ノードの「重要度」を測る指標です：

中心性定義意味
次数中心性$C_D(v) = d(v)$接続数が多い = 重要
近接中心性$C_C(v) = \frac{n-1}{\sum_{u} d(v,u)}$他ノードへ近い = 重要
媒介中心性$C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$最短経路上にある = 重要
固有ベクトル中心性$A \mathbf{x} = \lambda \mathbf{x}$重要なノードと接続 = 重要
PageRank反復計算による重要度Google検索アルゴリズム
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

print("=== グラフの特徴量計算 ===\n")

# Zachary Karate Club グラフ（有名な社会ネットワーク）
G = nx.karate_club_graph()
print(f"Zachary Karate Club ネットワーク:")
print(f"  ノード数: {G.number_of_nodes()}")
print(f"  エッジ数: {G.number_of_edges()}\n")

# 1. 次数（Degree）
print("=" * 60)
print("1. 次数（Degree）")
print("=" * 60)

degrees = dict(G.degree())
print("\n各ノードの次数（上位5ノード）:")
sorted_degrees = sorted(degrees.items(), key=lambda x: x[1], reverse=True)
for node, degree in sorted_degrees[:5]:
    print(f"  ノード {node:2d}: 次数 {degree}")

avg_degree = np.mean(list(degrees.values()))
print(f"\n平均次数: {avg_degree:.2f}")

# 2. クラスタリング係数（Clustering Coefficient）
print("\n" + "=" * 60)
print("2. クラスタリング係数（Clustering Coefficient）")
print("=" * 60)

clustering_coeffs = nx.clustering(G)
print("\nクラスタリング係数（上位5ノード）:")
sorted_clustering = sorted(clustering_coeffs.items(),
                          key=lambda x: x[1], reverse=True)
for node, coeff in sorted_clustering[:5]:
    print(f"  ノード {node:2d}: {coeff:.3f}")

avg_clustering = nx.average_clustering(G)
print(f"\n平均クラスタリング係数: {avg_clustering:.3f}")

# 3. 中心性指標（Centrality Measures）
print("\n" + "=" * 60)
print("3. 中心性指標（Centrality Measures）")
print("=" * 60)

# 次数中心性
degree_centrality = nx.degree_centrality(G)
print("\n次数中心性（上位5ノード）:")
sorted_dc = sorted(degree_centrality.items(), key=lambda x: x[1], reverse=True)
for node, centrality in sorted_dc[:5]:
    print(f"  ノード {node:2d}: {centrality:.3f}")

# 近接中心性
closeness_centrality = nx.closeness_centrality(G)
print("\n近接中心性（上位5ノード）:")
sorted_cc = sorted(closeness_centrality.items(), key=lambda x: x[1], reverse=True)
for node, centrality in sorted_cc[:5]:
    print(f"  ノード {node:2d}: {centrality:.3f}")

# 媒介中心性
betweenness_centrality = nx.betweenness_centrality(G)
print("\n媒介中心性（上位5ノード）:")
sorted_bc = sorted(betweenness_centrality.items(), key=lambda x: x[1], reverse=True)
for node, centrality in sorted_bc[:5]:
    print(f"  ノード {node:2d}: {centrality:.3f}")

# 固有ベクトル中心性
eigenvector_centrality = nx.eigenvector_centrality(G)
print("\n固有ベクトル中心性（上位5ノード）:")
sorted_ec = sorted(eigenvector_centrality.items(), key=lambda x: x[1], reverse=True)
for node, centrality in sorted_ec[:5]:
    print(f"  ノード {node:2d}: {centrality:.3f}")

# PageRank
pagerank = nx.pagerank(G)
print("\nPageRank（上位5ノード）:")
sorted_pr = sorted(pagerank.items(), key=lambda x: x[1], reverse=True)
for node, rank in sorted_pr[:5]:
    print(f"  ノード {node:2d}: {rank:.3f}")

# 4. グラフレベルの特徴量
print("\n" + "=" * 60)
print("4. グラフレベルの特徴量")
print("=" * 60)

# 直径（Diameter）：最長の最短経路
diameter = nx.diameter(G)
print(f"\n直径（Diameter）: {diameter}")

# 平均最短経路長
avg_shortest_path = nx.average_shortest_path_length(G)
print(f"平均最短経路長: {avg_shortest_path:.3f}")

# 密度（Density）
density = nx.density(G)
print(f"密度（Density）: {density:.3f}")

# 推移性（Transitivity）：グラフ全体のクラスタリング係数
transitivity = nx.transitivity(G)
print(f"推移性（Transitivity）: {transitivity:.3f}")

# 連結成分数
num_components = nx.number_connected_components(G)
print(f"連結成分数: {num_components}")

# 5. 可視化：中心性指標の比較
fig, axes = plt.subplots(2, 3, figsize=(18, 12))

pos = nx.spring_layout(G, seed=42)

# ノードサイズを中心性で調整
def draw_with_centrality(ax, centrality, title):
    node_sizes = [v * 3000 for v in centrality.values()]
    nx.draw(G, pos, ax=ax, node_size=node_sizes,
            node_color=list(centrality.values()),
            cmap='YlOrRd', with_labels=True, font_size=8,
            edge_color='gray', alpha=0.6)
    ax.set_title(title, fontsize=14, fontweight='bold')

draw_with_centrality(axes[0, 0], degree_centrality, '次数中心性')
draw_with_centrality(axes[0, 1], closeness_centrality, '近接中心性')
draw_with_centrality(axes[0, 2], betweenness_centrality, '媒介中心性')
draw_with_centrality(axes[1, 0], eigenvector_centrality, '固有ベクトル中心性')
draw_with_centrality(axes[1, 1], pagerank, 'PageRank')

# 次数分布
axes[1, 2].hist(list(degrees.values()), bins=15, color='skyblue', edgecolor='black')
axes[1, 2].set_xlabel('次数', fontsize=12)
axes[1, 2].set_ylabel('頻度', fontsize=12)
axes[1, 2].set_title('次数分布', fontsize=14, fontweight='bold')
axes[1, 2].grid(alpha=0.3)

plt.tight_layout()
plt.savefig('graph_features.png', dpi=150, bbox_inches='tight')
print("\n可視化を 'graph_features.png' に保存しました。")

実行結果の例

=== グラフの特徴量計算 ===

Zachary Karate Club ネットワーク:
  ノード数: 34
  エッジ数: 78

============================================================
1. 次数（Degree）
============================================================

各ノードの次数（上位5ノード）:
  ノード 33: 次数 17
  ノード  0: 次数 16
  ノード 32: 次数 12
  ノード  2: 次数 10
  ノード  1: 次数 9

平均次数: 4.59

============================================================
2. クラスタリング係数（Clustering Coefficient）
============================================================

クラスタリング係数（上位5ノード）:
  ノード  5: 0.667
  ノード  6: 0.600
  ノード 11: 0.545
  ノード  4: 0.500
  ノード 10: 0.467

平均クラスタリング係数: 0.571

============================================================
3. 中心性指標（Centrality Measures）
============================================================

次数中心性（上位5ノード）:
  ノード 33: 0.515
  ノード  0: 0.485
  ノード 32: 0.364
  ノード  2: 0.303
  ノード  1: 0.273

媒介中心性（上位5ノード）:
  ノード  0: 0.438
  ノード 33: 0.304
  ノード 32: 0.145
  ノード  2: 0.143
  ノード 31: 0.138

PageRank（上位5ノード）:
  ノード 33: 0.101
  ノード  0: 0.097
  ノード 32: 0.071
  ノード  2: 0.057
  ノード  1: 0.053

PageRankアルゴリズムの実装

PageRankは、Webページの重要度を計算するGoogleの検索アルゴリズムです。基本的なアイデアは：

「重要なページからリンクされているページは重要である」

PageRankは反復計算により求められます：

$$ PR(v) = \frac{1-d}{N} + d \sum_{u \in N_{in}(v)} \frac{PR(u)}{d_{out}(u)} $$

ここで：

1.4 グラフ埋め込み（Graph Embedding）

なぜグラフ埋め込みが必要か

グラフ構造データを機械学習モデルで扱うには、ノードやグラフ全体を低次元の連続ベクトル空間に埋め込む必要があります：

「グラフ埋め込みは、グラフの構造情報を保持しながら、ノードを低次元ベクトル表現に変換する技術である。」

グラフ埋め込みの目標

手法アプローチ特徴
DeepWalkランダムウォーク + Skip-gram無向グラフ、構造の保持
Node2Vecバイアス付きランダムウォークBFS/DFS の制御可能
LINE1次・2次近接性の保持大規模グラフに効率的
GCNグラフ畳み込みノード特徴量を活用
GraphSAGE近傍サンプリング + 集約帰納的学習が可能

DeepWalkとNode2Vec

DeepWalkの基本アイデア

  1. グラフ上でランダムウォークを実行してノード系列を生成
  2. この系列を「文」と見なし、Word2Vec（Skip-gram）を適用
  3. 近傍ノードが埋め込み空間でも近くになるように学習

目的関数：

$$ \max_f \sum_{v \in V} \log P(N(v) | f(v)) $$

ここで $N(v)$ はランダムウォークで訪れたノード $v$ の近傍、$f(v)$ はノード $v$ の埋め込みベクトル。

Node2Vecの改良点

Node2Vecは、ランダムウォークにバイアスを導入します：

パラメータ設定探索の特性捉える構造
$p$ 低, $q$ 高BFS的（広い探索）局所的なコミュニティ構造
$p$ 高, $q$ 低DFS的（深い探索）グローバルな構造、役割
import networkx as nx
import numpy as np
from sklearn.manifold import TSNE
from sklearn.decomposition import PCA
import matplotlib.pyplot as plt
from collections import defaultdict

print("=== DeepWalk / Node2Vec 風の実装 ===\n")

class SimpleNode2Vec:
    """
    Node2Vecの簡易実装
    """
    def __init__(self, G, embedding_dim=128, walk_length=80,
                 num_walks=10, p=1.0, q=1.0, window_size=10):
        """
        Parameters:
        -----------
        G : NetworkX graph
        embedding_dim : int
            埋め込み次元数
        walk_length : int
            1回のランダムウォークの長さ
        num_walks : int
            各ノードから開始するウォーク数
        p : float
            Return parameter（直前のノードに戻る確率の逆数）
        q : float
            In-out parameter（BFS vs DFS）
        window_size : int
            Skip-gramのウィンドウサイズ
        """
        self.G = G
        self.embedding_dim = embedding_dim
        self.walk_length = walk_length
        self.num_walks = num_walks
        self.p = p
        self.q = q
        self.window_size = window_size
        self.embeddings = None

    def _get_alias_edge(self, src, dst):
        """
        エッジの遷移確率を計算（Node2Vecのバイアス付き）
        """
        G = self.G
        p = self.p
        q = self.q

        unnormalized_probs = []
        for dst_nbr in G.neighbors(dst):
            if dst_nbr == src:
                # 直前のノードに戻る
                unnormalized_probs.append(1.0 / p)
            elif G.has_edge(dst_nbr, src):
                # 距離1のノード（共通の隣接ノード）
                unnormalized_probs.append(1.0)
            else:
                # 距離2のノード
                unnormalized_probs.append(1.0 / q)

        norm_const = sum(unnormalized_probs)
        normalized_probs = [float(u_prob) / norm_const
                          for u_prob in unnormalized_probs]

        return list(G.neighbors(dst)), normalized_probs

    def _node2vec_walk(self, start_node):
        """
        1回のNode2Vecランダムウォークを実行
        """
        G = self.G
        walk = [start_node]

        while len(walk) < self.walk_length:
            cur = walk[-1]
            cur_nbrs = list(G.neighbors(cur))

            if len(cur_nbrs) == 0:
                break

            if len(walk) == 1:
                # 最初のステップ：一様ランダムに選択
                walk.append(np.random.choice(cur_nbrs))
            else:
                # 2ステップ目以降：バイアス付き選択
                prev = walk[-2]
                neighbors, probs = self._get_alias_edge(prev, cur)
                walk.append(np.random.choice(neighbors, p=probs))

        return walk

    def _generate_walks(self):
        """
        全ノードからランダムウォークを生成
        """
        walks = []
        nodes = list(self.G.nodes())

        print(f"ランダムウォークを生成中...")
        print(f"  各ノードから {self.num_walks} 回のウォーク")
        print(f"  ウォーク長: {self.walk_length}")
        print(f"  p={self.p}, q={self.q}\n")

        for walk_iter in range(self.num_walks):
            np.random.shuffle(nodes)
            for node in nodes:
                walks.append(self._node2vec_walk(node))

        print(f"生成完了: {len(walks)} 個のウォーク\n")
        return walks

    def _skipgram_training(self, walks):
        """
        Skip-gram風の学習（簡易版）
        実際にはWord2VecやGensimを使用するが、ここでは説明用に簡略化
        """
        nodes = list(self.G.nodes())
        node_to_idx = {node: idx for idx, node in enumerate(nodes)}

        # ランダムに初期化
        embeddings = np.random.randn(len(nodes), self.embedding_dim) * 0.01

        print("Skip-gram学習中（簡易版）...")

        # 共起カウント
        cooccurrence = defaultdict(lambda: defaultdict(int))

        for walk in walks:
            for i, node in enumerate(walk):
                # ウィンドウ内のノードをカウント
                start = max(0, i - self.window_size)
                end = min(len(walk), i + self.window_size + 1)

                for j in range(start, end):
                    if i != j:
                        context_node = walk[j]
                        cooccurrence[node][context_node] += 1

        # 簡易的な埋め込み学習（実際はネガティブサンプリングなど使用）
        # ここでは共起頻度の高いノード対が近くなるように調整
        learning_rate = 0.01
        epochs = 5

        for epoch in range(epochs):
            for node in nodes:
                node_idx = node_to_idx[node]

                for context_node, count in cooccurrence[node].items():
                    context_idx = node_to_idx[context_node]

                    # 簡易的な勾配更新（実際はもっと複雑）
                    diff = embeddings[context_idx] - embeddings[node_idx]
                    embeddings[node_idx] += learning_rate * count * diff * 0.01

            if (epoch + 1) % 2 == 0:
                print(f"  Epoch {epoch + 1}/{epochs} 完了")

        print("学習完了\n")
        return embeddings

    def fit(self):
        """
        Node2Vec埋め込みを学習
        """
        walks = self._generate_walks()
        self.embeddings = self._skipgram_training(walks)
        return self

    def get_embeddings(self):
        """
        学習済み埋め込みを取得
        """
        if self.embeddings is None:
            raise ValueError("まず fit() を実行してください")

        nodes = list(self.G.nodes())
        return {node: self.embeddings[i] for i, node in enumerate(nodes)}

# テスト：Karate Clubグラフ
print("=" * 60)
print("Zachary Karate Club での Node2Vec")
print("=" * 60 + "\n")

G = nx.karate_club_graph()
print(f"グラフ情報:")
print(f"  ノード数: {G.number_of_nodes()}")
print(f"  エッジ数: {G.number_of_edges()}\n")

# Node2Vec学習
model = SimpleNode2Vec(
    G,
    embedding_dim=64,
    walk_length=30,
    num_walks=10,
    p=1.0,  # DeepWalk相当
    q=1.0,
    window_size=5
)

model.fit()
embeddings_dict = model.get_embeddings()

# 埋め込みベクトルを配列に変換
nodes = list(G.nodes())
embeddings = np.array([embeddings_dict[node] for node in nodes])

print(f"埋め込み結果:")
print(f"  形状: {embeddings.shape}")
print(f"  最初のノードの埋め込み（最初の5次元）: {embeddings[0, :5]}\n")

# t-SNEで2次元に可視化
print("t-SNEで2次元に削減中...")
tsne = TSNE(n_components=2, random_state=42, perplexity=15)
embeddings_2d = tsne.fit_transform(embeddings)
print("完了\n")

# 可視化
fig, axes = plt.subplots(1, 2, figsize=(16, 7))

# 左：元のグラフ
pos = nx.spring_layout(G, seed=42)
node_colors = [G.nodes[node]['club'] for node in G.nodes()]
nx.draw(G, pos, ax=axes[0],
        node_color=node_colors,
        cmap='Set1',
        with_labels=True,
        node_size=400,
        font_size=8,
        edge_color='gray',
        alpha=0.7)
axes[0].set_title('元のグラフ構造\n（色 = 所属クラブ）',
                  fontsize=14, fontweight='bold')

# 右：埋め込み空間での可視化
scatter = axes[1].scatter(embeddings_2d[:, 0], embeddings_2d[:, 1],
                         c=node_colors, cmap='Set1',
                         s=200, alpha=0.7, edgecolors='black')

for i, node in enumerate(nodes):
    axes[1].annotate(str(node),
                    (embeddings_2d[i, 0], embeddings_2d[i, 1]),
                    fontsize=8, ha='center', va='center')

axes[1].set_xlabel('t-SNE 次元 1', fontsize=12)
axes[1].set_ylabel('t-SNE 次元 2', fontsize=12)
axes[1].set_title('Node2Vec 埋め込み空間\n（t-SNE可視化）',
                  fontsize=14, fontweight='bold')
axes[1].grid(alpha=0.3)

plt.tight_layout()
plt.savefig('node2vec_embedding.png', dpi=150, bbox_inches='tight')
print("可視化を 'node2vec_embedding.png' に保存しました。")

1.5 実践：ソーシャルネットワーク分析

コミュニティ検出

ソーシャルネットワークには、密に接続されたノードの集団（コミュニティ）が存在します。コミュニティ検出は、このような構造を自動的に発見する手法です。

主なアルゴリズム

モジュラリティ（Modularity）

コミュニティ構造の品質を評価する指標：

$$ Q = \frac{1}{2m} \sum_{ij} \left[A_{ij} - \frac{k_i k_j}{2m}\right] \delta(c_i, c_j) $$

ここで：

リンク予測は、グラフ内で将来形成される可能性のあるエッジを予測するタスクです。推薦システムや知識グラフの補完に応用されます。

基本的なアプローチ

  1. 共通隣接数 ：共通の友人が多いほど繋がりやすい
  2. Jaccard係数 ：隣接ノード集合の類似度
  3. Adamic-Adar指数 ：共通隣接の希少性を考慮
  4. Preferential Attachment ：次数の積（人気者同士が繋がる）
import networkx as nx
import numpy as np
from sklearn.metrics import roc_auc_score, average_precision_score
import matplotlib.pyplot as plt

print("=== リンク予測（Link Prediction）===\n")

# グラフの準備
G_original = nx.karate_club_graph()
print(f"元のグラフ:")
print(f"  ノード数: {G_original.number_of_nodes()}")
print(f"  エッジ数: {G_original.number_of_edges()}\n")

# エッジを訓練用とテスト用に分割
print("エッジ分割:")
edges = list(G_original.edges())
np.random.seed(42)
np.random.shuffle(edges)

# 80%を訓練、20%をテスト
split_idx = int(0.8 * len(edges))
train_edges = edges[:split_idx]
test_edges = edges[split_idx:]

print(f"  訓練エッジ: {len(train_edges)}")
print(f"  テストエッジ: {len(test_edges)}\n")

# 訓練用グラフの作成
G_train = nx.Graph()
G_train.add_nodes_from(G_original.nodes())
G_train.add_edges_from(train_edges)

print(f"訓練グラフ:")
print(f"  ノード数: {G_train.number_of_nodes()}")
print(f"  エッジ数: {G_train.number_of_edges()}\n")

# 負例の生成（存在しないエッジ）
def generate_negative_edges(G, num_samples):
    """存在しないエッジをサンプリング"""
    non_edges = list(nx.non_edges(G))
    return [non_edges[i] for i in np.random.choice(
        len(non_edges), size=min(num_samples, len(non_edges)), replace=False
    )]

negative_edges = generate_negative_edges(G_train, len(test_edges))
print(f"負例エッジ: {len(negative_edges)}\n")

# リンク予測スコアの計算
print("=" * 60)
print("リンク予測手法の評価")
print("=" * 60 + "\n")

def evaluate_link_prediction(scores, test_edges, negative_edges):
    """
    リンク予測の評価
    """
    # テストエッジ（正例）のスコア
    positive_scores = [scores.get((u, v), scores.get((v, u), 0))
                      for u, v in test_edges]

    # 負例エッジのスコア
    negative_scores = [scores.get((u, v), scores.get((v, u), 0))
                      for u, v in negative_edges]

    # ラベルとスコアを結合
    y_true = [1] * len(positive_scores) + [0] * len(negative_scores)
    y_scores = positive_scores + negative_scores

    # 評価指標
    auc = roc_auc_score(y_true, y_scores)
    ap = average_precision_score(y_true, y_scores)

    return auc, ap, y_scores, y_true

# 1. 共通隣接数（Common Neighbors）
print("1. 共通隣接数（Common Neighbors）")
print("-" * 40)
cn_scores = {}
for u, v in test_edges + negative_edges:
    common_neighbors = len(list(nx.common_neighbors(G_train, u, v)))
    cn_scores[(u, v)] = common_neighbors

auc_cn, ap_cn, _, _ = evaluate_link_prediction(cn_scores, test_edges, negative_edges)
print(f"AUC: {auc_cn:.4f}")
print(f"Average Precision: {ap_cn:.4f}\n")

# 2. Jaccard係数
print("2. Jaccard係数")
print("-" * 40)
jaccard_scores = {}
for u, v in test_edges + negative_edges:
    preds = list(nx.jaccard_coefficient(G_train, [(u, v)]))
    jaccard_scores[(u, v)] = preds[0][2] if preds else 0

auc_jc, ap_jc, _, _ = evaluate_link_prediction(jaccard_scores, test_edges, negative_edges)
print(f"AUC: {auc_jc:.4f}")
print(f"Average Precision: {ap_jc:.4f}\n")

# 3. Adamic-Adar指数
print("3. Adamic-Adar指数")
print("-" * 40)
aa_scores = {}
for u, v in test_edges + negative_edges:
    preds = list(nx.adamic_adar_index(G_train, [(u, v)]))
    aa_scores[(u, v)] = preds[0][2] if preds else 0

auc_aa, ap_aa, _, _ = evaluate_link_prediction(aa_scores, test_edges, negative_edges)
print(f"AUC: {auc_aa:.4f}")
print(f"Average Precision: {ap_aa:.4f}\n")

# 4. Preferential Attachment
print("4. Preferential Attachment")
print("-" * 40)
pa_scores = {}
for u, v in test_edges + negative_edges:
    preds = list(nx.preferential_attachment(G_train, [(u, v)]))
    pa_scores[(u, v)] = preds[0][2] if preds else 0

auc_pa, ap_pa, _, _ = evaluate_link_prediction(pa_scores, test_edges, negative_edges)
print(f"AUC: {auc_pa:.4f}")
print(f"Average Precision: {ap_pa:.4f}\n")

# 結果の可視化
fig, axes = plt.subplots(1, 2, figsize=(14, 6))

# 手法の比較
methods = ['Common\nNeighbors', 'Jaccard', 'Adamic-\nAdar', 'Preferential\nAttachment']
aucs = [auc_cn, auc_jc, auc_aa, auc_pa]
aps = [ap_cn, ap_jc, ap_aa, ap_pa]

x = np.arange(len(methods))
width = 0.35

bars1 = axes[0].bar(x - width/2, aucs, width, label='AUC', color='steelblue')
bars2 = axes[0].bar(x + width/2, aps, width, label='Average Precision', color='coral')

axes[0].set_xlabel('手法', fontsize=12)
axes[0].set_ylabel('スコア', fontsize=12)
axes[0].set_title('リンク予測手法の性能比較', fontsize=14, fontweight='bold')
axes[0].set_xticks(x)
axes[0].set_xticklabels(methods, fontsize=10)
axes[0].legend()
axes[0].grid(axis='y', alpha=0.3)
axes[0].set_ylim([0, 1.0])

# 値をバーに表示
for bars in [bars1, bars2]:
    for bar in bars:
        height = bar.get_height()
        axes[0].text(bar.get_x() + bar.get_width()/2., height,
                    f'{height:.3f}',
                    ha='center', va='bottom', fontsize=9)

# グラフ可視化（訓練グラフとテストエッジ）
pos = nx.spring_layout(G_original, seed=42)

# 訓練エッジ
nx.draw_networkx_edges(G_train, pos, ax=axes[1],
                       edge_color='gray', alpha=0.3, width=1)

# テストエッジ（正例）
nx.draw_networkx_edges(G_original, pos, ax=axes[1],
                       edgelist=test_edges,
                       edge_color='green', width=2, alpha=0.7,
                       label='テストエッジ（正例）')

# ノード
nx.draw_networkx_nodes(G_original, pos, ax=axes[1],
                      node_color='lightblue', node_size=300)
nx.draw_networkx_labels(G_original, pos, ax=axes[1], font_size=8)

axes[1].set_title('訓練グラフとテストエッジ', fontsize=14, fontweight='bold')
axes[1].legend(loc='upper right', fontsize=10)
axes[1].axis('off')

plt.tight_layout()
plt.savefig('link_prediction.png', dpi=150, bbox_inches='tight')
print("可視化を 'link_prediction.png' に保存しました。")

演習問題

演習1：グラフの基本操作

問題 ：以下の条件を満たすグラフを作成し、その特徴を分析してください。

演習2：グラフ表現の変換

問題 ：以下のエッジリストで定義されるグラフを、隣接行列と隣接リストの両方で表現してください。

エッジリスト: [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]

演習3：PageRankの実装と検証

問題 ：簡単な有向グラフに対してPageRankを手動計算し、NetworkXの結果と比較してください。

import networkx as nx

G = nx.DiGraph()
G.add_edges_from([('A', 'B'), ('B', 'C'), ('C', 'A'), ('B', 'D')])

# 1. 手動でPageRankを3回反復計算
# 2. NetworkXのPageRankと比較
# 3. 収束までに何回の反復が必要か調査

演習4：コミュニティ検出の比較

問題 ：Louvain法とLabel Propagationで検出されたコミュニティの違いを分析してください。

演習5：Node2Vecのパラメータ調整

問題 ：Node2Vecの $p$ と $q$ パラメータを変えて、埋め込み結果がどう変わるか観察してください。

演習6：リンク予測の実装

問題 ：独自のグラフに対してリンク予測を実装し、異なる手法の性能を比較してください。

まとめ

この章では、グラフとグラフ表現学習の基礎を学びました：

次章では、これらの基礎知識を踏まえて、グラフニューラルネットワーク（GNN） の基本原理を学びます。グラフ畳み込みの仕組み、メッセージパッシング、近傍集約など、GNNの核心的な概念を理解していきます。

重要なポイント ：グラフ構造データは、画像や自然言語とは異なる特性を持ちます。可変サイズ、非ユークリッド構造、置換不変性などの性質を理解することが、GNNを効果的に使う鍵となります。

シリーズ目次に戻る 次の章 →
🎬 この章を動画で見る