Reti sociali Reti sociali Cosa sono • Una rete sociale e’ un grafo G = (V, E) dove – I nodi rappresentano entita’, spesso persone o gruppi di persone – Gli archi (pesati o meno) rappresentano relazioni tra i nodi della rete sociale • Esempio: grafo delle conoscenze – Vertici: persone – Esiste arco tra a e b se a e b si conoscono • Altri esempi nelle slide seguenti … Reti sociali Esempio - commercio mondiale Reti sociali Esempio - Internet Reti sociali Esempio - catena alimentare Reti sociali Cosa hanno in comune? • Grandi e complesse • Regolarita’, ma soltanto a livello macroscopico – – – – – Componente gigante connessa Piccolo mondo: distanza media tra i nodi bassa Grafi sparsi: |E| = o(|V|2) Aggregazione (v. piu’ avanti) Invarianza di scala • Distribuzione del grado secondo legge di potenza Reti sociali Perche’ studiarle • Comprendere le loro proprieta’ • Aspetti ingegneristici e algoritmici – Estrazione di informazioni • Es.: motori di ricerca – Progetto di algoritmi efficienti • Es.: Web Caching – Tolleranza ai guasti o agli attacchi –… Reti sociali Componente connessa • Nelle reti considerate, la maggior parte dei nodi appartiene a un’unica componente connessa – Es.: Web • Matematicamente, una frazione costante dei nodi appartiene a un’unica componente connessa Reti sociali Proprieta’ di piccolo mondo Reti sociali Piccolo mondo • 1967 - studio di Milgram: lunghezza media dei cammini in una rete di conoscenze – Esperimento: consegna di lettere a persone negli Stati Uniti a mano, sfruttando soltanto la rete delle conoscenze – Distanza media d = 6 • Numero di Erdös = distanza dal matematico Paul Erdös nella rete delle collaborazioni – 70975 matematici, 200000 archi – d < 8 per la maggior parte dei vertci a distanza finita • Molti altri esempi … Reti sociali Esperimento di Milgram • Spedire 160 lettere a una persona residente a Boston • Consegna a mano • Non si conosce indirizzo del destinatario ma si hanno soltanto informazioni generiche (ad esempio la professione) • Domanda: dopo quanti passaggi una lettera giunge a destinazione? Reti sociali Esperimento di Milgram/2 • Circa un terzo delle lettere giunse a destinazione – Si osservi che non si tratta di una bassa percentuale • La maggior parte delle lettere arrivate non aveva subito piu’ di 6 passaggi Reti sociali Reti piccolo mondo [WS98] • • • • • Grandi dimensioni (n >> 1) Sparse (grado medio k << n) Non esiste un nodo centrale (kmax << n) Coefficiente di aggregazione elevato Distanza media tra i nodi bassa, tipicamente O(log n) Reti sociali Esempi di reti piccolo mondo • Internet – La rete dei router – La rete degli Autonomous Systems • • • • Il Web La rete delle conoscenze Tutti gli esempi visti all’inizio Queste reti hanno altre proprieta’ oltre a quelle di piccolo mondo Reti sociali Clustering [Granovetter 73]: “la forza dei legami deboli“ • I miei conoscenti probabilmente si conoscono … • … ma alcuni hanno contatti con gruppi “lontani” Picture by T. Deckert - TU Dreseden Reti sociali Clustering/2 • Si supponga che il nodo v abbia dv vicini. Il massimo numero di archi tra di essi si ha quando essi formano una clique --> dv(dv 1)/2 archi. • Si supponga che invece sia nv il numero di archi tra i vicini di v • Il coefficiente di clustering (aggregazione) di v e’ Cv = 2nv/dv(dv- 1) • C = (1/n)∑vCv Reti sociali Clustering/3 • • • • C1 = C2 = C4 = C5 = 1 C3 = 1/6 C = (1/5)∑iCi = 5/6 I nodi con un solo arco incidente hanno fattore di clustering 1 Reti sociali v2 v1 v3 v4 v5 Distanza media tra i nodi • Assumiamo per il momento reti connesse • La distanza media tra i vertici e’ O(log n), spesso sub-logaritmica • Il coefficiente di clustering e’ alto ((1)) • Come spiegare tali proprieta’? Reti sociali Grafi casuali • Modello classico proposto da Erdös e Renyi • Modello probabilistico – Si hanno n nodi – Per ogni coppia u e v di nodi, l’arco (u, v) esiste con probabilita’ p indipendente da tutti gli altri • Proprieta’ – Per p sufficientemente grande, la maggior parte dei nodi si trova in una componente gigante connessa – Il diametro e’ logaritmico ma… – Il coefficiente di clustering e’ basso (O(1/n)) Reti sociali Modello di Watts e Strogatz [WS98] • Si inizia con un anello di n nodi. Ogni nodo connesso ad altri k nodi • Con probabilita’ p, ogni arco e’ riconnesso a una destinazione scelta casualmente in modo uniforme. – Granovetter, “The strength of weak ties” ordine caos Reti sociali Modello WS/cont. • L’obiettivo era mostrare che con meccanismi semplici e’ possibile ottenere una rete di tipo piccolo mondo • Risultati – Componente gigante connessa – Distanza media tra nodi connessi O(log n) – Coefficiente di clustering (1) Reti sociali Modello WS/clustering Scala logaritmica in p • Quando p = 0 • C = 3(k-2)/4(k-1) ~ 3/4 • L = n/k Reti sociali Modello di Kleinberg [Kl. 99] • Lattice bidimensionale – Si aggiungono q archi a ogni vertice u (shortcut) • Il vertice v destinazione di uno shortcut e’ scelto con probabilita’ [d(u,v)]-r/ ∑wu[d(u,v)]-r • se r = 0, si ha probabilita’ uniforme • Nel seguito q = 1 Reti sociali Modello di Kleinberg/2 • Data una sorgente s e una destinazione t, definire un algoritmo per muovere un agente da s a t che 1. conosce le posizioni dei nodi nella griglia 2. conosce i vicini e gli shortcut del nodo in cui si trova 3. ricorda i vicini e gli shortcut di tutti i nodi visitati 4. Ad ogni passo diminuisce la distanza da t Si tenta di riprodurre l’esperimento di Milgram La griglia modella una distribuzione geografica dei nodi Reti sociali Algoritmo • Nel generico nodo v – Scegli il vicino a distanza minima dalla destinazione • L’algoritmo usa soltanto un’informazione locale e la conoscenza della posizione dei nodi sul lattice Reti sociali Risultati • Per r=2, esiste un algoritmo locale che raggiunge la destinazione in un numero atteso di passi O(log2n). • Se r<2 un algoritmo locale richiede un numero atteso di passi (n(2-r)/3). • Se r>2 un algoritmo locale richiede un numero atteso di passi (n(r-2)/(r-1)). • Nota: numero atteso di passi sub-polinomiale soltanto per r=2 – Risultato dovuto probabilmente ai limiti del modello Reti sociali Prova per r = 2 e q = 1 v) / d(u, v] = d(u, P[u --> w) . -2 -2 wu d(u, w) wu -2 2n-2 2n-2 (4j)(j -2 )= j -1 j=1 j=1 4 + 4ln 2n-2 P[u --> v] 1/4ln(6n)d(u, 4ln(6n) v) 2 • P[u --> v]: probabilita’ che u scelga v come shortcut • Per ogni w, la distanza da u e’ compresa tra 1 e 2n-2 • Vi sono non piu’ di 4j nodi a distanza j da u Reti sociali Prova per r = 2 e q = 1/cont. • Fase j: insieme dei passi durante i quali l’agente si trova in nodi a distanza da t > 2j e <= 2j+1 – L’agente inizia al piu’ in fase log2n – Ad ogni passo l’agente si avvicina a t – Occorre calcolare il numero medio E[Xj] dei passi durante la j-esima fase – Quando l’agente lascia la fase j-esima e’ per entrare in una fase i <= j-1 – E[lunghezza percorso] = ∑jE[Xj] Reti sociali Prova per r = 2 e q = 1 /cont. Bj t u • Se ci troviamo in un nodo u durante la fase j – P[si lascia la fase j] >= P[si entra in Bj] – Bj: insieme dei nodi a distanza <= 2j da t Reti sociali Prova per r = 2 e q = 1 /cont. Bj t u • Bj contiene almeno 22j-1 nodi • Ciascun nodo in Bj dista al piu’ 2j+2 da u • Quindi P[si entra in Bj] >= 1/128ln(6n) Reti sociali Prova per r = 2 e q = 1 /cont. 1 EX j = PXj i 1 128ln(6n) i=1 i=1 128ln(6n) • Poiche’ vi sono O(log n) fasi abbiamo O(log2n) passi in media Reti sociali i Altre proprieta’ - grado Reti sociali Distribuzione del grado • # nodi con grado k: P(k) ~ k-a – P(k): % nodi con grado k – a circa 2.1 per il Web – [Broder et al. 2000] • Regola dell’ 80/20: – Una modesta percentuale di nodi ha quasi tutti i link --> Hub – I ricchi diventano sempre piu’ ricchi Reti sociali Reti prive di scala Reti sociali Matematicamente… • Non vi e’ una scala privilegiata per osservare le proprieta’ macroscopiche della rete • Nelle reti sociali l’invarianza di scala si riferisce alla distribuzione del grado dei nodi – Legge di potenza per distribuzione del grado entrante e/o uscente (es. il Web) Reti sociali Modelli di reti sociali Reti sociali Modelli di reti sociali • Cosa sono – Modelli per la generazione di grafi casuali • Es.: modello di Watts e Strogatz – obiettivo: riprodurre le proprieta’ osservate in pratica • I modelli di Watts e Strogatz e di Kleinberg spiegano il fenomeno di piccolo mondo ma non altre proprieta’ – Es.: la distribuzione del grado dei nodi Reti sociali Meccanismi di base • Attaccamento preferenziale – Un nuovo nodo ha maggiore probabilita’ di connettersi ai nodi esistenti di grado piu elevato • Esempio [Chung et al. 2000] per il Web – Per t = 1, 2, … • Con probabilita’ 1- si aggiunge un nuovo vertice con un link verso se stesso • Con probabilita si aggiunge un nuovo arco. Se u e v sono due nodi della rete, P[Si genera (u, v)] = du·dv/ ∑w,z dw·dz – La rete risultante e’ di tipo piccolo mondo – La distribuzione del grado segue una legge di potenza con esponente 1+1/ quando t e’ abbastanza grande Reti sociali Esempio • Si consideri il modello precedente e si supponga che = 0.9 e che al tempo t la distribuzione del grado entrante sia approssimativamente una legge di potenza con parametro 1+1/ • Stimare la probabilita’ che a t+1 venga creato un nuovo link verso un nodo di grado x Reti sociali Esempio/cont. A(x, t) = A P[A(x+1, t+1) = A(x+1, d v S(x,t) d t , do ve = 1 + 1/ x z . t) + 1] = d = dv u v S(x,t) d w v u w dz z S(x, t) x A(x, t)x = t t z = Ax 1- = Ax 1 / • La distribuzione dipende anche da t, che stavolta e’ una variabile • Senuovo link verso un nodo di grado x allora A(x+1, t+1) = A(x+1, t) + 1 • S(x, t): insieme dei nodi di grado x a t • Si ricordi che si introduce nuvo link con prob. Reti sociali Riferimenti • M. E. Newman. The structure and function of complex networks. – Buon lavoro di rassegna sulle reti sociali – Sezioni I, II, III e VI – http://citeseer.ist.psu.edu/newman03structure.html • M. E. Newman. Models of the Small World – Lavoro di rassegna sul modello di Watts e Strogatz e sue estensioni – http://citeseer.ist.psu.edu/487139.html • D. Watts and S. H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, Vol. 393, pp. 440 – 442, 1998 – Basta il lavoro di rassegna di Newman • J. Kleinberg. The small-world phenomenon: An algorithmic perspective. – Il lavoro di Kleinberg sulla navigazione nelle reti sociali – http://www.cs.cornell.edu/home/kleinber/nips14.ps Reti sociali
Scarica
