Grafon (teorie grafů)

Grafon je náhodný grafový model, zobecnění Erdős-Rényiho modelu . Grafony přirozeně vznikají při studiu limitního chování posloupnosti grafů .

Definice

Grafon je symetrická měřitelná funkce . $W:[0,1]^{2}\to [0,1]$

Grafon je obvykle chápán jako model náhodného grafu podle následujícího schématu:

Každému vrcholu grafu je přiřazena nezávislá náhodná hodnota $j$ $u_{j}\in [0,1]$
Hrana je nezávisle zahrnuta v grafu s pravděpodobností . $(i,j)$ $W(u_{i},u_{j})$

Model založený na grafu je někdy označován jako , analogicky s Erdős-Rényiho modelem náhodného grafu . Takto vytvořený graf z grafonu se nazývá -náhodný graf. $W$ $\mathbb {G} (n,W)$ $W$ $W$

Příklady

Nejjednodušší příklad grafonu: pro nějakou konstantu . V tomto případě je přidruženým náhradním modelem náhodného grafu Erdős-Rényiho model , který zahrnuje každou hranu nezávisle s pravděpodobností . $W(x,y)\equiv p$ $p\in [0,1]$ $G(n,p)$ $p$

Pokud místo toho začneme s po částech konstantním grafonem:

rozdělení jednotkového čtverce na bloky a $k\times k$
parametr rovný bloku , $W$ ${\displaystyle p_{lm))$ $(l,m)^{\text{th))$

pak výsledný model náhodného grafu je stochastickou blokovou generalizací Erdős-Rényiho modelu. Můžeme jej interpretovat jako náhodný grafový model skládající se z různých Erdős-Rényiho grafů s parametry , respektive s bigrafy mezi nimi, kde každá možná hrana mezi bloky a je také zahrnuta nezávisle s pravděpodobností . $k$ $k$ ${\displaystyle p_{ll))$ $(l,l)$ $(m, m)$ ${\displaystyle p_{lm))$

Grafonem lze definovat mnoho dalších náhodných grafových modelů. [jeden]

Koncepty konvergence

Existuje mnoho různých způsobů, jak změřit vzdálenost mezi dvěma grafy. Pokud nás zajímají metriky, které zachovávají extrémní vlastnosti grafů, pak musíme omezit svou pozornost na metriky, které náhodné grafy identifikují jako blízké. Pokud například náhodně zkonstruujeme dva grafy nezávisle pomocí Erdős-Rényiho modelu pro fixní , pak by se vzdálenost mezi těmito dvěma grafy pro rozumnou metriku měla blížit nule s vysokou pravděpodobností pro velké . $G(n,p)$ $p$ $n$

V tomto smyslu existují dvě přirozené metriky, které fungují dobře na náhodných grafech. První je vzorkovací metrika, která říká, že dva grafy jsou blízko, pokud jsou jejich distribuce podgrafů blízko. Druhým je metrika hranové divergence, která říká, že dva grafy jsou blízko, když jsou jejich hustoty hran blízko na všech jejich odpovídajících podmnožinách vrcholů.

Jako zázrakem posloupnost grafů konverguje vzhledem k jedné vzdálenosti právě tehdy, když konverguje vzhledem k jiné. Navíc se ukázalo, že limitními objekty v obou metrikách jsou grafony. Ekvivalence těchto dvou pojmů konvergence odráží ekvivalenci různých pojmů kvazináhodných grafů. [2]

Literatura

↑ Orbanz, P. (2015). „Bayesovské modely grafů, polí a jiných výměnných náhodných struktur“. Transakce IEEE na analýze vzorů a strojové inteligenci . 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). „Kvazináhodné grafy“ . Kombinatorika . 9 (4): 345-362. DOI : 10.1007/BF02125347 .

L. N. Corellano, A. A. Razborov . Sémantické limity hustých kombinatorických objektů // Uspekhi Mat . - 2020. - T. 75 , č. 4 (454) . — S. 45–152 . - doi : 10,4213/rm9956 . (Ruština)