ランダムグラフ

定義

簡単な定義

非決定論的な手続きで作られるか、ある確率分布に従って表現されるグラフをランダムグラフ^{random Graph}という。

難しい定義

確率空間 $( \Omega , \mathcal{F} , P)$ が与えられ、$2^{\binom{n}{2}}$ が $n$ 個の頂点を持つラベル付けされたグラフをすべて集めたグラフファミリーを表すとする。

$\mathcal{F}$-可測な関数 $\mathbb{G} : \Omega \to 2^{\binom{n}{2}}$ をランダムグラフ^{random Graph}という。つまり、$\mathbb{G}$ はすべての(グラフの)ボレルセット $B \in 2^{\binom{n}{2}}$ に対して $\mathbb{G}^{-1} \left( B \right) \in \mathcal{F}$ を満たす関数である。

説明

21世紀に入りネットワーク理論がますます多くの分野に応用される中で、ランダムネットワーク^{random Network}に関する議論も活発になっている。統計学で確率変数がデータを意味するように、応用数学ではランダムネットワークは、我々が望むかどうかにかかわらず、今手にしているあるデータの構造を意味することになる。

例えば、学科で各学生をノードとし、SNSのフォロー状態をリンクとしてネットワークを作ると、まさにランダムネットワークの良い例になる。ノードを繋ぐルールは明確だが、実際に調査(サンプリング)をする前にはこのネットワークの形を正確に知ることはできない。典型的な構造はあるだろうが、学科を変えて調査するたびに、偶然によって異なるネットワークを得ることになるだろう。

しかし、この説明は数学的に考えるにはあまりにもナイーブ^naiveである。難しい定義では、ランダムグラフは確率変数が定義されるのと正確に同じ方法で、測度論を使用する確率論で定義されている。結局のところ、Random Variableは現実の中の実験や試行のような$\omega \in \Omega$ をVariableにマッピングする関数であり、Random GraphはそれをGraphにマッピングする関数である。

手で直接書いてみると、もっと理解しやすい。特定のグラフ $G_{0}$ があるとして、ランダムに作られたグラフが $G_{0}$ である確率が $3/4$ だとすれば、次のように書けばいい。 $$ P \left( \mathbb{G} = G_{0} \right) = {{ 3 } \over { 4 }} $$ 上記の数式での事象は $\left\{ \mathbb{G} = G_{0} \right\} \in \mathcal{F}$ である。確率という関数の中に入るものはいつも事象である点を覚えておこう。ランダムグラフは、一般的な確率論でのただのランダムエレメント^{random element}であり、値域がグラフファミリーであることだけが違う。

例

$n$ 個のラベル付けされた頂点と$m$ 個のエッジを持つシンプルグラフというプロパティ $\mathscr{G}_{n,m} \subset 2^{\binom{n}{2}}$ を考えよう。

正確に$m$ 個のリンクを持つランダムグラフは$\mathbb{G}_{n, m} : \Omega \to \mathscr{G}_{n,m}$ のように表せる。このように作られるグラフは、$n$ 個のノードと$m$ 個のリンクを持っていれば、誰がどのような確率で作ったとしても、最終的には関係ない。つまり、まだ確率分布が与えられていない。ここで私たちが最も簡単に考えることができる確率分布は、全員が同じ確率を持つ均一分布である。

シンプルグラフは異なるノードを結ばなければならないので、$n$ 個のノードの中から$2$ 個を選んで$\binom{n}{2}$ 個のリンクを持つことができ、その中でも特に$m$ 個のリンクを選ぶと$\displaystyle \left| \mathscr{G}_{n,m} \right| = \binom{\binom{n}{2}}{m}$ になる。したがって、すべての$G \in \mathscr{G}_{n,m}$ に対して $$ P \left( \mathbb{G}_{n,m} = G \right) = \binom{\binom{n}{2}}{m}^{-1} $$ とすれば、$n$ 個のノードと$m$ 個のリンクを持つすべてのグラフが選ばれる確率が等しくなる。このような確率分布を持つランダムグラフ$\mathbb{G}_{n, m}$ がその名も有名なエルデシュ・レーニモデルである。