Grafo aleatorio
# 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 Errore del parser (SVG (MathML può essere abilitato tramite plug-in del browser): risposta non valida ("Math extension cannot connect to Restbase.") dal server "http://localhost:6011/it.wikipedia.org/v1/":): {\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.

## 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
