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.

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

Nel modello G(n,m) la probabilità è concentrata ed uniformemente distribuita sugli ${\displaystyle {\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.

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 ${\displaystyle B(p,{\tbinom {n}{2}})}$, con speranza ${\displaystyle {\tbinom {n}{2}}p}$.

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 ${\displaystyle 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.

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à, ${\displaystyle \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).

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	${\displaystyle \ \ {\frac {1}{n^{2}}}}$	${\displaystyle {\frac {1}{n{\sqrt {n}}}}}$	${\displaystyle {\frac {1}{n{\sqrt[{k}]{n}}}}}$	${\displaystyle \ \ {\frac {1}{n}}}$	${\displaystyle {\frac {\log n}{n}}}$

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

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

• Calcolo delle probabilità
• Teoria dei grafi

• (EN) Eric W. Weisstein, Random Graph, su MathWorld, Wolfram Research.
• (EN) Random Graphs, su cs.columbia.edu. URL consultato il 2 ottobre 2011 (archiviato dall'url originale il 26 marzo 2012).

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