networkx

NetworkX - ネットワーク分析とグラフ理論

NetworkX は、複雑なネットワークを分析するための定番ライブラリです。グラフを、ノード（ハッシュ可能な任意のオブジェクト）とエッジを格納する柔軟なコンテナーとして扱い、ノードやエッジには任意のメタデータを付与できます。

使用する場面

• ソーシャルネットワーク、生物学的ネットワーク、インフラネットワークを分析する場合。
• 経路に関する指標（最短経路、直径、フロー）を計算する場合。
• ノードの重要度（中心性、PageRank）を測定する場合。
• ネットワーク内のコミュニティやクラスターを検出する場合。
• ランダムグラフモデル（Erdős-Rényi、Barabási-Albert）を生成する場合。
• 連結成分やクリークを見つける場合。
• ルーティングや依存関係ツリーを設計、最適化する場合。

リファレンスドキュメント

公式ドキュメント: https://networkx.org/
アルゴリズムのリファレンス: https://networkx.org/documentation/stable/reference/algorithms/index.html
検索パターン: nx.Graph、nx.shortest_path、nx.degree_centrality、nx.connected_components

基本原則

グラフの種類

クラス	説明
Graph	無向グラフです。同じ自己ループを2回追加しても無視されます。
DiGraph	有向グラフです。エッジには特定の方向があります（A → B ≠ B → A）。
MultiGraph	無向グラフです。同じ2つのノード間に複数のエッジを設定できます。
MultiDiGraph	有向グラフです。ノード間に複数の有向エッジを設定できます。

ノードとエッジ

• ノード：ハッシュ可能な任意の Python オブジェクト（文字列、数値、タプル、さらにはオブジェクト）を使用できます。
• エッジ：2つのノード間の関係を表します。重み、容量、ラベルなどの属性を格納できます。

クイックリファレンス

インストール

pip install networkx matplotlib scipy

標準のインポート

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

基本パターン - 作成と分析

import networkx as nx

# 1. Create a graph
G = nx.Graph()

# 2. Add edges (nodes are created automatically)
G.add_edge("A", "B", weight=4.5)
G.add_edges_from([("B", "C"), ("C", "A"), ("C", "D")])

# 3. Analyze
print(f"Nodes: {G.number_of_nodes()}")
print(f"Shortest path A to D: {nx.shortest_path(G, 'A', 'D')}")

# 4. Draw
nx.draw(G, with_labels=True)

重要なルール

✅ 推奨事項

• 重み付きエッジを使う - 現実世界の距離やコストを分析する場合に使用します。
• 連結性を確認する - 単一の連結成分を前提とするアルゴリズムを実行する前に、必ず nx.is_connected(G) を確認します。
• 適切なクラスを選ぶ - 相互作用の方向が重要な場合（ウェブサイトのリンク、代謝経路など）は、DiGraph を使用します。
• 疎行列を使う - 大規模な計算では、nx.to_scipy_sparse_array を使用して SciPy の疎行列にエクスポートします。
• 属性にアクセスする - メタデータの保存や取得には、G.nodes[n]['attr'] または G.edges[u, v]['attr'] を使用します。
• ノードの不変性を保つ - ノードオブジェクトがハッシュ可能であり、キーとして使用する場合に状態が変化しないことを確認します。

❌ 非推奨事項

• 高性能な可視化に使わない - nx.draw は小規模なデバッグ用プロット向けです。大規模な可視化には Gephi または Cytoscape を使用します。
• 経路を手動でループ処理しない - 独自の BFS/DFS の実装は避けます。NetworkX の組み込みアルゴリズムは高度に最適化されています。
• ノードに大きなオブジェクトを格納しない - ノードはシンプルな ID にし、メモリ節約のため、複雑なデータは可能であれば別の辞書に格納します。
• グラフジェネレーターを無視しない - 複雑な合成グラフを手作業で作成せず、nx.random_graphs を使用します。

アンチパターン（絶対に避ける）

import networkx as nx

# ❌ BAD: Manual neighbor iteration for degree calculation
count = 0
for n in G.nodes():
    for neighbor in G.neighbors(n):
        count += 1

# ✅ GOOD: Use built-in degree property
degrees = dict(G.degree())

# ❌ BAD: Re-calculating shortest paths in a loop
for target in targets:
    path = nx.dijkstra_path(G, source, target) # Re-scans graph every time

# ✅ GOOD: Calculate single-source shortest paths once
paths = nx.single_source_dijkstra_path(G, source)
# 'paths' now contains the shortest path to every reachable node

# ❌ BAD: Using lists for edges in large graphs
# (Creating a graph from a massive edge list one by one is slow)

# ✅ GOOD: Bulk loading
G.add_edges_from(edge_list)

アルゴリズムの詳細

最短経路とフロー

# Shortest path with weights (Dijkstra)
path = nx.shortest_path(G, source="A", target="D", weight="weight")
length = nx.shortest_path_length(G, source="A", target="D", weight="weight")

# All-pairs shortest paths (returns a generator)
all_paths = dict(nx.all_pairs_dijkstra_path(G))

# Max Flow / Min Cut
from networkx.algorithms.flow import preflow_push
flow_value, flow_dict = nx.maximum_flow(G, "source_node", "sink_node", capacity="cap")

中心性と重要度

# Degree Centrality (fraction of nodes it's connected to)
deg_cent = nx.degree_centrality(G)

# Betweenness Centrality (importance as a bridge/bottleneck)
bet_cent = nx.betweenness_centrality(G)

# PageRank (influence in directed networks)
pagerank = nx.pagerank(G, alpha=0.85)

# Eigenvector Centrality
eig_cent = nx.eigenvector_centrality(G)

コミュニティ検出とクラスタリング

# Clustering coefficient (measure of "tightness")
avg_clustering = nx.average_clustering(G)

# Community detection (Girvan-Newman)
from networkx.algorithms import community
comp = community.girvan_newman(G)
top_level_communities = next(comp)

# Louvain Community Detection (standard for large networks)
# requires: pip install python-louvain
communities = community.louvain_communities(G)

連結性と連結成分

# Undirected components
components = list(nx.connected_components(G))
largest_cc = max(components, key=len)

# Directed connectivity
is_strong = nx.is_strongly_connected(DG) # Path in both directions
is_weak = nx.is_weakly_connected(DG)     # Path if direction is ignored

# Cliques (fully connected subgraphs)
cliques = list(nx.find_cliques(G))

グラフの入出力と相互運用性

フォーマットとコンバーター

# Reading/Writing files
nx.write_gexf(G, "network.gexf")   # For Gephi
nx.write_graphml(G, "data.graphml") # For general graph tools
G = nx.read_edgelist("edges.txt")   # From simple text file

# Integration with Pandas
df = nx.to_pandas_edgelist(G)
G_new = nx.from_pandas_edgelist(df, source='source', target='target', edge_attr='weight')

# Integration with NumPy/SciPy
adj_matrix = nx.to_numpy_array(G)
sparse_adj = nx.to_scipy_sparse_array(G)

実践的なワークフロー

1. タンパク質間相互作用（PPI）ネットワークの分析

def analyze_ppi(edge_list_file):
    G = nx.read_edgelist(edge_list_file)
    
    # 1. Basic stats
    print(f"Network density: {nx.density(G):.4f}")
    
    # 2. Find hubs (high degree)
    degree_dict = dict(G.degree())
    hubs = sorted(degree_dict.items(), key=lambda x: x[1], reverse=True)[:10]
    
    # 3. Find essential clusters
    communities = nx.community.louvain_communities(G)
    
    # 4. Check for articulation points (bottlenecks)
    bottlenecks = list(nx.articulation_points(G))
    
    return hubs, communities, bottlenecks

2. 制約付きの交通ルート設定

def find_route(G, start, end, max_load):
    """Find shortest path that respects a capacity constraint."""
    # Filter edges by capacity
    view = nx.subgraph_view(G, filter_edge=lambda u, v: G[u][v]['capacity'] >= max_load)
    
    if not nx.has_path(view, start, end):
        return None
    
    return nx.shortest_path(view, start, end, weight='distance')

3. 階層構造の可視化

def plot_tree(G, root):
    """Custom layout for tree-like structures."""
    pos = nx.spring_layout(G) # Basic layout
    # Or use graphviz for better tree layouts
    # pos = nx.nx_agraph.graphviz_layout(G, prog='dot')
    
    plt.figure(figsize=(12, 8))
    nx.draw(G, pos, with_labels=True, node_color='lightblue', 
            node_size=500, font_size=10, arrowsize=20)
    plt.show()

パフォーマンスの最適化

グラフビューの使用

ノードやエッジをフィルタリングする際にグラフのコピーを作成する代わりに、時間とメモリの計算量が O(1) の「ビュー」を使用します。

# Create a view of the graph with only heavy edges
heavy_edges = nx.subgraph_view(G, filter_edge=lambda u, v: G[u][v]['weight'] > 10)

効率的なノードアクセス

ノードとその属性を反復処理する際は、data=True を使用します。

# Faster than calling G.nodes[n] inside the loop
for n, attrs in G.nodes(data=True):
    if attrs.get('type') == 'target':
        do_something(n)

よくある落とし穴と解決策

反復処理中の辞書の変更

# ❌ Problem: Changing the graph while looping over nodes
for n in G.nodes():
    if G.degree(n) == 0:
        G.remove_node(n) # Error!

# ✅ Solution: Convert nodes to a list first
for n in list(G.nodes()):
    if G.degree(n) == 0:
        G.remove_node(n)

単純な Graph における自己ループと複数エッジ

# ❌ Problem: Adding a second edge between A and B in nx.Graph() 
G.add_edge("A", "B", weight=10)
G.add_edge("A", "B", weight=20) # Overwrites the first weight!

# ✅ Solution: Use MultiGraph if multiple relations exist
MG = nx.MultiGraph()
MG.add_edge("A", "B", weight=10)
MG.add_edge("A", "B", weight=20) # Both are preserved

フローアルゴリズムにおける方向性

# ❌ Problem: Running PageRank on an Undirected graph
# It works, but it's just a scaled degree centrality.

# ✅ Solution: Ensure you use DiGraph for influence metrics
DG = nx.DiGraph(G) # Converts undirected to directed with symmetric edges

NetworkX は、使いやすさとアルゴリズムの深さを完璧なバランスで備えています。小さな論理パズルを解く場合でも、複雑な生物学的システムを分析する場合でも、データの基盤となる構造を理解するためのツールを提供します。