Slumpmässig graf - Random graph

I matematik är slumpmässig graf den allmänna termen för att hänvisa till sannolikhetsfördelningar över grafer . Slumpmässiga grafer kan beskrivas helt enkelt genom en sannolikhetsfördelning eller genom en slumpmässig process som genererar dem. Teorin om slumpmässiga grafer ligger i skärningspunkten mellan grafteori och sannolikhetsteori . Ur ett matematiskt perspektiv används slumpmässiga grafer för att svara på frågor om egenskaperna hos typiska grafer. Dess praktiska tillämpningar finns inom alla områden där komplexa nätverk måste modelleras - många slumpmässiga grafmodeller är således kända, vilket speglar de olika typerna av komplexa nätverk som möts i olika områden. I ett matematiskt sammanhang hänvisar slumpmässig graf nästan uteslutande till slumpmässig grafmodell Erdős – Rényi . I andra sammanhang kan vilken grafmodell som helst kallas en slumpmässig graf .

Modeller

En slumpmässig graf erhålls genom att börja med en uppsättning n isolerade hörn och lägga till på varandra följande kanter slumpmässigt. Syftet med studien inom detta område är att bestämma i vilket skede en viss egenskap hos grafen sannolikt kommer att uppstå. Olika slumpmässiga grafmodeller producerar olika sannolikhetsfördelningar på grafer. Mest studerade är den föreslagna av Edgar Gilbert , betecknad G ( n , p ), där varje möjlig kant uppstår oberoende med sannolikhet 0 < p <1. Sannolikheten för att erhålla en viss slumpmässig graf med m -kanter är med notationen . ${\ displaystyle p^{m} (1-p)^{Nm}}$ ${\ displaystyle N = {\ tbinom {n} {2}}}$

En nära besläktad modell, Erdős – Rényi -modellen betecknad G ( n , M ), tilldelar alla grafer lika sannolikhet med exakt M -kanter. Med 0 ≤ M ≤ N har G ( n , M ) element och varje element uppstår med sannolikhet . Den senare modellen kan ses som en ögonblicksbild vid en viss tidpunkt ( M ) i den slumpmässiga grafprocessen , vilket är en stokastisk process som börjar med n hörn och inga kanter, och vid varje steg lägger till en ny kant som valts enhetligt från uppsättningen av saknade kanter. ${\ displaystyle {\ tbinom {N} {M}}}$ ${\ displaystyle 1/{\ tbinom {N} {M}}}$ ${\ displaystyle {\ tilde {G}} _ {n}}$

Om vi istället börjar med en oändlig uppsättning hörn, och återigen låter varje möjlig kant uppstå oberoende med sannolikhet 0 < p <1, då får vi ett objekt G som kallas ett oändligt slumpmässigt diagram . Förutom i de triviala fallen när p är 0 eller 1, har ett sådant G nästan säkert följande egenskap:

Med tanke på några n + m -element finns det en toppunkt c i V som ligger intill var och en av och inte ligger intill någon av . ${\ 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 visar sig att om toppunktsuppsättningen kan räknas så finns det, upp till isomorfism , bara en enda graf med denna egenskap, nämligen Rado -grafen . Således är varje oändligt oändlig slumpmässig graf nästan säkert Rado -grafen, som av denna anledning ibland kallas helt enkelt slumpmässig graf . Det analoga resultatet är emellertid inte sant för oräkneliga grafer, av vilka det finns många (icke -isomorfa) grafer som uppfyller ovanstående egenskap.

En annan modell, som generaliserar Gilberts slumpmässiga grafmodell, är den slumpmässiga punktproduktmodellen . En slumpmässig punkt-produkt-graf associerar med varje toppunkt en riktig vektor . Sannolikheten för en kant uv mellan alla hörn u och v är en funktion av prickprodukten u • v för deras respektive vektorer.

De nätverkssannolikhetsmatrismodeller slumpmässiga grafer genom kant sannolikheter, som representerar sannolikheten att en given kant existerar för en angiven tidsperiod. Denna modell kan utvidgas till regisserad och ostyrd; viktade och oviktade; och statisk eller dynamisk grafstruktur. ${\ displaystyle p_ {i, j}}$ ${\ displaystyle e_ {i, j}}$

För M ≃ pN , där N är det maximala antalet kanter, är de två mest använda modellerna, G ( n , M ) och G ( n , p ), nästan utbytbara.

Slumpmässiga vanliga grafer utgör ett specialfall, med egenskaper som kan skilja sig från slumpmässiga grafer i allmänhet.

När vi väl har en modell av slumpmässiga grafer blir varje funktion på graferna en slumpmässig variabel . Studien av denna modell är att avgöra om, eller åtminstone uppskatta sannolikheten för att en egendom kan inträffa.

Terminologi

Termen "nästan varje" i sammanhanget med slumpmässiga grafer hänvisar till en sekvens av mellanslag och sannolikheter, så att fel sannolikheter tenderar att nollas.

Egenskaper

Teorin om slumpmässiga grafer studerar typiska egenskaper hos slumpmässiga grafer, de som med stor sannolikhet håller för grafer som hämtas från en viss fördelning. Till exempel kan vi be om ett givet värde på och vilken sannolikhet som är kopplad . Vid studier av sådana frågor koncentrerar forskare sig ofta på det asymptotiska beteendet hos slumpmässiga grafer - värdena som olika sannolikheter konvergerar till när de växer sig mycket stora. Perkolationsteorin kännetecknar sambandet mellan slumpmässiga grafer, särskilt oändligt stora. ${\ displaystyle n}$ ${\ displaystyle p}$ ${\ displaystyle G (n, p)}$ ${\ displaystyle n}$

Perkolering är relaterat till grafens robusthet (kallas även nätverk). Med ett slumpmässigt diagram över noder och en genomsnittlig grad . Därefter tar vi bort slumpmässigt en bråkdel av noder och lämnar bara en bråkdel . Det finns en kritisk perkoleringströskel under vilken nätverket blir fragmenterat medan det finns en gigantisk ansluten komponent. ${\ displaystyle n}$ ${\ displaystyle \ langle k \ rangle}$ ${\ displaystyle 1-p}$ ${\ displaystyle p}$ ${\ displaystyle p_ {c} = {\ tfrac {1} {\ langle k \ rangle}}}$ ${\ displaystyle p_ {c}}$

Lokaliserad perkolering avser att ta bort en nod dess grannar, närmaste närmaste grannar etc. tills en bråkdel av noder från nätverket har tagits bort. Det visades att för slumpmässig graf med Poisson -fördelning av grader exakt som för slumpmässig borttagning. För andra typer av examensfördelningar för lokaliserad attack skiljer sig från slumpmässiga attacker (tröskelfunktioner, utveckling av ) ${\ displaystyle 1-p}$ ${\ displaystyle p_ {c} = {\ tfrac {1} {\ langle k \ rangle}}}$ ${\ displaystyle p_ {c}}$ ${\ displaystyle {\ tilde {G}}}$

Slumpmässiga grafer används ofta i den probabilistiska metoden , där man försöker bevisa förekomsten av grafer med vissa egenskaper. Förekomsten av en egenskap på en slumpmässig graf kan ofta innebära att egenskapen finns på nästan alla grafer via Szemerédi -regelbundenhetslemma.

I slump reguljär graf , är uppsättningen av -regular grafer med så att och är de naturliga talen, och är jämn. ${\ displaystyle G (n, r-reg)}$ ${\ displaystyle r}$ ${\ displaystyle r = r (n)}$ ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ displaystyle 3 \ leq r <n}$ ${\ displaystyle rn = 2m}$

Graden sekvens av en graf i beror endast på antalet kanter i uppsättningarna ${\ displaystyle G}$ ${\ displaystyle G^{n}}$

{\ displaystyle V_ {n}^{(2)} = \ vänster \ {ij \: \ 1 \ leq j \ leq n, i \ neq j \ höger \} \ delmängd V^{(2)}, \ qquad i = 1, \ cdots, n.}

Om kanterna, i en slumpmässig graf, är tillräckligt stora för att säkerställa att nästan alla har minsta grad minst 1, så är nästan alla anslutna och, om det är jämnt, nästan alla har en perfekt matchning. I synnerhet i det ögonblick som den sista isolerade hörnet försvinner i nästan varje slumpmässig graf, blir grafen ansluten. ${\ displaystyle M}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle G_ {M}}$ ${\ displaystyle n}$ ${\ displaystyle G_ {M}}$

Nästan varje grafprocess på ett jämnt antal hörn med kanten som höjer minsta graden till 1 eller en slumpmässig graf med något mer än kanterna och med sannolikhet nära 1 säkerställer att grafen har en fullständig matchning, med undantag för högst en toppunkt . ${\ displaystyle {\ tfrac {n} {4}} \ log (n)}$

För någon konstant är nästan varje märkt graf med hörn och åtminstone kanter Hamiltonian . Eftersom sannolikheten tenderar till 1, gör den speciella kanten som ökar miniminivån till 2 grafen Hamilton. ${\ displaystyle c}$ ${\ displaystyle n}$ ${\ displaystyle cn \ log (n)}$

Egenskaper för slumpmässig graf kan förändras eller förbli oföränderliga under grafomvandlingar. Mashaghi A. et al., Till exempel, visade att en transformation som omvandlar slumpmässiga grafer till sina kant-dubbla grafer (eller linjediagram) ger en ensemble av grafer med nästan samma gradfördelning, men med gradskorrelationer och en betydligt högre gruppering. koefficient.

Färg

Med en slumpmässig graf G i ordning n med toppunktet V ( G ) = {1, ..., n }, med den giriga algoritmen för antalet färger, kan hörnen färgas med färgerna 1, 2, ... (toppunkt 1 är färgad 1, toppunkt 2 är färgad 1 om den inte ligger i anslutning till toppunkt 1, annars är den färgad 2, etc.). Antalet korrekta färgningar av slumpmässiga grafer med ett antal q -färger, kallat dess kromatiska polynom , förblir okänt än så länge. Skalningen av nollor för det kromatiska polynomet för slumpmässiga grafer med parametrar n och antalet kanter m eller anslutningssannolikheten p har studerats empiriskt med hjälp av en algoritm baserad på symbolisk mönstermatchning.

Slumpmässiga träd

Ett slumpmässigt träd är ett träd eller arborescens som bildas av en stokastisk process . I ett stort antal slumpmässiga grafer av ordning n och storlek M ( n ) är fördelningen av antalet trädkomponenter i ordning k asymptotiskt Poisson . Typer av slumpmässiga träd inkluderar enhetligt spanträd , slumpmässigt minimalt spanträd , slumpmässigt binärt träd , treap , snabbt utforskande slumpmässigt träd , brunträd och slumpmässig skog .

Villkorliga slumpmässiga grafer

Tänk på en given slumpmässig grafmodell definierad på sannolikhetsutrymmet och låt vara en verklig värderad funktion som tilldelar varje graf i en vektor med m -egenskaper. För en fast , villkorlig slumpmässig graf är modeller där sannolikhetsmåttet tilldelar noll sannolikhet till alla grafer så att ' . ${\ displaystyle (\ Omega, {\ mathcal {F}}, P)}$ ${\ displaystyle {\ mathcal {P}} (G): \ Omega \ högerpil R^{m}}$ ${\ displaystyle \ Omega}$ ${\ displaystyle \ mathbf {p} \ i R^{m}}$ ${\ displaystyle P}$ ${\ displaystyle {\ mathcal {P}} (G) \ neq \ mathbf {p}}$

Specialfall är villkorligt enhetliga slumpmässiga grafer , där tilldelar lika stor sannolikhet för alla grafer som har specificerade egenskaper. De kan ses som en generalisering av Erdős – Rényi -modellen G ( n , M ), när konditioneringsinformationen inte nödvändigtvis är antalet kanter M , utan vilken annan godtycklig grafegenskap som helst . I detta fall finns mycket få analysresultat tillgängliga och simulering krävs för att erhålla empiriska fördelningar av genomsnittliga egenskaper. ${\ displaystyle P}$ ${\ displaystyle {\ mathcal {P}} (G)}$

Beroendeberoende grafer

I ömsesidigt beroende diagram är noder i ett nätverk (graf) beroende av att andra nätverk fungerar. Så misslyckanden i en eller flera grafer framkallar kaskadfel mellan graferna vilket kan leda till abrupt kollaps.

Historia

Den tidigaste användningen av en slumpmässig grafmodell var av Helen Hall Jennings och Jacob Moreno 1938 där ett "chanssociogram" (en regisserad Erdős-Rényi-modell) övervägdes för att studera jämförelsen av andelen återlänkade länkar i deras nätverksdata med den slumpmässiga modellen . En annan användning, under namnet "slumpmässigt nät", var av Solomonoff och Rapoport 1951, med en modell av riktade grafer med fasta utgrader och slumpmässigt valda bilagor till andra hörn.

Den Erdős-Renyi modell av slumpmässiga grafer först definieras av Paul Erdős och Alfréd Renyi i sin 1959 papper "på Random Graphs" och oberoende av Gilbert i sin uppsats "Random grafer".

Languages

In other projects