Grafon (teoria grafurilor)

Un graphon este un model de graf aleator, o generalizare a modelului Erdős-Rényi . Grafonii apar în mod natural în studiul comportamentului limită al unei secvențe de grafice .

Definiție

Un graphon este o funcție măsurabilă simetrică . $W:[0,1]^{2}\la [0,1]$

Un graphon este de obicei înțeles ca un model al unui graf aleator conform următoarei scheme:

Fiecărui vârf al graficului i se atribuie o valoare aleatorie independentă $j$ $u_{j}\in [0,1]$
O muchie este inclusă independent în grafic cu probabilitate . $(i,j)$ $W(u_{i},u_{j})$

Modelul bazat pe graphon este uneori notat ca , prin analogie cu modelul grafic aleatoriu Erdős-Rényi . Un grafic creat dintr-un graphon în acest fel se numește graf aleatoriu. $W$ $\mathbb {G} (n,W)$ $W$ $W$

Exemple

Cel mai simplu exemplu de graphon: pentru o constantă . În acest caz, modelul de înlocuire asociat al graficului aleatoriu este modelul Erdős-Rényi care include fiecare muchie independent cu probabilitatea . $W(x,y)\equiv p$ $p\in [0,1]$ $G(n,p)$ $p$

Dacă în schimb începem cu un graphon constant pe bucăți:

împărțirea pătratului unității în blocuri și $k\times k$
parametru egal cu bloc, $W$ $p_{lm)$ $(l,m)^{\text{th)}$

atunci modelul grafic aleator rezultat este o generalizare în bloc stocastică a modelului Erdős-Rényi. Îl putem interpreta ca un model de grafic aleatoriu constând din diferite grafice Erdős-Rényi cu parametri , respectiv, cu bigrafe între ei, unde fiecare muchie posibilă între blocuri și este, de asemenea, inclusă independent cu probabilitatea . $k$ $k$ $p_{ll)$ $(l,l)$ $(m,m)$ $p_{lm)$

Multe alte modele de grafice aleatoare pot fi definite de un graphon. [unu]

Concepte de convergență

Există multe moduri diferite de a măsura distanța dintre două grafice. Dacă suntem interesați de metrici care păstrează proprietățile extreme ale graficelor, atunci trebuie să ne limităm atenția la metricile care identifică graficele aleatoare ca fiind apropiate. De exemplu, dacă construim aleatoriu două grafice în mod independent folosind modelul Erdős-Rényi pentru o valoare fixă , atunci distanța dintre aceste două grafice pentru o metrică rezonabilă ar trebui să fie aproape de zero cu o probabilitate mare pentru mare . $G(n,p)$ $p$ $n$

În acest sens, există două metrici naturale care funcționează bine pe grafice aleatorii. Prima este metrica de eșantionare, care spune că două grafice sunt apropiate dacă distribuțiile lor subgraf sunt apropiate. A doua este metrica divergenței marginilor, care spune că două grafice sunt apropiate atunci când densitățile lor de margine sunt apropiate pe toate submulțimile lor corespunzătoare de vârfuri.

În mod miraculos, o secvență de grafice converge față de o distanță dacă și numai dacă converge față de alta. Mai mult decât atât, obiectele limită din ambele metrici se dovedesc a fi grafoni. Echivalența acestor două noțiuni de convergență reflectă echivalența diferitelor noțiuni de grafice cvasialeatoare. [2]

Literatură

↑ Orbanz, P. (2015). „Modele bayesiene de grafice, matrice și alte structuri aleatoare interschimbabile”. Tranzacții IEEE privind analiza modelelor și inteligența mașinii . 37 (2): 437-461. arXiv : 1312,7857 . DOI : 10.1109/tpami.2014.2334607 . PMID 26353253 .
↑ Chung, Fan RK ; Graham, Ronald L .; Wilson, R.M. (1989). „Grafice cvasi-aleatoare” . Combinatorica . 9 (4): 345-362. DOI : 10.1007/BF02125347 .

L. N. Corellano, A. A. Razborov . Limitele semantice ale obiectelor combinatorii dense // Uspekhi Mat . - 2020. - T. 75 , nr. 4 (454) . — S. 45–152 . - doi : 10.4213/rm9956 . (Rusă)