AR - 01 - Introduzione

Supponiamo di avere una rete sociale in cui ci sono tre individui: \(A\), \(B\) e \(C\).

L'individuo \(A\) è un amico stretto sia di \(B\) che di \(C\). Invece, gli individui \(B\) e \(C\) non vanno molto d'accordo. Si può intuire che la rete sociale appena descritta formata dal gruppo di tre individui non è una rete "stabile". Infatti, sarà difficile per \(A\) mantenere uno stretto rapporto di amicizia con entrambi \(B\) e \(C\), in quanto, ad esempio, se \(A\) esce con \(B\) allora non può uscire con \(C\) e viceversa. Se invece non c'è questo conflitto tra \(B\) e \(C\), oppure se \(A\) è solo amico di \(B\) oppure di \(C\), allora la rete diventa "stabile".

Questo esempio ci fa vedere come le relazioni all'interno di una rete sono capaci di modificare le strutture all'interno di una rete.

La professoressa Di Ianni vive più o meno nella zona di Ostia. Per arrivare all'università ha due scelte: prendere la via del mare oppure prendere l'ostiense. Generalmente prende la via del mare, in quanto la via ostiense è una strada locale.

Se un giorno però la Di Ianni dovesse vedere una serie di macchine che cambiano repentinamente direzione e si immettono nella via ostiense, molto probabilmente penserebbe che queste macchine sanno qualcosa che lei non sa, e dunque questa informazione sul comportamento degli altri individui potrebbe far cambiare il comportamento della DI Ianni, facendole scegliere l'ostiense al posto della via del mare.

Questo è un piccolo esempio che descrive come un individuo che appartiene ad una determinata rete sociale può cambiare il proprio comportamento se riceve informazioni da altri individui appartenenti alla stessa rete sociali.

Al fine di rappresentare una rete utilizziamo il modello matematico del grafo. Un grafo \(G = (V, E)\) è definito come una coppia di insiemi, in cui \(V = \{v_1, v_2, ..., v_N\}\) è l'insieme dei vertici del grafo, mentre \(E \subseteq V \times V\) è l'insieme degli archi del grafo. Utilizzando il grafo come modello matematico di una rete possiamo studiare sicuramente almeno le seguenti cose:

• Lo studio delle comunità del grafo, ovvero lo studio delle parti più "densamente connesse".

• Lo studio della connettività della rete, ovvero l'eventuale presenza di componenti connesse e di componenti fortemente connesse, in caso di grafi diretti.

• Lo studio del diametro della rete, dove con diametro intendiamo la massima distanza tra due nodi nel grafo. Ovvero, volendo essere formali, e ricordando la definizione per \(d_G(u, v)\) come la lunghezza di un cammino minimo che da \(u\) a \(v\), troviamo la seguente definizione

  \[ Diam(G = (V, E)) := \max_{u, v \in V }d_G(u, v) \]

In questo articolo, chiamato "Planetary-Scale Views on an Instant-Messaging Network", e presente al seguente link, Leskovec e Hrovitz hanno avuto accesso ai dati generati in un mese un sistema telefonico di comunicazione, sviluppato da Microsoft e chiamato ``Instant Messaging''.

I dati sono stati utilizzati per costruire una rete sociale, in cui i nodi erano gli utenti e le connessioni erano i tentativi di comunicazioni tra un utente e l'altro.

Si è scoperto, tra le altre cose, che all'interno del grafo c'era una componente fortemente connessa che conteneva un sacco di invidui. Su 240 milioni di utenti totali infatti, la componente scoperta ne conteneva 200 milioni.

In questo esperimento, noto come small-world experiment, e disponibile al seguente link, Milgram e altri ricercatori hanno studiato la media della lunghezza dei cammini presenti nella rete sociale formata dalla popolazione degli stati uniti.

In particolare si è trovato che, in media, tale lunghezza è \(6\). Questo vuol dire che generalmente ci sono intorno alle \(6\) persone che permettono di passare da una data persona \(x\) ad un'altra persona \(y\), qualunque siano queste persone \(x, y\) all'interno della rete sociale in questione.

Da questo esperimento è poi diventato famoso il concetto dei "6 gradi di separazione".

Un grafo casuale generato con il modello di Erdős-Rényi \(G_{n,p} = (V, E)\), è un grafo tale che:

• \(V = [n] := \{1, 2, ..., n\}\).

• \(\forall u, v \in [n], \,\, P((u, v) \in E) = \begin{cases} 0 &, u = v \\ p &, \text{ altrimenti } \\ \end{cases}\)

Ovvero \(G\) ha \(n\) nodi, con \(n \in \mathbb{N}\), e la probabilità che ci sia un arco tra una coppia di nodi distinti \(u, v \in V\) è \(p\), con \(0 \leq p \leq 1\).

Supponiamo di voler utilizzare il modello generativo di Erdős-Rényi. Notiamo che nella definizione del nostro modello la scelta del parametro \(p\) è influenzata dal tipo di rete che vogliamo modellare. Ad esempio, se vogliamo modellare una rete sociale, una proprietà che potremmo potenzialmente volere è la seguente

\[\text{il valore atteso del grado di ogni individuo deve essere costante}\]

Andiamo quindi a trovare il giusto parametro per \(p\) al fine di ottenere questa proprietà.

A tale fine imponiamo \(p = \lambda/n\), e riscrivendo la formula, otteniamo

\[\begin{split} \delta(k) &= P(d_i = k) \\ &= \binom{n-1}{k}p^k(1-p)^{n-1-k} \\ &= \binom{n-1}{k}(\frac{\lambda}{n})^k (1 - \frac{\lambda}{n})^{n-1-k} \\ \end{split}\]

Notiamo a questo punto che, per \(n \to \infty\) si ha che \(\frac{\lambda}{n} \to 0\). Ma allora, utilizzando il fatto che \(1 - x \approx e^{-x}\), per \(x \to 0\), otteniamo che, per \(n \to \infty\), è possibile approssimare \(1 - \lambda/n\) con \(e^{-\frac{\lambda}{n}}\), ottenendo quindi la seguente formula

\[\binom{n-1}{k}(\frac{\lambda}{n})^k (1 - \frac{\lambda}{n})^{n-1-k} \approx \frac{(n-1)(n-2)...(n-k)}{k!} (\frac{\lambda}{n})^k e^{-\frac{\lambda}{n}(n-1-k)}\]

Dato poi che per \(n \to \infty\) abbiamo che \(e^{-\frac{\lambda}{n}(n - 1- k)} \approx e^{-\lambda}\), troviamo

\[\begin{split} \delta(k) &\approx \frac{(n-1)(n-2)...(n-k)}{k!} (\frac{\lambda}{n})^k e^{-\lambda} \\ &= \frac{(n-1)(n-2)...(n-k)\lambda^k}{k!n^k} e^{-\lambda} \\ \end{split}\]

Infine, utilizazndo l'approssimazione di Stirling \(k! \approx \sqrt{2 \pi k} (\frac{k}{e})^k\) e prendendo il limite per \(n \to \infty\), otteniamo il seguente risultato

\[\begin{split} \delta(k) &\approx^{n \to \infty} \frac{(n-1)(n-2)...(n-k)}{n^k} \cdot \frac{\lambda^k}{k!} e^{-\lambda} \\ &\approx \frac{\lambda^k}{k!} e^{-\lambda} \\ &\approx \frac{1}{\sqrt{2 \pi k}} (\frac{e}{k})^k \lambda^k e^{-\lambda} \\ &= \frac{e^{-\lambda}}{\sqrt{2 \pi k}} (\frac{\lambda e}{k})^k \end{split}\]

Riassumendo abbiamo dimostrato che, per \(n \to \infty\),

\[\delta(k) = P(d_i = k) \approx \frac{e^{-\lambda}}{\sqrt{2 \pi k}} (\frac{\lambda e}{k})^k\]

e quindi possiamo concludere osservando che

\[\delta(k) \to 0, \text{ per } k \to \infty\]

il che è un risultato ragionevole in una rete sociale. Notiamo inoltre, per finire, che tale funzione tende a \(0\) come \(\frac{1}{k^k}\), ovvero come l'inversa di un esponenziale. Questo risultato sarà importante nello studio del fenomeno rich get richer.

Per \(x < -1\) il caso è banale, in quanto \(e^x > 0 > 1 + x\). Per \(x \geq -1\), utilizziamo la disuguaglianza di Bernoulli, dimostrabile per induzione su \(n\), che ci dice che, dato \(n > 0\) intero e \(y \geq -2\) numero reale, si ha che

\[1 + ny \leq (1 + y)^n\]

In particolare quindi, posto \(y = x/n\), troviamo

\[1 + x \leq (1 + \frac{x}{n})^n\]

Infine, ricordando che \(\lim_{n \to \infty} (1 + x/n)^n = e^x\), troviamo il risultato cercato, ovvero che

\[1 + x \leq (1 + \frac{x}{n})^n \leq \lim_{n \to \infty} (1 + \frac{x}{n})^n = e^x\]

Notiamo che \(g(x) = x + 1\) è l'espressione della retta tangete al grafico di \(f(x) = e^x\) quando \(x = 0\). Inoltre, abbiamo che \(f(x)\) è una funzione convessa, e quindi il grafico di \(f(x)\) si trova sempre sopra il grafico delle sue retti tangenti. Ma allora,

\[x + 1 = g(x) \leq f(x) = e^x\]

Graficamente,