Complex Networks and Decentralized Search Algorithms
(Jon Kleinberg)
Federico Barocci
Sistemi Complessi
Informatica Magistrale - University of Bologna
a.a. 2013-2014
Federico Barocci Complex Networks and Decentralized Search Algorithms
Alcune premesse
In una rete complessa i nodi tipicamente non possiedono conoscenza globale della rete.
Nelle reti Small World esistono cammini brevi tra due nodi.
Delivery time = numero di nodi attraversati per raggiungere il nodo destinatario.
“Sei gradi di separazione” (Milgram)
Alcune premesse
In una rete sociale di n persone esistono cammini relativamente brevi che uniscono qualsiasi coppia scelta casualmente.
Federico Barocci Complex Networks and Decentralized Search Algorithms
Definizione del problema
Ci domandiamo:
Esiste un algoritmo decentralizzato di ricerca con delivery time polilogaritmico in n?
Quali modelli di rete possiamo considerare per ottenere prestazioni ottimali con questi algoritmi?
Occorre:
Definire un modello
Parametrizzare la distribuzione dei contatti long-range
Stabilire per quali valori dei parametri si possono
raggiungere prestazioni efficienti in delivery time.
Definizione del problema
Ci domandiamo:
Esiste un algoritmo decentralizzato di ricerca con delivery time polilogaritmico in n?
Quali modelli di rete possiamo considerare per ottenere prestazioni ottimali con questi algoritmi?
Occorre:
Definire un modello
Parametrizzare la distribuzione dei contatti long-range Stabilire per quali valori dei parametri si possono raggiungere prestazioni efficienti in delivery time.
Federico Barocci Complex Networks and Decentralized Search Algorithms
Definizione del problema
Ci domandiamo:
Esiste un algoritmo decentralizzato di ricerca con delivery time polilogaritmico in n?
Quali modelli di rete possiamo considerare per ottenere prestazioni ottimali con questi algoritmi?
Occorre:
Definire un modello
Parametrizzare la distribuzione dei contatti long-range
Stabilire per quali valori dei parametri si possono
raggiungere prestazioni efficienti in delivery time.
Definizione del problema
Ci domandiamo:
Esiste un algoritmo decentralizzato di ricerca con delivery time polilogaritmico in n?
Quali modelli di rete possiamo considerare per ottenere prestazioni ottimali con questi algoritmi?
Occorre:
Definire un modello
Parametrizzare la distribuzione dei contatti long-range
Stabilire per quali valori dei parametri si possono raggiungere prestazioni efficienti in delivery time.
Federico Barocci Complex Networks and Decentralized Search Algorithms
Definizione del problema
Ci domandiamo:
Esiste un algoritmo decentralizzato di ricerca con delivery time polilogaritmico in n?
Quali modelli di rete possiamo considerare per ottenere prestazioni ottimali con questi algoritmi?
Occorre:
Definire un modello
Parametrizzare la distribuzione dei contatti long-range
Stabilire per quali valori dei parametri si possono
raggiungere prestazioni efficienti in delivery time.
Small World
Watts - Strogatz
Una rete Small World ` e una rete strutturata in cui per ogni coppia di nodi esiste un cammino relativamente breve, eventualmente con alcuni archi “casuali” che connettono porzioni della rete distanti tra loro.
Federico Barocci Complex Networks and Decentralized Search Algorithms
Small World
Bollob´ as - de la Vega
Dato un insieme di n nodi e fissata d ≥ 3 costante, si aggiungano archi tra coppie di nodi scelti casualmente in modo che ogni nodo possieda esattamente grado d .
Con alta probabilit` a per ogni coppia di nodi esiste un cammino di
lunghezza O(log n).
Small World
Bollob´ as - Chung
Dato un anello di n nodi, si costruisca un grafo aggiungendo un arco ad ogni coppia di nodi scelti casualmente.
Con alta probabilit` a per ogni coppia di nodi esiste un cammino di lunghezza O(log n).
Federico Barocci Complex Networks and Decentralized Search Algorithms
Analisi dei modelli di rete
Teorema
Nel modello di Watts - Strogatz si dimostra che per ogni algoritmo decentralizzato di ricerca la complessit` a in delivery time ` e Ω(n 2/3 ).
Estensione del modello
Invece di scegliere casualmente i contatti long-range, questi sono approssimativamente distribuiti in modo uniforme su larga scala.
Occorre definire una correlazione tra contatti long-range e disposizione geometrica dei nodi.
Occorre definire una probabilit` a di scelta dei nodi.
Analisi dei modelli di rete
Teorema
Nel modello di Watts - Strogatz si dimostra che per ogni algoritmo decentralizzato di ricerca la complessit` a in delivery time ` e Ω(n 2/3 ).
Estensione del modello
Invece di scegliere casualmente i contatti long-range, questi sono approssimativamente distribuiti in modo uniforme su larga scala.
Occorre definire una correlazione tra contatti long-range e disposizione geometrica dei nodi.
Occorre definire una probabilit` a di scelta dei nodi.
Federico Barocci Complex Networks and Decentralized Search Algorithms
Analisi dei modelli di rete
Teorema
Nel modello di Watts - Strogatz si dimostra che per ogni algoritmo decentralizzato di ricerca la complessit` a in delivery time ` e Ω(n 2/3 ).
Estensione del modello
Invece di scegliere casualmente i contatti long-range, questi sono approssimativamente distribuiti in modo uniforme su larga scala.
Occorre definire una correlazione tra contatti long-range e disposizione geometrica dei nodi.
Occorre definire una probabilit` a di scelta dei nodi.
Alcuni modelli
Consideriamo alcuni esempi di modelli:
Modello basato su griglia Modello basato su gerarchie Modello basato su insiemi
Federico Barocci Complex Networks and Decentralized Search Algorithms
Modello basato su griglia
Consideriamo una griglia di d dimensioni:
ρ(v , w ) = lunghezza cammino minimo tra i nodi v , w Aggiungiamo 1 connessione long-range ad ogni nodo Probabilit` a selezione nodo: ρ(v , w ) −α
Parametri ottimali
Modello basato su griglia
In una griglia quadrata (d = 2) con parametro α:
Se 0 ≤ α < 2 il delivery time ` e Ω(n
2−α3) Se α = 2 il delivery time ` e O(log 2 n) Se α > 2 il delivery time ` e Ω(n
α−2α−1)
Federico Barocci Complex Networks and Decentralized Search Algorithms
Modello basato su griglia
In una griglia quadrata (d = 2) con parametro α:
Se 0 ≤ α < 2 il delivery time ` e Ω(n
2−α3)
Se α = 2 il delivery time ` e O(log 2 n)
Se α > 2 il delivery time ` e Ω(n
α−2α−1)
Modello basato su gerarchie
Un esempio di modello gerarchico:
Federico Barocci Complex Networks and Decentralized Search Algorithms
Modello basato su gerarchie
Ipotizziamo un albero b-ario completo con n nodi foglia:
h(v , w ) = altezza antenato comune ai nodi foglia v , w Costruiamo un grafo considerando solamente i nodi foglia Ad ogni foglia si assegnano k archi orientati uscenti Probabilit` a selezione destinatario: b −β∗h(v ,w )
Parametri ottimali
β = 1 e out-degree k = c log 2 n, c costante sufficientemente
grande.
Modello basato su insiemi
Esempio di modello basato su insiemi:
Federico Barocci Complex Networks and Decentralized Search Algorithms
Modello basato su insiemi
Consideriamo un insieme composto da gruppi di nodi:
g (v , w ) = dimensione del pi` u piccolo gruppo contenente entrambi i nodi v , w
Ad ogni nodo aggiungiamo k archi Probabilit` a selezione nodo: g (v , w ) −γ Parametri ottimali
γ = 1 e out-degree k = c log 2 n, c costante sufficientemente
grande.
Descrizione algoritmo
Algoritmo Greedy
Ogni nodo invia il messaggio al vicino la cui distanza verso il destinatario ` e la pi` u piccola disponibile.
Federico Barocci Complex Networks and Decentralized Search Algorithms
Varianti con informazioni aggiuntive
Nei risultati precedenti si assume che i nodi non interagiscano per ottenere una visione pi` u ampia della rete.
Alcune varianti dell’algoritmo:
Consultazione anticipata
Vicini dei vicini
Consultazione anticipata
Prima di inoltrare il messaggio vengono consultati al pi` u O(log n) nodi vicini.
Il messaggio viene inoltrato al nodo con distanza inferiore rispetto al destinatario.
Nodi totali consultati: O(log 2 n)
Passi nel cammino costruito: O(log n(log log n) 2 )
Federico Barocci Complex Networks and Decentralized Search Algorithms
Vicini dei vicini
Ogni nodo consulta i propri vicini per ricevere un elenco dei loro rispettivi vicini.
Il messaggio viene inviato al nodo con distanza inferiore rispetto al destinatario.
Passi nel cammino costruito: O(log n/ log log n)
Conclusioni
Una rete Small World non garantisce automaticamente un delivery time polilogaritmico.
In generale non basta considerare l’algoritmo, le prestazioni possono variare a seconda del modello considerato e dal valore dei relativi parametri.
Esistono diverse varianti che possono essere considerate e presentano prestazioni differenti.
Federico Barocci Complex Networks and Decentralized Search Algorithms
