Grafon (grafteori)

En grafon är en slumpmässig grafmodell, en generalisering av Erdős-Rényi-modellen . Grafoner uppstår naturligt i studien av gränsbeteendet för en sekvens av grafer .

Definition

En grafon är en symmetrisk mätbar funktion . $W:[0,1]^{2}\to [0,1]$

En grafon förstås vanligtvis som en modell av en slumpmässig graf enligt följande schema:

Varje vertex i grafen tilldelas ett oberoende slumpmässigt värde $j$ $u_{j}\in [0,1]$
En kant ingår oberoende av varandra i grafen med sannolikhet . $(I j)$ $W(u_{i},u_{j})$

Den grafonbaserade modellen betecknas ibland som , i analogi med Erdős-Rényis slumpmässiga grafmodell . En graf som skapas från en grafon på detta sätt kallas en -slumpmässig graf. $W$ $\mathbb {G} (n,W)$ $W$ $W$

Exempel

Det enklaste exemplet på en grafon: för någon konstant . I det här fallet är den associerade ersättningsmodellen för den slumpmässiga grafen Erdős-Rényi-modellen som inkluderar varje kant oberoende av varandra med sannolikhet . $W(x,y)\equiv p$ $p\in [0,1]$ $G(n,p)$ $sid$

Om vi istället börjar med en bitvis konstant grafon:

uppdelning av enhetstorget i block och $k\times k$
parameter lika med block, $W$ ${\displaystyle p_{lm))$ $(l,m)^{\text{th))$

då är den resulterande slumpmässiga grafmodellen en stokastisk blockgeneralisering av Erdős-Rényi-modellen. Vi kan tolka det som en slumpmässig grafmodell bestående av olika Erdős-Rényi-grafer med respektive parametrar, med bigrafer mellan dem, där varje möjlig kant mellan blocken och även ingår oberoende med sannolikhet . $k$ $k$ ${\displaystyle p_{ll))$ $(l,l)$ $(m,m)$ ${\displaystyle p_{lm))$

Många andra slumpmässiga grafmodeller kan definieras av en grafon. [ett]

Konvergensbegrepp

Det finns många olika sätt att mäta avståndet mellan två grafer. Om vi är intresserade av mått som bevarar grafernas extrema egenskaper, måste vi begränsa vår uppmärksamhet till mått som identifierar slumpmässiga grafer som näraliggande. Till exempel, om vi slumpmässigt konstruerar två grafer oberoende av varandra med hjälp av Erdős-Rényi-modellen för en fast , då bör avståndet mellan dessa två grafer för ett rimligt mått vara nära noll med hög sannolikhet för stor . $G(n,p)$ $sid$ $n$

I denna mening finns det två naturliga mått som fungerar bra på slumpmässiga grafer. Den första är samplingsmåttet, som säger att två grafer är nära om deras subgraffördelningar är nära. Den andra är kantdivergensmåttet, som säger att två grafer är nära när deras kantdensiteter är nära på alla deras motsvarande delmängder av hörn.

Mirakulöst nog konvergerar en sekvens av grafer med avseende på ett avstånd om, och endast om, det konvergerar med avseende på ett annat. Dessutom visar sig gränsobjekten i båda måtten vara grafoner. Ekvivalensen av dessa två begrepp om konvergens återspeglar ekvivalensen av olika begrepp om kvasi-slumpmässiga grafer. [2]

Litteratur

↑ Orbanz, P. (2015). "Bayesianska modeller av grafer, matriser och andra utbytbara slumpmässiga strukturer". IEEE-transaktioner på mönsteranalys och maskinintelligens . 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). "Kvasislumpmässiga grafer" . Combinatorica . 9 (4): 345-362. DOI : 10.1007/BF02125347 .

L.N. Corellano, A.A. Razborov . Semantiska gränser för täta kombinatoriska objekt // Uspekhi Mat . - 2020. - T. 75 , nr 4 (454) . — S. 45–152 . - doi : 10.4213/rm9956 . (ryska)