Appunti e domande Software Engineering

L

n ≈ k ovvero un numero L tale che, da qualsiasi v, e andando a distanza L, posso

raggiungere tutti i nodi della rete. Quindi, tale L approssimerà la lunghezza media della rete

L

n ≈ k → L = log (n) / log (k)

Il "grado di separazione" in una rete casuale è cresciuto solo logaritmicamente, quindi le

reti casuali sono “Small World”. Ma non rappresentano un modello realistico.

I veri social network sono da qualche parte tra l’ordine delle reti regolari e il "caos" della rete

casuale, infatti conosciamo bene un numero limitato di persone che si conoscono anche

definendo cluster connessi, come nei d-Lattices con k ragionevolmente alto e quindi con fattori

di clustering ragionevolmente elevati

Allo stesso tempo, conosciamo anche alcune persone qua e là, lontane dal nostro solito gruppo

di amici

Abbiamo così un modo per sfuggire al nostro solito gruppo di amici tramite conoscenti che sono

come archi casuali nella rete. L'idea chiave (Watts e Strogatz, 1999) e che i social network

debbano quindi essere:

- Abbastanza regolare da promuovere il clustering

- Abbastanza caotico da promuovere piccoli gradi di

separazione

Cominciamo con un reticolo regolare e iniziamo a ricablare

uno degli archi in modo casuale. Si continua a ricablare gli

archi uno per uno e continuando questo processo, il reticolo

regolare viene progressivamente trasformato in una rete casuale.

Le reti ricablate sono tra ordine e caos

Per un ricablaggio limitato, conservano una ragionevole regolarità equindi un ragionevole

raggruppamento

Tuttavia, l’introduzione delle "scorciatoie", permettono di collegare parti della rete che

sarebbero state lontane l'una dall'altra. Ciò consente di accorciare la lunghezza della rete. Ma

quanto ricablaggio è necessario? Fare un calcolo esatto è impossibile ma gli esperimenti

dimostrano che:

Una quantità molto limitata di ricablaggio è sufficiente per ridurre drasticamente la lunghezza

della rete

Allo stesso tempo il clustering della rete inizia a diminuire più tardi, per un maggior grado di

ricablaggio

Così esiste un regime moderato di ricablaggio “tra ordine e caos” per il quale la rete

mostra "comportamento da small world".

Dato un insieme di processi/agenti che interagiscono secondo una specifica struttura di rete, in

che modo la struttura influisce sul comportamento dinamico dell'intero sistema? E questo può

riferirsi a:

- Dinamica di diffusione delle informazioni

- Dinamica della diffusione dell'influenza (come ciò che un nodo influenza le attività di altri

nodi)

- Velocità di accordo (nella percezione e nel ragionamento)

Tutto quanto sopra può essere considerato un problema epidemico

Supponiamo che un singolo individuo, in un social network, sia inizialmente infetto e che abbia

una probabilità 0 ≤ p ≤ 1 di infettare i suoi vicini (a causa della presenza di individui non

sensibili che non si contraggono e non riproducono ulteriormente l'infezione)

Per p = 0, l'infezione non si diffonde

Per p = 1, l'infezione si diffonde su tutta la rete, se la rete è completamente connessa, nel

modo più veloce

Cosa succede quando 0 < p < 1?

Percolazione: il processo mediante il quale qualcosa (un fluido, una particella, una malattia) si

diffonde attraverso un mezzo (un fluido, un labirinto, una rete)

Soglia di percolazione: il valore critico di un parametro oltre il quale il processo di diffusione

può completarsi ovvero può diffondersi su tutta la rete. È una sorta di transizione di stato. Nel

caso di epidemie sui social network la soglia di percolazione è il valore p di p al quale

c

l'epidemia si diffonde su tutta la rete (“epidemia gian”).

In generale, data una rete, la percolazione mostra una "transizione di stato". All'improvviso,

oltre la soglia, l'epidemia diventa "gigante".

- Nelle reti casuali la soglia di percolazione è

piuttosto bassa

- Nelle reti fortemente raggruppate la soglia di

percolazione è alta

- Nelle piccole reti mondiali le soglie di percolazione

si avvicinano a quelle delle reti casuali, anche in

presenza di ricablaggi molto limitati

Le epidemie si diffondono molto più velocemente di

quanto previsto dai modelli normali (ipotizzando reti

regolari) con pochi passaggi si raggiungono tutti i

nodi (dato che i nodi sono vicini tra loro) anche con

una bassa percentuale di soggetti suscettibili. Se ciò

che un processo fa/percepisce/decide influenza

l'altro, l'influenza si propaga molto velocemente.

Lezione 16. Scale-Free Networks & Emerging Models

1. Properties of scale-free networks?

2. What is a power law?

La maggior parte delle reti sociali, tecnologiche ed ecologiche sono caratterizzate dall'essere:

- Small World

- Raggruppate

- Scale-Free (distribuzione della legge di potenza)

Ora dobbiamo capire qual è la distribuzione della ”power law” e come possiamo modellarla

nelle reti.

- Reti reticolari regolari: i nodi sono collegati in un vicinato regolare, di solito

sono k-regolari, con un numero fisso k di archi per ogni nodo. Non mostrano

le caratteristiche del piccolo mondo. La distanza media tra i nodi cresciuti

con la radice d di n, dove n è il numero di nodi. Possono mostrare clustering

ed a seconda del reticolo e del fattore k, anche i nodi vicini sono in qualche

modo collegati tra loro.

- Reti casuali: le reti casuali hanno archi connessi casualmente. Se il

numero di archi è M, ogni nodo ha una media di k = M / 2n archi, dove n è

il numero di nodi. Esibiscono le caratteristiche del piccolo mondo. La

distanza media tra i nodi è log (n), dove n è il numero di nodi. Non

mostrano raggruppamento. Il fattore di raggruppamento è circa C = k / n

per n grande

- Small World Networks: Watts e Strogatz (1999) propongono un modello

per le reti "Tra ordine e caos". La rete mostra la caratteristica del piccolo

mondo, come reti casuali e allo stesso tempo mostrano raggruppamenti

rilevanti, come reticoli regolari. Il modello è costruito semplicemente

ricablando a caso una piccola percentuale degli archi regolari. Questo è

sufficiente per ridurre drasticamente la lunghezza media del percorso,

senza distruggere il raggruppamento.

Cos’è il grado di distribuzione? È il modo in cui i vari archi della rete "si

distribuiscono" attraverso i vertici, ovvero quanti archi collegano i vari vertici della rete. Per i

precedenti tipi di reti:

- Nei reticoli regolari k-regolari, il grado di distribuzione è costante

P(k ) = 1 per tutti i nodi (tutti i nodi hanno lo stesso numero k fisso di archi)

r r

- Nelle reti casuali, la distribuzione può essere costante o esponenziale

P(k ) = 1 per tutti i nodi (la rete randon è stata costruita come una rete k-regolare)

r -βk

P(k ) = αe , ovvero la normale distribuzione “gaussiana”, in quanto derivata dal fatto che

r

gli archi vengono aggiunti indipendentemente a caso

In un modello di rete casuale, ogni nuovo nodo che si collega alla rete collega i suoi archi

indipendentemente dalla situazione attuale. Quindi, tutti gli eventi sono indipendenti.

La probabilità che un nodo abbia un certo numero di archi attaccati è quindi una

−(k /m )

)=(1/m)e

P(k

distribuzione "normale", esponenziale:

La maggior parte delle reti reali, invece, segue una distribuzione "power law" per la

connettività del nodo. In termini generali, una distribuzione di probabilità è "power law” se la

probabilità P(k) che una data variabile k abbia un valore specifico diminuisce

-γ

proporzionalmente a k , dove γ è un valore costante.

Per le reti, questo implica che la probabilità che un nodo

−γ

)=α

P(k k

abbia k archi connessi è proporzionale a:

Non è più una distribuzione esponenziale ma iperbolica

polinomiale.

La principale differenza è nel decadimento: la

distribuzione esponenziale decade più velocemente

appunto in modo esponenziale mente la distribuzione

“power law” decade leggermente più lentamente.

Dall’analisi della statistica, una curva esponenziale

sottende un’area finita, al contrario l’integrale di una curva che decade polinomialmente

sottende un’area infinita. Nel primo caso ci permette di definire il concetto di varianza e

deviazione standard, che non è possibile definire per una distribuzione “power law”.

Ciò implica che nella distribuzione esponenziale, la probabilità di avere dei nodi che hanno un

alto numero di connessioni, molto più alto della media, è bassisimo.

In una distribuzione “power law” che hanno un numero

di archi molto maggiore della media non è trascurabile:

si parla di “coda lunga”.

La distribuzione della “power law” implica una "varianza

infinita". L'area dei “grandi k" in una distribuzione

esponenziale tende a zero con k che tende ad infinito.

Questo non è vero per la distribuzione della “power law”,

che implica una varianza infinita.

La “power law” è ubiqua, infatti la maggior parte dei

sistemi e degli eventi reali ha una distribuzione di probabilità che non segue la distribuzione

"normale" e obbedisce a una distribuzione della legge di potere.

Esempi, oltre a reti tecnologiche e social

- La distribuzione della dimensione dei file nei file system

- La distribuzione della latenza di rete in Internet

- La distribuzione dell'accesso ai servizi Web

La distribuzione della legge di potenza è la distribuzione "normale" per sistemi complessi (cioè,

sistemi di componenti autonomi interagenti).

Le reti "Scale-Free" mostrano la presenza di nodi che agiscono come hub, cioè come punto a

cui la maggior parte degli altri nodi si connette per agire come connettori, cioè nodi che danno

un grande contributo nel riunire una grande porzione della rete. Esistono "nodi più piccoli" che

fungono da hub o connettori per la porzione locale della rete. Perché le reti di distribuzione a

seguito di una “power law” per i collegamenti sono chiamati “Scale-Free”? Qualunque sia la

scala alla quale osserviamo la rete, ha lo stesso aspetto, cioè sembra simile a se stessa. Le

proprietà complessive della rete vengono preservate indipendentemente dalla scala. In

particolare: ae tagliamo i dettagli di una rete, saltando tutti i nodi con un numero limitato di

collegamenti, la rete pr