Model d'Erdős-Rényi

En teoria de grafs, el model d'Erdős-Rényi fa referència un dels dos models estretament relacionats en la generació de grafs aleatoris. Duen el nom de Paul Erdős i Alfréd Rényi, que van ser els primers a introduir-los l'any 1959;^[1]^[2] el segon model va ser introduït independentment i de manera contemporània per Edgar Gilbert.^[3] En el primer model, tots els grafs d'un conjunt fix de vèrtexs amb un cert nombre d'arestes són iguals de probables; mentre que en el segon model (introduït per Gilbert) tota aresta té una probabilitat fixa de ser present o absent, independentment de la resta d'arestes. Aquests models poden ser usats en el mètode probabilístic per demostrar l'existència de grafs que satisfacin diverses propietats, o per proporcionar una definició rigorosa de què significa per una propietat de donar-se a gairebé tots els grafs.

Història

El model G(n, p) va ser introduït per primer cop en un article d'Edgar Gilbert de l'any 1959 sobre el llindar de connectivitat.^[3] El model G(n, M) va ser introduït per Erdős i Rényi en el seu article de 1959. Com en el cas de Gilbert, les seves investigacions eren sobre la connectivitat de G(n, M), sobre el qual van fer una anàlisi més profunda l'any 1960.

Definició

Hi ha dos variants estretament relacionades del model de grafs aleatoris d'Erdős–Rényi (ER):

En el model G(n, M), un graf és elegit uniformement i de manera aleatòria del conjunt de tots els grafs possibles amb n nodes i M arestes. Per exemple, en el model G(3, 2), cada un dels 3 possibles grafs de 3 vèrtexs i 2 arestes s'inclouen amb probabilitat 1/3.
En el model G(n, p) model, es construeix un graf connectant els nodes aleatòriament. Cada aresta s'inclou en el graf amb una probabilitat p, independent en cada aresta. De manera equivalent, tot graf d'n nodes i M arestes té una probabilitat de:

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

Es pot entendre el paràmetre p d'aquest model com una funció de pes; a mesura que p augmenta de 0 a 1, en el model cada vegada serà més probable que s'hi incloguin grafs amb moltes arestes i menys probable que s'hi incloguin grafs amb poques. En particular, el cas en què

p=0.5

correspon al cas en què tots els

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

grafs d'n vèrtexs poden ser elegits amb igual probabilitat.

El comportament dels grafs aleatoris se sol estudiar quan n, el nombre de vèrtexs, tendeix a infinit. Tot i que es poden fixar els valors de p i M, també poden ser funcions que depenguin d'n. Per exemple, l'afirmació:

Gairebé tots els grafs generats pel model

G(n,2\,\ln {n}/n)

són connexos.

significa que:

A mesura que

n

tendeix a infinit, la probabilitat que un graf de

n

vèrtexs amb probabilitat d'aresta

p=2\,\ln {n}/n

sigui connex, tendeix a 1.

Comparació entre els dos models

El nombre esperat d'arestes a G(n, p) i per la llei dels grans nombres qualsevol graf de G(n, p) tindrà gairebé amb tota seguretat aproximadament aquest nombre d'arestes (atès que el nombre esperat d'arestes tendeix a infinit). Per tant, aplicant heurística aproximada, es pot dir que si pn² → ∞, llavors G(n,p) hauria de mostrar un comportament semblant a G(n, M) amb $M={\tbinom {n}{2}}p$ a mesura que n augmenta.

Per moltes propietats dels grafs, això es compleix. Sigui P una propietat de grafs qualsevol que és monòtona respecte subgrafs d'ordre inferior (és a dir, que si A és un subgraf de B i A satisfà P, llavors B també satisfarà P), llavors les afirmacions "P es compleix en gairebé tots els grafs de G(n, p)" i "P es compleix per gairebé tots els grafs de $G(n,{\tbinom {n}{2}}p)$ " són equivalents (sempre que pn² → ∞). Per exemple, això es compleix quan P és la propietat de la connectivitat, o si P és propietat de contenir un cicle hamiltonià. Tanmateix, això no es complirà amb propietats no monòtones (per exemple, la propietat de tenir un nombre parell d'arestes).

En la pràctica, el model G(n, p) és el més usat actualment, en part a causa de la facilitat en la seva anàlisi gràcies a la independència de les seves arestes.

Aplicacions

Les aplicacions d'aquest model són molt limitades, atès que poques xarxes reals es comporten tal com es descriu en el model d'Erdös–Rényi.^[4] No obstant això existeixen aproximacions en teoria de grafs sobretot en el camp de les xarxes socials (xarxa d'afiliació i graf bipartit). Una diferència clara entre les xarxes socials i les generades per aquest model és la distribució de grau, que en el cas de les generades per aquest model són poissonianes, mentres que en la realitat tendeixen a ser exponencials.^[5] En les xarxes amb distribucions poissonianes es concentra la probabilitat al voltant d'un valor $k$ (grau nodal) i decreix a raó d' 1/k! quan s'allunya del valor central. En les xarxes exponencials no existeix un valor preferent i la probabilitat decau al llarg de l'espectre de k a mesura que creix.

Referències

↑ Erdős, P.; Rényi, A. «On Random Graphs. I». Publicationes Mathematicae, 6, 1959, pàg. 290–297.
↑ Bollobás, B. Random Graphs. 2nd. Cambridge University Press, 2001. ISBN 0-521-79722-5.
↑ ^3,0 ^3,1 Gilbert, E.N. «Random Graphs». Annals of Mathematical Statistics, 30, 4, 1959, pàg. 1141–1144. DOI: 10.1214/aoms/1177706098.
↑ "Random graph models of social networks", M. E. J. Newman, D. J. Watts, S. H. Strogatz, 2566–2572, PNAS, February 19, 2002, vol. 99, suppl. 1
↑ Albert, R., Jeong, H. and Barabási, A.-L., 2000. Attack and error tolerance of complex networks. Nature 406, 378–382

[er59-1] Erdős, P.; Rényi, A. «On Random Graphs. I». Publicationes Mathematicae, 6, 1959, pàg. 290–297.

[b01-2] Bollobás, B. Random Graphs. 2nd. Cambridge University Press, 2001. ISBN 0-521-79722-5.

[g59-3] 3,0 ^3,1 Gilbert, E.N. «Random Graphs». Annals of Mathematical Statistics, 30, 4, 1959, pàg. 1141–1144. DOI: 10.1214/aoms/1177706098.

[4] "Random graph models of social networks", M. E. J. Newman, D. J. Watts, S. H. Strogatz, 2566–2572, PNAS, February 19, 2002, vol. 99, suppl. 1

[5] Albert, R., Jeong, H. and Barabási, A.-L., 2000. Attack and error tolerance of complex networks. Nature 406, 378–382

[1]

[2]

[3]

[4]

[5]