Grafo aleatorio

Da Wikipedia, l'enciclopedia libera.

In teoria dei grafi un grafo aleatorio è un grafo generato da un procedimento aleatorio, ovvero è una variabile aleatoria le cui realizzazioni sono dei grafi. Ad esempio, un grafo scelto "a caso" uniformemente tra tutti i grafi che hanno gli stessi n vertici è un grafo aleatorio.

Nello studio delle reti di conoscenze, o di computer, vengono studiati grafi aleatori con distribuzioni di probabilità che privilegiano il raggruppamento di collegamenti (in inglese e in informatica cluster) e possono prevedere effetti di massa critica.

Dei grafi aleatori viene studiato il comportamento asintotico, considerando una successione di grafi aleatori con un numero n di vertici che tende a infinito.

Distribuzioni di probabilità[modifica | modifica wikitesto]

Con n vertici fissati si possono costruire e=\tbinom{n}{2} archi e 2e grafi.

Numero di archi[modifica | modifica wikitesto]

Nel modello G(n,m) la probabilità è concentrata ed uniformemente distribuita sugli \tbinom{e}{m} grafi che hanno esattamente m archi.

Un grafo aleatorio di G(n,m+1) può essere ottenuto aggiungendo un arco, scelto in maniera uniforme, ad un grafo di G(n,m). In particolare un grafo aleatorio di G(n,m) può essere generato partendo dal grafo privo di archi ed aggiungendo m archi, uno alla volta ed uniformemente.

Probabilità d'arco[modifica | modifica wikitesto]

Nel modello G(n,p) le funzioni indicatrici degli archi costituiscono un processo di Bernoulli, ovvero ogni possibile arco ha probabilità p di appartenere al grafo, indipendentemente dagli altri archi.

Il numero M di archi di un grafo aleatorio segue allora la distribuzione binomiale B(p,\tbinom{n}{2}), con speranza \tbinom{n}{2}p.

Collegamenti[modifica | modifica wikitesto]

La distribuzione G(n,p) può essere interpretata come G(n,M), ovvero come una mistura di distribuzioni G(n,m) secondo la distribuzione binomiale B(p,\tbinom{n}{2}).

Per m=np i due modelli G(n,m) e G(n,p) condividono molte proprietà e sono quasi interscambiabili.

Proprietà asintotiche[modifica | modifica wikitesto]

Scegliendo una successione pn si determina una successione di grafi aleatori Gn, scelti in G(n,pn).

Per ogni proprietà X si può allora calcolare la probabilità che Gn soddisfi X. La probabilità asintotica di X è il limite di queste probabilità, \lim_{n\to\infty}P(G_n\in X).

Una proprietà X è asintoticamente quasi certamente vera (o falsa) se la sua probabilità asintotica è 1 (o 0).

Funzioni soglia[modifica | modifica wikitesto]

Alcune proprietà cambiano "rapidamente" le loro probabilità asintotiche al variare di pn; in particolare le loro probabilità asintotiche possono passare da 0 a 1 (o da 1 a 0) quando pn "attraversa una soglia".

Una funzione t è una funzione soglia per una proprietà X se X è asintoticamente quasi certamente vera per p∈o(t) ed è asintoticamente quasi certamente falsa per p∈ω(t) (ovvero t∈o(p)), oppure il contrario.

Ogni proprietà monotona (monotona rispetto all'operazione di aggiungere archi) possiede una funzione soglia.

Esempi di funzioni soglia sono:

proprietà esiste un arco esistono tre vertici connessi esiste un albero con k+1 vertici esiste un ciclo il grafo è connesso
soglia \ \ \frac{1}{n^2} \frac{1}{n\sqrt{n}} \frac{1}{n\sqrt[k]{n}} \ \ \frac{1}{n} \frac{\log n}{n}

Evoluzione dei grafi[modifica | modifica wikitesto]

Leggendo le proprietà ordinate secondo il comportamento asintotico delle loro funzioni soglia è possibile vedere l'evoluzione di un grafo aleatorio, ovvero le sue proprietà asintoticamente quasi certe al crescere di pn. Partendo dal grafo completamente sconnesso (privo di archi) con p=0 ed aggiungendo successivamente degli archi si arriva al grafo completo con p=1; in questa "evoluzione" si vedono apparire (o scomparire) diverse proprietà, man mano che p ne "attraversa" le rispettive soglie.

Ad esempio, nell'ordine:

  • compaiono i primi archi, che collegano vertici distinti
  • da alcuni vertici partono due archi distinti, formando un 3-albero
  • gli alberi diventano più grandi
  • alcuni alberi si "chiudono" e creano dei cicli
  • le componenti connesse si uniscono e il grafo risulta connesso

Bibliografia[modifica | modifica wikitesto]

  • Béla Bollobás, Random Graphs, 2nd Edition, 2001, Cambridge University Press
  • Joel H. Spencer, The strange logic of random graphs, 2001, Springer-Verlag

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica