Gigantyczny składnik

dużą

Erdősa – – Gilberta z wierzchołkami przy prawdopodobieństwie krawędzi krytycznej wiele Przy tym prawdopodobieństwie krawędzi duży komponent nie jest jeszcze gigantycznym komponentem: zawiera tylko podliniową liczbę wierzchołków.

W teorii sieci gigantyczny składnik jest połączonym składnikiem danego grafu losowego , który zawiera skończony ułamek wierzchołków całego grafu .

Gigantyczny komponent w modelu Erdősa-Rényiego

Gigantyczne składowe są wyróżniającą się cechą modelu Erdősa-Rényiego (ER) grafów losowych, w którym każda możliwa para łącząca krawędzie danego zbioru $n$ wierzchołków jest obecna, niezależnie od innych krawędzi, z prawdopodobieństwem $p$ . W $wszystkie$ $_$ jeśli dla to dużym połączone elementy grafu mają rozmiar $O(log n)$ i nie ma gigantycznego komponentu. Jednak dla ${\ Displaystyle p \ geq {\ Frac {1+ \ epsilon} {n}}}$ z dużym prawdopodobieństwem istnieje pojedynczy gigantyczny składnik, a wszystkie inne składniki mają rozmiar $O (log n)$ . $}}$ do pośredni między tymi dwiema możliwościami, liczba wierzchołków w największym składniku wykresu, ${\ Displaystyle P _ {\ inf}}$ jest z dużym prawdopodobieństwem proporcjonalny do ${\ Displaystyle n ^ {2/3}}$ .

Składnik gigantyczny jest również ważny w teorii perkolacji. Gdy $próg$ węzłów , jest losowo usuwany z ER o stopniu , $langle k \ rangle$ ⟩ ${\ Displaystyle p_ {c} = {\ Frac {1} {\ langle k \ rangle}}}$ . Powyżej istnieje gigantyczny składnik (największy klaster) o rozmiarze $\$ $inf}}$ . ${\ Displaystyle P _ {\ inf}}$ spełnia, ${\ Displaystyle P _ {\ inf} = p (1- \ exp (- \ langle k\rangle P_{\inf}})}$ . Dla $}}$ rozwiązaniem tego równania jest ${\ displaystyle P _ {\ inf} = 0}$ , tj. nie ma gigantycznego składnika.

${\ Displaystyle p_ {c}}$ do rozkład rozmiarów klastrów zachowuje się jak prawo potęgowe , $\ Displaystyle n (s)}$ ~ ${\ Displaystyle s ^ {- 5 / 2}}$ , która jest cechą przejścia fazowego .

$krawędzi$ losowo wybrane krawędzie po jednej na raz, zaczynając od pustego wykresu , to dopiero po dodaniu około zawiera dużą składową, a wkrótce potem że komponent staje się gigantyczny. Dokładniej, gdy dodano $t krawędzi, dla wartości$ $t$ bliskich, ale większych niż $2n$ rozmiar gigantycznego składnika wynosi około $displaystyle 4t-$ . Jednak zgodnie z problemem kolekcjonera kuponów $są potrzebne$ , aby mieć duże prawdopodobieństwo, że

Wykresy z dowolnymi rozkładami stopni

Podobny ostry próg między parametrami, które prowadzą do wykresów ze wszystkimi komponentami małymi i parametrami, które prowadzą do gigantycznego komponentu, występuje również w losowych wykresach z niejednorodnymi rozkładami stopni . Rozkład stopni nie definiuje wykresu jednoznacznie. Jednak przy założeniu, że pod wszystkimi względami innymi niż ich rozkład stopni, wykresy są traktowane jako całkowicie losowe, znanych jest wiele wyników dotyczących rozmiarów elementów skończonych / nieskończonych. W tym modelu istnienie gigantycznej składowej zależy tylko od pierwszych dwóch (mieszanych) momentów rozkładu stopni. Niech losowo wybrany wierzchołek ma stopień $gdy$ to gigantyczny składnik istnieje wtedy i tylko wtedy,

{\ Displaystyle \ mathbb {E} [k ^ {2}] -2 \ mathbb {E} [k]> 0.}

{\ Displaystyle \ mathbb {E} [k]},

który jest również zapisany w postaci

{\ Displaystyle {\ langle k \ rangle}}

to średni stopień sieci. Podobne wyrażenia obowiązują również dla grafów skierowanych , w których rozkład stopni jest dwuwymiarowy. W grafach skierowanych występują trzy rodzaje połączonych elementów . Dla losowo wybranego wierzchołka:

out-component to zbiór wierzchołków, do których można dotrzeć rekurencyjnie podążając za wszystkimi krawędziami zewnętrznymi do przodu;
in-component to zbiór wierzchołków, do których można dotrzeć, rekurencyjnie podążając wstecz za wszystkimi krawędziami;
słaby komponent to zbiór wierzchołków, do których można dotrzeć, rekurencyjnie podążając za wszystkimi krawędziami niezależnie od ich kierunku.

Kryteria istnienia gigantycznych składowych w grafach konfiguracji skierowanej i nieskierowanej

Niech losowo wybrany wierzchołek ma $krawędziach$ i $.$ krawędziach Z definicji średnia liczba krawędzi wejściowych i zewnętrznych pokrywa się tak, że do $}] = \mathbb {E} [k_{\text{wyj}}]}$ . Jeśli ${\ Displaystyle G_ {0} (x) = \ textstyle \ suma _ {k} \ Displaystyle P (k) x ^ {k}}$ jest funkcją generującą rozkład stopni dla sieci nieskierowanej, to można zdefiniować jako ${\ Displaystyle G_$ ${1}$ ${\ Displaystyle G_ {1} (x) = \ textstyle \ suma _ {k} \ Displaystyle {\ Frac {k} {\ langle k \ rangle}} P (k) x^{k-1}}$ . W przypadku sieci skierowanych funkcję generującą przypisaną do wspólnego rozkładu prawdopodobieństwa można zapisać za pomocą dwóch wartości $(k_ {in}, k_ {out})}$ $Displaystyle$ i ${\ Displaystyle y}$ jak: ${\ Displaystyle { \mathcal {G}} (x, y) = \ suma _ {k_ {in}, k_ {out}} \ Displaystyle P ({k_ {in}, k_ {out}}) x ^ {k_ {in}} y^{k_{out}}}$ , to można zdefiniować ${\ Displaystyle g (x) = {\ Frac {1} {c}} {\ częściowe {\ mathcal {G}} \ ponad \ częściowe x} \ vert _ {y = 1}}$ i ${\ Displaystyle f (y) = {\ Frac {1} {c}} {\ częściowe {\ mathcal {G}} \ ponad \ częściowe y} \ vert _ {x = 1}}$ . Kryteria istnienia gigantycznych składowych w skierowanych i nieskierowanych grafach losowych podano w poniższej tabeli:


Typ	Kryteria
nieukierunkowany: gigantyczny komponent	${\ Displaystyle \ mathbb {E} [k ^ {2}] -2 \ mathbb {E} [k]> 0}$ lub ${\ Displaystyle G'_ {1} (1) = 1}$
skierowany: gigantyczny komponent wejścia/wyjścia	${\ Displaystyle \ mathbb {E} [k _ {\ tekst {w}} k_ {na zewnątrz}] - \ mathbb {E} [k _ {\ tekst { w}}]> 0}$ lub ${\ Displaystyle g'_ {1} (1) = f'_ {1} (1) = 1}$
reżyseria: gigantyczny słaby komponent	${\ Displaystyle 2 \ mathbb {E} [k _ {\ tekst {w}}] \ mathbb {E} [k _ {\ tekst {w}} k_ {\ tekst {na zewnątrz} }]-\mathbb {E} [k_{\text{in}}]\mathbb {E} [k_{\text{out}}^{2}]-\mathbb {E} [k_{\text{in }}]\mathbb {E} [k_{\text{in}}^{2}]+\mathbb {E} [k_{\text{in}}^{2}]\mathbb {E} [k_{ \text{out}}^{2}]-\mathbb {E} [k_{\text{in}}k_{\text{out}}]^{2}>0}$

Zobacz też