有向ネットワーク入門：定義・表現・中心性・アルゴリズムから応用までを網羅する総合ガイド
エバープレイ編集部有向ネットワークとは — 概要と定義
有向ネットワーク（有向グラフ、directed network / directed graph）は、ノード（頂点）と辺（エッジ）から成るネットワークの一種で、各辺に向き（方向性）が付与されているものを指します。数学的には頂点集合 V と有向辺集合 E ⊆ V × V の組 (V, E) として表され、辺 (u, v) は u → v の向きで情報・影響・資源などが流れることを意味します。
基本用語と表現
- 出次数（out-degree）：あるノードから出て行く有向辺の数。
- 入次数（in-degree）：あるノードに入ってくる有向辺の数。
- 隣接行列（adjacency matrix）：n×n 行列 A で、A[i][j]=1（あるいは重み）なら i→j の辺が存在する。一般に非対称になり得る。
- パスとサイクル：有向パスは向きに従って連続する辺の列。向きに従わないと通過できない。向きに沿ったサイクルは有向サイクル。
- 強連結・弱連結：任意のノード間で双方向の有向パスが存在するなら強連結。辺の向きを無視したときに連結なら弱連結。
行列表現とスペクトル的性質
有向ネットワークは隣接行列 A（非対称一般）で表現され、ここから多くの解析が可能です。非負行列に対してはベルンハルト・フォン・ペロン、フロベニウスの定理（Perron–Frobenius）が適用でき、最大固有値と対応する固有ベクトルが中心性や拡散過程の長期振る舞いを決めます。
また、Markov 遷移行列（行確率・列確率で定義）を用いるとランダムウォークや PageRank のような尺度が得られます。PageRank は遷移確率行列に遷移先のランダムテレポート（ランダムジャンプ）を組み合わせた Google 行列の定常分布として定義されます。
連結性と構造的分類
- 強連結成分（SCC）：互いに到達可能なノード群。アルゴリズムとしては Tarjan 法や Kosaraju 法で線形時間に抽出できます。
- DAG（有向非巡回グラフ）：有向サイクルを持たないグラフ。タスクの依存関係やパイプライン表現に用いられ、トポロジカルソート（Kahn アルゴリズム等）で順序付け可能です。
代表的アルゴリズムと解析手法
- 探索：有向グラフにも BFS・DFS が適用され、訪問順や後退辺を利用してサイクル検出や到達可能性を調べます。
- 強連結分解：Tarjan（深さ優先＋スタック）・Kosaraju（二回 DFS）
- 最短経路：Dijkstra（非負重み）、ベルマン–フォード（負辺あり）、トポロジカルソートを使う DAG 特化法
- 最大流・最小カット：フォード–ファルカーソン、エドモンズ–カルプ等。流れには明確な始点（ソース）と終点（シンク）が必要。
- 中心性：入次数／出次数、ベットウィーンネス、クローズネス（有向距離を用いる）、固有ベクトル中心性や PageRank、HITS（hub/authority）など、向きを扱える指標が多数あります。
中心性（指標）の注目点
有向性は中心性評価に大きく影響します。例えば入次数が高ければ参照されやすい（受信性が高い）ノード、出次数が高ければ広める立場にあるノードと解釈できます。PageRank は「受信による重要度」を定義する一方、HITS はハブ（多くの権威へリンクするノード）とオーソリティ（多くのハブから参照されるノード）という二面性を扱います。
クラスタリング・コミュニティ検出
無向ネットワーク向けのモジュラリティやスペクトル手法をそのまま使うと向きの情報が失われることがあります。したがって、向きを考慮する拡張手法（向き付きモジュラリティ、遷移行列ベースのコミュニティ検出、確率的ブロックモデルの有向拡張など）が提案されています。実運用では目的に応じて向きを保持するか無視するか判断する必要があります。
モデル化と生成モデル
- ランダム有向グラフ：Erdős–Rényi の有向版（各有向辺が独立に存在）
- 成長モデル：優先選択（preferential attachment）の有向拡張、論文引用ネットワークやWebの進化を模すモデルなど。
- 確率的ブロックモデル（SBM）：グループ間の有向接続確率を持ち、コミュニティ構造や役割検出に用いる。
動的過程と拡散
情報拡散、感染症伝播、ランダムウォーク、意見形成などのダイナミクスは、向きによって伝播経路が制限されるため、無向モデルとは挙動が異なります。例えば、源（感染源）からのアウトフローのみで広がるケースや、戻りができない場合（DAG的依存）には可逆性が失われます。疫学モデル（SIR/SEIR）の有向版や影響最大化問題も盛んに研究されています。
応用事例
- World Wide Web：ページ間のハイパーリンクは有向辺。PageRank などの評価が有効。
- ソーシャルネットワーク：フォロー関係（Twitter など）は有向性を持つ。
- 引用ネットワーク：論文・特許の引用は典型的な有向ネットワーク。
- 交通・供給網：片方向道路や供給チェーンのフロー表現。
- 代謝経路・神経回路：生物学的ネットワークで反応の向きやシナプスの有向性が重要。
可視化と実務上の注意点
可視化では向きの視認性（矢印）や重なりの多さが課題になります。レイアウト手法（層別配置、階層レイアウト、力学モデル）を選び、必要に応じて辺を集約・簡略化して可読性を確保します。また、データ取得時に向き情報が欠損していたり逆向きに記録されていることがあるため、前処理で向きの意味（発信／受信の定義）を明確にすることが重要です。
測定上の留意点と誤解しやすい点
- 向きを無視して解析すると、重要な構造（一次流れ、因果関係）が失われることがある。
- 入次数が大きい＝重要、ではない。入次数は量を示すだけで、質（どのノードからの入っているか）は別の指標で評価する必要がある。
- PageRank 等はモデル化仮定（ランダムウォーク、テレポート率）に敏感であり、解釈は文脈依存。
まとめ
有向ネットワークは、方向性が情報や流れの本質を決める多くのシステムを表現する強力なモデルです。行列・スペクトル解析、中心性指標、連結性やフロー問題、生成モデルまで幅広い理論とアルゴリズムがあり、研究と実務で不可欠なツールになっています。解析の際は向きの意味を明確にし、適切な指標やアルゴリズムを選ぶことが重要です。
参考文献
- Directed graph — Wikipedia
- PageRank — Wikipedia
- NetworkX — Strongly connected components
- M. E. J. Newman, Networks: An Introduction (2010)
- Tarjan's strongly connected components algorithm — Wikipedia
- Edmonds–Karp algorithm — Wikipedia
- Perron–Frobenius theorem — Wikipedia
- Albert-László Barabási, Network Science (book / resources)
投稿者プロフィール
