Grafo aleatorio

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à

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

Numero di archi

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

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

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

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

Per ogni proprietà X si può allora calcolare la probabilità che G_n 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

Alcune proprietà cambiano "rapidamente" le loro probabilità asintotiche al variare di p_n; in particolare le loro probabilità asintotiche possono passare da 0 a 1 (o da 1 a 0) quando p_n "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

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 p_n. 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

• 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

• Calcolo delle probabilità
• Teoria dei grafi

Collegamenti esterni

• (EN) Random Graphs, su cs.columbia.edu. URL consultato il 2 ottobre 2011 (archiviato dall'url originale il 26 marzo 2012).