Tilfældig graf - Random graph

I matematik er tilfældig graf det generelle udtryk for at referere til sandsynlighedsfordelinger over grafer . Tilfældige grafer kan ganske enkelt beskrives ved en sandsynlighedsfordeling eller ved en tilfældig proces, der genererer dem. Teorien om tilfældige grafer ligger i skæringspunktet mellem grafteori og sandsynlighedsteori . Fra et matematisk perspektiv bruges tilfældige grafer til at besvare spørgsmål om typiske grafers egenskaber . Dens praktiske anvendelser findes på alle områder, hvor komplekse netværk skal modelleres - mange tilfældige grafmodeller kendes således, hvilket afspejler de forskellige typer komplekse netværk, der findes i forskellige områder. I en matematisk kontekst refererer tilfældig graf næsten udelukkende til Erdős - Rényi tilfældig grafmodel . I andre sammenhænge kan enhver grafmodel omtales som en tilfældig graf .

Modeller

En tilfældig graf opnås ved at starte med et sæt n isolerede hjørner og tilføje successive kanter mellem dem tilfældigt. Formålet med undersøgelsen på dette område er at bestemme på hvilket trin en bestemt egenskab af grafen sandsynligvis vil opstå. Forskellige tilfældige grafmodeller producerer forskellige sandsynlighedsfordelinger på grafer. Mest undersøgt er den foreslåede af Edgar Gilbert , betegnet G ( n , p ), hvor hver mulig kant forekommer uafhængigt med sandsynlighed 0 < p <1. Sandsynligheden for at opnå en bestemt tilfældig graf med m -kanter er med notationen . ${\ displaystyle p^{m} (1-p)^{Nm}}$ ${\ displaystyle N = {\ tbinom {n} {2}}}$

En nært beslægtet model, Erdős – Rényi -modellen betegnet G ( n , M ), tildeler alle sandsynligheder lige stor sandsynlighed for alle grafer med præcis M -kanter. Med 0 ≤ M ≤ N har G ( n , M ) elementer, og hvert element forekommer med sandsynlighed . Sidstnævnte model kan ses som et øjebliksbillede på et bestemt tidspunkt ( M ) i den tilfældige grafproces , som er en stokastisk proces, der starter med n hjørner og ingen kanter, og ved hvert trin tilføjer en ny kant valgt ensartet fra sættet af manglende kanter. ${\ displaystyle {\ tbinom {N} {M}}}$ ${\ displaystyle 1/{\ tbinom {N} {M}}}$ ${\ displaystyle {\ tilde {G}} _ {n}}$

Hvis vi i stedet starter med et uendeligt sæt hjørner, og igen lader enhver mulig kant forekomme uafhængigt med sandsynlighed 0 < p <1, så får vi et objekt G kaldet en uendelig tilfældig graf . Undtagen i de trivielle tilfælde, når p er 0 eller 1, har et sådant G næsten helt sikkert følgende egenskab:

I betragtning af n + m -elementer er der et toppunkt c i V , der støder op til hver af og ikke støder op til nogen af . ${\ displaystyle a_ {1}, \ ldots, a_ {n}, b_ {1}, \ ldots, b_ {m} \ i V}$ ${\ displaystyle a_ {1}, \ ldots, a_ {n}}$ ${\ displaystyle b_ {1}, \ ldots, b_ {m}}$

Det viser sig, at hvis toppunktsættet er tællbart, er der op til isomorfisme kun en enkelt graf med denne egenskab, nemlig Rado -grafen . Således er enhver uendelig tilfældig graf næsten helt sikkert Rado -grafen, som af denne grund undertiden kaldes simpelthen den tilfældige graf . Imidlertid er det analoge resultat ikke sandt for utallige grafer, hvoraf der er mange (nonisomorfe) grafer, der opfylder ovenstående egenskab.

En anden model, der generaliserer Gilberts tilfældige grafmodel, er tilfældig prikproduktmodel . En tilfældig prik-produktgraf forbinder med hvert toppunkt en reel vektor . Sandsynligheden for en kant uv mellem eventuelle hjørner u og v er en funktion af prikproduktet u • v for deres respektive vektorer.

De netværk sandsynlighed matrix modeller tilfældige grafer gennem kant sandsynligheder, som repræsenterer sandsynligheden for , at en given kant findes for en specificeret tidsperiode. Denne model kan udvides til instrueret og ikke -styret; vægtet og uvægtet; og statisk eller dynamisk grafstruktur. ${\ displaystyle p_ {i, j}}$ ${\ displaystyle e_ {i, j}}$

For M ≃ pN , hvor N er det maksimale antal kanter, er de to mest udbredte modeller, G ( n , M ) og G ( n , p ), næsten udskiftelige.

Tilfældige almindelige grafer danner et specielt tilfælde med egenskaber, der kan afvige fra tilfældige grafer generelt.

Når vi har en model af tilfældige grafer, bliver hver funktion på grafer til en tilfældig variabel . Undersøgelsen af denne model er at afgøre, om eller i det mindste estimere sandsynligheden for, at en ejendom kan forekomme.

Terminologi

Udtrykket 'næsten alle' i sammenhæng med tilfældige grafer refererer til en sekvens af mellemrum og sandsynligheder, således at fejlsandsynlighederne har en tendens til nul.

Ejendomme

Teorien om tilfældige grafer studerer typiske egenskaber ved tilfældige grafer, dem, der med stor sandsynlighed holder for grafer trukket fra en bestemt fordeling. For eksempel kan vi bede om en given værdi af, og hvad sandsynligheden er, der er forbundet . Ved at studere sådanne spørgsmål koncentrerer forskere sig ofte om tilfældige graferes asymptotiske adfærd - de værdier, som forskellige sandsynligheder konvergerer til, efterhånden som de vokser meget store. Perkolationsteori karakteriserer sammenhængen mellem tilfældige grafer, især uendeligt store. ${\ displaystyle n}$ ${\ displaystyle p}$ ${\ displaystyle G (n, p)}$ ${\ displaystyle n}$

Perkolering er relateret til grafens robusthed (kaldes også netværk). Givet en tilfældig graf over noder og en gennemsnitlig grad . Dernæst fjerner vi tilfældigt en brøkdel af noder og efterlader kun en brøkdel . Der findes en kritisk perkolationstærskel, under hvilken netværket bliver fragmenteret, mens der over en kæmpe forbundet komponent eksisterer. ${\ displaystyle n}$ ${\ displaystyle \ langle k \ rangle}$ ${\ displaystyle 1-p}$ ${\ displaystyle p}$ ${\ displaystyle p_ {c} = {\ tfrac {1} {\ langle k \ rangle}}}$ ${\ displaystyle p_ {c}}$

Lokaliseret perkolering refererer til fjernelse af en knude, dens naboer, næste nærmeste naboer osv., Indtil en brøkdel af noder fra netværket er fjernet. Det blev vist, at for tilfældig graf med Poisson -fordeling af grader nøjagtigt som for tilfældig fjernelse. For andre former for gradfordelinger for lokaliseret angreb er forskellig fra tilfældigt angreb (tærskelfunktioner, udvikling af ) ${\ displaystyle 1-p}$ ${\ displaystyle p_ {c} = {\ tfrac {1} {\ langle k \ rangle}}}$ ${\ displaystyle p_ {c}}$ ${\ displaystyle {\ tilde {G}}}$

Tilfældige grafer bruges meget i den probabilistiske metode , hvor man forsøger at bevise eksistensen af grafer med visse egenskaber. Eksistensen af en ejendom på en tilfældig graf kan ofte via Szemerédi regelmæssighedslemma indebære eksistensen af denne egenskab på næsten alle grafer.

I tilfældige regelmæssige grafer , er det sæt af -det af regelmaessige grafer med sådan, at og er de naturlige tal, og er endda. ${\ displaystyle G (n, r-reg)}$ ${\ displaystyle r}$ ${\ displaystyle r = r (n)}$ ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ displaystyle 3 \ leq r <n}$ ${\ displaystyle rn = 2m}$

Gradsekvensen for en graf i afhænger kun af antallet af kanter i sætene ${\ displaystyle G}$ ${\ displaystyle G^{n}}$

{\ displaystyle V_ {n}^{(2)} = \ left \ {ij \: \ 1 \ leq j \ leq n, i \ neq j \ right \} \ undersæt V^{(2)}, \ qquad i = 1, \ cdots, n.}

Hvis kanterne i en tilfældig graf er store nok til at sikre, at næsten alle har minimumsgrad mindst 1, så er næsten alle forbundet og, hvis det er lige, næsten alle har en perfekt matchning. Især i det øjeblik det sidste isolerede toppunkt forsvinder i næsten hver tilfældig graf, bliver grafen forbundet. ${\ displaystyle M}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle n}$ ${\ displaystyle G_ {M}}$

Næsten hver grafproces på et lige antal hjørner med kanten, der hæver minimumsgraden til 1 eller en tilfældig graf med lidt mere end kanter og med sandsynlighed tæt på 1, sikrer, at grafen har en fuldstændig matchning, med undtagelse af højst et toppunkt . ${\ displaystyle {\ tfrac {n} {4}} \ log (n)}$

For nogle konstante er næsten hver mærket graf med hjørner og i det mindste kanter Hamiltonian . Med sandsynligheden tilbøjelig til 1, gør den særlige kant, der øger minimumsgraden til 2, grafen til Hamilton. ${\ displaystyle c}$ ${\ displaystyle n}$ ${\ displaystyle cn \ log (n)}$

Egenskaber for tilfældig graf kan ændre sig eller forblive uforanderlige under grafomdannelser. Mashaghi A. et al. Viste for eksempel, at en transformation, der konverterer tilfældige grafer til deres kant-dobbelte grafer (eller linjediagrammer), producerer et ensemble af grafer med næsten samme gradfordeling, men med gradskorrelationer og en betydeligt højere klynger koefficient.

Farvelægning

I betragtning af en tilfældig graf G af rækkefølge n med toppunktet V ( G ) = {1, ..., n }, af den grådige algoritme om antallet af farver, kan hjørnerne farves med farverne 1, 2, ... (toppunkt 1 er farvet 1, toppunkt 2 er farvet 1, hvis det ikke støder op til toppunkt 1, ellers er det farvet 2 osv.). Antallet af korrekte farvninger af tilfældige grafer givet et antal q farver, kaldet dets kromatiske polynom , er hidtil ukendt. Skalering af nuller i det kromatiske polynom af tilfældige grafer med parametre n og antallet af kanter m eller forbindelsessandsynligheden p er blevet undersøgt empirisk ved hjælp af en algoritme baseret på symbolsk mønstermatchning.

Tilfældige træer

Et tilfældigt træ er et træ eller arborescens , der dannes ved en stokastisk proces . I et stort udvalg af tilfældige grafer af rækkefølge n og størrelse M ( n ) er fordelingen af antallet af trækomponenter i rækkefølge k asymptotisk Poisson . Typer af tilfældige træer omfatter ensartet spændingstræ , tilfældigt minimalt spændende træ , tilfældigt binært træ , treap , hurtigt udforskende tilfældigt træ , brunt træ og tilfældig skov .

Betingede tilfældige grafer

Overvej en given tilfældig grafmodel defineret på sandsynlighedsrummet, og lad være en reel værdsat funktion, der tildeler hver graf i en vektor med m -egenskaber. For en fast , betinget tilfældig graf er modeller, hvor sandsynlighedsmålet tildeler nul sandsynlighed til alle grafer, således at ' . ${\ displaystyle (\ Omega, {\ mathcal {F}}, P)}$ ${\ displaystyle {\ mathcal {P}} (G): \ Omega \ højre pil R^{m}}$ ${\ displaystyle \ Omega}$ ${\ displaystyle \ mathbf {p} \ i R^{m}}$ ${\ displaystyle P}$ ${\ displaystyle {\ mathcal {P}} (G) \ neq \ mathbf {p}}$

Specialtilfælde er betinget ensartede tilfældige grafer , hvor alle grafer har specificerede egenskaber tildelt lige stor sandsynlighed. De kan ses som en generalisering af Erdős – Rényi -modellen G ( n , M ), når konditioneringsinformationen ikke nødvendigvis er antallet af kanter M , men uanset hvilken anden vilkårlig grafegenskab . I dette tilfælde er meget få analytiske resultater tilgængelige, og simulering er påkrævet for at opnå empiriske fordelinger af gennemsnitlige egenskaber. ${\ displaystyle P}$ ${\ displaystyle {\ mathcal {P}} (G)}$

Indbyrdes afhængige grafer

I indbyrdes afhængige grafer er noder i et netværk (graf) afhængige af, at andre netværk fungerer. Så fejl i en eller flere grafer forårsager kaskadefejl mellem graferne, hvilket kan føre til pludseligt sammenbrud.

Historie

Den tidligste brug af en tilfældig grafmodel var af Helen Hall Jennings og Jacob Moreno i 1938, hvor et "tilfældigt sociogram" (en instrueret Erdős-Rényi-model) blev overvejet ved undersøgelse af sammenligning af brøkdelen af gengældte links i deres netværksdata med den tilfældige model . En anden anvendelse, under navnet "tilfældigt net", var af Solomonoff og Rapoport i 1951 ved hjælp af en model af rettede grafer med faste ud-grader og tilfældigt valgte vedhæftede filer til andre hjørner.

Den Erdös-Renyi model af tilfældige grafer blev først defineret af Paul Erdős og Alfréd Renyi i deres 1959 papir "On Random Grafer" og uafhængigt af Gilbert i hans papir "Random grafer".

Languages

In other projects