AR - Lesson 01

Una definizione più precisa di componente gigante equivale a una componente connessa grande una frazione costante dei nodi del grafo. Per frazione costante, si intende che al variare del numero di nodi del grafo, il rapporto tra \(n\) e la grandezza della componente gigante rimane invariato. Si dice quindi che una componente gigante ha grandezza \(\Theta(n)\), dove (ribadendo) \(n\) è il numero di nodi del grafo.

Per quanto riguarda la distribuzione distribuzione Erdős–Rényi ci si potrebbe chiedere se esiste un valore di \(p\) per cui esiste (con buona probabilità) una componente gigante in \(G_{n,p}\), e se sì, per quale valore.

Un risultato già noto dice che se \(p > \frac{ \ln{64} }{ n }\) allora con alta probabilità (w.h.p.) esisterà una componente connessa con almeno la metà dei nodi.
Il termine "alta probabilità" non è usato in maniera impropria, bensì cela un significato rigoroso e preciso. Per alta probabilità si intende con probabilità dell'ordine di almeno \(\left( 1 - \frac{ b }{ n^c } \right)\), per qualche coppia di costanti \(b,c\) strettamente positive.

Da cui quindi il seguente teorema:

THM sia \(G_{n,p}\) un Erdős–Rényi random graph di parametri \(n,p\), e sia \(X\) la variabile aleatori che indica il numero di nodi della più grande componente connessa di \(G_{n,p}\). \[ p > \frac{ \ln{64} }{ n } \implies \mathcal{P} \left( X \geq \frac{n}{2} \right) \geq 1 - 2^{-n/8} \]

Per dimostrare il teorema è prima necessario introdurre il seguente lemma

Lemma Se \(X < \frac{n}{2}\) allora esiste un insieme \(A \subset \left[ n \right]\), detto insieme buono, tale che \[ \frac{n}{4} \leq |A| < \frac{3}{4}n \] e \[ \nexists \{ u,v \} \in E : u \in A \land v \in [n] \setminus A \]

Proof (Lemma) Siano \(C_1, C_2, ..., C_k\) tutte le componenti connesse di \(G_{n,p}\) ordinate in senso non decrescente di grandezza, ovvero \[ |C_1| \leq |C_2| \leq ... \leq |C_k| := X < \frac{n}{2} \] Si scelga un indice \(h\) tale che \[ |C_1| + |C_2| + ... |C_{h-1}| < \frac{n}{4} \] e \[ |C_1| + |C_2| + ... |C_{h-1}| + |C_h| \geq \frac{n}{4} \] Si osservi che necessariamente \(h < k\), infatti poiché \(|C_k| < \frac{n}{2}\), se fosse \(h=k\) risulterebbe \[ |C_1| + |C_2| + ... |C_{k-1} | + |C_k | < \frac{n}{4} + \frac{n}{2} < n \] e questo è assurdo in quanto \(C_1, C_2, ..., C_k\) sono una partizione di \(V\), perciò la dimensione della loro unione è esattamente \(n\).

Scelto un \(h\) adeguato, poniamo \(A = \bigcup_{i=1}^{h} C_h\). Necessariamente \(A \neq \emptyset\) in quanto è composto da almeno \(C_1\) (il quale ha almeno un nodo per definizione di componente), e \(\left[ n \right] \setminus A \neq \emptyset\) in quanto al più \(h\) può valere \(k-1\) (lasciando fuori \(C_k\) dall'insieme \(A\)).

Seguono quindi le condizioni del lemma

• \(|A| \geq \frac{n}{4}\) per costruzione
• \(|A| = \underbrace{|C_1| + |C_2| + ... + |C_{k-1}|}_{ < n/4 } + \underbrace{|C_k|}_{< n/2} < \frac{n}{4} + \frac{n}{2} = \frac{3}{4}n\)
• Non ci possono essere archi nel taglio \((A,\left[ n \right] \setminus A)\), in quanto i due insiemi sono composti da componenti connesse. Infatti se esistesse un arco nel taglio, i due estremi apparterrebbero a due componenti connesse \(C_i, C_j\) distinte, ma ciò significherebbe che \(C_i \cup C_j\) è a sua volta una componente connessa (assurdo!). \(\square\)

Una diretta conseguenza del lemma è che la probabilità che la più grande componente connessa di \(G_{n,p}\) sia più piccola di \(n/2\) è minore o uguale alla probabilità sia presente un insieme buono. In fatti, in probabilità, dati due eventi \(\mathcal{E_1},\mathcal{E_2}\), se \(\mathcal{E_1} \implies \mathcal{E_2}\) allora \(\mathcal{P}(\mathcal{E_1}) \leq \mathcal{P}(\mathcal{E_2})\). In questo caso gli eventi corrispondono \(\mathcal{E_1}\) = "\(X < n/2\)" e \(\mathcal{E_2}\) = "esiste un insieme buono \(A\)".

Proof (THM) Si desidera calcolare \(\mathcal{P}\left( X < \frac{n}{2} \right)\), ovvero il complementare della probabilità che si desidera dimostrare.

Dal Lemma avremo che

\begin{align*} \mathcal{P}\left( X < \frac{n}{2} \right) &\leq \mathcal{P}( \exists A \subset \left[ n \right] : A \mbox{ è buono})\\ &= \mathcal{P}\left( \bigcup_{A \subset \left[ n \right] \land \frac{n}{4} \leq |A| < \frac{3}{4}n } A : \mbox{ non ci sono archi nel taglio } (A, \overline{A}) \right) \;\;\; \mbox{-- per definizione di insieme buono}\\ &\leq \sum_{A \subset \left[ n \right] \land \frac{n}{4} \leq |A| < \frac{3}{4}n } \mathcal{P}\left(\mbox{ non ci sono archi nel taglio } (A, \overline{A}) \right) \;\;\; \mbox{-- per il principio di union bound}\\ &= \sum_{A \subset \left[ n \right] \land \frac{n}{4} \leq |A| < \frac{3}{4}n } (1-p)^{|A| \cdot |\overline{A}|} \;\;\; \mbox{(1)}\\ &\leq \sum_{A \subset \left[ n \right] \land \frac{n}{4} \leq |A| < \frac{3}{4}n } (1-p)^{\frac{3}{16}n^2} \;\;\; \mbox{(2)}\\ &\leq 2^{n} (1-p)^{\frac{3}{16}n^2} \;\;\; (3)\\ &< 2^{n} \left(1 - \frac{ \ln{64} }{n} \right)^{\frac{3}{16}n^2} \;\;\; (4)\\ &= 2^{n} \left[ \left(1- \frac{ \ln{64} }{n} \right)^n \right]^{\frac{3}{16}n}\\ &= 2^{n} \left[ \left(1- \frac{ \ln{64} }{n} \right)^{n \cdot \left( \frac{ -\ln{64} }{ -\ln{64} } \right) } \right]^{\frac{3}{16}n}\\ &\approx 2^{n} \left[ e^{-\ln{64}} \right]^{\frac{3}{16}n} \;\;\; (5)\\ &= 2^{n} \left[ 64^{-1} \right]^{\frac{3}{16}n}\\ &= 2^{n} \left[ 2^{-6} \right]^{\frac{3}{16}n} = 2^{n} 2^{ -\frac{18}{16}n } = 2^{-\frac{n}{8}} \;\;\; \square \end{align*}

Di seguito spiegate le disuguaglianze:

• (1) è data dal fatto che tale probabilità è data dalla probabilità che non esista un arco nel taglio, ovvero \((1-p)\), moltiplicato tante volte quanti i archi possono esistere tra \(A\) e \(\overline{A}\), ovvero \(|A| \cdot |\overline{A}|\).
• (2) è invece data dal fatto chef il punto di minimo della funzione \(|A| \cdot |\overline{A}|\) è per valori di \(|A| = \frac{1}{4}, \frac{3}{4}\). Ci interessano i punti di minimo in quanto essendo \((1-p) < 1\), \((1-p)^{x}\) assume valori massimi per \(x\) minimo.
• (3) è dato dal fatto che il numero massimo di sottoinsiemi \(A \subseteq \left[ n \right]\) è \(2^n\).
• (4) per ipotesi del teorema
• (5) perché \(\lim_{n \rightarrow \infty} \left( 1 + \frac{1}{n} \right) = e^{n}\)

Una versione più generale del precedente teorema è la seguente

Teorema generale Sia \(G_{n,p}\) un grafo aleatorio campionato dalla distribuzione Erdős–Rényi, allora:

1. se \(p(n-1) < 1\) allora quasi sicuramente (asymptotically almost surely, o in breve a.a.s.) tutte le componenti connesse di \(G_{n,p}\) avranno \(O( \log{n} )\) nodi (ovvero saranno molto piccole).
2. se \(p(n-1) = 1\) allora a.a.s. \(G_{n,p}\) avrà una componente connessa grande \(\approx n^{ \frac{2}{3} }\).
3. se \(p(n-1) > 1\) allora a.a.s. \(G_{n,p}\) avrà una componente connessa grande \(\Omega (n)\) nodi e tutte le altre grandi \(O(\log{n})\).

Ciò che suggerisce il teorema più generale è che la presenza di componenti connesse dipende in qualche modo dal prodotto \(p(n-1)\), ma cosa rappresenta questa quantità? Questo verrà mostrato nella seguente sezione.

Dato un grafo Erdős–Rényi \(G_{n,p}\), definiamo col simbolo \(\delta_i\) la variabile aleatoria che esprime il grado del nodo \(i\). Sia inoltre la v.a. binaria tale che \(\forall j \in \left[ n \right] \setminus \lbrace i \rbrace\) \[ X_{i,j} = \begin{cases} 1 &\mbox{se esiste l'arco }(j,i) \in E\\ 0 &\mbox{altrimenti} \end{cases} \] Perciò il valore atteso di \(\delta_i\) sarà

\begin{align*} \mathbb{E} \left[ \delta_i \right] &= \mathbb{E} \left[ \sum_{j \in \left[ n \right] \setminus \lbrace i \rbrace } X_{j,i} \right]\\ &= \sum_{j \in \left[ n \right] \setminus \lbrace i \rbrace } \mathbb{E} \left[ X_{j,i} \right] \;\;\; \mbox{(per linearità del valore atteso)}\\ &= \sum_{j \in \left[ n \right] \setminus \lbrace i \rbrace } 1 \cdot p + 0 \cdot (1-p) = (n-1)p \end{align*}

Perciò la quantità \(p(n-1)\) vista nella precedente sezione, altro non è che il grado medio di un nodo. Ciò significa che, fissato un \(p\) costante, ogni individuo nella rete sarà in contatto con una porzione constante della reta stessa, ovvero il grado medio cresce in maniera lineare nel numero di nodi. Ovviamente è inverosimile che in una rete di un social network composta da centinaia di milioni (se non miliardi) di nodi, io abbia un numero di amicizie proporzionale al numero di utenti (non penso sarà mai così famoso).

Perciò, per modellare una rete che sia più verosimile, si potrebbe volere che \(p\) sia una funzione di \(n\), e che magari decresca in maniera inversamente proporzionale, del tipo \[ p = p(n) = \frac{ \lambda }{n} \] Scegliendo \(p\) in questa maniera, avremo che il grado medio di un nodo sarà pari alla costante \(\lambda\), indipendentemente dalla dimensione della rete.

Un'altra domanda che è utile chiedersi è: fissato un \(k \leq n\), con quale probabilità che un nodo \(i \in \left[ n \right]\) ha esattamente grado \(k\). Intuitivamente, questa è pari alla probabilità che esistano esattamente \(k\) archi incidenti a \(i\). Tale probabilità è esattamente definita dalla legge binomiale \(\mathcal{B}(n-1,p)\), ovvero \[ \mathcal{P}\left( \delta_i = k \right) = \binom{n-1}{k} p^k \left( 1-p \right)^{(n-1) - k} \] Questo perché:

1. \(\binom{n-1}{k}\) è il numero di tutte le possibili $k$-uple di nodi in \(\left[ n \right] \setminus \lbrace i \rbrace\).
2. \(p^k\) è la probabilità che esistano gli archi tra \(i\) e i nodi di una \(k\) -upla.
3. \(\left( 1-p \right)^{(n-1) - k}\) è la probabilità che non esista nessun altro arco (ne vogliamo solo \(k\)).

Scegliendo \(p = \frac{ \lambda }{n}\) in funzione di \(n\) come detto in precedenza, avremo che la probabilità che un nodo abbia grado medio esattamente \(k\) è

\begin{align*} \mathcal{P}\left( \delta_i = k \right) &= \binom{n-1}{k} p^k \left( 1-p \right)^{(n-1) - k}\\ &= \binom{n-1}{k} \left( \frac{ \lambda }{n} \right)^k \left( 1- \frac{ \lambda }{n} \right)^{(n-1) - k}\\ &= \frac{(n-1) \cdot (n-2) \cdot ... \cdot (n-k)}{k!} \frac{ \lambda^k }{ n^k } \left( 1- \frac{ \lambda }{n} \right)^{(n-1) - k}\\ &< \frac{(n-1) \cdot (n-2) \cdot ... \cdot (n-k)}{k!} \frac{ \lambda^k }{ n^k } e^{ \frac{-\lambda (n - 1 - k)}{n}} \;\;\; (1)\\ &< \frac{n^k}{k!} \frac{ \lambda^k }{ n^k } e^{ \frac{-\lambda (n - 1 - k)}{n}}\\ &\approx \frac{ \lambda^k }{ k! } e^{ -\lambda } \;\;\; \mbox{per } n \mbox{ sufficientemente grande} \end{align*}

Più semplicemente \[ \mathcal{P}\left( \delta_i = k \right) < \frac{ \lambda^k }{ k! } e^{ -\lambda } \] La disuguaglianza (1) è data dal fatto che \(\forall x < 1\) vale sempre che \(1-x < e^{-x}\).

Applicando l'approssimazione di Stirling secondo la quale \(k! \thicksim \sqrt{2 \pi k} \left( \frac{k}{e} \right)^k\), possiamo semplificare il tutto con \[ \mathcal{P} \left( \delta_i = k \right) < \frac{ (\lambda e)^k }{ \sqrt{2 \pi k} k^k }e^{ -\lambda } = \frac{ e^{ -\lambda } }{ \sqrt{2 \pi k} } \left( \frac{ \lambda e }{k} \right)^k \] Quest'ultima disuguaglianza ci suggerisce che la probabilità che un generico nodo abbia grado \(k\) decresce molto velocemente al crescere di \(k\), più precisamente decresce esponenzialmente in \(k\) (come \(k^{-k}\)).

Una volta stabilità questa probabilità, si può calcolare il numero atteso di nodi che hanno grado esattamente \(k\). Per prima cosa definiamo la variabile aleatoria binaria \(\delta_{i,k}\) tale che \[ \delta_{i,k} = \begin{cases} 1 &\mbox{se } \delta_i = k\\ 0 &\mbox{altrimenti} \end{cases} \] Definiamo in oltre la v.a. \(F_k\) che indica la frazione di nodi della rete che hanno grado \(k\) \[ F_k = \frac{ \sum_{i \in \left[ n \right] } \delta_{i,k} }{n} \] con valore atteso

\begin{align*} \mathbb{E} \left[ F_k \right] &= \mathbb{E} \left[ \frac{ \sum_{i \in \left[ n \right] } \delta_{i,k} }{n} \right]\\ &= \frac{1}{n} \sum_{i \in \left[ n \right] } \mathbb{E} \left[ \delta_{i,k} \right] \;\;\; \mbox{per linearità}\\ &= \frac{1}{n} \sum_{i \in \left[ n \right] } \left( 1 \cdot \mathcal{p}(\delta_{i,k} = 1) + 0 \cdot \mathcal{p}(\delta_{i,k} = 0) \right)\\ &= \frac{1}{n} \sum_{i \in \left[ n \right] } \left( 1 \cdot \mathcal{p}(\delta_i = k) + 0 \cdot \mathcal{p}(\delta_i \neq k) \right)\\ &= \frac{1}{n} \sum_{i \in \left[ n \right] } \mathcal{p}(\delta_i = k)\\ &< \frac{1}{n} \sum_{i \in \left[ n \right] } \frac{ e^{ -\lambda } }{ \sqrt{2 \pi k} } \left( \frac{ \lambda e }{k} \right)^k\\ &= \frac{ e^{ -\lambda } }{ \sqrt{2 \pi k} } \left( \frac{ \lambda e }{k} \right)^k \end{align*}

Perciò, in un grafo Erdős–Rényi \(G_{n,p}\) con grado medio constante, ovvero con parametro \(p = \frac{\lambda}{n}\), il numero di nodi di grado esattamente \(k\) decresce esponenzialmente in \(k\) (come \(k^{-k}\)).

---