グラフとは｜ネットワーク科学

🎓 レベル：基礎　|　重要度：A（必須）

📎 前提：なし　|　関連：グラフの表現・次数・道・連結成分

要点（BLUF）

グラフ $G=(V,E)$ は、対象の集合 $V$ （ノード）と、対象間の関係 $E$ （エッジ）の対。
関係に向きがあるか（有向/無向）、強さがあるか（重み付き/なし）で4種類に分かれ、表せる現象が変わる。
「何をノードにし、何をエッジにするか」というモデル化の選択が、その後の分析すべてを決める。

概念：関係そのものをデータにする

ふつうのデータ表は「個体ごとの属性」を並べます。身長・体重・年齢のように。ところが現実には、個体と個体の間にある関係こそが本質という現象があります。友人関係、論文の引用、Web のリンク、駅と路線、タンパク質の相互作用 — これらは「誰と誰がつながっているか」が情報の中心です。

グラフは、この関係を正面から表すための数学的対象です。点（ノード／頂点）でモノを表し、点を結ぶ線（エッジ／辺）で関係を表す。たったこれだけの語彙で、ソーシャルから生体まであらゆる複雑系を同じ枠組みで扱えるのがネットワーク科学の強みです。

数式による定義

グラフは集合の対として定義されます。

G = (V,\, E), \qquad E \subseteq V \times V

$V$ ：ノード集合（vertex set）。 $n = |V|$ をノード数とします。
$E$ ：エッジ集合（edge set）。 $m = |E|$ をエッジ数とします。各エッジはノードの対 $(u,v)$ 。

無向グラフでは $(u,v)$ と $(v,u)$ を区別せず、 $\{u,v\}$ という非順序対として扱います。有向グラフ（ダイグラフ）では順序対 $(u,v)$ を「 $u$ から $v$ への矢印」とみなし、向きを区別します。

重み付きグラフは、各エッジに実数を割り当てる関数 $w: E \to \mathbb{R}$ を添えた $G=(V,E,w)$ です。距離・容量・親密度などを表します。

要するに何か

グラフとは「点と線の集まり」です。点が登場人物、線がその間の関係。向き（一方通行か双方向か）と重み（つながりの強さ）を加えるかどうかで、表現力が段階的に上がります。

4つの基本タイプ

向き \ 重み	重みなし	重みあり
無向	友人関係（相互）	道路網（距離）
有向	Twitter のフォロー	送金額・引用回数

graph LR
    subgraph 無向グラフ
        A1((A)) --- B1((B))
        B1 --- C1((C))
        A1 --- C1
    end
    subgraph 有向グラフ
        A2((A)) --> B2((B))
        B2 --> C2((C))
        C2 --> A2
    end

無向グラフでは「A と B は友人」のように関係が対称です。有向グラフでは「A は B をフォローしているが逆は不明」のように非対称な関係を表せます。Web のリンクや引用は本質的に有向です。

具体例：モデル化の選択が分析を決める

同じ「Twitter」を題材にしても、ノードとエッジの取り方で見えるものが変わります。

ノード＝ユーザー、エッジ＝フォロー（有向）→ 影響力・情報の流れを分析できる
ノード＝ユーザー、エッジ＝「同じハッシュタグを使った」（無向・重み付き）→ 話題コミュニティが見える
ノード＝ハッシュタグ、エッジ＝共起 → 話題どうしの関連構造が見える

何をノードにし、何をエッジにするかは、その後に計算できる量（中心性・コミュニティ・距離）をすべて規定します。グラフ分析でいちばん大事な意思決定は、実はこのモデル化の段階にあります。

数式の直観的意味

定義 $E \subseteq V \times V$ が言っているのは、「エッジとはノードの組であり、ありうる組（ $V \times V$ ）の一部を選んだもの」ということです。 $n$ ノードの無向グラフでは、ありうるエッジは最大 $\binom{n}{2}=n(n-1)/2$ 本。実際の $m$ がこの最大値にどれだけ近いかが、後で学ぶ密度になります。

⚠️ よくある誤解・落とし穴

「ノードは人・モノに限る」ではない：ノードは抽象的な対象なら何でもよい（単語・状態・時刻でも）。柔軟さがグラフの力です。
有向と無向を混同しない：引用ネットワークを無向で扱うと「どちらが先行研究か」の情報が消えます。向きの有無は分析の前提です。
多重辺・自己ループの扱い：同じ対の間に複数のエッジ（多重グラフ）や、自分自身へのループを許すかは設計の選択。単純グラフ（simple graph）はこれらを禁じます。