AR - 15 - Ricerca Decentralizzata I

Nasce dunque il problema di rispondere alla seguente domanda: perché ci sono tante shortest paths nelle reti sociali?

Una prima risposta potrebbe considerare il fatto che l'elevato numero di relazioni di amicizia, o anche solo di conoscenza, che ciascun individuo ha porta a diminuire il diametro della rete, in quanto è possibile raggiungere tantissimi nodi passando da una amicizia ad un'altra. Ad esempio se supponiamo che ciascuna persona conosce altre \(100\) persone, si potrebbe supporre di avere una crescita esponenziale nel numero di persone raggiungibili come descritta dalla seguente figura

Notiamo però che la crescita esponenziale appena descritta non tiene in considerazione che nelle reti sociali l'omofilia e la chiusura triadica giocano un ruolo fondamentale nella creazione delle relazioni. In altre parole, molti dei nostri amici e conoscenti si potrebbero conoscere tra loro, andando così a diminuire il numero diverso di amici e conoscenti che possiamo raggiungere. Una figura più realistica è quindi la seguente

Questo significa che nelle reti sociali la chiusura triadica, discussa in una precedente lezione, tende a limitare il numero di persone che possono essere raggiunte seguendo i cammini brevi della rete.

Un altro aspetto fondamentale emerso dai risultati ottenuti da Milgram è stato il fatto che gli individui sono stati collettivamente in grado di trovare dei cammini brevi per arrivare al target.

Notiamo che la ricerca effettuata dai partecipanti dell'esperimento non può essere considerata né una ricerca centralizzata e né una ricerca distribuita. Ogni individuo infatti effettuava le proprie scelte personali, senza coordinarsi in modo consapevole con gli altri individui. Questo tipo di ricerca prende il nome di ricerca decentralizzata.

Nasce quindi il seguente quesito: perché le reti sociali sono strutturate in modo da rendere questo tipo di ricerca decentralizzata così efficiente?

Il primo modello che analizziamo è il modello di Watts-Strogatz. L'idea alla base di questo modello è semplice: si parte da un grafo a griglia con le diagonali (unit-disk graph), e lo si modifica andando ad aggiungere degli archi random scelti in modo uniforme.

Notiamo come la struttura base del grafo a griglia con l'aggiunta delle diagonali permette di catturare la parte omofila di una rete sociale

La griglia di base però non ci permette di avere tante shortest paths. Per aumentare il numero di shortest paths quindi si aggiungono degli archi random nel seguente modo: Si fissa un valore del parametro \(k \in \mathbb{N}\) e si collega ogni nodo della griglia con altri \(k\) nodi scelti in modo uniforme. Notiamo che questi archi random aggiunti hanno la funzione di weak-ties, ovvero il loro obiettivo è quello di portare nuova informazioni nella rete, andando così ad aumentare il numero di shortest paths. Troviamo quindi la seguente figura

È possibile dimostrare che il grafo random costruito in questo modo contiene tante shortest paths. Intuitivamente questo segue dal fatto che, se abbiamo costruito la rete come descritto, e se abbiamo tanti nodi, allora è molto improbabile che gli archi aggiunti come weak ties collegano nodi tra loro vicini. Dunque gli archi aggiunti permettono di ricoprire l'intera rete.

Osservazione: In realtà è possibile dimostrare un risultato più forte: il numero di shortest paths è alto anche se facciamo partire un solo arco in modo uniforme da ogni cluster di \(k\) nodi. Dunque ci basta una quantità di randomness molto limitata per ottenere gli stessi risultati.

---

Anche se il modello di Watts-Strogatz appena descritto è in grado di catturare bene il fatto che nelle reti sociali ci sono tanti shortest paths, gli archi aggiunti risultano essere troppo random, in quanto i nodi vengono collegati senza far riferimento a nessun concetto di "distanza" o gradiente. Come conseguenza di ciò, nel modello di Watts-Strogatz non è possibile risolvere in modo efficiente il problema della ricerca decentralizzata discusso in precedenza.

Andiamo adesso a descrivere un modello che contiene tante shortest paths e che ci permette di risolvere in modo efficiente il problema della ricerca decentralizzata.

Seguendo l'idea di Watts-Strogtaz, iniziamo con una griglia in grado di catturare l'omofilia delle reti sociali. Supponiamo inoltre che la griglia sia poggiata su una sfera, per ottenere la massima simmetria. Seguendo sempre il modello Watts-Strogtaz, introduciamo alcuni archi random che serviranno da weak ties. Questa volta però gli archi vengono introdotti utilizzando una nozione di distanza. In particolare, ogni nodo ha un solo weak tie descritto dalla seguente distribuzione di probabilità

\[P[(u, v) \in E] = \frac{1}{z_u} \cdot \frac{1}{d(u, v)^q}\]

dove,

• \(z_u\) è una costante di normalizzazione.

• \(d(u, v)\) è la distanza tra \(u\) e \(v\) nella griglia iniziale.

• \(q\) è un parametro del modello chiamato esponente di clustering.

---

Notiamo che la costante \(z_u\) è necessaria al fine di avere una distribuzione di probabilità. Per trovare il valore di \(z_u\) imponiamo quindi la seguente equivalenza

\[\begin{split} &\;\;\;\;\;\;\;\;\;\;\; \sum\limits_{v \in V - \{u\}} P[(u, v) \in E] = 1 \\ &\iff \frac{1}{z_u} \cdot \sum\limits_{v \in V - \{u\}} \frac{1}{d(u, v)^q} = 1 \\ &\iff z_u = \sum\limits_{v \in V - \{u\}} \frac{1}{d(u, v)^q} \end{split}\]

Notiamo che anche se tecnicamente la costante di normalizzazione \(z_u\) è specifica per il singolo nodo \(u\), data la simmetria del grafo con cui stiamo lavorando abbiamo che per ogni coppia di nodi \(u, v\) vale \(z_u = z_v\), e dunque la possiamo considerare la costante di normalizzazione come un singolo valore \(z\) uguale per tutti i nodi.

---

Il parametro \(q\) invece viene utilizzato per controllare il processo di creazione degli weak-ties. A tale fine notiamo che

• Se \(q = 0\), allora \(z = n - 1\) e quindi

  \[P[(u, v) \in E] = \frac{1}{n-1}\]

  ovvero la creazione dei weak ties si riduce ad una scelta uniforme, riducendo così il modello al modello di Watts-Strogtaz visto prima.

• In generale all'aumentare di \(q\) diminuisce la probabilità di trovare weak-ties tra nodi lontani, come mostra la seguente figura

  

Al fine di trovare un modello che ci aiuti nella ricerca decentralizzata siamo quindi interessati a trovare valori di \(q\) tali che

1. Sia possibile raggiungere nodi "abbastanza" lontani utilizzando i weak ties;

2. I nodi collegati dai weak ties non devono però essere "troppo" lontani tra loro.

Sperimentalmente è stato dimostrato che un valore ideale per \(q\) è dato dalla dimensione dello spazio in cui ci troviamo. Dunque, se stiamo in uno spazio a tre dimensioni, allora \(q = 3\); se invece stiamo in un piano a due dimensioni, come la griglia appena descritta, allora \(q = 2\). Infine, se ci troviamo in un anello ad una dimensione, abbiamo che \(q = 1\).