Riassunto esame Network analytics, Prof. Dell'olmo Paolo, libro consigliato Network Science, Barabasi

C.

Possiamo definire il coefficiente di clustering globale come:

3 ⋅

=

si osservi che il 3 al numeratore è giustificato dal fatto che ogni triangolo viene contato tre volte nel

conteggio delle terzine.

Oss: i due modi per calcolare coefficiente di clustering per una rete sono comparabili ma non uguale

premesso che si stia vedendo una rete non estrema, tipo solo due nodi collegati.

CAPITOLO 3: 3.2

Il modello di rete casuale

Uno degli obiettivi che si pone la network science è quello di costruire reti con proprietà simili a

quelli di reti reali. Tuttavia queste reti non hanno una forma di regolarità, anzi, sembrano costruiti

casualmente. Proprio da questa idea la teoria delle reti costruisce reti che sono veramente aleatorie.

La difficoltà di generare una rete sta nel comprendere dove posizionare gli archi tra vari nodi in

modo da riprodurre una rete reale. Per risolvere questo dilemma si generano rete random

posizionando casualmente il collegamento tra due nodi attraverso due strategie/definizioni.

Def:

1° : Dati N nodi si posizionano casualmente con L archi.

2° : Ogni coppia di N nodi è connessa con una probabilità p.

Oss: il primo modello, detto di Erdos e Renyi fissa il numero totale di collegamenti mentre il

secondo, ideato da Gilbert, fissa la probabilità che due nodi siano connessi.

Il vantaggio di Erdos-Renyi sta nella facilità di trovare il grado medio, tuttavia viene preferita la

definizione di Gilbert perché gode di un facilità elevata di calcolare le caratteristiche chiave della

rete.

I passaggi per costruire una rete casuale sfruttando la definizioni di Gilbert sono i seguenti:

- Definiti N nodi isolati.

- Selezionata una coppia di nodi, si genera un numero casuale tra 0 ed 1.

- Se tale numero supera la probabilità prefissata p allora si collegano i due nodi tramite un

arco, altrimenti si lasciano disconnessi.

- Si ripete il passaggio per tutte le coppie di nodi possibili.

Viene così genera un grafo denominato random. 3.3

Numero di collegamenti

Ogni rete casuale generata con stessi parametri appare leggermente diversa, per via sia del numero

di archi che la loro posizione.

Tuttavia possiamo ritrovare una distribuzione nota dietro al numero di archi generati da una rete

(−1)

random; infatti tale probabilità non è nient’altro che un binomiale di parametri e p.

2

Ovvero: ( − 1) (−1)

−

(1

( )

= ⋅ ⋅ − ) 2

2

inoltre possiamo affermare che il suo valore atteso, la media degli archi che tale rete random genera,

sarà: (−1)

2 ( − 1)

⟨⟩ = ∑ =

2

=1

dato questo risultato, possiamo reinterpretare il significato del grado medio di una rete random

come: 2⟨⟩

⟨⟩ = = ( − 1)

cioè il prodotto tra la probabilità che due nodi siano connessi ed il numero massimo di collegamenti

che un nodo può avere.

Oss: si osservi come il valore atteso della V.A. numero degli archi in una rete random ed anche il

suo grado medio siano direttamente proporzionale sia al numero di nodi che alla probabilità p.

3.4

Distribuzione dei gradi

In questa sezione deriviamo la distribuzione del grado dei nodi per una rete random e ne discutiamo

le proprietà. Si ricordi inoltre che stiamo osservando la probabilità che il nodo i abbia esattamente k

archi.

In particolare la forma esatta della distribuzione dei gradi è la distribuzione binomiale, tuttavia tale

distribuzione è ben approssimata da una Poisson nel caso in cui Il vantaggio

⟨⟩.

>>

dell’approssimazione si ha osservando che essa dipenda solo da un parametro, il grado medio.

In sintesi, anche se la distribuzione di Poisson è solo un’approssimazione della distribuzione dei

gradi di una rete random, grazie alla sua semplicità analitica, è la forma preferita per la

distribuzione del grado dei nodi .

Distribuzione di Poisson per il grado dei nodi in una rete random:

⟨⟩

−⟨⟩

= ⋅

!

3.5

Le reti reali non sono Poisson

Adesso andiamo ad osservare le differenze tra la distribuzione del grado dei nodi di una rete random

con una rete reale.

In primo luogo possiamo affermare che in una grande rete random il grado della maggior parte dei

nodi è nelle vicinanze del grado medio.

Ciò ha come conseguenza che mancano valori anomali, fatto che è totalmente in conflitto con la

realtà.

Per capire l’origine di queste discrepanze dobbiamo confrontare la distribuzione dei gradi delle reti

reali e random.

Dal confronto grafico si osserva che la deviazione significativa tra dati e l’adattamento di Poisson

indica che il modello di rete random sottostima la dimensione e la frequenza dei nodi di altro e

basso grado. 3.6

L’evoluzione di una rete casuale

Esaminiamo come la dimensione del più grande cluster connesso, indicato con , varia con ⟨⟩.

Innanzitutto osserviamo i due casi estremi:

- Per p=0: ho = 0 e tutti i nodi sono isolati. Perciò la Giant component sarà pari a 1 ed

⟨⟩

per N grande.

→ 0

-

Per p=1: ho che e la rete è un grafo completo. Pertanto e .

⟨⟩ = − 1 = 1 =

Tra i due casi estremi ci si aspetta che la Giant Component cresca gradualmente da a

= 1 =

al variare di tra o ed N-1 . Tuttavia non accade ciò: per valori di piccoli la rimane zero.

⟨⟩ ⟨⟩

una volta che supera un valore critico si osserva che inizia ad aumentare segnalando così la

⟨⟩

comparsa della Giant Component.

Erdos e Renyi affermano che tale valore critico debba essere pari a 1, cioè deve essere vero che ogni

nodo ha mediamente più di un arco. Il che non è inaspettato. Infatti, affinché esista una Giant

Component, ciascuno dei suoi nodi deve essere collegato ad almeno un altro nodo.

2⟨⟩

Sfruttando la relazione ho che la soglia critica espressa per p sarà:

⟨⟩ = = ( − 1)

1

≈

Ovvero più grande è una rete, più piccolo p è sufficiente per la Giant Component.

Inoltre possiamo osservare quattro regimi al variare del grado medio in una rete casuale.

1

- Regime sub critico: 0< <k> <1 ( )

<

Il cluster più grande è un albero di dimensioni , quindi la sua dimensione aumenta molto

~ log

log

più lentamente della dimensione della rete. Quindi per N che tende ad infinito.

≈ → 0

1

- Punto critico: <k> = 1 ( )

= 2

−

La dimensione della Giant Component è . di conseguenza essa cresce molto più

~ 3

1

−

lentamente della dimensione della rete, quindi la sua dimensione relativa diminuisce come ~ 3

con N che tende ad infinito. 1

- Regime super critico: <k> >1 ( )

>

Questo regime ha la massima rilevanza per sistemi reali, poiché la Giant Component sembra una

rete. In prossimità del punto critico la dimensione della Giant Component varia come:

~⟨⟩ − 1

Più ci allontaniamo dal punto critico, più ad esso apparterrà una frazione maggiore di nodi.

OSS: la dimensione della giant component segue una distribuzione esponenziale.

log

- Regime connesso: <k> > logN ( )

<

Per p abbastanza grandi la componente assorbe tutti i nodi e le componenti, quindi ~

3.7

Le reti reali sono supercritiche

Troviamo che la maggior parte delle rete reali sono in regime supercritico. Pertanto si prevede che

queste reti abbiano una Giant Component. Tuttavia, questa Giant Component dovrebbe coesistere

con molti componenti disconnessi, una previsione che fallisce per diverse reti reali. Nei prossimi

capitoli capiremo perché le reti reali possono rimanere connesse nonostante non soddisfino i criteri

⟨⟩ > log . 3.8

Small world

Una rete gode della proprietà dei sei gradi di separazione, chiamata anche proprietà Small World, se

la distanza tra due nodi qualsiasi in una rete è breve; cosa significa breve? Come si spiega

l’esistenza di queste brevi distanze?

Ad entrambe le domande si risponde che il numero atteso di nodi fino alla distanza d dal nostro

nodo di partenza è : +1

⟨⟩ 1

() ≈ ⟨⟩ − 1

Perciò assumendo che <k> >>1 possiamo trascurare il termine -1 ottenendo che:

log

≈

max log⟨⟩

Tale risultato si interpreta nel seguente modo: per piccolo intendiamo che il diametro dipende log

aritmicamente dalla dimensione del sistema.

Il perché ci sorprende tanto la proprietà di Small World risiede sulla nostra concezione di distanza

in reticoli regolari, che non mostrano le proprietà di Small World.

In generale per un reticolo di dimensione D il diametro scalano nel seguente modo con N:

1

~

max

Queste dipendenze polinomiali prevedono un aumento molto più rapido con N rispetto al caso visto

precedentemente, indicando che nei reticoli le lunghezze dei percorsi sono molto più lunghe che in

una rete casuale. 3.9

Coefficiente di clustering

Per il calcolo del coefficiente di clustering locale per un nodo in una rete casuale dobbiamo per

prima cosa stimare il valore atteso dei collegamenti tra i k vicini del nodo i ( ovvero dobbiamo

calcolarci )

Tale valore atteso sarà dato dal prodotto tra la probabilità che due vicini si leghino ed il numero di

possibili archi tra k vicini di i. (

− 1)

⟨ ⟩ = ⋅

2

Perciò il coefficiente di clustering locale per il nodo i sarà:

⟩ ⟨⟩

2⟨

= ==

(

− 1)

Si noti che, per un livello fissato di grado medio, più la rete è grande più il coefficiente sarà piccolo(

tale ragionamento è esteso anche al ). Tuttavia con reti reali ciò non si mostra: si osserva un

⟨⟩

coefficiente di c