GRAFI

Vincenzo Auletta

STRUTTURA DELLE RETI SOCIALI

TEORIA DEI GRAFI E RETI

La Teoria dei Grafi è una branca della Matematica che permette di descrivere insiemi di oggetti insieme alle loro relazioni Nasce nel 1700 con Eulero

Soluzione al problema dei ponti di Konigsberg

La Teoria dei Grafi fornisce un linguaggio unificante per descrivere la struttura di una network

La possibilità di raccogliere dati su larga scala usando computer e reti di computer consente nuovi approcci individuare proprietà statistiche che caratterizzano la

struttura delle network e fornire modi per misurarle

creare modelli di network e descrivere la loro formazione

Prevedere il comportamento delle network sulla base dei modelli e delle proprietà strutturali

Au

tun

no 2

01

2

1

Stru

ttura

delle

Reti S

ocia

li

DEFINIZIONE DI GRAFO

Un grafo consiste di

Un insieme di nodi (vertici)

Un insieme di archi (collegamenti)

Un arco collega due nodi

Due nodi sono vicini (neighbor) se sono collegati da

un arco

I nodi C e D sono adiacenti all’arco (C, D)

Au

tun

no 2

01

2

2

Stru

ttura

delle

Reti S

ocia

li

GRAFI DIRETTI E INDIRETTI

Gli archi possono avere un orientamento Archi diretti: relazione vale solo tra testa e coda dell’arco

Archi indiretti: relazione vale in tutte e due le direzioni

Grafo indiretto Grafo diretto

La differenza è sostanziale Modelli di formazione e mantenimento della rete differenti

Algoritmi differenti

Au

tun

no 2

01

2

3

Stru

ttura

delle

Reti S

ocia

li

GRAFI PESATI

Possiamo associare agli archi delle informazioni aggiuntive

segno (amici-nemici)

forza del legame (forza della relazione sociale)

distanza (lunghezza del collegamento)

ritardo (tempo di trasmissione)

affidabilità (percentuale di errore nella trasmissione)

costo (costo di utilizzo del collegamento)

In un grafo pesato ogni arco ha un numero associato che ne definisce il peso

In un grafo segnato ogni arco ha un segno positivo o negativo

Au

tun

no 2

01

2

4

Stru

ttura

delle

Reti S

ocia

li

RAPPRESENTAZIONE DEI GRAFI

La Teoria dei Grafi è una teoria matematica

interessante di per se

Studia le caratteristiche e le proprietà dei grafi

Un grafo è una coppia di insiemi

G = (V, E)

Rappresentazioni più utilizzate

Matrice di adiacenza

Matrice n x n (n numero dei vertici in V)

Elemento (i, j) vale 1 se esiste l’arco tra i e j

Lista dei vertici V e degli archi E

Rappresentazione grafica

Au

tun

no 2

01

2

5

Stru

ttura

delle

Reti S

ocia

li

RAPPRESENTAZIONE DEI GRAFI

Nello studio delle networks i nodi rappresentano entità del mondo reale

alcune astrazioni di network sono comunemente utilizzate

Alcuni esempi

Reti di comunicazione Dispositivi di rete, linee di comunicazione

Social networks Persone, relazioni/amicizie

Reti di informazioni Web sites, hyperlinks

Reti biologiche Specie, legami di predazione. (molecole, legami chimici)

Au

tun

no 2

01

2

6

Stru

ttura

delle

Reti S

ocia

li

ARPANET: PRECURSORE DI INTERNET

Creata nel 1970 con 13 nodi

Au

tun

no 2

01

2

7

Stru

ttura

delle

Reti S

ocia

li

RAPPRESENTAZIONE COME GRAFO

Siamo interessati solo alla connettività

Le distanze possono essere rappresentate come pesi

Au

tun

no 2

01

2

8

Stru

ttura

delle

Reti S

ocia

li

RETI DI TRASPORTO

La terminologia dei grafi è in gran parte derivata dal mondo dei trasporti “cammino minimo”, “diametro”, “flusso”

Questioni a cui siamo interessati La struttura della rete è in grado di supportare le performance

richieste? Quanto è robusta? Si presta a fallimenti a cascata?

Au

tun

no 2

01

2

9

Stru

ttura

delle

Reti S

ocia

li

GRAFI DI DIPENDENZE

Nodi sono task e archi indicano dipendenze

Il progetto di complessi sistemi software o di processi industriali richiedono un’attenta analisi del grafo di dipendenze per definire un buon scheduling

Au

tun

no 2

01

2

10

Stru

ttura

delle

Reti S

ocia

li

RETI STRUTTURALI

Le strutture interne di edifici, meccanismi, corpi umani sono definite come reti di strutture

La teoria della rigidità studia la stabilità di queste strutture dal punto di vista della teoria dei grafi

Au

tun

no 2

01

2

11

Stru

ttura

delle

Reti S

ocia

li

CONCETTI PRINCIPALI SUI GRAFI

“Graph theory is a terminological jungle in which

every newcomer may plant a tree“ (Social scientist John

Barnes)

Ci occupereremo solo dei concetti principali per i

nostri scopi

cammini

cicli

connectività

componenti (e componente gigante)

distanza

Au

tun

no 2

01

2

12

Stru

ttura

delle

Reti S

ocia

li

CAMMINI

Le cose spesso viaggiano lungo gli archi del grafo Mezzi di trasporto

informazioni

influenza

malattie

Altre quantità fisiche

Un cammino (path) è una sequenza di nodi con la proprietà che ogni coppia di nodi consecutivi sono connessi da un arco Possiamo vederlo anche come sequenza di archi in cui due

archi consecutivi condividono un estremo

Moltiplicando la matrice di adiacenza per se stessa k volte possiamo scoprire quanti cammini di lunghezza k ci sono tra ogni coppia di nodi Mk(i, j) = # di cammini tra i e j di lunghezza k

Au

tun

no 2

01

2

13

Stru

ttura

delle

Reti S

ocia

li

CAMMINI

MIT – BBN – RAND – UCLA è un cammino

UCSB – UCLA – RAND – MIT non è un cammino

Un percorso può attraversa lo stesso nodo più volte SRI – STAN – UCLA – SRI – UTAH – MIT

Un cammino semplice non attraversa mai uno stesso nodo due volte

Au

tun

no 2

01

2

14

Stru

ttura

delle

Reti S

ocia

li

CICLI

Un ciclo è un percorso semplice che inizia e terminano

nello stesso nodo

LINC – CASE – CARN – HARV – BBN – MIT – LINC è un

ciclo

Ogni ciclo ha almeno tre archi

Nelle reti di comunicazione e nelle reti di trasporto ogni

nodo appartiene ad uno o più cicli

Aumenta la robustezza della rete e garantisce il

funzionamento anche in presenza di guasti

In una rete sociale i cicli sono frequenti ma non voluti

L’amica della cugina di mia moglie è la sorella del mio collega

d’ufficio

Au

tun

no 2

01

2

15

Stru

ttura

delle

Reti S

ocia

li

CONNETTIVITÀ

Un grafo è connesso se da ogni nodo è possibile

raggiungere ogni altro nodo attraverso un percorso

Il grafo di ARPANET è connesso

Le reti di comunicazione sono in genere connesse

In molti casi i grafi possono essere sconnessi

Social networks

Reti di collaborazione

etc.

Un grafo diretto è fortemente connesso se da ogni

nodo è possibile raggiungere ogni altro nodo

attraverso un percorso diretto

Au

tun

no 2

01

2

16

Stru

ttura

delle

Reti S

ocia

li

COMPONENTI

Se un grafo non è connesso può essere diviso in sottografi che sono a loro volta connessi

Una componente connessa di un grafo non diretto è un sottinsieme di nodi tali che Ogni nodo ha un percorso verso ogni altro nodo della sua componente

Per ogni nodo u non appartenente alla componente esiste un nodo v nella componente tale che non esiste nessun cammino da u a v

Un arco di una componente è un bridge se la sua cancellazione sconnette la componente

Una componente fortemente connessa di un grafo diretto è un sottinsieme di nodi tali che Ogni nodo ha un percorso diretto verso ogni altro nodo della sua

componente

Per ogni nodo u non appartenente alla componente esiste un nodo v nella componente tale che non esiste nessun cammino da u a v o da v a u

Au

tun

no 2

01

2

17

Stru

ttura

delle

Reti S

ocia

li

COMPONENTI

Tre componenti connesse

{A,B}, {C,D,E}, {F,G,...,M}

{H, L, M} non è una componente

L’arco (D, E) è un bridge

Au

tun

no 2

01

2

18

Stru

ttura

delle

Reti S

ocia

li

ANALISI DELLE COMPONENTI

Fornisce informazioni globali sulla struttura della

rete

Cosa lega ogni componente?

Come si diffondono le informazioni?

Che ruolo svolgono i nodi?

Au

tun

no 2

01

2

19

Stru

ttura

delle

Reti S

ocia

li

Grafo delle

collaborazioni in un

centro di ricerca

ANALISI DELLE COMPONENTI

Individuiamo le regioni più densamente connesse e i

confini tra queste regioni

Un altro importante tipo di analisi

Per esempio includiamo solo gli archi con un peso

superiore ad una certa soglia

Incrementando gradualmente la soglia il grafo si

frammenterà in componenti sempre più piccole

Au

tun

no 2

01

2

20

Stru

ttura

delle

Reti S

ocia

li

COMPONENTI GIGANTI

Molti grafi non sono connessi ma includono una componente molto grande

E.g. Il grafo delle relazioni amorose in un liceo della lezione precedente, il grafo del Web

Grosse reti spesso contengono una componente gigante

Una componente che contiene una grande percentuale di tutti i nodi della rete

In genere la componente gigante è unica

Quando due componenti giganti si fondono possono verificarsi eventi traumatici

Grafo delle relazioni umane prima della scoperta dell’America aveva due componenti giganti

La fusione delle due componenti ha segnato lo sterminio di una componente

Au

tun

no 2

01

2

21

Stru

ttura

delle

Reti S

ocia

li

COMPONENTI GIGANTI

Esistenza della componente gigante implica un maggior rischio di diffusione di malattie sessuali

Au

tun

no 2

01

2

22

Stru

ttura

delle

Reti S

ocia

li

INTORNI

L’intorno (neighborhood) di un nodo è l’insieme di

tutti i suoi vicini

L’intorno di un insieme di vertici S è l’insieme dei

vertici del grafo che non appartengono ad S ma sono

adiacenti a vertici di S

Au

tun

no 2

01

2

23

Stru

ttura

delle

Reti S

ocia

li

GRADI

Il grado di un nodo è il numero di nodi adiacenti

Numero di link adiacenti al nodo

uguale alla cardinalità dell’intorno

In un grafo diretto distinguiamo tra grado-in e

grado-out

Grado-in: numero di archi entranti nel nodo

Grado-out: numero di archi uscenti dal nodo

Au

tun

no 2

01

2

24

Stru

ttura

delle

Reti S

ocia

li

DISTANZE

La distanza tra una coppia di nodi è la lunghezza

del cammino minimo che li unisce

Ogni arco ha peso 1

Il diametro di un grafo è la più grande distanza tra

coppie di nodi del grafo

Qual è la distanza tra MIT e SDC?

Qual è il diametro della rete?

Au

tun

no 2

01

2

25

Stru

ttura

delle

Reti S

ocia

li

CALCOLO DELLE DISTANZE MINIME

Dato un grafo, come troviamo le distanze da un

nodo a tutti gli altri?

Abbiamo bisogno di un algoritmo

Come approcciamo il problema?

BFS

Au

tun

no 2

01

2

26

Stru

ttura

delle

Reti S

ocia

li

BREADTH-FIRST SEARCH (BFS)

Dal nodo sorgente(root)

Trova tutti i nodi direttamente connessi

Questi nodi sono a “distanza 1“

Trova tutti i nodi che sono direttamente connessi ai nodi

a distanza 1 e che non sono ancora stati visitati

Questi nodi sono a “distanza 2“

...

Trova tutti i nodi che sono direttamente connessi a nodi

a distanza j e che non sono già stati visitati

Questi nodi sono a distanza j+1“

Au

tun

no 2

01

2

27

Stru

ttura

delle

Reti S

ocia

li

BFS TREE A

utu

nn

o 2

01

2

28

Stru

ttura

delle

Reti S

ocia

li

BFS SUL GRAFO DI ARPANET A

utu

nn

o 2

01

2

29

Stru

ttura

delle

Reti S

ocia

li

SMALLWORLD PHENOMENON

Ipotesi: in reti di grandi dimensioni quasi tutti i nodi appartengono ad una componente gigante e sono connessi da percorsi molto brevi

Veloce diffuzione delle informazioni/infezioni

Primo esperimento condotto da Stanley Milgram in 1960s (research budget $680)

A 296 persone scelte a caso negli USA è stato chiesto di fa arrivare una lettera ad un certo destinatario spedendola ad una persona che conoscevano direttamente Ogni partecipante conosceva un profilo del destinatario

(residenza, occupazione, tipo di studi, città di origine, ecc.)

è stato valutato il numero medio di passaggi delle lettere

Au

tun

no 2

01

2

30

Stru

ttura

delle

Reti S

ocia

li

SEI GRADI DI SEPARAZIONE

Nell’esperimento di Milgram 64 lettere arrivarono a

diestinazione con una lunghezza media del percorso

inferiore a 6

Lo studio è stato largamente criticato negli anni

successivi

Au

tun

no 2

01

2

31

Stru

ttura

delle

Reti S

ocia

li

SEI GRADI DI SEPARAZIONE

Diversi esperimenti sono stati condotti che

confermano i risultati di Milgram

Un nuovo esperimento simile a quello di Milgram è

stato condotto nel 2008 da Leskovec and Horvitz

Utilizzati i dati relativi alle connessioni su Messanger di

240 millioni di utenti durante un periodo di 30 giorni

Hanno individuato una componente gigante con distanza

media di 6.6

Dati ottenuti selezionando un campione di 1000

utenti e calcolando le distanze minime da questi

nodi con la BFS

Au

tun

no 2

01

2

32

Stru

ttura

delle

Reti S

ocia

li

SEI GRADI DI SEPARAZIONE

distanza media attesa = 6.6, mediana = 7

Au

tun

no 2

01

2

33

Stru

ttura

delle

Reti S

ocia

li

SIX DEGREES OF GEEKINESS

Grafo delle collaborazioni scientifiche centrato su Paul Erdös Quasi tutti i matematici (ed informatici) hanno Erdös numer < 5

Au

tun

no 2

01

2

34

Stru

ttura

delle

Reti S

ocia

li

COME DESCRIVERE UN GRAFO SENZA

RAPPRESENTARLO ESPLICITAMENTE

Una network su larga scala non può essere

visualizzata facilmente

Abbiamo bisogno di un insieme di parametri quantitativi

che permettano di descrivere e confrontare grafi senza

doverli rappresentare esplicitamente

Alcuni parametri comunemente utilizzati

Diametro lunghezza media dei cammini

Indici di clustering

Misure di centralità

Distribuzioni dei gradi dei nodi

Au

tun

no 2

01

2

35

Stru

ttura

delle

Reti S

ocia

li

NETWORK DATA-SETS

Principali data-sets disponibili in rete su network di grandi dimensioni Grafi di Collaborazioni

Wikipedia, World of Warcraft, Citation graphs

Grafi chi-parla-con-chi Microsoft IM, Cell phone graphs

Reti di informazioni Hyperlinks

Reti tecnologiche Power grids, communication links, Internet

Reti naturali e biologiche Food webs, neural interconnections, cell metabolism

Leskovec‘s SNAP a Stanford ha un repository di dati su reti di grandi dimensioni http://snap.stanford.edu/data

Au

tun

no 2

01

2

36

Stru

ttura

delle

Reti S

ocia

li