Grafic aleatoriu - Random graph

În matematică , graficul aleatoriu este termenul general pentru a se referi la distribuțiile de probabilitate peste grafice . Graficele aleatorii pot fi descrise pur și simplu printr-o distribuție de probabilitate sau printr-un proces aleatoriu care le generează. Teoria graficelor aleatorii se află la intersecția dintre teoria graficelor și teoria probabilităților . Din perspectivă matematică, graficele aleatorii sunt folosite pentru a răspunde la întrebări despre proprietățile graficelor tipice . Aplicațiile sale practice se găsesc în toate domeniile în care rețelele complexe trebuie modelate - sunt cunoscute astfel numeroase modele de grafice aleatorii, care reflectă diversele tipuri de rețele complexe întâlnite în diferite zone. Într-un context matematic, graficul aleatoriu se referă aproape exclusiv la modelul graficului aleatoriu Erdős-Rényi . În alte contexte, orice model de grafic poate fi denumit grafic aleatoriu .

Modele

Un grafic aleatoriu se obține începând cu un set de n vârfuri izolate și adăugând margini succesive între ele la întâmplare. Scopul studiului în acest domeniu este de a determina în ce etapă este posibil să apară o anumită proprietate a graficului. Diferite modele de grafice aleatorii produc distribuții de probabilitate diferite pe grafice. Cel mai frecvent studiat este cel propus de Edgar Gilbert , notat G ( n , p ), în care fiecare margine posibilă apare independent cu probabilitatea 0 < p <1. Probabilitatea de a obține un anumit grafic aleatoriu cu m margini este cu notația . ${\ displaystyle p ^ {m} (1-p) ^ {Nm}}$ ${\ displaystyle N = {\ tbinom {n} {2}}}$

Un model strâns înrudit, modelul Erdős – Rényi notat G ( n , M ), atribuie o probabilitate egală tuturor graficelor cu exact M muchii. Cu 0 ≤ M ≤ N , G ( n , M ) are elemente și fiecare element apare cu probabilitate . Ultimul model poate fi privit ca un instantaneu la un anumit moment ( M ) al procesului grafic aleatoriu , care este un proces stocastic care începe cu n vârfuri și fără margini, și la fiecare pas adaugă o margine nouă aleasă în mod uniform din setul de margini lipsă. ${\ displaystyle {\ tbinom {N} {M}}}$ ${\ displaystyle 1 / {\ tbinom {N} {M}}}$ ${\ displaystyle {\ tilde {G}} _ {n}}$

Dacă, în schimb, începem cu un set infinit de vârfuri și lăsăm din nou fiecare margine posibilă să apară independent cu probabilitatea 0 < p <1, atunci obținem un obiect G numit grafic aleatoriu infinit . Cu excepția cazurilor banale când p este 0 sau 1, un astfel de G are aproape sigur următoarea proprietate:

Având în vedere orice elemente n + m , există un vârf c în V care este adiacent fiecăruia și nu este adiacent niciunui dintre . ${\ displaystyle a_ {1}, \ ldots, a_ {n}, b_ {1}, \ ldots, b_ {m} \ în V}$ ${\ displaystyle a_ {1}, \ ldots, a_ {n}}$ ${\ displaystyle b_ {1}, \ ldots, b_ {m}}$

Se pare că, dacă setul de vârfuri poate fi numărat, există, până la izomorfism , doar un singur grafic cu această proprietate, și anume graficul Rado . Astfel, orice grafic aleatoriu infinit este aproape sigur graficul Rado, care din acest motiv este uneori numit pur și simplu graficul aleatoriu . Cu toate acestea, rezultatul analog nu este adevărat pentru graficele nenumărate, dintre care există multe grafice (neizomorfe) care satisfac proprietatea de mai sus.

Un alt model, care generalizează modelul de graf aleatoriu al lui Gilbert, este modelul aleatoriu de punct-produs . Un grafic aleatoriu produs-punct asociază cu fiecare vârf un vector real . Probabilitatea unei margini uv între oricare vârfuri u și v este o funcție a produsului punct u • v al vectorilor lor respectivi.

De matrice de probabilitate de rețea modele grafice aleatoare prin probabilități de margine, care reprezintă probabilitatea ca o anumită muchie există pentru o perioadă de timp specificată. Acest model este extensibil la direcționat și neorientat; ponderat și neponderat; și structura graficelor statice sau dinamice. ${\ displaystyle p_ {i, j}}$ ${\ displaystyle e_ {i, j}}$

Pentru M ≃ pN , unde N este numărul maxim de margini posibil, cele două modele cele mai utilizate, G ( n , M ) și G ( n , p ), sunt aproape interschimbabile.

Graficele regulate aleatorii formează un caz special, cu proprietăți care pot diferi de graficele aleatorii în general.

Odată ce avem un model de grafice aleatorii, fiecare funcție pe grafice, devine o variabilă aleatorie . Studiul acestui model este de a determina dacă sau cel puțin estimează probabilitatea ca o proprietate să poată apărea.

Terminologie

Termenul „aproape fiecare” în contextul graficelor aleatorii se referă la o succesiune de spații și probabilități, astfel încât probabilitățile de eroare tind să fie zero.

Proprietăți

Teoria graficelor aleatorii studiază proprietățile tipice ale graficelor aleatorii, cele care au o probabilitate ridicată pentru graficele extrase dintr-o anumită distribuție. De exemplu, am putea cere o anumită valoare și ceea ce este probabilitatea ca este conectat . În studierea unor astfel de întrebări, cercetătorii se concentrează adesea pe comportamentul asimptotic al graficelor aleatorii - valorile la care converg diferite probabilități crește foarte mult. Teoria percolației caracterizează conectivitatea graficelor aleatorii, în special a celor infinit de mari. ${\ displaystyle n}$ ${\ displaystyle p}$ ${\ displaystyle G (n, p)}$ ${\ displaystyle n}$

Percolarea este legată de robustețea graficului (numită și rețea). Dat fiind un grafic aleatoriu de noduri și un grad mediu . Apoi eliminăm aleator o fracțiune de noduri și lăsăm doar o fracțiune . Există un prag critic de percolație sub care rețeaua devine fragmentată, în timp ce deasupra unei componente gigant conectate există. ${\ displaystyle n}$ ${\ displaystyle \ langle k \ rangle}$ ${\ displaystyle 1-p}$ ${\ displaystyle p}$ ${\ displaystyle p_ {c} = {\ tfrac {1} {\ langle k \ rangle}}}$ ${\ displaystyle p_ {c}}$

Percolarea localizată se referă la eliminarea unui nod vecinii săi, vecinii apropiați etc., până când o parte din noduri din rețea este eliminată. S-a arătat că pentru graficul aleatoriu cu distribuția Poisson a gradelor exact ca pentru eliminarea aleatorie. Pentru alte tipuri de distribuții de grade pentru atacul localizat este diferit de atacul aleator (funcții prag, evoluția ) ${\ displaystyle 1-p}$ ${\ displaystyle p_ {c} = {\ tfrac {1} {\ langle k \ rangle}}}$ ${\ displaystyle p_ {c}}$ ${\ displaystyle {\ tilde {G}}}$

Graficele aleatorii sunt utilizate pe scară largă în metoda probabilistică , unde se încearcă dovedirea existenței graficelor cu anumite proprietăți. Existența unei proprietăți pe un grafic aleatoriu poate implica adesea, prin lema regularității Szemerédi , existența acelei proprietăți pe aproape toate graficele.

În grafice regulate aleatorii , sunt setul de grafice -regulare cu astfel încât și sunt numerele naturale ,, și este par. ${\ displaystyle G (n, r-reg)}$ ${\ displaystyle r}$ ${\ displaystyle r = r (n)}$ ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ displaystyle 3 \ leq r <n}$ ${\ displaystyle rn = 2m}$

Secvența de grade a unui grafic în depinde doar de numărul de muchii din seturi ${\ displaystyle G}$ ${\ displaystyle G ^ {n}}$

{\ displaystyle V_ {n} ^ {(2)} = \ left \ {ij \: \ 1 \ leq j \ leq n, i \ neq j \ right \} \ subset V ^ {(2)}, \ qquad i = 1, \ cdots, n.}

Dacă muchiile, într-un grafic aleatoriu, sunt suficient de mari pentru a se asigura că aproape fiecare are grad minim cel puțin 1, atunci aproape fiecare este conectat și, dacă este egal, aproape fiecare are o potrivire perfectă. În special, în momentul în care ultimul vârf izolat dispare în aproape fiecare grafic aleatoriu, graficul devine conectat. ${\ displaystyle M}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle n}$ ${\ displaystyle G_ {M}}$

Aproape fiecare proces de grafic pe un număr par de vârfuri cu marginea ridicând gradul minim la 1 sau un grafic aleatoriu cu puțin mai mult de margini și cu o probabilitate apropiată de 1 asigură că graficul are o potrivire completă, cu excepția a cel mult un vârf . ${\ displaystyle {\ tfrac {n} {4}} \ log (n)}$

Pentru unele constante , aproape fiecare grafic etichetat cu vârfuri și cel puțin margini este hamiltonian . Cu probabilitatea de a tinde la 1, muchia specială care crește gradul minim la 2 face graficul hamiltonian. ${\ displaystyle c}$ ${\ displaystyle n}$ ${\ displaystyle cn \ log (n)}$

Proprietățile graficului aleator se pot modifica sau rămâne invariante sub transformările graficului. Mashaghi A. și colab., De exemplu, au demonstrat că o transformare care convertește grafice aleatoare în graficele lor margine-duale (sau grafice liniare) produce un ansamblu de grafice cu aproape aceeași distribuție de grade, dar cu corelații de grade și o concentrare semnificativ mai mare coeficient.

Colorare

Dat fiind un grafic aleatoriu G de ordinul n cu vârful V ( G ) = {1, ..., n }, prin algoritmul lacom pe numărul de culori, vârfurile pot fi colorate cu culorile 1, 2, ... (vârful 1 este colorat 1, vârful 2 este colorat 1 dacă nu este adiacent vârfului 1, altfel este colorat 2 etc.). Numărul de coloranți corespunzători ai graficelor aleatorii dat de un număr de q culori, numit polinomul său cromatic , rămâne necunoscut până acum. Scalarea zerourilor polinomului cromatic al graficelor aleatorii cu parametrii n și numărul muchiilor m sau a probabilității de conexiune p a fost studiată empiric folosind un algoritm bazat pe potrivirea simbolică a modelelor.

Copaci aleatori

Un copac aleatoriu este un copac sau arborescență care se formează printr-un proces stochastic . Într-o gamă largă de grafice aleatorii de ordinul n și mărimea M ( n ), distribuția numărului de componente arborescente de ordinul k este asimptotic Poisson . Tipuri de copaci aleatorii includ copac uniforme Spanning , aleatoare copac minim Spanning , arbore binar aleator , treap , explorând rapid copac aleatoare , copac browniană , și pădure aleatoare .

Grafice aleatorii condiționate

Luați în considerare un model de grafic aleatoriu definit pe spațiul de probabilitate și să fie o funcție reală cu valoare care atribuie fiecărui grafic într- un vector cu m proprietăți. Pentru un grafic fix , condiționat aleatoriu sunt modele în care măsura probabilității atribuie zero probabilitate tuturor graficelor astfel încât ' . ${\ displaystyle (\ Omega, {\ mathcal {F}}, P)}$ ${\ displaystyle {\ mathcal {P}} (G): \ Omega \ rightarrow R ^ {m}}$ ${\ displaystyle \ Omega}$ ${\ displaystyle \ mathbf {p} \ în R ^ {m}}$ ${\ displaystyle P}$ ${\ displaystyle {\ mathcal {P}} (G) \ neq \ mathbf {p}}$

Cazurile speciale sunt grafice aleatorii uniform condiționate , unde atribuie probabilitate egală tuturor graficelor cu proprietăți specificate. Ele pot fi văzute ca o generalizare a modelului Erdős – Rényi G ( n , M ), atunci când informațiile de condiționare nu sunt neapărat numărul de muchii M , ci orice altă proprietate de grafic arbitrară . În acest caz sunt disponibile foarte puține rezultate analitice și este necesară simularea pentru a obține distribuții empirice ale proprietăților medii. ${\ displaystyle P}$ ${\ displaystyle {\ mathcal {P}} (G)}$

Grafice interdependente

În graficele interdependente nodurile dintr-o rețea (grafic) depind de alte rețele pentru a funcționa. Deci, eșecurile într-unul sau mai multe grafice induc eșecuri în cascadă între grafice, ceea ce poate duce la prăbușirea bruscă.

Istorie

Cea mai timpurie utilizare a unui model de grafic aleatoriu a fost făcută de Helen Hall Jennings și Jacob Moreno în 1938, unde a fost luată în considerare o „sociogramă întâmplătoare” (un model Erdős-Rényi regizat) în compararea fracțiunii de legături reciproce din datele rețelei lor cu modelul aleatoriu. . O altă utilizare, sub denumirea de "rețea aleatorie", a fost realizată de Solomonoff și Rapoport în 1951, folosind un model de grafice direcționate cu atașamente fixe de grad și alese aleatoriu la alte vârfuri.

Modelul Erdős – Rényi al graficelor aleatorii a fost definit pentru prima dată de Paul Erdős și Alfréd Rényi în lucrarea lor din 1959 „On Random Graphs” și independent de Gilbert în lucrarea sa „Random graphs”.

Languages

In other projects