Università degli Studi di L’Aquila

Facoltà di Scienze MM. FF. NN.

“ Il Fenomeno Small-World: Una Prospettiva Algoritmica”

Tesina presentata per la laurea in

Scienze dell’Informazione

da

Samuel Zallocco

RELATORE LAUREANDO

prof. Michele Flammini Samuel Zallocco

A.A. 2005/2006

2

Il fenomeno Small-World: Una Prospettiva Algoritmica

Tesina presentata per la laurea in Scienze dell’Informazione

da

Samuel Zallocco

Abstract

Un esperimento un po’ visionario degli anni sessanta, abbandonato nei cassetti della facoltà di psicologia sociale della Yale University, si ripropone nell’era della Rete con interessanti risvolti sull’evoluzione del World Wide Web. Al di là del folklore, il “fenomeno del piccolo mondo” è stato inaugurato come un’area di studio sperimentale delle scienze sociali attraverso lo studio pionieristico di Stanley Milgram negli anni ’60. L’ipotesi di Milgram è che i membri di una qualsiasi “rete sociale” (nel suo caso, Milgram utilizzò la popolazione degli Stati Uniti) siano interconnessi l’uno all’altro attraverso una breve catena di conoscenze intermedie. Al fine di testare la sua ipotesi Milgram condusse due esperimenti molto simili tra loro, usando una tecnica empirica ma rivoluzionaria: spedì a circa duecento persone del Nebraska e del Kansas (regioni assai decentrate e poco popolate), selezionate in modo casuale, una lettera nella quale spiegando l’esperimento, chiedeva loro di inviare la stessa lettera ad una persona, a loro sconosciuta, residente nell’area di Boston. Milgram nella sua lettera fissava dei vincoli che ognuno doveva rispettare. Ogni persona che riceveva la lettera, doveva aggiungere alcune informazioni personali e rispedire la lettera a qualcuno che conoscevano molto bene da poterlo chiamare per nome di battesimo e che, basandosi solo sul nome del destinatario, sul fatto che abitasse a Boston e sul suo lavoro, poteva conoscerlo o comunque poteva avere maggiori possibilità di loro di far giungere la lettera a destinazione. Il risultato sorprendente del suo esperimento, ora divenuto parte della cultura popolare grazie ad un famoso film ed assurto a dogma della sociologia, è che in media la lettera arriva a destinazione dopo sei passaggi. Questo risultato, verificato in seguito anche da altri esperimenti simili, ha portato a parlare dei “sei gradi di separazione” che dividerebbero due persone di una qualunque rete sociale. Basandosi sull’esperimento di Milgram, altri studiosi hanno pensato di verificare questa teoria, applicandola ad altre discipline e tipologie di reti, tentando di costruire un modello matematico per poter studiare analiticamente il problema. Uno dei modelli più recenti e più raffinato è stato formulato da Watts e Strogatz. Il loro modello ha fornito prove evidenti, che il fenomeno del piccolo mondo è riscontrabile in una serie di reti, relative sia a fenomeni naturali che tecnologici, e che rappresenterà un ingrediente fondamentale nell’evoluzione del World Wide Web. Tuttavia i modelli esistenti sono risultati insufficienti a spiegare la notevole componente algoritmica presente nell’esperimento originale di Milgram: “gli individui di una rete sociale, usando solo informazioni locali sono collettivamente molto efficienti nel costruire percorsi brevi tra due soggetti della rete sociale stessa”. Jon Kleinberg nel suo lavoro: “The Small-World Phenomenon: An Algorithmic Perspective” (lavoro da cui prende spunto questa tesina), tenta di dimostrare che, sebbene recenti modelli di rete risultino ricchi di percorsi brevi, nessun algoritmo decentralizzato, operando solamente con informazioni locali, è in grado di costruire cammini brevi su queste reti con probabilità di successo trascurabile. Kleinberg, definisce una famiglia infinita di modelli di rete che generalizza il modello di Watts-Strogatz, e mostra che per uno di questi modelli, esiste un algoritmo decentralizzato capace di trovare un cammino breve con alta probabilità.

3

Indice 1 Introduzione .................................................................................................................................4

2 Modellare il fenomeno .................................................................................................................6

3 Spiegare il Piccolo Mondo...........................................................................................................8

3.1 Erdıs e Rényi: Random Graphs...........................................................................................9

3.2 Watts e Strogatz: Rewired Ring Lattice.............................................................................11

4 Il lavoro di Kleinberg: un piccolo mondo navigabile ................................................................13

4.1 Il modello di Kleinberg: rete e algoritmo decentralizzato .................................................14

5 Limite superiore per la distribuzione quadratica inversa ...........................................................26

6 Limiti inferiori per altre distribuzioni ........................................................................................29

7 Conclusioni ................................................................................................................................36

4

1 Introduzione

Quando parliamo di rete sociale intendiamo semplicemente un insieme, anche vasto, di persone (o

altre entità facenti parte di un contesto) che siano legate tra loro da una qualche relazione che

rappresenti: interazione, collaborazione o vicendevole influenza. Queste relazioni ad esempio

possono essere: reciproca dichiarazione di amicizia, parentela, collaborazione ad un progetto, aver

scritto un libro insieme, aver lavorato sullo stesso set cinematografico o essersi scambiati un e-mail.

Una qualsiasi rete sociale si dice mostrare il fenomeno del piccolo mondo se, presi a caso due

individui di questa rete essi sono collegati da una breve sequenza di conoscenze intermedie.

Questa teoria fu formulata per la prima volta, nel 1929, dallo scrittore Ungherese Frigyes Karinthy

in un breve racconto dal titolo “Chains”. Negli anni ’50, Ithiel da Sola Pool (MIT) e Manfred

Kochen (IBM) cercarono di provare questa teoria matematicamente e formularono quindi la

domanda: dato un insieme di N persone, quale è la probabilità che ogni membro di N sia connesso

ad un altro membro attraverso k1, k2, k3, … ,

kn membri intermedi? Persino dopo quasi

venti anni di tentativi però, nessuno era

ancora riuscito a risolvere il problema in

modo soddisfacente. Nel 1967, il sociologo

americano Stanley Milgram trovò un nuovo

sistema per testare questa teoria, che egli

chiamò “teoria del piccolo mondo”. Il suo

esperimento, empirico ma rivoluzionario,

aveva l’obiettivo di determinare quale fosse la più breve catena di amicizie intermedie che

collegano due persone qualsiasi degli Stati Uniti. Il risultato sorprendente del suo esperimento fu

che, su un numero molto elevato di tentativi, il numero medio di intermediari si attestava tra cinque

e sei [Figura 1.1]. Questo numero entrò in seguito nella cultura popolare come il principio dei “sei

gradi di separazione”. In seguito qualcuno sostenne che Milgram aveva usato un numero di tentativi

troppo esiguo per ritenere il numero “sei” come affidabile, e che aveva volutamente trascurato i

risultati più pessimistici non divulgandoli.

Altri esperimenti, come quello di Brett C. Tjaden, evidenziarono risultati ancora migliori. Tjaden

nel 1996, pubblicò sul sito della University of Virginia, un gioco basato sull’ Internet Movie Data

Base (IMDB http://www.imdb.com/ ) per documentare i collegamenti esistenti tra gli attori. Time

Magazine nominò il suo sito come uno dei “10 migliori siti web del 1996”. Il numero di passi tra

attori differenti è però, in media, più basso di sei, in quanto l’insieme degli attori contiene alcuni

Figura 1.1: Sei gradi di separazione

5

“nodi speciali” (attori che hanno partecipato a molti film), che abbattono drasticamente questo

numero. Il grado di separazione per Kevin Bacon, l’attore

su cui era originariamente incentrata questa ricerca,

risulterà essere compreso tra tre e quattro.

Nel 2001, Duncan Watts, un professore della Columbia

University, riprese per conto suo la ricerca e ricreò

l’esperimento di Milgram su Internet. Watts usò un

messaggio di posta elettronica come “pacchetto” che

doveva essere consegnato e, sorprendentemente, dopo aver analizzato i dati ottenuti degli invii

effettuati da 48.000 differenti persone residenti in 157 stati diversi, nei confronti di 19 “bersagli”,

Watts trovò che il numero medio di intermediari era effettivamente sei, riconfermando la validità

dell’esperimento di Milgram. La ricerca di Watts e l’avvento dell’era di Internet permisero

l’applicazione della teoria dei sei gradi di separazione anche in aree differenti, tra cui l’analisi delle

reti informatiche, delle reti elettriche, la trasmissione di malattie, la teoria dei grafi, le

telecomunicazioni e la progettazione della componentistica per apparati elettronici.

La teoria, apparentemente strana, può essere facilmente

intuita con un semplice calcolo. Stando ai dati relativi alla

crescita della popolazione mondiale forniti dal U.S. Census

Boreau (http://www.census.gov/ipc/www/world.html)

[Figura 1.2 e Figura 1.3], la popolazione mondiale al 6

Dicembre 2006 risulta essere pari a 6.561.536.382 persone.

Ora ammettendo che ognuno di noi, nell’arco della sua vita,

conosca almeno 1000 persone e di queste almeno 100

molto bene (per fare una stima per difetto diciamo circa 20

parenti, 20 amici delle scuole elementari, 15 delle scuole medie, 10 delle scuole superiori, 10

dell’università, altre 10 conoscenze derivanti dal lavoro e altri 15 derivanti da hobby, sport e

incontri casuali), e che queste 100 persone a loro volta conoscano altre 100 persone, allora

100x100=10.000 persone con soli due livelli di separazione, al terzo siamo già a 1003 persone, così

via fino al sesto grado di separazione che ci dà 1006 persone, cioè 1.000.000.000.000 di persone,

che è un numero circa 152,403 volte superiore alla popolazione mondiale attuale.

Questo calcolo, pur nella sua banalità, ci da una base pratica da cui partire per “intuire” che i sei

gradi di separazione non sono poi una stima così assurda. Ma se basta un semplice calcolo per

spiegare questo fenomeno, perché scomodare complesse teorie matematiche? Perché conoscere

Figura 1.3: Tasso di crescita della popolazione mondiale

Figura 1.2: Popolazione mondiale

6

dove agire all’interno della rete sociale che unisce i gruppi di persone risulta particolarmente utile.

È vero che in genere ci sono sei gradi di separazione, anche se questo numero è puramente

convenzionale, ma è altrettanto vero che ci sono persone che fanno da ponte tra gruppi quasi isolati

di persone. Conoscere strutture di rete di questo tipo è di grande importanza strategica, rispetto a

una conoscenza puramente casuale dei contatti tra persone.

2 Modellare il fenomeno

La dimostrazione empirica del fenomeno del piccolo mondo ha portato alla ricerca di una prova

analitica della sua validità. Gli sforzi degli studiosi del fenomeno sono stati concentrati

principalmente nel cercare una risposta alla seguente domanda:

(1) Perché dovrebbe esistere un breve catena di conoscenze intermedie che lega insieme due

persone apparentemente sconosciute?

Molti dei risultati delle ricerche di questi studiosi, iniziando dal lavoro di Pool e Kochen che

precedette l’esperimento di Milgram, sono basati sulla seguente spiegazione: “le reti casuali

(random network) hanno un diametro piccolo” [11]. Cioè, se ogni individuo degli Stati Uniti ha un

piccolo numero di conoscenze selezionate uniformemente in modo casuale nella popolazione – e se

le conoscenze sono in qualche modo simmetriche – allora, con molta probabilità, due individui

scelti a caso saranno collegati da una breve catena di intermediari. Questi primi lavori evidenziano

le limitazioni del modello casuale uniforme (uniform random model); se A e B sono due individui

con un amico C in comune è molto probabile che essi stessi siano amici. Ma allo stesso tempo, una

rete di conoscenze che sia troppo raggruppata (clustered network) non avrà il diametro piccolo che

l’esperimento di Milgram ha indicato.

Recentemente Watts e Strogatz hanno proposto un modello per il fenomeno del piccolo mondo

basato su una classe di random network che si può considerare un’interpolazione di questi due

estremi (random network e clustered network), nel quale i bordi della rete vengono divisi in contatti

“locali” ( local contacts) e contatti a lungo-raggio (long-range contacts) [19]. L’esempio usato come

caso di studio è costituito da una “grata ad anello riconnessa” (rewired ring lattice), costruita come

segue: si inizia con un insieme V di n punti spaziati uniformemente su un cerchio, si unisce con un

arco ogni punto con i suoi k punti vicini, per k costante sufficientemente piccolo, quelli che si

ottengono sono i “local contacts” della rete; poi si introduce un piccolo numero di archi scelti a

7

caso in modo uniforme da V, e questi sono i “long-range contacts”. Watts e Strogatz sostengono

che questo modello contiene alcuni parametri cruciali delle reti sociali:

- una struttura semplice che spiega la presenza

di molti degli archi locali,

- alcuni archi sono prodotti da un processo

casuale che non rispetta la struttura base,

- ha un diametro piccolo (come le uniform

random networks),

- molti dei vicini di un nodo u sono loro stessi

vicini (differentemente dalle uniform random

networks).

Watts e Strogatz mostrano che un certo numero di reti

esistenti (in natura e non) sono dotate di queste

proprietà (come ad esempio la rete di connessioni

neurali del verme Caenorhabditis Elegans [Figura

2.1], e la rete elettrica della Western United States

[Figura 2.2]), ed il loro approccio è stato applicato

con successo all’analisi degli hyperlink del World

Wide Web.

Altro lavoro notevole nell’area della probabilistica

combinatoria è quello di Ballobás e Chung [5], i quali riescono a dare dei limiti al diametro di un

random graph, aggiungendo delle corrispondenze casuali ai nodi di un ciclo [6] nello studio di reti

formate dalla sovrapposizione di “structured subgraph” e “random subgraph”.

Figura 2.2: U.S.A. Power Grid Interconnection Map

Figura 2.1: Nematode Caenorhabditis Elegans Neural Network

8

3 Spiegare il Piccolo Mondo

Circa cinquanta anni dopo l’esperimento originale di Milgram è facile pensare che i suoi risultati

siano intuitivi ed ovvi ma, a quel tempo, quando egli presentò il suo studio il numero “sei” fu una

grande sorpresa. Quando Milgram pubblicò i suoi risultati l’impressione dominante che si formò nel

mondo accademico fu che, in realtà, il numero sei non era una buona stima della realtà, ma che il

risultato reale si doveva attestare intorno ad un numero a tre cifre. Il fenomeno del piccolo mondo

aveva quindi ancora bisogno di una spiegazione. Prima di discutere sui modelli specifici che sono

stati creati per spiegare il fenomeno del piccolo mondo, notiamo che le reti sociali reali sono

assimilabili a grafi sparsi (sparse graphs). In media, come già detto, una persona ha un numero di

amici dell’ordine delle migliaia [23], e per questo un modello reale del fenomeno non può usare i

grafi densi (dense graphs) per spiegare il piccolo mondo.

9

3.1 Erdıs e Rényi: Random Graphs

Storicamente la spiegazione data ai risultati dell’esperimento di Milgram è semplice: i

random graphs hanno un diametro piccolo. Il modello standard dei grafi casuali è

rappresentato dal grafo casuale G(n,p) di Erdıs e Rényi [25][26][27]: si inizia con un

insieme di n nodi e, per ognuna delle

2n coppie di nodi del grafo, si aggiunge un

arco che li collega indipendentemente a caso con una certa probabilità fissa p. Sono state condotte

significative ricerche sulle proprietà matematiche dei grafi casuali G(n,p), le quali hanno mostrato

che, fra le molte proprietà di cui sono dotati, essi hanno un diametro piccolo. Paul Erdıs,

ovviamente, ha giocato un altro importante ruolo nell’ambito della ricerca sulle reti sociali:

l’equivalente matematico del Bacon Game è infatti l’Erdıs Number, ovvero un gioco che consiste

nel calcolare la distanza sul grafo da Erdıs nella rete sociale costituita dai suoi coautori.

Tuttavia l’importanza dei grafi casuali applicati alle reti sociali risulta avere poca consistenza in

molti casi reali. Si vedano, ad esempio, la Figura 3.1 e la Figura 3.2 che mostrano due reti sociali,

una relativa alle amicizie ed una ai corteggiamenti di una scuola superiore.

Figura 3.1: Rete sociale dei corteggiamenti di una

scuola superiore. I nodi scuri (blu) sono i ragazzi,

quelli chiari (rosa) sono le ragazze.

Figura 3.2: Rete sociale delle amicizie instaurate in una scuola superiore. I

nodi chiari (beige) sono studenti bianchi, quelli scuri (verdi) sono studenti

neri, il resto (rossi) sono studenti di altre razze.

I grafi sono stati costruiti in base alle informazioni fornite dagli studenti stessi, ed i nodi sono

piazzati nello spazio senza alcun significato particolare. Nella seconda immagine si nota un taglio

verticale ed uno orizzontale: il primo è dovuto alla razza, il secondo all’età.

10

Dando una rapida occhiata ai due esempi risulta evidente che i grafi sparsi di Erdıs/Rényi non sono

un buon modello per queste due reti sociali, infatti la probabilità di generazione p di questi due grafi

è molto bassa p << 1. Il primo grafo è un near-pseudotree (un grafo connesso formato dalla

sostituzione del nodo radice di un tree-graph da un ciclo), il secondo è un grafo i cui nodi possono

essere divisi in quattro insiemi densamente connessi, e questi quattro insiemi connessi a loro volta

tra di loro in modo sparso l’uno con l’altro.

Il coefficiente di raggruppamento (clustering coefficient) di una rete sociale è una misura della

probabilità che due persone con un amico in comune siano a loro volta amici. Il clustering

coefficient di una rete sociale è radicalmente più alto di quanto accade nei grafi connessi di

Erdıs/Rényi quando p << 1 (condizione necessaria affinché il grafo risultante sia sparso). Questa

differenza si può in parte spiegare attraverso la propensione delle reti sociali a costituire aggregati

di persone omogenee per razza, posizione geografica, religione, credo politico, interessi e così via.

D’altro canto, la distribuzione dei gradi (degree distribution1) di un grafo casuale G(n,p) è ben

approssimata da una distribuzione binomiale, che è una cattiva approssimazione delle reti sociali

reali, che quindi non sono ben modellabili mediante l’uso dei grafi casuali di Erdıs/Rényi.

1 Degree Distribution: nel campo matematico della teoria dei grafi la distribuzione dei gradi di un grafo è una funzione che descrive il numero totale di vertici in un grafo con un dato grado, ovvero il numero di collegamenti ad altri vertici.

11

3.2 Watts e Strogatz: Rewired Ring Lattice

Verso la Fine del 1990 Duncan Watts e Steve Strogatz definirono un nuovo modello di grafo

random per le reti sociali, tale modello era in grado di soddisfare simultaneamente il bisogno di

avere un diametro piccolo (small diameter) e un alto coefficiente di raggruppamento (clustering

coefficients). Il loro lavoro ebbe l'effetto di suscitare nuovo interesse verso gli studi per le reti

sociali, attirando molti studiosi, tra cui numerosi matematici.

Figura 3.3: Modello di rete sociale ideato da Watts e Strogatz. Nella figura è possibile notare come al variare della probabilità p si

modifichi la topologia del grafo.

Watts e Strogatz immaginarono di disporre alcune persone su di una griglia circolare

k-dimensionale (essi focalizzarono lo studio al caso k=1, ma il modello si dimostrerà applicabile

anche per dimensioni maggiori), e che ogni persona u posta sulla griglia fosse collegata con le

persone distanti (nel senso della distanza di Manhattan1 fra i nodi del grafo) di una certa quantità

δ > 1 (contatti locali di u). In questo modo la rete risultante avrebbe avuto un elevato coefficiente di

clustering [Figura 3.3(a)], che però, avrebbe fatto svanire il fenomeno del piccolo mondo, poiché in

una rete simile solo i vicini immediati di un vertice sono a stretto contatto con esso.

Per ovviare a questo problema alcune connessioni nella rete furono alterate in maniera casuale

[Figura 3.3(b)]. Con la medesima probabilità p ogni arco <u,v> nel grafo sarebbe stato “ricollegato”

(Rewired) casualmente diventando <u,v’>, dove v’ è scelto in modo uniformemente casuale

dall’insieme di tutti i nodi del grafo. Per valori di p=0 ci troveremo ancora nella situazione iniziale,

con un alto coefficiente di clustering (per ogni coppia di nodi vicini u e v, molti dei nodi che sono

1 Distanza di Manhattan: la distanza di Manhattan è una grandezza data dalla somma delle differenze in valore assoluto

delle componenti dimensionali delle posizioni di u e v. ∑ =−k

i ii vu0

12

vicini a u lo saranno anche a v) che impedisce la formazione di piccoli mondi. Avremo inoltre un

diametro grande (polinomiale rispetto alla grandezza della popolazione), in quanto i soli archi

presenti nel grafo sono link locali che consentono di effettuare salti che coprono distanze dell’O(1)

nella griglia.

D'altro canto per valori di p≈1 [Figura 3.3(c)] si avrà il diametro bassissimo di un random graph –

che porterà ad un modello topologicamente e ideologicamente identico a quello dei grafi randomici

di Erdıs/Rényi – ma avremo ancora un basso coefficiente di clustering, sempre perché il grafo

risultante è essenzialmente un random graph.

Il risultato principale, degli studi condotti da Watts e Strogatz, consiste nella scoperta empirica che

la rete riesce a mantenere i vantaggi di entrambe le proprietà (diametro piccolo e alto coefficiente di

clustering) per valori intermedi della probabilità p. Per valori di p compresi tra 0 e 1, infatti, l'alto

coefficiente di clustering persiste, perché molti degli archi originali rimangono immutati (la

probabilità p che questi siano ricollegati è piccola), e per due nodi vicini u e v, i nodi vicini ad u

sono, nella maggior parte dei casi, gli stessi che sono vicini a v. Allo stesso tempo risulta intuitivo

come il piccolo diametro appaia anche per valori relativamente piccoli di p, perché gli archi inseriti

casualmente formano a tutti gli effetti un grafo casuale G(n,p) formato da piccoli cluster di nodi

vicini, in cui il diametro di ogni singolo cluster risulta piccolo.

13

4 Il lavoro di Kleinberg: un piccolo mondo navigabile

Tornando all’esperimento di Milgram, Kleinberg sostiene che esso contenga

realmente due scoperte sorprendenti e fondamentali: in primo luogo che tali catene

corte dovrebbero esistere in una rete di conoscenti; e secondo, che le persone

dovrebbero essere capaci di trovare queste catene avendo a disposizione solo poche

informazioni “locali” sul destinatario. Da un punto di vista analitico, la prima di queste scoperte

risulta essere una caratteristica intrinseca delle reti sociali, mentre la seconda dà vita ad una idea

algoritmica del fenomeno, ovvero ci rivela che degli individui, con la sola informazione relativa alla

posizione dei loro conoscenti diretti sono comunque in grado, collettivamente, di costruire un breve

cammino tra due punti della rete. Basandosi su questi argomenti Kleinberg suggerisce una nuova

domanda da aggiungere alla domanda (1) a cui rispondere per studiare il fenomeno ovvero:

(2) Perché due individui, apparentemente sconosciuti e usando solo informazioni locali,

riescono a trovare una catena breve di conoscenze intermedie in grado di unirli?

In altre parole Kleinberg, invece di vedere l’esperimento di Milgram come un risultato relativo

all’ordine di grandezza del diametro di una rete sociale, suggerisce che esso rappresenti un risultato

relativo al “successo” (ovvero aver trovato una catena corta di intermediari) di un particolare

algoritmo di routing (che quindi deve esistere) quando esso viene eseguito su di un grafo.

La cosa importante da notare è che la domanda (2) solleva questioni distanti dagli scopi della

domanda (1): infatti, anche se risulta abbastanza facile immaginare la possibilità che esistano catene

brevi di conoscenze tra due individui, risulta molto più complesso immaginare un meccanismo che

consenta di trovare queste catene basandosi esclusivamente su informazioni “locali”. Il successo

dell’esperimento di Milgram suggerisce che nelle reti sociali vi sia una fonte intrinseca di

“indicazioni di navigazione”, usando le quali un messaggio può essere guidato velocemente ed in

modo implicito dalla sorgente alla destinazione. Viene allora naturale chiedersi quali proprietà

debba avere una rete sociale al fine di possedere queste indicazioni intrinseche, tali da consentire ai

suoi membri di trovare delle brevi catene attraverso di essa.

Kleinberg focalizza il suo studio su di un algoritmo decentralizzato1 attraverso il quale degli

individui, conoscendo solo la posizione dei suoi conoscenti più prossimi, cercano di recapitare un

messaggio da una sorgente ad una destinazione attraverso una catena breve di intermediari.

Come risultato del suo studio, Kleinberg dimostrerà alcuni fatti fondamentali: 1 Nell’accezione classica per algoritmo decentralizzato si intende un algoritmo che ad una determinata fase della sua esecuzione si troverà a dover effettuare una scelta, che effettuerà in modo casuale.

14

− primo, egli mostra che i modelli esistenti non sono sufficienti a spiegare il successo

dell’algoritmo decentralizzato nel trovare cammini brevi in una rete sociale. In particolare

Kleinberg mostrerà che presa in considerazione la classe dei modelli di reti sociali di Watts

e Strogatz, non esiste alcun algoritmo decentralizzato capace di costruire un cammino breve

di lunghezza prefissata (relativamente al diametro della rete stessa).

− secondo: egli definisce una famiglia infinita di modelli che generalizza ed estende il modello

di Watts e Strogatz. Ed in seguito mostrerà che solo per uno di questi modelli, esiste un

algoritmo decentralizzato in grado di trovare cammini brevi sulla rete con alta probabilità.

− infine, egli dimostra che esiste un unico modello di rete sociale, all’interno di questa

famiglia di modelli, per il quale l’algoritmo decentralizzato risulta efficace.

Il principale risultato, a cui Kleinberg approdò, fu la caratterizzazione di un teorema in grado di

stabilire esattamente quando un algoritmo, basandosi solo su informazioni locali, è in grado di

costruire un cammino breve tra i nodi di un grafo.

4.1 Il modello di Kleinberg: rete e algoritmo decen tralizzato

Diamo ora una precisa definizione del modello a rete utilizzato da Kleinberg e la definizione di

algoritmo decentralizzato; successivamente vedremo la dimostrazione formale del risultato

principale del suo modello.

Figura 4.1: (A) Una griglia bi-dimensionale con n = 6, p = 1, e q = 0. (B) I contatti di un nodo u con p = 1 e q = 2. v e w sono due contatti

a lungo raggio.

Kleinberg definisce il suo modello a rete cercando di incapsulare il paradigma usato da Watts e

Strogatz: costruire un modello a rete ricco di connessioni locali con poche connessioni a lungo

raggio. A differenza del modello di Watts-Strogatz, Kleinberg non utilizza come base di partenza un

15

anello riconnesso (dove cioè, alcuni contatti locali venivano trasformati in contatti a lungo raggio e

quindi persi), bensì un reticolo bidimensionale con archi orientati [Figura 4.1(A)] (dove i contatti

locali restano tutti, e quelli a lungo raggio sono in aggiunta).

Iniziando con un insieme di nodi (che rappresentano gli individui della rete sociale) identificati da

un insieme di punti sul reticolo in un quadrato n × n: { ( i,j) : 1 ≤ i ≤ n , 1 ≤ j ≤ n }, definisce la:

Definizione: distanza tra due nodi del reticolo (lattice distance o distanza reticolare).

Si definisce distanza reticolare tra due nodi (i, j) e (k, l) di un reticolo di dimensione

n×n il numero, dato dalla distanza in “numero di passi” che separano i due punti,

calcolato come differenza in valore assoluto delle componenti dimensionali delle

posizioni dei nodi: ( ) jliklkjid −+−=),(),,( .

Si consideri la Figura 4.1(B), per una qualsiasi costante p ≥ 1, il nodo u ha un arco orientato verso

ogni altro nodo che sia ad una distanza reticolare p (contatti locali). Considerando due altre costanti,

q ≥ 0 e r ≥ 0, possiamo costruire degli archi diretti da u verso altri q nodi del reticolo (contatti a

lungo raggio) usando prove casuali indipendenti; l’i-esimo arco orientato in uscita da u, avrà come

destinazione v con probabilità proporzionale a [ ] rvud −),( . (Per ottenere la distribuzione di

probabilità, sarà sufficiente dividere questa quantità per una opportuna costante di normalizzazione:

[ ]∑ −v

rvud ),( ; la distribuzione di probabilità così definita prende il nome di distribuzione

r-potenziale inversa).

16

Esempio:

Si considerino i punti u ≡ (ux = 4, uy = 4), v ≡ (vx = 1, vy = 3) e w ≡ (wx = 6, wy = 3), su di un reticolo

7x7:

Calcoliamo le distanze:

d X1 X2 X3 X4 X5 X6 X7

Y1 6 5 4 3 4 5 6

Y2 5 4 3 2 3 4 5

Y3 4 3 2 1 2 3 4

Y4 3 2 1 0 1 2 3

Y5 4 3 2 1 2 3 4

Y6 5 4 3 2 3 4 5

Y7 6 5 4 3 4 5 6 X1

X2X3

X4X5

X6X7

Y1

Y2

Y3

Y4

Y5

Y6

Y7

0

1

2

3

4

5

6

La probabilità che u scelga v come suo contatto a lungo raggio P[u→v] è data da:

∑ −

−

=→v

r

r

vu

vuvu

),(d

),(d][P , ma per comodità calcoliamo prima la matrice rvu −),(d :

Per r = 0:

0),(d −vu X1 X2 X3 X4 X5 X6 X7

Y1 1.000 1.000 1.000 1.000 1.000 1.000 1.000 7.000

Y2 1.000 1.000 1.000 1.000 1.000 1.000 1.000 7.000

Y3 1.000 1.000 1.000 1.000 1.000 1.000 1.000 7.000

Y4 1.000 1.000 1.000 0.000 1.000 1.000 1.000 6.000

Y5 1.000 1.000 1.000 1.000 1.000 1.000 1.000 7.000

Y6 1.000 1.000 1.000 1.000 1.000 1.000 1.000 7.000

Y7 1.000 1.000 1.000 1.000 1.000 1.000 1.000 7.000

7.000 7.000 7.000 6.000 7.000 7.000 7.000 48.000

][P vu → X1 X2 X3 X4 X5 X6 X7

Y1 2.08% 2.08% 2.08% 2.08% 2.08% 2.08% 2.08%

Y2 2.08% 2.08% 2.08% 2.08% 2.08% 2.08% 2.08%

Y3 2.08% 2.08% 2.08% 2.08% 2.08% 2.08% 2.08%

Y4 2.08% 2.08% 2.08% 0.00% 2.08% 2.08% 2.08%

Y5 2.08% 2.08% 2.08% 2.08% 2.08% 2.08% 2.08%

Y6 2.08% 2.08% 2.08% 2.08% 2.08% 2.08% 2.08%

Y7 2.08% 2.08% 2.08% 2.08% 2.08% 2.08% 2.08%

17

Per r = 1:

1),(d −vu X1 X2 X3 X4 X5 X6 X7

Y1 0.167 0.200 0.250 0.333 0.250 0.200 0.167 1.567

Y2 0.200 0.250 0.333 0.500 0.333 0.250 0.200 2.067

Y3 0.250 0.333 0.500 1.000 0.500 0.333 0.250 3.167

Y4 0.333 0.500 1.000 0.000 1.000 0.500 0.333 3.667

Y5 0.250 0.333 0.500 1.000 0.500 0.333 0.250 3.167

Y6 0.200 0.250 0.333 0.500 0.333 0.250 0.200 2.067

Y7 0.167 0.200 0.250 0.333 0.250 0.200 0.167 1.567

1.567 2.067 3.167 3.667 3.167 2.067 1.567 17.267

][P vu → X1 X2 X3 X4 X5 X6 X7

Y1 0.97% 1.16% 1.45% 1.93% 1.45% 1.16% 0.97%

Y2 1.16% 1.45% 1.93% 2.90% 1.93% 1.45% 1.16%

Y3 1.45% 1.93% 2.90% 5.79% 2.90% 1.93% 1.45%

Y4 1.93% 2.90% 5.79% 0.00% 5.79% 2.90% 1.93%

Y5 1.45% 1.93% 2.90% 5.79% 2.90% 1.93% 1.45%

Y6 1.16% 1.45% 1.93% 2.90% 1.93% 1.45% 1.16%

Y7 0.97% 1.16% 1.45% 1.93% 1.45% 1.16% 0.97%

Per r = 2:

2),(d −vu X1 X2 X3 X4 X5 X6 X7

Y1 0.028 0.040 0.063 0.111 0.063 0.040 0.028 0.372

Y2 0.040 0.063 0.111 0.250 0.111 0.063 0.040 0.677

Y3 0.063 0.111 0.250 1.000 0.250 0.111 0.063 1.847

Y4 0.111 0.250 1.000 0.000 1.000 0.250 0.111 2.722

Y5 0.063 0.111 0.250 1.000 0.250 0.111 0.063 1.847

Y6 0.040 0.063 0.111 0.250 0.111 0.063 0.040 0.677

Y7 0.028 0.040 0.063 0.111 0.063 0.040 0.028 0.372

0.372 0.677 1.847 2.722 1.847 0.677 0.372 8.514

][P vu → X1 X2 X3 X4 X5 X6 X7

Y1 0.33% 0.47% 0.73% 1.30% 0.73% 0.47% 0.33%

Y2 0.47% 0.73% 1.30% 2.94% 1.30% 0.73% 0.47%

Y3 0.73% 1.30% 2.94% 11.74% 2.94% 1.30% 0.73%

Y4 1.30% 2.94% 11.74% 0.00% 11.74% 2.94% 1.30%

Y5 0.73% 1.30% 2.94% 11.74% 2.94% 1.30% 0.73%

Y6 0.47% 0.73% 1.30% 2.94% 1.30% 0.73% 0.47%

Y7 0.33% 0.47% 0.73% 1.30% 0.73% 0.47% 0.33%

Per r = 5:

2),(d −vu X1 X2 X3 X4 X5 X6 X7

Y1 0.000 0.000 0.001 0.004 0.001 0.000 0.000 0.007

Y2 0.000 0.001 0.004 0.031 0.004 0.001 0.000 0.042

Y3 0.001 0.004 0.031 1.000 0.031 0.004 0.001 1.073

Y4 0.004 0.031 1.000 0.000 1.000 0.031 0.004 2.071

Y5 0.001 0.004 0.031 1.000 0.031 0.004 0.001 1.073

Y6 0.000 0.001 0.004 0.031 0.004 0.001 0.000 0.042

Y7 0.000 0.000 0.001 0.004 0.001 0.000 0.000 0.007

0.007 0.042 1.073 2.071 1.073 0.042 0.007 4.314

][P vu → X1 X2 X3 X4 X5 X6 X7

Y1 0.00% 0.01% 0.02% 0.10% 0.02% 0.01% 0.00%

Y2 0.01% 0.02% 0.10% 0.72% 0.10% 0.02% 0.01%

Y3 0.02% 0.10% 0.72% 23.18% 0.72% 0.10% 0.02%

Y4 0.10% 0.72% 23.18% 0.00% 23.18% 0.72% 0.10%

Y5 0.02% 0.10% 0.72% 23.18% 0.72% 0.10% 0.02%

Y6 0.01% 0.02% 0.10% 0.72% 0.10% 0.02% 0.01%

Y7 0.00% 0.01% 0.02% 0.10% 0.02% 0.01% 0.00%

Per r ≥ 14:

2),(d −vu X1 X2 X3 X4 X5 X6 X7

Y1 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000

Y2 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000

Y3 0.000 0.000 0.000 1.000 0.000 0.000 0.000 1.000

Y4 0.000 0.000 1.000 0.000 1.000 0.000 0.000 2.000

Y5 0.000 0.000 0.000 1.000 0.000 0.000 0.000 1.000

Y6 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000

Y7 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000

0.000 0.000 1.000 2.000 1.000 0.000 0.000 4.000

][P vu → X1 X2 X3 X4 X5 X6 X7

Y1 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%

Y2 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%

Y3 0.00% 0.00% 0.00% 25.00% 0.00% 0.00% 0.00%

Y4 0.00% 0.00% 25.00% 0.00% 25.00% 0.00% 0.00%

Y5 0.00% 0.00% 0.00% 25.00% 0.00% 0.00% 0.00%

Y6 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%

Y7 0.00% 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%

18

Andamenti di ][P vu → per r = 0, 1, 2, 5 e r ≥ 14:

0.00%1.00%2.00%3.00%4.00%5.00%6.00%7.00%8.00%9.00%

10.00%11.00%12.00%13.00%14.00%15.00%16.00%17.00%18.00%19.00%20.00%21.00%22.00%23.00%24.00%25.00%26.00%27.00%28.00%

0.00%1.00%2.00%3.00%4.00%5.00%6.00%7.00%8.00%9.00%

10.00%11.00%12.00%13.00%14.00%15.00%16.00%17.00%18.00%19.00%20.00%21.00%22.00%23.00%24.00%25.00%26.00%27.00%28.00%

0.00%1.00%2.00%3.00%4.00%5.00%6.00%7.00%8.00%9.00%

10.00%11.00%12.00%13.00%14.00%15.00%16.00%17.00%18.00%19.00%20.00%21.00%22.00%23.00%24.00%25.00%26.00%27.00%28.00%

0.00%1.00%2.00%3.00%4.00%5.00%6.00%7.00%8.00%9.00%

10.00%11.00%12.00%13.00%14.00%15.00%16.00%17.00%18.00%19.00%20.00%21.00%22.00%23.00%24.00%25.00%26.00%27.00%28.00%

0.00%1.00%2.00%3.00%4.00%5.00%6.00%7.00%8.00%9.00%

10.00%11.00%12.00%13.00%14.00%15.00%16.00%17.00%18.00%19.00%20.00%21.00%22.00%23.00%24.00%25.00%26.00%27.00%28.00%

19

I dati per r = 0 evidenziano che nel modello di Watts e Strogatz risulta:

2

1][P

nvu =→

dove n2 è il numero totale di nodi della matrice ■

20

Questo modello ha una semplice interpretazione “geografica”: si può immaginare che i membri di

una rete sociale vivano su di una “griglia” e conoscano i loro vicini (in tutte le direzioni) che

risiedono ad una breve distanza da loro; ma, inoltre, essi hanno un certo numero di conoscenti che

sono distribuiti in modo più ampio sulla griglia ed ad una distanza maggiore.

Se si fissano p e q otteniamo una famiglia di modelli a reti definita da un unico parametro r. Quando

r = 0, abbiamo una distribuzione uniforme dei contatti a lungo raggio, che è la distribuzione usata

nel modello di rete sociale base di Watts e Strogatz – dove i contatti a lungo raggio sono scelti

indipendentemente dalla loro posizione sulla griglia. Al crescere di r, i contatti a lungo raggio di un

nodo diventano sempre più raggruppati nelle relative vicinanze sulla griglia. Quindi, la r serve da

parametro strutturale di base che misura quanto sia ampiamente “interconnessa” la società dei nodi

sottostante al modello.

La componente algoritmica del modello di Kleinberg si basa sull’esperimento di Milgram.

Consideriamo due nodi arbitrari della rete, diciamo s e t; il nostro obiettivo è quello di riuscire a

trasmettere un messaggio da s a t con il minor numero di passi possibile. Si ha la seguente

definizione di algoritmo decentralizzato:

Definizione: Algoritmo decentralizzato (Decentralized Algorithms)

Per algoritmo decentralizzato, intendiamo un meccanismo mediante il quale un

messaggio viene scambiato in modo sequenziale dal possessore attuale del messaggio

ad uno dei suoi contatti (locali o a lungo raggio), usando solo informazioni locali.

In particolare, il possessore u del messaggio ad un dato istante, è a conoscenza solo:

i) dell’insieme dei contatti locali fra tutti i nodi (cioè della struttura della griglia sottostante al

modello);

ii) della posizione, sul reticolo, del destinatario t del messaggio;

iii) delle posizioni e dei contatti a lungo raggio di tutti i nodi che sono venuti in possesso del

messaggio.

Fondamentalmente, u non ha alcuna conoscenza dei contatti a lungo raggio dei nodi che non hanno

ancora posseduto il messaggio. Con questa assunzione, u deve scegliere, con un qualche criterio,

uno dei suoi contatti v, ed inviargli il messaggio.

A questo punto si può dare la definizione di quella che costituisce una prima figura di merito

dell’analisi di Kleinberg:

21

Definizione: tempo previsto di consegna (expected delivery time)

Il tempo previsto di consegna, di un algoritmo decentralizzato, è il numero atteso di

passi, generato in accordo con una distribuzione r-potenziale inversa, necessari

all’algoritmo per consegnare il messaggio attraverso una rete, da una sorgente ad una

destinazione scelte a caso in modo uniforme da un insieme di nodi.

Sicuramente, costringere l’algoritmo ad utilizzare solo le informazioni locali è una caratteristica

cruciale del modello di Kleinberg; infatti, se si avesse a disposizione l’informazione globale dei

contatti locali ed a lungo raggio di tutti i nodi della rete, la catena minima tra due nodi della rete

stessa potrebbe essere calcolata in modo banale con una ricerca breadth-first1.

Si potrebbe pensare che l’assunzione (iii) vista sopra, dia all’algoritmo decentralizzato troppa

potenza in termini di informazione sulla struttura della rete. Tuttavia, questa assunzione serve solo a

rinforzare il risultato del modello di Kleinberg, infatti: il lower bound varrà anche per algoritmi a

cui viene data questa conoscenza, mentre l’upper bound farà uso di algoritmi decentralizzati che

richiedono solo le assunzioni (i) e (ii).

Vediamo ora i risultati principali del lavoro di Kleinberg, risultati relativi alle modalità con cui la

struttura della rete influisce sull’abilità di un algoritmo decentralizzato di costruire cammini brevi

sulla rete.

Quando r = 0 – si ha una distribuzione uniforme dei contatti a lungo raggio – possono essere

utilizzati i risultati standard della teoria dei grafi, per mostrare che devono esistere, con un’alta

probabilità, dei cammini tra ogni coppia di nodi la cui lunghezza è limitata da una polinomiale di

ordine Θ(log n), che è esponenzialmente più piccola del numero totale dei nodi. Tuttavia, non

esiste alcun modo per un algoritmo decentralizzato di riuscire a trovare queste “catene” brevi.

Teorema 1: Esiste una costante α0 , dipendente da p e da q ma indipendente da n, tale che, quando

r=0, l’expected delivery time di un algoritmo decentralizzato, è almeno α0n2/3. (Ovvero

esponenziale nella lunghezza del cammino minimo atteso.)

1 Breadth-first: Nella teoria dei grafi la ricerca breadth-first (BFS) identifica un algoritmo di ricerca che, iniziando dal nodo radice, esplora tutti i nodi confinanti. Dopodiché, per ognuno di questi nodi, l’algoritmo esplora tutti i nodi inesplorati confinanti, e così via, finché non trova il suo obbiettivo. BFS è un metodo di ricerca uniforme ed esaustivo con lo scopo di espandere ed esaminare tutti i nodi di un grafo in modo sistematico in cerca della soluzione.

22

Al crescere di r un algoritmo decentralizzato può trarre molto vantaggio dalla “topologia” dei

contatti a lungo raggio; ma allo stesso tempo, i contatti a lungo raggio diventano meno utili quando

si dovrà spostare il messaggio su lunghe distanze. Esiste un valore della r per il quale questa

tendenza può essere sfruttata algoritmicamente; questo valore è r = 2, che corrispondente alla

distribuzione quadratica inversa.

Teorema 2: Esistono un algoritmo decentralizzato A ed una costante α2 ,indipendente da n, tale

che quando r=2 e p=q=1, l’expected delivery time di A è al massimo α2(log n)2.

Questi due teoremi riflettono una conseguenza fondamentale del modello di Kleinberg. Quando i

contatti a lungo raggio sono formati in modo indipendente dalle geometria della griglia sottostante,

si può dimostrare che esistono catene corte di intermediari ma che i nodi, operando solo ad un

livello “locale”, non saranno in grado di trovarle. Quando, invece, i contatti a lungo raggio vengono

generati da un processo che rifletta in qualche modo la geometria della griglia, le catene brevi di

intermediari continueranno ad esistere e, questa volta i nodi, con la sola conoscenza locale dei

collegamenti, saranno in grado di trovarle.

L’algoritmo decentralizzato A da cui si ottiene il limite del teorema 2, si basa sulla seguente

semplice regola1: ad ogni passo, il possessore attuale u del messaggio sceglie un contatto che sia il

più “vicino possibile” (in termini di distanza reticolare) al destinatario t e gli invia il messaggio.

Sfruttando questa semplice regola, l’algoritmo A usa molte meno informazioni di quante ne siano

previste dal modello generale di Kleinberg: in particolare il nodo u, che detiene attualmente il

messaggio, non ha alcuna necessità di conoscere l’insieme dei nodi precedenti attraverso i quali è

transitato il messaggio da consegnare.

Definizione: Fase dell’algoritmo decentralizzato

Per poter analizzare l’esecuzione di un algoritmo A diciamo che esso è nella fase j se la

distanza reticolare, dal possessore attuale u del messaggio al destinatario t, è compresa

tra 2j e 2j+1, cioè 2j < d(u,t) ≤ 2j+1.

1 Questa regola è nota anche come greedy algorithm o greedy routing.

23

Si dimostrerà che nella fase j il tempo atteso, prima che il possessore attuale abbia un contatto a

lungo raggio con una distanza reticolare inferiore a 2j passi da t, è limitato proporzionalmente dal

log n; a questo punto la fase j si avvierà alla fine. Poiché ci sono al massimo 1 + log n fasi, ne segue

un limite proporzionale a (log n)2. Questa analisi conferma l’intuizione di Kleinberg e anche la

descrizione di Milgram relativa a come, nella vita reale, vengono create le catene brevi di

intermediari: “Il movimento geografico del messaggio da Nebraska al Massachusetts è

impressionante. C’è un progressivo avvicinamento alla zona contenente il destinatario man mano

che ogni nuova persona viene aggiunta alla catena” [13].

Fondamentalmente, l’impossibilità del risultato del Teorema 1, è basato sul fatto che la

distribuzione uniforme impedisce all’algoritmo decentralizzato di usare gli “indizi” forniti dalla

geometria della rete. In altre parole, consideriamo l’insieme U di tutti i nodi che abbiano una

distanza reticolare inferiore a n2/3 dal destinatario t del messaggio ( 34

32

32

nnnU =⋅= ). Supponiamo

che la sorgente s del messaggio sia posizionata al di fuori di U. Se il messaggio non è mai passato

da un nodo che costituisce un contatto a lungo raggio di un membro di U, il numero di passi

necessari per raggiungere t dovrà essere almeno proporzionale a n2/3. Ma la probabilità che qualsiasi

possessore attuale del messaggio abbia un contatto a lungo raggio in U è n-2/3

( 32

34

32

2][ −− ==

⋅=∈→= n

n

n

nn

UUvuPn ), così il numero atteso di passi (

][

1

UvuP ∈→) prima che

venga trovato un contatto a lungo raggio tra i membri di U deve essere almeno proporzionale anche

a n2/3 ( 32

32

1

][

1n

nUvuP==

∈→ − ).

In modo più generale, possiamo mostrare un teorema che rappresenta una più forte caratterizzazione

per questa famiglia di modelli: r = 2 è il solo valore per il quale esiste un algoritmo decentralizzato

capace di produrre catene la cui lunghezza è una polinomiale di ordine log n:

Teorema 3:

a) Sia 0 ≤ r < 2. Esiste una costante αr , dipendente da p, q, r, ma indipendente da n, tale che il

tempo atteso di consegna di un algoritmo decentralizzato sia almeno αrn(2-r)/3.

b) Sia r > 2. Esiste una costante αr ,dipendente da p, q, r, ma indipendente da n, tale che il

tempo atteso di consegna di un algoritmo decentralizzato sia almeno αrn(r-2)/(r-1).

24

Figura 4.2: Il lower bound implicato dal Teorema 3. Sull'asse x ci sono i valori di r ; sull'asse y c'è il risultante esponente su n.

La dimostrazione del Teorema 3a è analoga a quella del Teorema 1. Mentre la dimostrazione del

Teorema 3b ci svela un “doppio” ostacolo per gli algoritmi decentralizzati: per valori molto grandi

di r occorrerà un “tempo significativo” prima che il messaggio raggiunga un nodo con un contatto a

lungo raggio che sia molto distante (in termini di distanza reticolare); questo, limiterà la “velocità”

alla quale un messaggio riuscirà a viaggiare da una sorgente s ad una destinazione t del reticolo.

Sebbene Kleinberg abbia focalizzato il suo studio ai reticoli bidimensionali, la sua analisi può

essere estesa a modelli più generali. I suoi risultati saranno estendibili anche ai reticoli

k-dimensionali – per un qualche valore costante di k – così come a grafi meno strutturati ma con le

stesse proprietà di scaling. In particolare, nel caso k-dimensionale, un algoritmo decentralizzato

potrà costruire cammini di lunghezza polinomiale dell’ordine del log n se e solo se risulterà r = k.

Quindi nel caso in esame (modello bidimensionale k = 2) l’algoritmo decentralizzato troverà

cammini dell’O(log n) per r = 2; mentre in modelli tridimensionale (k = 3) l’algoritmo troverà

cammini dell’O(log n) per r = 3.

Questi risultati suggeriscono una proprietà fondamentale delle reti, distinta dal diametro, che aiuta a

spiegare il successo degli esperimenti sul fenomeno del piccolo mondo. Si potrebbe pensare a

questa proprietà come al “tasso di trasmissione” di una certa classe di reti.

Definizione: Tasso di trasmissione di una classe di reti

Il tasso di trasmissione di un algoritmo decentralizzato, rispetto ad una certa classe di

reti, è il tempo di consegna minimo atteso, che questo algoritmo impiegherà per far

giungere un messaggio dalla sorgente s alla destinazione t, operando su una qualsiasi

rete casuale della classe stessa.

25

Così vedremo che minimizzare il tasso di trasmissione di una rete non è necessariamente lo stesso

che minimizzare il suo diametro. Questo fatto potrebbe risultare poco intuitivo, ma di fatto

formalizza una nozione sollevata all’inizio: oltre che avere cammini brevi, una rete dovrebbe

contenere delle informazioni strutturali latenti che possano essere usate per guidare un messaggio

verso il destinatario finale. La dipendenza delle connessioni a lungo raggio dalla geometria del

reticolo, ci sta fornendo proprio queste informazioni implicite.

La dimostrazione dei teoremi ci rivelerà una proprietà generale e strutturale del modello, la quale

implicherà che l’esponente ottimale per i reticoli bidimensionali è proprio r = 2: c’è un unico

esponente per il quale i contatti a lungo raggio di un nodo sono quasi uniformemente distribuiti su

tutte le “scale di distanza”. Specificatamente, dato un qualsiasi nodo u, possiamo dividere i restanti

nodi del reticolo negli insiemi A0, A1, A2, … , Alog n , dove Aj contiene tutti i nodi la cui distanza

reticolare da u si trova tra 2j e 2j+1. Questi insiemi corrispondono a differenti livelli di “risoluzione”

man mano che ci allontaniamo da u; tutti i nodi di ogni Aj sono approssimativamente alla stessa

distanza (con un fattore di 2) da u. Per r = 2, ogni contatto a lungo raggio di u è quasi ugualmente

probabile che appartenga ad uno qualsiasi degli insiemi Aj ; quando r < 2, c’è una maggiore

polarizzazione dei contatti a lungo raggio verso gli insiemi Aj che sono a distanze maggiori da u;

quando in fine r > 2, si nota una maggiore polarizzazione dei contatti a lungo raggio verso quegli

insiemi Aj che sono maggiormente vicini a u.

26

5 Limite superiore per la distribuzione quadratica inversa

Vediamo ora la dimostrazione dei teoremi visti nel capitolo precedente. Quando si analizza un

algoritmo decentralizzato, si può adottare la seguente formulazione equivalente per il modello di

Kleinberg, che rende la dimostrazione dei teoremi più agevole. Anche se il modello di Kleinberg

prevede che tutti i contatti a lungo raggio vengano generati inizialmente in modo casuale, si può

sfruttare il principio delle decisioni differite1 [14], ed assumere che i contatti a lungo raggio di un

nodo v siano generati solo quando un messaggio raggiunge per la prima volta v. Dato che un

algoritmo decentralizzato non viene a conoscenza dei contatti a lungo raggio di v fino a quando un

messaggio non raggiunge v, le due formulazioni sono equivalenti dal punto di vista dell’analisi.

In seguito, con log n si intende il logaritmo in base 2 di n, mentre con ln n si intende il logaritmo

naturale (base e) di n.

Teorema 2: Esiste un algoritmo decentralizzato A ed una costante α2 ,indipendente da n, tale che

quando r=2 e p=q=1, l’expected delivery time di A è al massimo α2(log n)2.

Dimostrazione: Dato che p = q = 1, abbiamo una rete nella quale ogni nodo u è connesso con i suoi

quattro vicini più prossimi del reticolo (due o tre vicini nel caso di nodi sul bordo), e che ha un solo

contatto a lungo raggio v.

La probabilità che u scelga v come suo contatto a lungo raggio, è data da:

∑≠

−

−

=→

uv

vud

vudvu

2

2

),(),(

]Pr[

risulta:

)6ln(4)22ln(444)(4)])(4[(),(22

1

122

1

222

1

22 nnjjjjjvudn

j

n

j

n

juv

≤−+≤==≤ ∑∑∑∑−

=

−−

=

−−

=

−

≠

−

dove nella prima maggiorazione 4j è esattamente il numero di nodi che sono a distanza j da u, j-2 è

la distanza alla -2 e dunque ))(4( 2−jj è esattamente d(u,v)-2; nella penultima maggiorazione si è

usato: [ ] ( )22ln122ln1ln22lnln1 22

1

22

1

22

1

1 −+≤−=−−=== −−− −∫∫ nnnj

jj

nnn; mentre l’ultima

maggiorazione risulta vera da un certo n in poi.

1 Principle of Deferred Decisions: Un meccanismo comune per l’analisi di algoritmi randomici. Per maggiori dettagli si veda [14].

27

Quindi la probabilità che u scelga v come contatto a lungo raggio è almeno:

[ ] 122

2

2

2

),()6ln(4),()6ln(4

1

)6ln(4

),(

),(

),(]Pr[

−−

≠

−

−

==≥=→∑

vudnvudnn

vud

vud

vudvu

uv

L’Algoritmo decentralizzato A è definito come segue: ad ogni passo, il possessore attuale del

messaggio u sceglie un contatto che sia il più vicino possibile al destinatario t, dove per “vicino” si

intende nel senso della distanza reticolare. Per ogni j > 0 diciamo che l’esecuzione di A è nella fase j

quando la distanza reticolare del nodo corrente u dal destinatario t è: 2j < d(u,t) ≤ 2j+1. Diciamo che

A è nella fase 0 quando la distanza reticolare del nodo corrente u dal destinatario t è: d(u,t) ≤ 2.

Quindi, il valore iniziale massimo che j può assumere è j ≤ log n. Ora, affinché la distanza del

messaggio dall’obiettivo sia strettamente decrescente ad ogni passo, ogni nodo che diventa il

possessore attuale del messaggio non deve aver già posseduto il messaggio in precedenza; quindi,

dobbiamo assumere che proprio in questo momento venga generato dal possessore del messaggio

un contatto a lungo raggio.

Supponiamo di essere nella fase j, log(log n) ≤ j < log n, e che il possessore attuale del messaggio

sia il nodo u. Qual è la probabilità che la fase j abbia termine durante questo passo dell’algoritmo?

Affinché ciò avvenga è necessario che il messaggio sia entrato nell’insieme Bj = {u | d(u,t)<2j} dei

nodi la cui distanza reticolare è entro 2j da t. Ci sono almeno:

( ) 12222

1

2221

221

12221

11 −

=

>++=++=+= ∑ jjjjj

ij

j

iB

nodi in Bj , ognuno ad una distanza reticolare inferiore a 2j+1 + 2j < 2j+1 + 2j+1 = 2j+2 da u, e quindi

∀ v∈Bj la sua probabilità di diventare un contatto a lungo raggio di u è pari almeno a:

( ) [ ] 1424222

2)6ln(42)6ln(4

1

2)6ln(4

1]Pr[

−+++

==≥∈→ jjjj n

nnBvu .

Se qualcuno di questi nodi è il contatto a lungo raggio di u, esso sarà quindi il contatto di u più

prossimo a t; quindi il messaggio entrerà nell’insieme dei nodi Bj con probabilità pari almeno a:

)6ln(1281

)6ln(21

)6ln(1

2221

)6ln(1

22

222

)6ln(1

222

2)6ln(42

]Pr[]in entriPr[

7

422

2

42

1

422

12

42

12

nn

nn

nnBBvuB

j

j

j

j

j

j

jjj

==

===

==≥⋅∈→=−

+

−

+

−

M

28

Sia Xj definito come il numero di passi spesi durante la fase j, con log(log n) ≤ j < log n. Abbiamo

che:

)6ln(128)6ln(128

11]Pr[

1

1

1

nn

iXEXi

i

ijj =

−≤≥= ∑∑∞

=

−∞

=

Un insieme analogo di limiti mostrerà che EXj ≤ 128ln(6n) pure per j = log n. Ed infine, se

0 ≤ j ≤ log(log n), allora la disuguaglianza EXj ≤ 128ln(6n) continuerà a valere ugualmente, per la

semplice ragione che l’algoritmo può spendere al massimo log n passi durante la fase j anche se

tutti i nodi passano il messaggio ad un contatto locale.

Ora, se X denota il numero totale di passi spesi dall’algoritmo, abbiamo:

∑=

=n

jjXX

log

0

e così per linearità delle aspettative avremo che:

( )( ) ( )22

log

0

log

0

log

0

log)6ln(128log1)6ln(128 nnnnEXXEEXn

j

n

jj

n

jj α≤+≤≤=

= ∑∑∑

===

dove l’ultima maggiorazione segue effettuando un cambiamento di base per il logaritmo

(e

nn

2

2

log6log

)6ln( = ) e per una opportuna scelta di α2 ■CVD

29

6 Limiti inferiori per altre distribuzioni

Vediamo ora la dimostrazione del Teorema 3 e del Teorema 1; la dimostrazione di quest’ultimo è

implicata dal Teorema 3a ponendo r = 0. Anche in questo caso la dimostrazione data da Kleinberg

farà uso del Principio di Decisione Differita [14] e, come nella dimostrazione precedente, verrà

usata una versione leggermente modificata del suo modello di algoritmo decentralizzato.

Un algoritmo all’inizio possiede la conoscenza della struttura della griglia, di tutti i contatti locali,

della posizione di s e della posizione di t. Ad un generico passo i esisterà un insieme Si di nodi che

hanno già “toccato” il messaggio M. Di conseguenza l’algoritmo decentralizzato possiede anche la

conoscenza di tutti i contatti a lungo raggio di tutti i nodi in Si (seguendo il principio di decisione

differita i contatti a lungo raggio degli altri nodi, non compresi in Si , verranno costruiti a “run-time”

quando saranno raggiunti dal messaggio M). Basandosi su queste informazioni, l’algoritmo

sceglierà un contatto v di un qualche nodo in Si che non abbia ancora ricevuto il messaggio (non c’è

bisogno che v sia un contatto del possessore “attuale” del messaggio), e poi invierà il messaggio

proprio a v. Ora, l’insieme dei nodi “toccati” dal messaggio sarà Si+1, che contiene appunto un

elemento in più rispetto a Si, e l’algoritmo itererà fino a che il messaggio non raggiunge t. Questa

estensione fornisce un modello quasi uguale a quello iniziale eccetto per il fatto che, con questa

variante, non prendiamo in considerazione gli step nei quali l’algoritmo “torna sui suoi passi”

inviando il messaggio a qualche nodo che lo ha già posseduto in precedenza.

Kleinberg fa anche una ulteriore estensione “tecnica” al suo modello. L’algoritmo funzionerà per

una sequenza infinita di passi; inizialmente esso si comporterà come descritto sopra, ma quando il

messaggio avrà raggiunto il destinatario t, esso rimarrà in t per tutti i passi successivi. Questo

affinché considerando il generico passo i-esimo dell’algoritmo non dobbiamo preoccuparci della

possibilità che l’algoritmo abbia già terminato la sua esecuzione.

Teorema 3:

a) Sia 0 ≤ r < 2. Esiste una costante αr , dipendente da p, q, r, ma indipendente da n, tale che il

tempo atteso di consegna di un algoritmo decentralizzato sia almeno αrn(2-r)/3.

b) Sia r > 2. Esiste una costante αr ,dipendente da p, q, r, ma indipendente da n, tale che il

tempo atteso di consegna di un algoritmo decentralizzato sia almeno αrn(r-2)/(r-1).

30

Dimostrazione (a): Consideriamo un generico algoritmo decentralizzato del tipo descritto sopra, e

consideriamo il numero atteso di passi richiesti affinché il messaggio compia il viaggio da s a t, con

i nodi s e t generati in modo casuale uniforme sulla griglia.

Dato che abbiamo la libertà di sceglierci la costante αr, per semplicità potremmo anche assumere

che la n sia almeno grande quanto una fissata costante assoluta n0. La probabilità che un nodo u

scelga v come suo i-esimo contatto a lungo raggio al di fuori di q è:

∑≠

−

−

=→

uv

r

r

vud

vudvu

),(),(

]Pr[

dovendo minorare la costante di normalizzazione, e dato che per 1 ≤ j ≤ n/2 il numero di nodi a

distanza j è dato da j+1 > j :

si può scrivere:

( ) rr

rnr

n

j

rn

j

rn

j

r

uv

r nr

nrdxxjjjjjvud −

−

−−−

=

−

=

−

=

−

≠

− ⋅−

≥

−

−≥≥=≥+≥ ∫∑∑∑∑ 23

21

2/

1

12/

1

12/

1

2/

1 2)2(1

12

2))(())(1(),(

dove l’ultima minorazione, segue se imponiamo n2-r ≥ 23-r.

Sia definito:

32 r−=δ con 0 ≤ r < 2

sia inoltre U l’insieme di tutti i nodi la cui distanza reticolare da t è minore di δpn . Notiamo che

risulterà:

δδδδδδδ

2222

11

42212

)1(414141 nppnnp

pnpnjjU

pn

j

pn

j

≤++=++=+=+≤ ∑∑==

se assumiamo che n sia grande abbastanza affinché 2≥δpn :

31

δδ

δδ

δ

δ

δ

δδ

δδ

δδ

δδδ

δδδ

pnpn

pnpn

pn

pn

nppnnp

pnnppnnp

pnnpnpnppnnp

21

1

21

22

22

122221221

24214221

22

22

22

22

2222

2222

+≥

+≥

+≥≥+−−≤−

−≤−+≤++

essendo 0 ≤ r < 2 risulta 12

1 ≤δpn quindi si può assumere 2

2

11 ≥+≥ δ

δ

pnpn come richiesto.

Definiamo:

( ) 1282−−= qprλ con 0 ≤ r < 2.

Siano definiti i seguenti “eventi”:

− 'ε : in meno di λnδ passi, il messaggio raggiunge un nodo, diverso da t, con un contatto a

lungo raggio in U .

− iε' : al passo i, il messaggio raggiunge un nodo, diverso da t, con un contatto a lungo raggio

in U.

Risulta:

Uδλni

iεε≤

= ''

Ora il nodo raggiunto al passo i possiede q contatti a lungo raggio che vengono generati in modo

casuale quando esso viene incontrato; così avremo:

r

r

r

r

r

r

rr

vu

r

r

i

n

nqpr

n

nqpr

n

npqr

nr

Uq

vud

vudUqvuUqε

−

−

−

−

−

−

−−

≠

−

−

−=

⋅⋅−=⋅−≤

⋅−

≤

⋅⋅=→⋅⋅=∑

2

225

2

2232

2

223

23

2)2(

22)2(42)2(

2)2(1

),(),(

]Pr[]'Pr[

δ

δδ

dove la prima maggiorazione è dovuta al fatto che d(u,v)≥1 e quindi d(u,v)-r per 0 ≤ r < 2 risulta

essere d(u,v)-r≤1, e la seconda a δ224 npU ≤ .

32

Dato che la probabilità dell’unione di eventi è limitata dalla somma delle loro probabilità, risulta:

41

241

22

2)2(

2)2(

2)2(]'Pr[]'Pr[

3325

2

325

2

225

≤−=−=−=

−≤

−≤≤

−

−

−

−

−

≤∑

rrqpr

n

nqpr

n

nqprn

r

r

r

r

r

niiεε

λ

λ

λ

δ

δδ

λ δ

dove l’ultima maggiorazione segue ricordandoci che 0 ≤ r < 2.

Definiamo altri due ulteriori eventi:

− F : la sorgente s e la destinazione t sono separati da una distanza reticolare di almeno n/4.

− ε : il messaggio raggiunge t entro λnδ passi.

Mostriamo che 21]Pr[ ≥F , consideriamo una matrice con 6 x 6 = 36 nodi, risulta n/4 = 6/4 = 1,5 < 2:

Caso migliore Caso Medio Caso Peggiore

scegliendo s a caso, esisterà un’intorno di s che contiene i nodi la cui distanza reticolare è inferiore

o uguale a n/4 da s, e che quindi non soddisfano F. Nel caso peggiore, tutto l’intorno d(u,s) ≤ n/4,

sarà contenuto nella griglia, mentre nel caso migliore s si troverà in uno degli angoli.

Il numero di nodi a distanza minore o uguale di n/4 da s è dato da:

281

421

442

2)1(

4442

444/

1

4/

1

nnnnnnjj

nnn

j

n

j

+=

+=

+=

+== ∑∑==

quindi il numero di nodi che sono a distanza maggiore o uguale a n/4 saranno:

+−=−∑

= 284

22

4/

1

2 nnnjn

n

j

da cui si ricava che:

nnn

nn

n

nnn

n

jnn

j

21

87

21

81

121

8284

]Pr[ 2

22

2

4/

1

2

−=−−=

+−=

+−

=−

=∑

=F

e quindi

33

nn

n

n

nn

n

jn

j

21

812

1

8284

]Pr[2

2

2

4/

1 +=

+=

+

==∑

=F

In qualsiasi caso reale, risulterà n > 1, e quindi per n→∞ si avrà:

21

21

87

]Pr[ ≥−=n

F e l’uguaglianza si avrà per n = 4/3 > 1;

21

21

81

]Pr[ ≤+=n

F e l’uguaglianza si avrà per n = 4/3 > 1.

Da cui si ricava 43

41

21]Pr[ ' =+≤∨ εF (dato che 2

1]Pr[ ≥F implica 21]Pr[1]Pr[ ≤−= FF e

che 41]Pr[ ' ≤ε ) ed anche che 4

1]Pr[ ' ≥∧ εF (dato che 41

41

21 )(1]Pr[1]Pr[ '' =+−≥∨−=∧ εε FF ).

Indichiamo con X la variabile casuale uguale al numero di passi impiegati dal messaggio per

raggiungere t.

Vogliamo verificare che se l’evento F accade e l’evento 'ε non accade, allora l’evento ε non può

accadere.

Supponiamo per assurdo che ε accada. Poiché F accade: d(s,t) ≥ n/4 > pλnδ, per ogni cammino s→t

di al massimo λnδ passi (evento ε ), il messaggio dovrebbe essere passato almeno una volta da un

nodo ad un contatto a lungo raggio. Se questo è accaduto, allora il contatto a lungo raggio deve

essere in U (cioè 'ε accade). Ma questo contraddice la nostra ipotesi che 'ε non accada.

Perciò deve risultare 0]|Pr[ ' =∧ εε F , e quindi δλnXE ε ≥∧ ]|[ 'F .

Da cui si ricava:

3

2

41]Pr[]|[ ''

r

r nnXEEX εε−

=≥∧⋅∧≥ αλ δFF

ovvero la tesi (a) del Teorema 3, avendo sostituito i valori di λ, δ; e con 2102

1

4 qprr −== λα ■CVD

34

Dimostrazione (b): Sia r > 2, come sopra consideriamo un generico algoritmo decentralizzato, e

come sopra assumiamo che n sia più grande di una data costante assoluta n0. Scriviamo ε = r – 2.

Consideriamo un nodo u, e sia v un contatto a lungo raggio di u generato in modo casuale. La

costante di normalizzazione per la distribuzione r-potenziale inversa è almeno 1, e così per un dato

m, abbiamo:

εε −−−−

∞−

−

+=

−

−

+=

−

=−≤

≤

=

≤>

∫

∑

∑

mmr

dxx

j

jjmvud

r

m

r

n

mj

r

n

mj

r

121

1

22

1

1

22

1

)2(

4

))(4(]),(Pr[

Poniamo:

q8

)1,min('

11

1

ελ

εγ

εεβ

=

+=

+=

Prendiamo una n sufficientemente grande affinché nγ ≥ p.

Definiamo i seguenti due eventi:

− iε' : al passo i, il messaggio raggiunge un nodo u, diverso da t, con un contatto a lungo

raggio v che soddisfi la disuguaglianza d(u,v)> nγ.

− Uβλ ni

iεε'

''≤

= : il messaggio raggiunge un nodo u, diverso da t, con un contatto a lungo raggio

v, che soddisfi la disuguaglianza d(u,v)> nγ in meno di λ′nβ passi.

Abbiamo

411

1

'

'

'

]),(Pr[']'Pr[]'Pr[

≤=

⋅≤

>⋅⋅≤≤

−

−−

≤∑

ελ

ελ

λ

εγβ

γβ

λ β

q

nqn

nvudqnni

iεε

35

Quest’ultima maggiorazione ( 411' ≤−ελ q ) si potrebbe giustificare come segue:

se εε =)1,min( vuol dire che 1<ε quindi: 4

1

8

11

8' 1 <==−

εεελ qq

q ;

se 1)1,min( =ε vuol dire che 1≥ε quindi: 4

1

8

11

8

11

8

1' 1 <≤==−

εεελ q

qq .

Come per la parte (a) del teorema, definiamo gli eventi:

− F : la sorgente s e la destinazione t sono separati da una distanza reticolare di almeno n/4.

− ε : il messaggio raggiunge t entro λ′nβ passi.

Risulta 41]Pr[ ' ≥∧ εF .

Sia X la variabile casuale definita uguale al numero di passi necessari al messaggio per raggiungere

la destinazione t.

Si vuole verificare che se l’evento F accade e l’evento 'ε non accade, allora ε non può accadere.

Se 'ε non accade, allora il messaggio può spostarsi di una distanza reticolare di al più nγ in ognuno

dei suoi primi λ′nβ passi. Questo corrisponde ad una distanza reticolare totale di al più

λ′nβ nγ = λ′nβ+γ = λ′n < n/4,

in quanto:

<

<<==

4

1

8

141

81

88

)1,min('

q

qqq

εελ

e quindi il messaggio non raggiungerà la destinazione t dato che F accade.

Quindi βλ nXE ε ']|[ ' ≥∧F , e risulta:

)1(

)2(

41 ']Pr[]|[ '' −

−

=≥∧⋅∧≥ r

r

rnnXEEX εε αλ βFF

cioè la tesi (b) del Teorema 3, con αr = 1/4 λ′ ■CVD

36

7 Conclusioni

Altri lavori [15][3] hanno trattato il problema di trovare un efficiente algoritmo di routing che

funzionasse bene sfruttando solo informazioni locali. Anche se i risultati di Kleinberg sono

leggermente differenti da quelli ottenuti da questi altri studi, essi condividono comunque l’obiettivo

comune di riuscire ad identificare le proprietà qualitative di un modello a rete che rendano

“trattabile” il problema del routing con informazioni locali, arrivando a fornire un modello su cui

poter ragionare e testare questi schemi di routing.

Kleinberg ha deliberatamente finalizzato il suo studio alla creazione di un modello che fosse il più

chiaro e “pulito” possibile, ma lascia comunque intendere come dalle reti small-world si possano

derivare conclusioni più generali, ad esempio: che la correlazione fra la struttura locale ed i

collegamenti a lungo raggio può fornire indicazioni fondamentali per l'individuazione dei percorsi

attraverso la rete. Quando questa correlazione è vicina ad una certa soglia critica, la struttura dei

collegamenti a lungo raggio forma una specie di “gradiente” che consente agli individui di guidare

efficientemente il messaggio verso il bersaglio. Quando questa correlazione scende sotto questa

soglia critica e quindi la rete sociale diventa più omogenea, queste indicazioni tendono a sparire; al

limite, quando i contatti a lungo raggio sono generati in modo casuale uniforme, il modello di

Kleinberg descrive un mondo nel quale esistono ancora delle catene brevi, ma gli individui, inondati

dalla disposizione di questi collegamenti “disorientanti”, non sono più in grado di trovarle.

37

Riferimenti [1] L. Adamic, “The small world Web”, Proceedings of the European Conf. On Digital Libraries,

1999. [2] R. Albert, H. Jeong, A.-L. Barabasi “The diameter of the World Wide Web”, Nature 401, 130

(1999). [3] P. Berman, “On-Line searching and navigation”, On-Line Algorithms: The State of the Art, A.

Fiat and G. Woeginger, Eds. Springer, 1998. [4] B. Bollobás, “Random Graphs” (Academic Press, London, 1985). [5] B. Bollobás, F.R.K. Chung, “The diameter of a cycle plus a random matching”, SIAM J.

Discrete Math. 1, 328 (1988). [6] F.R.K. Chung, M.R. Garey, “Diameter bounds for altered graphs”, J. Graph Theory 8, 511

(1984). [7] J. Guare, “Six Degrees of Separation: A Play”, (Vintage Books, New York, 1990). [8] J. Hunter and R. Shotland, “Treating data collected by the small world method as a Markov

process”, Social Forces 52, 321 (1974). [9] J. Kaiser, Ed., “It’s a small Web after all”, Science 285, 1815 (1999). [10] P. Killworth and H. Bernard, “Reverse small world experiment”, Social Networks 1, 159

(1978). [11] M. Kochen, Ed., “The Small World” (Abex, Norwood, 1989). [12] C. Korte and S. Milgram, “Acquaintance networks between racial groups: Application of the

small world method”, J. Personality and Social Psych., 15, 101 (1978). [13] S. Milgram, “The small world problem”, Psychology Today 1, 61 (1967). [14] R. Motwani and P. Raghavan, “Randomized Algorithms” (Cambridge University Press,

Cambridge, 1995). [15] D. Peleg, E. Upfal, “A trade-off between size and efficiency for routing tables”, Journal of

the ACM 36 (1989). [16] I. De Sola Pool and M. Kochen, “Contacts and influence”, Social Networks 1, 5 (1978). [17] H. Kautz, B. Selman, M. Shah, “Referral Web: Combining Social Networks and

Collaborative Filtering”, Communications of the ACM, 30, 3 (March 1997). [18] J. Travers and S. Milgram, “An experimental study of the small world problem”, Sociometry

32, 425 (1969). [19] D. Watts and S. Strogatz, “Collective dynamics of small-world networks”, Nature 393, 440

(1998). [20] H. White, “Search parameters for the small world problem”, Social Forces 49, 259 (1970). [21] Jon M. Kleinberg, “The Small World Phenomenon: An Algorithmic Perspective”, Cornell

Computer Science Technical Report 99-1776 (October 1999). [22] Jon M. Kleinberg, “Navigation in a small world – It is easier to find short chains between

point in some networks than others.”, brief communications, Nature 845, 406 (2000). [23] Manfred Kochen, editor. “The Small World: A Volume of Recent Research Advances

Commemorating Ithiel de Sola Pool, Stanley Milgram, Theodore Newcomb.”, Abex, Norwood (NJ), 1989.

[24] David Liben-Nowell, “An Algorithmic Approach to Social Networks”, work in partial fulfillment of the requirements for degree of Doctor of Philosophy in Computer Science at MIT (June 2005).

[25] P. Erdıs e A. Rényi, “On random graphs”, Pubblicationes Mathematicae, 6:290-297 (1959). [26] P. Erdıs e A. Rényi, “On the evolution of random graphs”, Pubblications of the

Mathematical Institute of Hungarian Academy of Sciences, 5:17-61 (1960). [27] P. Erdıs e A. Rényi, “On the strength of connectedness of random graph”, Acta

Mathematica Scientia Hungary, 12:261-267 (1961).