Grafon (gráfelmélet)

A grafon egy véletlen gráfmodell , az Erdős-Rényi modell általánosítása . A grafonok természetesen felmerülnek egy gráfsorozat határjellegének vizsgálata során .

Definíció

A grafon szimmetrikusan mérhető függvény . $W:[0,1]^{2}\to [0,1]$

A grafont általában egy véletlen gráf modelljeként értelmezik a következő séma szerint:

A gráf minden csúcsához független véletlenszerű érték tartozik $j$ $u_{j}\in [0,1]$
Egy él a valószínűséggel függetlenül szerepel a gráfban . $(i,j)$ $W(u_{i},u_{j})$

A grafon alapú modellt az Erdős-Rényi véletlen gráfmodell analógiájára néha -nek jelölik . Egy grafonból ily módon létrehozott gráfot -random gráfnak nevezünk . $W$ $\mathbb {G} (n,W)$ $W$ $W$

Példák

A grafon legegyszerűbb példája: valamilyen állandóra . Ebben az esetben a véletlen gráf társított helyettesítési modellje az Erdős-Rényi modell , amely az egyes éleket egymástól függetlenül tartalmazza valószínűséggel . $W(x,y)\equiv p$ $p\in [0,1]$ $G(n,p)$ $p$

Ha ehelyett egy darabonkénti állandó grafonnal kezdjük:

egységnégyzet blokkokra bontása és $k\times k$
blokkal egyenlő paraméter , $W$ ${\displaystyle p_{lm))$ $(l,m)^{\text{th))$

akkor a kapott véletlen gráfmodell az Erdős-Rényi modell sztochasztikus blokkáltalánosítása. Értelmezhetjük úgy, mint egy véletlen gráfmodellt, amely különböző paraméterekkel rendelkező Erdős-Rényi gráfokból áll, köztük bigráfokkal, ahol minden lehetséges blokk közötti él és valószínűséggel függetlenül is szerepel . $k$ $k$ ${\displaystyle p_{ll))$ $(l,l)$ ${\megjelenítési stílus (m, m)}$ ${\displaystyle p_{lm))$

Sok más véletlen gráf modell definiálható egy grafonnal. [egy]

A konvergencia fogalmai

Két grafikon közötti távolság mérésére számos különböző módszer létezik. Ha olyan metrikák érdekelnek bennünket, amelyek megőrzik a gráfok szélsőséges tulajdonságait, akkor figyelmünket azokra a metrikákra kell korlátoznunk, amelyek a véletlenszerű gráfokat közeliként azonosítják. Például, ha véletlenszerűen szerkesztünk két gráfot egymástól függetlenül az Erdős-Rényi-modell segítségével egy fixhez , akkor a két gráf távolságának egy ésszerű metrika esetén nullához közel kell lennie, nagy valószínűséggel nagy valószínűséggel . $G(n,p)$ $p$ $n$

Ebben az értelemben két természetes metrika van, amelyek jól teljesítenek véletlenszerű grafikonokon. Az első a mintavételi metrika, amely szerint két gráf közel van, ha részgráf-eloszlása közel van. A második az éldivergencia metrika, amely azt mondja, hogy két gráf közel van, ha élsűrűségük közel van az összes megfelelő csúcsrészhalmazán.

Csodálatos módon egy gráfsorozat akkor és csak akkor konvergál egy távolsághoz képest, ha egy másikhoz képest. Ráadásul mindkét metrika határobjektumai grafonok. E két konvergenciafogalom ekvivalenciája a kvázi véletlen gráfok különböző fogalmainak egyenértékűségét tükrözi. [2]

Irodalom

↑ Orbanz, P. (2015). Grafikonok, tömbök és egyéb cserélhető véletlenszerű struktúrák Bayes-i modelljei. IEEE-tranzakciók a mintaelemzésről és a gépi intelligenciáról . 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). „Kvázi véletlenszerű grafikonok” . Combinatorica . 9 (4): 345-362. DOI : 10.1007/BF02125347 .

L. N. Corellano, A. A. Razborov . Sűrű kombinatorikus objektumok szemantikai határai // Uspekhi Mat . - 2020. - T. 75 , 4. sz (454) . – S. 45–152 . - doi : 10.4213/rm9956 . (Orosz)