Model Erdősa-Rényiego

Wykres Erdősa – Rényi – Gilberta z 1000 wierzchołkami $prawdopodobieństwie$ i

W matematycznej dziedzinie teorii grafów model Erdősa -Rényiego odnosi się do jednego z dwóch ściśle powiązanych modeli generowania losowych wykresów lub ewolucji losowej sieci . Modele te zostały nazwane na cześć węgierskich matematyków Paula Erdősa i Alfréda Rényi , którzy wprowadzili jeden z modeli w 1959 r. Edgar Gilbert wprowadził drugi model jednocześnie i niezależnie od Erdősa i Rényi. W modelu Erdősa i Rényiego wszystkie grafy na ustalonym zbiorze wierzchołków ze stałą liczbą krawędzi są jednakowo prawdopodobne. W modelu wprowadzonym przez Gilberta, zwanym także modelem Erdősa-Rényi-Gilberta , każda krawędź ma ustalone prawdopodobieństwo obecności lub braku, niezależnie od innych krawędzi. Modele te mogą być używane w metodzie probabilistycznej do udowodnienia istnienia grafów spełniających różne właściwości lub do zapewnienia rygorystycznej definicji tego, co to znaczy, że właściwość jest zachowana dla prawie wszystkich grafów.

Definicja

Istnieją dwa blisko spokrewnione warianty modelu grafów losowych Erdősa-Rényiego.

Wykres wygenerowany przez dwumianowy model Erdősa i Rényiego ( p = 0,01)

• W $modelu wykres$ wybierany równomiernie losowo ze zbioru wszystkich wykresów, które $M$ krawędzie $}$ . Węzły są uważane za oznakowane, co oznacza, że ​​grafy otrzymane od siebie przez permutację wierzchołków są uważane za odrębne. Na przykład w modelu istnieją trzy wykresy dwukrawędziowe na trzech oznaczonych wierzchołkach (po jednym dla każdego wyboru środkowego wierzchołka na ścieżce dwukrawędziowej) ${\ Displaystyle G (3,2) }$ , a każdy z tych trzech wykresów jest zawarty z prawdopodobieństwem ${\ displaystyle {\ tfrac {1} {3}}}$ .
• W $modelu$ konstruowany przez losowe Każda krawędź jest zawarta na wykresie z prawdopodobieństwem $.$ niezależnie od każdej innej krawędzi Równoważnie prawdopodobieństwo wygenerowania każdego wykresu, który ma $krawędzie,$ i wynosi ${\ displaystyle M}$
  $${\ Displaystyle p ^ {M} (1-p) ^ {{n \ wybierz 2} -M}.}$$
  Parametr w tym $modelu$ można traktować jako funkcję ważenia wraz ze $displaystyle$ od 1 {\ $1}$ do ${\ displaystyle 1}$ jest coraz bardziej prawdopodobne, że model będzie zawierał wykresy z większą liczbą krawędzi, a coraz rzadziej będzie zawierał wykresy z mniejszą liczbą krawędzi. W $Displaystyle 2 ^ {\ binom {$ przypadek przypadkowi, w którym wszystkie $} {2} }}$ Wykresy na $wierzchołkach$ wybierane z równym prawdopodobieństwem.

Zachowanie losowych wykresów jest często badane w przypadku, gdy $wierzchołków$ dąży do nieskończoności. Chociaż i można $je$ naprawić, mogą to być również funkcje zależne od $}$$n$ . Na przykład stwierdzenie, że prawie każdy wykres w $jest$ , oznacza, że ​​sol $\ ln (n) / n)}$$n$ , prawdopodobieństwo, że wykres na z prawdopodobieństwem krawędzi , $dąży$$1}$$\$ .

Porównanie obu modeli

Oczekiwana liczba krawędzi w G ( n , p ) to ${\ Displaystyle {\ tbinom {n} {2}} p}$ , a zgodnie z prawem wielkich liczb dowolny wykres w G ( n , p ) prawie na pewno będzie miał w przybliżeniu tyle krawędzi (pod warunkiem, że oczekiwana liczba krawędzi dąży do nieskończoności). Dlatego zgrubna heurystyka polega na tym, że jeśli pn ² → ∞, to G ( n , p ) powinien zachowywać się podobnie do sol ( n , M ) z ${\ Displaystyle M = {\ tbinom {n} 2}}p}$ wraz ze wzrostem n .

Tak jest w przypadku wielu właściwości grafu. Jeśli P jest jakąkolwiek właściwością grafu, która jest monotoniczna względem uporządkowania podgrafów (co oznacza, że ​​jeśli A jest podgrafem B i A spełnia P , to B również spełnia P ), to stwierdzenia „ P zachodzą dla prawie wszystkich grafów w sol ( n , p )” i „ P zachodzi dla prawie wszystkich wykresów w ${\ Displaystyle G (n, {\ tbinom {n} {2}} p)}$ "są równoważne ( pod warunkiem pn ² → ∞). Na przykład obowiązuje to, jeśli P jest właściwością bycia połączonym lub jeśli P jest właściwością zawierania cyklu hamiltonowskiego . Jednak niekoniecznie będzie to dotyczyć właściwości niemonotonicznych (np. własności posiadania parzystej liczby krawędzi).

W praktyce model G ( n , p ) jest dziś bardziej powszechnie używany, częściowo ze względu na łatwość analizy, na jaką pozwala niezależność krawędzi.

Właściwości G ( n , p )

Przy powyższym zapisie wykres w sol ( n , p ) ma średnio krawędzie ${\ displaystyle {\ tbinom {n} {2}} p} .$ Rozkład stopnia dowolnego wierzchołka jest dwumianowy :

${\ Displaystyle P (\ stopień (v) = k) = {n-1 \ wybrać k}p^{k}(1-p)^{n-1-k},}$

gdzie n jest całkowitą liczbą wierzchołków grafu. Od

${\ Displaystyle P (\ deg (v) = k) \ do {\ Frac {(np) ^ {k} \ operatorname {e} ^ {-np}} {k! }}\quad {\text{ as }}n\to \infty {\text{ i }}np={\text{stała}},}$

ten rozkład to Poissona dla dużych n i np = const.

W artykule z 1960 roku Erdős i Rényi bardzo dokładnie opisali zachowanie G ( n , p ) dla różnych wartości p . Ich wyniki obejmowały, że:

• Jeśli np < 1, to wykres w G ( n , p ) prawie na pewno nie będzie miał połączonych składowych o rozmiarze większym niż O(log( n )).
• Jeśli np = 1, to wykres w G ( n , p ) prawie na pewno będzie miał największy składnik, którego rozmiar jest rzędu n ^2/3 .
• Jeśli np → c > 1, gdzie c jest stałą, to graf w G ( n , p ) prawie na pewno będzie miał unikalną gigantyczną składową zawierającą dodatnią część wierzchołków. Żaden inny komponent nie będzie zawierał więcej niż O(log( n )) wierzchołków.
• Jeśli ${\ Displaystyle p <{\ tfrac {(1-\ varepsilon) \ ln n} {n}}} , to$ prawie na pewno wykres w G ( n , p ) zawierają izolowane wierzchołki, a zatem są odłączone.
• Jeśli ${\ Displaystyle p > {\ tfrac {(1 + \ varepsilon) \ ln n} {n}}}$ , to wykres w G ( n , p ) prawie na pewno być podłączonym.

Zatem ${\ Displaystyle {\ tfrac {\ ln n} {n}}}$ jest ostrym progiem dla łączności G ( n , p ).

Dalsze właściwości wykresu można opisać niemal dokładnie, ponieważ n dąży do nieskończoności. Na przykład istnieje k ( n ) (w przybliżeniu równe 2 log ₂ ( n )) takie, że największa klika w G ( n , 0,5) prawie na pewno ma rozmiar k ( n ) albo k ( n ) + 1.

Tak więc, chociaż znalezienie rozmiaru największej kliki na grafie jest NP-zupełne , rozmiar największej kliki na „typowym” grafie (zgodnie z tym modelem) jest bardzo dobrze poznany.

Grafy podwójne krawędzi grafów Erdosa-Renyiego to grafy o prawie takim samym rozkładzie stopni, ale z korelacjami stopni i znacznie wyższym współczynnikiem grupowania .

Stosunek do perkolacji

W teorii perkolacji bada się graf skończony lub nieskończony i losowo usuwa się krawędzie (lub połączenia). Zatem proces Erdősa-Rényiego jest w rzeczywistości nieważoną perkolacją łącza na pełnym wykresie . (Jedno odnosi się do perkolacji, w której węzły i / lub łącza są usuwane z niejednorodnymi wagami jako perkolacja ważona). Ponieważ teoria perkolacji ma swoje korzenie w fizyce , większość przeprowadzonych badań dotyczyła sieci w przestrzeniach euklidesowych. Przejście przy np = 1 od gigantycznego składnika do małego składnika ma analogie dla tych wykresów, ale dla sieci punkt przejścia jest trudny do określenia. Fizycy często nazywają badanie pełnego wykresu średnią teorią pola . Zatem proces Erdősa – Rényiego jest przypadkiem perkolacji w średnim polu.

Wykonano również kilka znaczących prac nad perkolacją na losowych wykresach. Z punktu widzenia fizyka byłby to nadal model pola średniego, więc uzasadnienie badań jest często formułowane w kategoriach solidności grafu, postrzeganego jako sieć komunikacyjna. Biorąc pod uwagę losowy wykres n ≫ 1 węzłów o średnim stopniu ${\ Displaystyle \ langle k \ rangle}$ . $Usuń$$i$ ułamek ułamek z Istnieje krytyczny próg $poniżej$${\ displaystyle p'_ {c}} istnieje$ a gigantyczny połączony składnik rzędu n . Względny rozmiar olbrzymiego składnika, P _∞ , jest określony przez

${\ Displaystyle P _ {\ infty} = p' [1- \ exp (- \ langle k \ rangle P _ {\ infty})]. \,}$

Zastrzeżenia

Oba główne założenia modelu G ( n , p ) (że krawędzie są niezależne i że każda krawędź jest jednakowo prawdopodobna) mogą być nieodpowiednie do modelowania pewnych rzeczywistych zjawisk. W przeciwieństwie do wielu sieci społecznościowych, wykresy Erdősa – Rényiego mają niskie grupowanie. Niektóre alternatywy modelowania obejmują model Barabásiego – Alberta oraz model Wattsa i Strogatza . Te alternatywne modele nie są procesami perkolacji, ale reprezentują odpowiednio model wzrostu i zmiany okablowania.

Historia

Model G ( n , p ) został po raz pierwszy wprowadzony przez Edgara Gilberta w artykule z 1959 r., W którym badano wspomniany powyżej próg łączności. Model G ( n , M ) został wprowadzony przez Erdősa i Rényi w ich artykule z 1959 roku . Podobnie jak w przypadku Gilberta, ich pierwsze badania dotyczyły łączności G ( n , M ), a bardziej szczegółowa analiza nastąpiła w 1960 roku.

Reprezentacja granic kontinuum krytycznego ${\ Displaystyle G (n, p)}$

Ruch Browna z kwadratowym dryfem ujemnym jest rozkładany na ruchy Browna o malejących rozmiarach.

Granica kontinuum wykresu została uzyskana, gdy jest rzędu $displaystyle$$1/n}$ . W szczególności rozważ sekwencję wykresów ${\ Displaystyle G_ {n}: = G (n, 1/n + \ lambda n ^ {- {\ frac {4}{3}}})}$ dla ${\ Displaystyle \ lambda \ in \ mathbb {R}}$ . Obiekt graniczny można skonstruować w następujący sposób:

• $t): = W (t) + \ lambda t- {\ frac { t ^ {2}}{2}}}$ ( gdzie $Browna$ standardowym ruchem .
• $): = W ^ {\lambda}(t)-\inf \limits_{s\in [0,t]}W^{\lambda}(s)}$ t . Proces ten można postrzegać jako zawierający wiele następujących po sobie wyskoków (niezupełnie wycieczek Browna, zob. ). Ponieważ dryf ${\ displaystyle W ^ {\ lambda}}$ jest zdominowany przez ${\ Displaystyle - {\ Frac {t ^ {2}} {2}}}$ , te wycieczki stają się coraz krótsze, gdy ${\ Displaystyle t \ do + \ infty}$ . W szczególności można $}} o malejących$ posortować według malejącej długości: możemy podzielić ) $N$$(C_ {i}) _ {i \ in \ mathbb {N$$jest$$\mathbb {N} }$$,$ tak że ograniczona do wycieczką Browna dla dowolnego $displaystyle i \$ .
• Rozważmy teraz wycieczkę ${\ Displaystyle (e (s)) _ {s \ w [0,1]}}$ . Skonstruuj losowy wykres w następujący sposób:
  

  Wycieczka Browna ${\ Displaystyle (e (t)) _ {t \ w [0,1]}}$ . Tutaj proces ma jeden punkt, oznaczony czerwoną $kropką$ Czerwona linia odpowiada pojedynczemu wewnętrznemu węzłowi powiązanego drzewa $displaystyle$ zielona linia odpowiada liściowi $T_ {e}}$ \ Jeśli doda się krawędź między dwoma węzłami, otrzyma się wykres z pojedynczym cyklem
  • Skonstruuj $($ drzewo patrz drzewo Browna .
  • Rozważmy proces punktu Poissona $z$ [ $\ displaystyle [0,1] \ razy \ mathbb {R} _ {+}}$ jednostkową intensywnością. Do każdego punktu ${\ Displaystyle (x, s) \ in \ Xi}$ takiego, że ${\ Displaystyle x \ eq e (s)}$ , ​​odpowiada podstawowemu węzłowi wewnętrznemu i a liść drzewa ${\ displaystyle T_ {e}}$ . Identyfikując dwa $Displaystyle$$\ Gamma _ {e}}$ drzewo staje się wykresem

Stosując tę ​​​​procedurę, otrzymuje się sekwencję losowych nieskończonych wykresów o malejących rozmiarach: ${\ Displaystyle (\ Gamma _ {i}) _ {i \ in \ mathbb {N}}}$ . Twierdzenie stwierdza, że ​​​​ten wykres odpowiada w pewnym sensie obiektowi granicznemu $displaystyle$ n $n \ do + \ infty$ .

Zobacz też

• Wykres Rado - Graf nieskończony zawierający wszystkie grafy policzalne, graf utworzony przez rozszerzenie modelu G ( n , p ) na grafy o policzalnej nieskończonej liczbie wierzchołków. Inaczej niż w przypadku skończonym, wynikiem tego nieskończonego procesu jest (z prawdopodobieństwem 1 ) ten sam wykres, aż do izomorfizmu.
• Ewolucja dwufazowa - proces, który napędza samoorganizację w złożonych systemach adaptacyjnych, opisuje sposoby, w jakie właściwości związane z modelem Erdősa-Rényiego przyczyniają się do powstawania porządku w systemach.
• Wykładnicze modele grafów losowych - modele statystyczne do analizy sieci Strony wyświetlające opisy danych wiki jako rozwiązanie awaryjne opisują ogólny rozkład prawdopodobieństwa grafów na „n” węzłach, biorąc pod uwagę zestaw statystyk sieci i różne parametry z nimi związane.
• Stochastyczny model blokowy , uogólnienie modelu Erdősa – Rényiego dla grafów z ukrytą strukturą zbiorowości
• Model Wattsa – Strogatza - Metoda generowania losowych grafów małego świata
• Model Barabásiego – Alberta – algorytm generowania losowych sieci Strony wyświetlające opisy wikidanych jako rozwiązanie awaryjne

Literatura

•   Zachód, Douglas B. (2001). Wprowadzenie do teorii grafów (wyd. 2). Sala Prentice'a. ISBN 0-13-014400-2 .
• Newman, MEJ (2010). Sieci: wprowadzenie . Oksford.

Linki internetowe

• Wideo: losowy wykres Erdosa-Renyiego