AR - 11 - Popolarità

Il Teorema del Limite Centrale ci dice che la somma di v.a. indipendenti e con la stessa distribuzione converge ad una distribuzione normale.

Dato che possiamo esprimere il grado del nodo \(u\), \(X_u\), come somma di v.a. indipendenti e aventi tutti la stessa distribuzione, abbiamo che \(X_u\) all'aumentare del numero di nodi \(n\) segue una distribuzione normale descritta dalla seguente densità

Inoltre, dato che \(X_u\) è una somma di v.a. indipendenti, per calcolare la probabilità \(P(X_u > k)\), possiamo utilizzare il secondo Chernoff Bound, che dice che, dato \(\mathbb{E}[X_u] = \mu\), allora

\[P(X_u > (1 + \delta) \cdot \mu) < \bigg[ \frac{e^{\delta}}{(1 + \delta)^{1 + \delta}} \bigg]^{\mu}\]

Dunque, nel modello di Erdős-Rényi la probabilità del grado di un nodo diminuisce in modo esponenziale all'aumentare del grado. In termine di popolarità questo significa che, nel modello di Erdős-Rényi ci sono pochissimi nodi popolari.

Siamo adesso interessati a far vedere che questo nuovo modello definito esibisce una power law, ovvero che il numero di nodi che hanno grado \(k\) decresce in modo polinomiale rispetto a \(k\).

Dato però che è molto difficile far vedere questa relazione per il modello esatto descritto, quello che faremo sarà modificare il modello originale per ottenere due modelli approssimati, uno discreto e l'altro continuo. Faremo poi vedere che la relazione di power law è valida per il modello continuo. Un risultato analogo è stato comunque dimostrato per il modello originale.

A tale fine definiamo la seguente quantità,

\[A_j(t) := \text{numero di in-links del nodo } j \text{ al passo } t \,\,\, , \,\,\, j \leq t\]

Dal modello originario otteniamo che \(A_j(j) = 0\) e anche che,

\[\begin{split} P(A_j(t+1) - A_j(t) = 1) &= P(t + 1 \to j) \\ &= \frac{p}{t} + \frac{a-p}{t} \cdot A_j(t) \end{split}\]

---

Il primo modello che approssima il modello originale, quello discreto, è definito dalla funzione discreta \(X_j(t)\), \(t \in \mathbb{N}\), nel seguente modo

• \(X_j(j) = 0\)

• \(\displaystyle{X_j(t+1) - X_j(t) = \frac{p}{t} + \frac{a-p}{t} \cdot X_j(t)}\)

Il modello discreto appena descritto è stato ottenuto imponendo il valore della probabilità del modello originario come valore deterministico della variazione del numero di archi entranti in \(j\) tra il passo \(t\) e il passo \(t+1\).

---

Dato però che è difficile lavorare con funzioni discrete, facciamo una ulteriore approssimazione introducendo un nuovo modello, questa volta continuo, definito dalla funzione continua \(x_j(t)\), \(t \in \mathbb{R}\), nel seguente modo

• \(x_j(j) = 0\)

• \(\displaystyle{x_j(t+1) - x_j(t) = \frac{p}{t} + \frac{1-p}{t} \cdot x_j(t)}\)

Da adesso in poi siamo interessati ad esprimere in forma chiusa la funzione \(x_j(t)\). A tale fine notiamo che l'equazione che descrive la variazione tra \(x_j(t+1)\) e \(x_j(t)\) può essere approssimata tramite la seguente equazione differenziale

\[\frac{d \,\, x_j(t)}{d \,\, t} = \frac{p}{t} + \frac{1-p}{t} \cdot x_j(t)\]

Tale E.D. è facilmente risolvibile, in quanto è una E.D. del primo ordine a variabili separabili. Procediamo quindi impostando i due integrali,

\[\require{cancel} \begin{split} \frac{d \,\, x_j(t)}{dt} = \frac{p}{t} + \frac{1-p}{t} \cdot x_j(t) &\iff \frac{d \,\, x_j(t)}{dt} = \Big(p + (1 - p) \cdot x_j(t)\Big) \cdot \frac1t \\ &\iff \frac{1}{\Big(p + (1 - p) \cdot x_j(t)\Big)} \cdot \frac{d \,\, x_j(t)}{dt} = \frac1t \\ &\iff \int \frac{1}{\Big(p + (1 - p) \cdot x_j(t)\Big)} \cdot \frac{d \,\, x_j(t)}{\cancel{dt}} \cdot \cancel{dt} = \int \frac1t dt \\ &\iff \int \frac{1}{\Big(p + (1 - p) \cdot x_j(t)\Big)} \cdot d \,\, x_j(t) = \int \frac1t dt \\ \end{split}\]

---

Per risolvere l'integrale del lato sinistro effettuiamo un cambiamento di variabili, introducendo \(z := p + (1-p) \cdot x_j(t)\). Otteniamo quindi,

\[dz = (1-p) d \,\, x_j(t) \iff d \,\, x_j(t) = \frac{dz}{1-p}\]

sostituendo nel primo integrale troviamo

\[\begin{split} \int \frac{1}{\Big(p + (1 - p) \cdot x_j(t)\Big)} \cdot d \,\, x_j(t) &= \int \frac1z \cdot \frac{dz}{1-p} \\ &= \frac{\ln z}{p-1} + C_1\\ &= \frac{1}{p-1} \cdot \Big[ \ln{(p + (p-1) \cdot x_j(t))}\Big] + C_1\\ \end{split}\]

---

Per il secondo integrale troviamo

\[\int \frac1t dt = \ln t + C_2\]

---

Mettendo tutto assieme siamo in grado di esplicitare \(x_j(t)\) nel seguente modo

\[\begin{split} &\;\;\;\;\;\;\;\;\;\;\; \frac{1}{p-1} \cdot \Big[ \ln{(p + (p-1) \cdot x_j(t))}\Big] + C_1 = \ln t + C_2 \\ &\iff \frac{1}{p-1} \cdot \Big[ \ln{(p + (p-1) \cdot x_j(t))}\Big] = \ln t + C\\ &\iff \Big[ \ln{(p + (p-1) \cdot x_j(t))}\Big] = (1-p) \cdot \ln t + C\\ &\iff \Big[ \ln{(p + (p-1) \cdot x_j(t))}\Big] = \ln t^{1-p} + C\\ &\iff \Big[ \ln{(p + (p-1) \cdot x_j(t))}\Big] = \ln t^{1-p} + \ln H\\ &\iff \Big[ \ln{(p + (p-1) \cdot x_j(t))}\Big] = \ln{t^{1-p} \cdot H}\\ &\iff p + (p-1) \cdot x_j(t) = H \cdot t^{1-p} \\ \end{split}\]

Dall'ultima equazione siamo in grado di esplicitare \(x_j(t)\), trovando la seguente

\[x_j(t) = \frac{H \cdot t^{1-p} - p}{1 - p}\]

dove \(H\) è una costante tale che \(C = \ln H\). Per trovare il valore di tale costante ci basta imporre la condizione iniziale, che ci dice che

\[\begin{split} x_j(j) = 0 &\iff \frac{H \cdot t^{1-p} - p}{1 - p} = 0 \\ &\iff H = \frac{p}{j^{1-p}} \\ \end{split}\]

Sostituendo il valore di \(H\) trovato nella formula chiusa di \(x_j(t)\) troviamo quindi

\[x_j(t) = \frac{p}{j^{1-p}} \cdot \frac{t^{1-p}}{1-p} - \frac{p}{1-p} \iff x_j(t) = \frac{p}{1-p} \cdot \Big[ \Big(\frac{t}{j}\Big)^{1-p} -1 \Big]\]

---

Ora che siamo in grado di calcolare il numero di nodi di grado \(k\), possiamo procedere nel nostro intento, che è quello di calcolare la frazione di nodi di grado \(k\). A tale fine definiamo,

• \(\Gamma(k, t) := \text{ numero nodi con grado entrante } \geq k \text{ al tempo } t\)

Utilizzando la funzione \(x_j(t)\) sappiamo che, nel modello continuo,

\[\Gamma(k, t) = |\{j : \,\, x_j(t) \geq k\} |\]

Impostando e risolvendo la relativa disuguaglianza otteniamo che

\[\begin{split} &x_j(t) \geq k \\ &\iff \frac{p}{1-p} \cdot \Big[ \Big(\frac{t}{j}\Big)^{1-p} -1 \Big] \geq k \\ &\iff \Big(\frac{t}{j}\Big)^{1-p} \geq k \cdot \frac{1-p}{p} + 1 \\ &\iff \frac{t}{j} \geq \Big( k \cdot \frac{1-p}{p} + 1 \Big)^{\frac{1}{1-p}} \\ &\iff j \leq t \cdot \Big( k \cdot \frac{1-p}{p} + 1 \Big)^{-\frac{1}{1-p}} \\ \end{split}\]

Possiamo quindi approssimare \(\Gamma(k, t)\) con la seguente funzione continua

\[\Gamma(k, t) = t \cdot \bigg[ \frac{1-p}{p} \cdot k + 1 \bigg]^{-\frac{1}{1-p}}\]

Procediamo definendo quindi calcolando la funzione \(F(k)\), il cui valore è definito come la frazione dei nodi che hanno grado \(\geq k\). Dal calcolo di \(\Gamma(k, t)\) effettuato prima segue che

\[F(k) = \frac{\Gamma(k, t)}{t} = \bigg[ \frac{1-p}{p} \cdot k + 1 \bigg]^{-\frac{1}{1-p}}\]

Infine, denotando che \(f(k)\) la frazione di nodi di grado \(k\), troviamo che

\[f(k) = F(K) - F(k+1) = -\bigg[\frac{F(k+1) - F(k)}{1} \bigg] \approx - \frac{d F(k)}{k}\]

Dunque possiamo approssimare \(f(k)\) con la seguente funzione

\[f(k) \approx \frac{1}{p} \cdot \bigg[ \frac{1-p}{p} \cdot k + 1\bigg]^{-\frac{1}{1-p} -1}\]

---

Notiamo come \(f(k)\), che è proprio la funzione che cercavamo, ovvero la frazione di nodi di grado \(k\), decresce come \(k^{-c}\), dove \(c\) è una costante ottenuta in funzione di \(p\), che vale \(-2\), quando \(p = 0\).

Concludiamo quindi osservando che il modello sintetico definito esibisce una power law rispetto alla popolarità dei nodi, e quindi si avvicina alle reti sociali di più del modello di Erdős-Rényi.