Grafon (graafiteoria)

Graafi on satunnainen graafimalli, Erdős- Rényi-mallin yleistys . Grafonit syntyvät luonnollisesti graafisen sarjan rajakäyttäytymisen tutkimuksessa .

Määritelmä

Grafoni on symmetrinen mitattavissa oleva funktio . $W:[0,1]^{2}\to [0,1]$

Grafonia pidetään yleensä satunnaisen graafin mallina seuraavan kaavion mukaisesti:

Jokaiselle graafin kärjelle on määritetty itsenäinen satunnaisarvo $j$ $u_{j}\in [0,1]$
Reuna sisältyy graafiin itsenäisesti todennäköisyydellä . $(i,j)$ $W(u_{i},u_{j})$

Grafonipohjaista mallia kutsutaan joskus nimellä , analogisesti Erdős-Rényin satunnaisgraafimallin kanssa . Graafista tällä tavalla luotua graafia kutsutaan -satunnaisgraafiksi. $W$ $\mathbb {G} (n,W)$ $W$ $W$

Esimerkkejä

Yksinkertaisin esimerkki grafonista: jollekin vakiolle . Tässä tapauksessa satunnaisgraafiin liittyvä korvausmalli on Erdős-Rényi-malli, joka sisältää jokaisen reunan itsenäisesti todennäköisyydellä . $W(x,y)\equiv p$ $p\in [0,1]$ $G(n,p)$ $s$

Jos sen sijaan aloitamme paloittain vakiografonilla:

yksikköneliön jakaminen lohkoihin ja $k\times k$
parametri sama kuin lohko, $W$ ${\displaystyle p_{lm))$ ${\näyttötyyli (l,m)^{\teksti{th))}$

niin tuloksena saatu satunnaisgraafimalli on Erdős-Rényi-mallin stokastinen lohkoyleistys. Voimme tulkita sen satunnaisena graafimallina, joka koostuu erilaisista Erdős-Rényi-graafista parametreineen , niiden välissä bigrafeilla, jossa jokainen mahdollinen lohkojen välinen reuna on mukana myös itsenäisesti todennäköisyydellä . $k$ $k$ ${\displaystyle p_{ll))$ ${\näyttötyyli (l,l)}$ ${\näyttötyyli (m, m)}$ ${\displaystyle p_{lm))$

Monet muut satunnaiset graafimallit voidaan määrittää grafonilla. [yksi]

Lähentymisen käsitteet

Kahden kaavion välisen etäisyyden mittaamiseen on monia eri tapoja. Jos olemme kiinnostuneita mittareista, jotka säilyttävät graafien äärimmäiset ominaisuudet, meidän on rajoitettava huomiomme mittareihin, jotka tunnistavat satunnaiset kaaviot läheisiksi. Jos esimerkiksi rakennamme satunnaisesti kaksi kuvaajaa toisistaan riippumatta käyttämällä Erdős-Rényi-mallia kiinteälle , niin näiden kahden kaavion välisen etäisyyden tulisi järkevässä metriikassa olla lähellä nollaa suurella todennäköisyydellä . $G(n,p)$ $s$ $n$

Tässä mielessä on olemassa kaksi luonnollista mittaria, jotka toimivat hyvin satunnaisissa kaavioissa. Ensimmäinen on otantametriikka, joka sanoo, että kaksi kuvaajaa ovat lähellä, jos niiden alagraafijakaumat ovat lähellä. Toinen on reunadivergenssin metriikka, joka sanoo, että kaksi kuvaajaa ovat lähellä, kun niiden reunatiheydet ovat lähellä niitä kaikkia vastaavia kärkien osajoukkoja.

Ihme kyllä, kaaviosarja konvergoi yhden etäisyyden suhteen, jos ja vain jos se suppenee suhteessa toiseen. Lisäksi molempien mittareiden rajaobjektit osoittautuvat grafoneiksi. Näiden kahden konvergenssikäsitteen vastaavuus heijastaa kvasisatunnaisten graafien eri käsitteiden vastaavuutta. [2]

Kirjallisuus

↑ Orbanz, P. (2015). "Bayesian mallit graafisista, taulukoista ja muista vaihdettavissa olevista satunnaisrakenteista". IEEE Transactions on Pattern Analysis and Machine Intelligence . 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). "Kesasatunnaiset kaaviot" . Combinatorica . 9 (4): 345-362. DOI : 10.1007/BF02125347 .

L. N. Corellano, A. A. Razborov . Tiheiden kombinatoristen objektien semanttiset rajat // Uspekhi Mat . - 2020. - T. 75 , nro 4 (454) . — S. 45–152 . - doi : 10.4213/rm9956 . (Venäjän kieli)