Erdős-Renyi malli

Erdős-Rényi-malli on yksi kahdesta läheisesti liittyvästä satunnaiskuvaajan generointimallista . Mallit on nimetty matemaatikoiden Pal Erdősin ja Alfred Rényin mukaan, jotka ensimmäisen kerran esittelivät yhden malleista vuonna 1959 [1] [2] , kun taas Edgar Hilbert ehdotti toista mallia samanaikaisesti ja Erdősistä ja Rényistä riippumatta [3] . Erdősin ja Rényin mallissa kaikki graafit, joissa on kiinteä kärkijoukko ja kiinteä joukko reunoja, ovat yhtä todennäköisiä. Hilbertin mallissa jokaisella reunalla on kiinteä läsnäolo- tai poissaolotodennäköisyys muista reunoista riippumatta . Näitä malleja voidaan käyttää probabilistisessa menetelmässäeri ominaisuuksia tyydyttävien graafien olemassaolon todistamiseksi tai tarkan määritelmän antamiseksi tämän ominaisuuden katsotaan pätevän lähes kaikille kaavioille.

Määritelmä

Satunnaisgraafin Erdős-Rényi-mallista on kaksi läheisesti liittyvää versiota.

Mallissa graafi valitaan tasaisesti ja satunnaisesti kaikkien graafien joukosta, joilla on n kärkeä ja M reunaa. Esimerkiksi mallissa jokainen kolmesta mahdollisesta graafista, jossa on kolme kärkeä ja kaksi reunaa, valitaan todennäköisyydellä 1/3. $G(n,M)$ $G(3,2)$
Mallissa graafi rakennetaan satunnaisesti lisäämällä reunoja. Jokainen reuna sisältyy kuvaajaan todennäköisyydellä p riippumatta muista reunoista. Vastaavasti kaikilla kaavioilla, joissa on n solmua ja M reunaa, on sama todennäköisyys. $G(n,p)$

p^{M}(1-p)^{{n \choose 2}-M}.

Tämän mallin parametria p voidaan pitää painon funktiona. Kun p kasvaa arvosta 0 arvoon 1, malli sisältää todennäköisemmin kaavioita, joissa on enemmän reunoja. Erityisesti tapaus p = 0,5 vastaa tapausta, jossa kaikki n -pisteiset graafit valitaan samalla todennäköisyydellä.

2^{\binom {n}{2))

Satunnaisten graafien käyttäytymistä tutkitaan usein, kun n , graafin kärkien lukumäärä, pyrkii äärettömään. Vaikka p ja M voivat olla kiinteitä tässä tapauksessa, ne voivat myös riippua n:n funktiosta . Esimerkiksi lausunto

Lähes kaikki kaaviot ovat yhteydessä toisiinsa

G(n,2ln(n)/n)

tarkoittaa

Koska n pyrkii äärettömyyteen, todennäköisyys, että graafi, jossa on n kärkeä ja reunan inkluusiotodennäköisyys 2ln( n )/ n , on yhdistetty, on yleensä 1.

Kahden mallin vertailu

Reunojen lukumäärän matemaattinen odotus on yhtä suuri kuin , ja suurten lukujen lain mukaan missä tahansa B:n graafissa on lähes varmasti suunnilleen tämä määrä reunoja. Siksi karkeasti sanottuna jos , niin G ( n , p ) pitäisi käyttäytyä kuten G ( n , M ) s n kasvaessa . $G(n,p)$ ${\tbinom {n}{2}}p$ $G(n,p)$ $pn^{2}\to \infty$ $M={\tbinom {n}{2}}p$

Tämä koskee monia graafin ominaisuuksia. Jos P on mikä tahansa graafin ominaisuus, joka on monotoninen osagraafin järjestyksen suhteen (eli jos A on B :n osagraafi ja A täyttää P , niin B täyttää myös arvon P ), lauseet " P pätee lähes kaikkiin graafisiin in " ja " P pätee melkein kaikkiin kaavioihin " ovat samanarvoisia (for ). Tämä pätee esimerkiksi, jos P :llä on ominaisuus olla yhteydessä tai jos P :llä on Hamiltonin syklin ominaisuus . Tämä ei kuitenkaan välttämättä päde ei-monotonisille ominaisuuksille (esimerkiksi ominaisuus, jolla on parillinen määrä reunoja). $G(n,p)$ $G(n,{\tbinom {n}{2}}p)$ $pn^{2}\to \infty$

Käytännössä malli on nykyään yksi käytetyimmistä, osittain reunariippumattomuuden tarjoaman analyysin helppouden vuoksi. $G(n,p)$

Kaavion ominaisuudet $G(n,p)$

Yllä olevalla merkinnällä graafilla on keskimäärin reunat. Vertex-astejakauma on binomi [4] : $G(n,p)$ ${\tbinom {n}{2}}p$

P(\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k},

missä n on graafin pisteiden kokonaismäärä. Koska

P(\deg(v)=k)\to {\frac {(np)^{k}\mathrm {e} ^{-np}}{k!)}}

klo ja

n\to\infty

np={\teksti{vakio)),

tämä jakauma on Poisson-jakauma suurelle n :lle ja np = vakio.

Erdős ja Rényi [5] kuvasivat vuoden 1960 julkaisussa käyttäytymistä erittäin tarkasti eri p - arvoille . Niiden tuloksia ovat mm. $G(n,p)$

Jos np < 1, niin graafissa ei läheskään varmasti ole yhteenliitettyjä komponentteja, joiden koko on suurempi kuin O(log( n )). $G(n,p)$
Jos np =1, niin graafissa in on lähes varmasti suuria komponentteja, joiden koko on luokkaa n 2/3 . $G(n,p)$
Jos , Jossa c on vakio, niin kaaviossa on lähes varmasti yksi jättiläinen komponentti , joka sisältää positiivisen osuuden kärkejä. Millään muulla komponentilla ei ole enempää kuin O(log( n ))-pisteitä. $np\to c>1$ $G(n,p)$
Jos , Graafi sisältää lähes varmasti eristettyjä pisteitä, ja siksi se on irrotettu. $p<{\tfrac {(1-\varepsilon )\ln n}{n))$ $G(n,p)$
Jos , kaavio on lähes varmasti yhdistetty. $p>{\tfrac {(1+\varepsilon )\ln n}{n))$ $G(n,p)$

Näin ollen on tarkka kynnys todennäköisyys yhteyksille . ${\tfrac {\ln n}{n))$ $G(n,p)$

Graafin muita ominaisuuksia voidaan kuvata lähes täsmälleen siten, että n pyrkii äärettömään. Esimerkiksi on k ( n ) (suunnilleen yhtä suuri kuin 2log 2 ( n )), niin että suurin klikki on lähes varmasti joko kokoa k ( n ) tai [6] . $G(n,0,5)$ $k(n)+1$

Sitten, vaikka ongelma kaavion suurimman klikkin koon löytämisessä on NP-täydellinen , suurimman klikkin koko "tyypillisessä" kaaviossa (tämän mallin mukaan) ymmärretään hyvin.

Erdős-Rényi-graafien reuna-duaaligraafit ovat graafeja, joilla on lähes samat astejakaumat, mutta astekorrelaatio ja paljon korkeampi klusterointikerroin [7] .

Suhde perkolaatioon

Perkolaatioteoriassa tarkastellaan äärellistä tai ääretöntä graafia ja reunat (tai yhteydet) poistetaan satunnaisesti. Tällöin Erdős-Rényi-prosessi on itse asiassa painottamaton perkolaatio koko graafille . Koska perkolaatioteorialla on syvät juuret fysiikassa , euklidisten tilojen hiloja on tutkittu paljon . Siirtymisellä np =1 jättiläiskomponentista pieneen komponenttiin on analogeja näille kaavioille, mutta hiloille siirtymäkohtaa on vaikea määrittää. Fyysikot puhuvat usein koko graafin tutkimisesta itsejohdonmukaisena kenttämenetelmänä . Tällöin Erdős-Rényi-prosessi on keskimääräisen perkolaatiokentän tapaus.

Merkittävää työtä on myös tehty satunnaisten graafien perkolaatiossa. Fysikaalisesta näkökulmasta malli pysyy keskimääräisenä kenttämallina, joten tutkimuksen motivaatio muotoutuu usein viestintäverkkona katsotun graafin stabiiliuden perusteella. Olkoon annettu satunnainen graafi, jossa on solmuja, joiden keskimääräinen aste on < k >. Poistamme osuuden solmuista ja jätämme verkon osuuden p′ . On olemassa kriittinen perkolaatiokynnys , jonka alapuolella verkko pirstoutuu, kun taas kynnyksen yläpuolella on jättimäinen yhdistetty komponentti luokkaa n . Jättimäisen komponentin suhteellinen koko saadaan kaavasta [5] [1] [2] [8] . $n\gg 1$ $1-p'$ $p'_{c}={\tfrac {1}{\langle k\rangle ))$ ${\displaystyle p'_{c))$ ${\displaystyle P_{\infty ))$

P_{\infty }=p'[1-\exp(-\langle k\rangle P_{\infty })].\,

Varoitukset

Molempien mallien pääoletukset (että reunat ovat riippumattomia ja että jokainen reuna on yhtä todennäköinen) eivät välttämättä sovellu joidenkin tosielämän ilmiöiden mallintamiseen. Erityisesti Erdős-Rényi-graafien kärkiasteiden jakaumassa ei ole raskaita jakauman häntäjä, kun taas jakauman katsotaan olevan raskas häntä monissa todellisissa verkoissa . Lisäksi Erdős-Rényi-kaavioilla on alhainen klusteroituminen, mikä ei ole tilanne monissa sosiaalisissa verkostoissa. Katso suositut mallivaihtoehdot artikkeleista The Barabasi-Albert Model ja The Watts and Strogats Model . Nämä vaihtoehtoiset mallit eivät ole perkolaatioprosesseja , vaan ne ovat kasvu- ja uudelleenjohdotusmalleja. Erdős-Rényi-verkoston vuorovaikutusmallin kehittivät äskettäin Buldyrev ym . [9] . $G(n,p)$

Historia

Ensimmäisen mallin ehdotti Edgar Hilbert vuonna 1959 julkaistussa artikkelissa, jossa tutkittiin edellä mainittua liitettävyyskynnystä [3] . Erdős ja Renyi ehdottivat mallia vuoden 1959 julkaisussaan . Kuten Hilbertin tapauksessa, he tutkivat liitettävyyttä , ja tarkempi analyysi tehtiin vuonna 1960. $G(n,p)$ $G(n,M)$ $G(n,M)$

Muunnelmia ja yleistyksiä

Graafi (graafiteoria) on yleisempi malli satunnaisesta graafista.

Rado-graafi , joka muodostetaan laajentamalla mallia graafisiin, joissa on laskettava määrä pisteitä. Toisin kuin viimeisessä tapauksessa, tämän äärettömän prosessin tulos on ( todennäköisyydellä 1 ) sama graafi isomorfismiin asti. $G(n,p)$

Barabashi-Albert malli .

Muistiinpanot

↑ 1 2 Erdős, Rényi, 1959 , s. 290-297.
↑ 12 Bollobás , 2001 .
↑ 1 2 Gilbert, 1959 , s. 1141-1144.
↑ Newman, Strogatz, Watts, 2001 , s. 026118.
↑ 1 2 ( Erdős, Rényi 1960 , 17–61) Tässä käytetty todennäköisyys p viittaa $N(n)={\tbinom {n}{2}}p$
↑ Matula, 1972 , s. A-382.
↑ Ramezanpour, Karimipour, Mashaghi, 2003 , s. 046107.
↑ Bollobás, Erdős, 1976 , s. 419–427.
↑ Buldyrev, Parshani, Paul, Stanley, Havlin, 2010 , s. 1025–8.

Kirjallisuus

Mark EJ Newman, Strogatz SH, Watts DJ Satunnaiset graafit mielivaltaisilla astejakaumilla ja niiden sovellukset // Physical Review E. - 2001. - T. 64 . - doi : 10.1103/PhysRevE.64.026118 . - . - arXiv : cond-mat/0007235 . , Equ. (yksi)
Erdős P., Rényi A. Satunnaisten graafien evoluutiosta // Magyar Tudományos Akadémia Matematikai Kutató Intézetének Kőzleményei [Unkarin tiedeakatemian matemaattisen instituutin julkaisut]. - 1960. - T. 5 .
David W. Matula. Työntekijäpuolueen ongelma // Notices of the American Mathematical Society. - 1972. - Helmikuu ( osa 19 ). - S. A-382 .
Ramezanpour A., Karimipour V., Mashaghi A. Korreloituneiden verkkojen luominen korreloimattomista // Physical Review E. - 2003. - Huhtikuu ( osa 67 , numero 4 ). - doi : 10.1103/PhysRevE.67.046107 . - . - arXiv : cond-mat/0212469 .
Erdős P., Renyi A. On Random Graphs. I // Julkaisut Mathematicae. - 1959. - T. 6 .
Bollobas B. Satunnaiskuvaajat. – 2. - 2001. - ISBN 0-521-79722-5 .
Bollobás B., Erdős P. Klikit satunnaiskaavioissa // Cambridge Philosophical Societyn matemaattiset julkaisut. - 1976. - T. 80 , no. 3 . - doi : 10.1017/S0305004100053056 . - .
Buldyrev SV, Parshani R., Paul G., Stanley HE, Havlin S. Katastrofaalinen epäonnistumisten kaskadi toisistaan riippuvaisissa verkoissa // Luonto. - 2010. - T. 464 , no. 7291 . - doi : 10.1038/luonto08932 . - . - arXiv : 0907.1182 . — PMID 20393559 .
Gilbert EN Random Graphs // Annals of Mathematical Statistics. - 1959. - T. 30 , no. 4 . - doi : 10.1214/aoms/1177706098 .

Lue lisää lukemista varten

Raigorodsky, Andrei Mihailovitš Satunnaiskaaviomallit . - M. : MTSNMO, 2011. - ISBN 978-5-94057-840-6 .
Douglas B. West. Johdatus graafiteoriaan. - 2001. - ISBN 0-13-014400-2 .
Newman MEJ Networks: Johdanto. – 2010.
Monimutkaiset verkot: rakenne, kestävyys ja toiminta . – 2010.