巨大コンポーネント

ネットワーク理論では、巨大コンポーネントとは、グラフ全体の頂点のかなりの部分を含む、特定のランダム グラフの接続コンポーネントです。

より正確には、任意の大きさのグラフ上の確率分布からランダムに抽出されたグラフにおいて、巨大成分とは、全体の頂点数の割合がゼロから離れるように制限された連結成分のことです。エルデシュ・レーニイモデルに従って分布された十分に密なグラフでは、巨大成分が高確率で存在します。

巨大成分はランダムグラフのエルデシュ・レーニモデル(ER)の顕著な特徴であり、与えられたn頂点の組のペアを接続する各可能な辺は、他の辺とは独立して、確率pで存在します。このモデルでは、任意の定数 に対して の場合、高い確率で( が無限大に近づく極限で) グラフのすべての接続成分のサイズはO(log n )となり、巨大成分は存在しません。ただし、 の場合、高い確率で単一の巨大成分が存在し、他のすべての成分のサイズはO(log n )となります。これら 2 つの可能性の中間である の場合、グラフの最大成分の頂点数はに比例する確率が高いです。^[1]${\displaystyle p\leq {\frac {1-\epsilon }{n}}}$${\displaystyle \epsilon >0}$${\displaystyle n}$${\displaystyle p\geq {\frac {1+\epsilon }{n}}}$${\displaystyle p=p_{c}={\frac {1}{n}}}$${\displaystyle P_{\inf}}$${\displaystyle n^{2/3}}$

巨大成分はパーコレーション理論でも重要です。^{[1] [2]}次数 の ER ネットワークからノードの一部 がランダムに削除されると、臨界しきい値 が存在します。それより上には、サイズ の巨大成分 (最大クラスター) が存在します。 はを満たします。この式の解は であり、つまり巨大成分は存在しません。 ${\displaystyle q=1-p}$${\displaystyle \langle k\rangle }$${\displaystyle p_{c}={\frac {1}{\langle k\rangle }}}$${\displaystyle p_{c}}$${\displaystyle P_{\inf}}$${\displaystyle P_{\inf}}$${\displaystyle P_{\inf }=p(1-\exp(-\langle k\rangle P_{\inf }))}$${\displaystyle p<p_{c}}$${\displaystyle P_{\inf }=0}$

では、クラスターサイズの分布はべき乗則として振る舞い、これは相転移の特徴です。 ${\displaystyle p_{c}}$${\displaystyle n(s)}$${\displaystyle s^{-5/2}}$

あるいは、空のグラフから始めて、ランダムに選択されたエッジを 1 つずつ追加すると、約 個のエッジが追加されて初めてグラフに大きなコンポーネントが含まれ、その後すぐにコンポーネントが巨大になります。より正確には、個のエッジが追加された場合、に近いが より大きいtの値に対して、巨大コンポーネントのサイズはおよそ です。^{[1]ただし、}クーポンコレクターの問題によると、ランダムグラフ全体が接続されている確率を高めるには、エッジが必要です。 ${\displaystyle n/2}$${\displaystyle n/2}$${\displaystyle 4t-2n}$${\displaystyle \Theta (n\log n)}$

すべてのコンポーネントが小さいグラフにつながるパラメータと、巨大なコンポーネントにつながるパラメータとの間の同様の急激なしきい値は、不均一な次数分布 を持つツリー状のランダムグラフでも発生します。次数分布はグラフを一意に定義しません。ただし、次数分布以外のすべての点でグラフが完全にランダムであると仮定すると、有限/無限コンポーネントのサイズに関する多くの結果が知られています。このモデルでは、巨大コンポーネントの存在は、次数分布の最初の 2 つの（混合）モーメントのみに依存します。ランダムに選択された頂点の次数が であるとすると、巨大コンポーネントが存在する場合^[3]は、次の場合のみです。これは、モロイとリードの条件として知られています。^[4]の最初のモーメントは、ネットワークの平均次数です。一般に、次のモーメントは と定義されます。 ${\displaystyle P(k)}$${\displaystyle k}$$${\displaystyle \langle k^{2}\rangle -2\langle k\rangle >0.}$$${\displaystyle P(k)}$${\displaystyle n}$${\displaystyle \langle k^{n}\rangle =\mathbb {E} [k^{n}]=\sum k^{n}P(k)}$

巨大成分がない場合、小さな成分の予想サイズも第1モーメントと第2モーメントによって決定できますが、巨大成分がある場合、巨大成分のサイズを評価するのはより困難です。^[2]${\displaystyle 1+{\frac {\langle k\rangle ^{2}}{2\langle k\rangle +\langle k^{2}\rangle }}.}$

同様の表現は有向グラフにも適用でき、その場合次数分布は2次元となる。^[5]有向グラフには3種類の連結成分がある。ランダムに選ばれた頂点の場合:

1. アウトコンポーネントは、すべてのアウトエッジを再帰的にたどることで到達できる頂点の集合です。
2. インコンポーネントは、すべてのインエッジを後方に再帰的にたどることで到達できる頂点の集合です。
3. 弱いコンポーネントは、方向に関係なくすべてのエッジを再帰的にたどることで到達できる頂点の集合です。

ランダムに選ばれた頂点に入辺と出辺があるとします。定義により、入辺と出辺の平均数は となるように一致します。 が無向ネットワークの次数分布の生成関数である場合、 は と定義できます。有向ネットワークの場合、結合確率分布に割り当てられた生成関数は、2 つの変数と を用いてとと書くことができます。の場合、およびを定義できます。有向および無向ランダム グラフにおける巨大コンポーネントの存在の基準を次の表に示します。 ${\displaystyle k_{\text{in}}}$${\displaystyle k_{\text{out}}}$${\displaystyle c=\mathbb {E} [k_{\text{in}}]=\mathbb {E} [k_{\text{out}}]}$${\displaystyle G_{0}(x)=\textstyle \sum _{k}\displaystyle P(k)x^{k}}$ ${\displaystyle P(k)}$${\displaystyle G_{1}(x)}$${\displaystyle G_{1}(x)=\textstyle \sum _{k}\displaystyle {\frac {k}{\langle k\rangle }}P(k)x^{k-1}}$ ${\displaystyle P(k_{in},k_{out})}$${\displaystyle x}$${\displaystyle y}$${\displaystyle {\mathcal {G}}(x,y)=\sum _{k_{in},k_{out}}\displaystyle P({k_{in},k_{out}})x^{k_{in}}y^{k_{out}}}$${\displaystyle g(x)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial x}\vert _{y=1}}$${\displaystyle f(y)={\frac {1}{c}}{\partial {\mathcal {G}} \over \partial y}\vert _{x=1}}$

• Erdős-Rényi モデル – ランダム グラフを生成するための 2 つの密接に関連したモデル
• フラクタル – 無限に詳細な数学的構造Pages displaying short descriptions of redirect targets
• グラフ理論 – 離散数学の分野
• 相互依存ネットワーク – ネットワーク科学のサブフィールド
• パーコレーション理論 – ランダムグラフ内の連結クラスターの挙動に関する数学理論
• 浸透 – 多孔質材料を通した流体の濾過
• 複雑ネットワーク – 非自明なトポロジー特性を持つネットワーク
• ネットワーク科学 – 学術分野
• スケールフリーネットワーク – 次数分布がべき乗法則に従うネットワーク