ADRC - 12 - Sparse Expanders

Data: [2018-12-03 lun] + [2018-12-06 gio]

---

In questa lezione abbiamo analizzato il protocollo \(\text{RTA}\), che ci permette di costruire dei grafi sparsi e scalabili con delle buone proprietà di connettività.

In generale siamo interessati ai grafi che presentano le seguenti proprietà:

• Grado "piccolo" per ogni nodo;

• Diametro del grafo "piccolo";

• Fault tolerance "media";

A tale fine definiamo il seguente protocollo, chiamato protocollo \(\text{RTA}\), che sta per "Request Then Accept". Il protocollo lavora sul grafo completo \(K_n\), prende in input un parametro \(d \in \mathbb{N}\), e può essere descritto come segue:

• Ogni nodo \(v \in V := [n]\) sceglie in modo uniforme e indipendente altri \(d\) nodi \(w_1, w_2, \ldots, w_d\). A ciascun nodo scelto invia un messaggio (link-request) in cui richiede al nodo l'utilizzo dell'arco \((v, w_i)\), che viene quindi salvato nella lista \(N_v\) memorizzata dal nodo \(v\).

• Ogni nodo \(v\) che riceve una link-request dal nodo \(w\) la accetta, e memorizza l'arco \((v, w)\) nella sua particolare lista \(N_v\).

• Il grafo costruito e ritornato dal protocollo è

  \[G = (V,E) \,\,\,\,,\,\,\,\, E := \bigcup\limits_{v \in V} N_v\]

Osservazione: Dato che i nodi scelgono con ripetizione, può accadere che un nodo \(v\) scelga due volte lo stesso nodo \(w\). Il grafo ritornato dal protocollo potrebbe quindi essere un multigrafo con dei self-loops.

Andiamo adesso ad analizzare alcune proprietà del grafo \(G\) ritornato dal protocollo \(\text{RTA}\).

Per quanto riguarda il grado dei nodi del grafo, sia \(V = \{1, 2, \ldots, n\} = [n]\) un ordinamento arbitrario dei nodi. Se indichiamo con \(\Delta_v^{\text{in}}\) la v.a. che conta il numero delle link-request ricevute dal nodo \(v\), si nota subito che

\[\Delta(v) = d + \Delta_v^{\text{in}}\]

Andiamo quindi ad analizzare il grado medio, il grado massimo, e il grado generale dei nodi del grafo.

Fino a questo momento abbiamo analizzato il grado dei nodi del grafo generato dal protocollo \(\text{RTA}(n, d)\). Andiamo ora ad analizzare altre proprietà del grafo \(G\), come ad esempio la connettività e la fault-tolerance. Segue qualche definizione iniziale

---

Definizione 1: Dato un grafo \(G = (V, E)\) con \(V = [n] = \{1, 2, \ldots, n\}\), la (node)-expansion di un qualsiasi sottoinsieme \(S \subseteq V\) è indicata con \(|N(S)|\), dove

\[N(S) := \{w \in V \setminus S: \,\,\, \exists v \in S: \,\, (v, w) \in E\}\]

Definizione 2: Per un fissato \(\alpha \geq 0\), diciamo che \(G\) è un \(\alpha\) -expander se ogni sottoinsieme \(S \subseteq V\) con \(|S| \leq n/2\) ha una espansione di almeno \(\alpha \cdot |S|\).

---

Andiamo adesso a dimostrare che il protocollo \(\text{RTA}\) ritorna un grafo quasi-sparso ma con delle buone proprietà di connessione. In particolare vale il seguente risultato

Teorema: Per ogni \(n \geq 1\) e per \(d = \beta \log n\), con \(\beta > 0\) costante assoluta abbastanza grande, il grafo \(G = (V, E)\) ritornato dal protocollo \(\text{RTA}(n, d)\) è con alta probabilità un \(\Omega(1) -\) expander.

Dimostrazione: Consideriamo una esecuzione del protocollo \(\text{RTA}\) come se fosse divisa in \(d\) fasi consecutive e mutualmente indipendenti. Durante la fase \(j\) ciascun nodo invia la propria \(j\) esima link-request ad un altro nodo scelto in modo uniforme e indipendente.

Sia quindi \(s \leq n/2\) e fissiamo un qualsiasi sottoinsieme \(S \subseteq V\) con \(|S| = s\). Definiamo le seguenti v.a.

\[Y_v^j := \begin{cases} 1 \,\,\,&,\,\,\, \text{ la } j \text{ esima richiesta di } v \text{ è inviata a qualche nodo } u \in S \\ 0 \,\,\,&,\,\,\, \text{ altrimenti} \\ \end{cases}\]

dove \(j = 1, 2, \ldots, d\) sono le varie fasi del protocollo e \(v \in V \setminus S\).

Dato che il grafo è completo e le richieste vengono inviate in modo uniforme, si può facilmente osservare che

\[Pr[Y_v^j = 1] = \frac{s}{n}\]

Consideriamo ora il seguente random subset di nodi in \(V \setminus S\)

\[N^j(S) := \{v \in V \setminus S: \,\,\, Y_v^j = 1\}\]

Dato che \(s \leq n/2\), per ogni fase \(j\) troviamo

\[\mathbb{E}[|N^j(S)|] = \mathbb{E}\Big[\sum\limits_{v \in V \setminus S} Y_v^j\Big] = \sum\limits_{v \in V \setminus S} \mathbb{E} \Big[ Y_v^j \Big] = (n - s) \cdot \frac{s}{n} \geq \frac{n}{2} \cdot \frac{s}{n} = \frac{s}{2}\]

Dal fatto poi che \(|N^j(S)|\) è una somma di v.a. indipendenti e a valori binari, possiamo utilizzare un Chernoff Bound per ottenere

\[Pr\Big[ |N^j(S)| \leq \Big(1 - \frac12 \Big) \cdot \frac{s}{2} \Big] = Pr \Big[|N^j(S)| \leq \frac{s}{4} \Big] \leq e^{-\frac{s}{16}}\]

---

Per continuare, definiamo i seguenti eventi

• \(B^j(S) := |N^j(S)| \leq s/4\)

• \(B(S) := \bigcap\limits_{j = 1}^d B^j(S)\)

Dato che gli eventi \(B^j(S)\) sono mutualmente indipendenti al variare di \(j=1,2,\ldots,d\), otteniamo

\[Pr[B(S)] = \prod\limits_{j = 1}^d Pr[B^j(S)] \leq \Big(s^{-\frac{s}{16}}\Big)^d\]

Notiamo che se l'evento \(B(S)\) non succede, allora l'insieme \(S\) nel grafo finale ottenuto dal protocollo \(\text{RTA}\) ha una espansione di \(1/4\). Continuando, la probabilità che esiste un "cattivo" \(S\) per cui vale \(B(S)\) può essere limitata effettuando un union bound su tutti i possibili insiemi \(S\) di size \(s\). Tale probabilità è al più

\[\binom{n}{s} \cdot e^{- \frac{ds}{16}} \leq \Big(\frac{en}{s}\Big)^s \cdot e^{-\frac{ds}{16}} = e^{s + s \log n - s \log s - \frac{1}{16} ds}\]

dove l'ultimo termine può essere reso \(\leq 1/n^2\) scegliendo un valore di \(\beta > 0\) abbastanza grande, con \(d = \beta \cdot \log n\).

Per finire, dobbiamo effettuare un ulteriore union bound. Infatti il bound ottenuto vale per ogni sottoinsieme \(S\) con il size fissato a \(s \leq n/2\). Necessitiamo quindi di un altro union bound per coprire ogni possibile valore di \(s\). Dato che il numero di sizes possibili è \(n/2\), otteniamo immediatamente che la probabilità che esiste un insieme \(S\) di size \(\leq n/2\) per cui vale \(B(S)\) è al più

\[\frac{n}{2} \cdot \frac{1}{n^2} \leq \frac{1}{n}\]

Ma allora abbiamo che con alta probabilità qualsiasi sottoinsieme \(S\) con size \(|S| \leq n/2\) ha una espansione di almeno \(1/4\), il che equivale a dire che con alta probabilità il grafo ritornato dal protocolo è un \(\Omega(1) -\) expander.

\[\tag*{$\blacksquare$}\]

Per finire la lezione, andiamo ad analizzare una proprietà che rende interessanti i grafi che sono \(\Omega(1) -\) expanders: il fatto che hanno un diametro limitato. In particolare vale il seguente

Teorema: Consideriamo la seguente famiglia infinita di grafi

\[\{G_n = (V_n, E_n): \,\,\, V_n = [n], \,\,\, E_n \subseteq V_n^2, \,\,\, n \geq 1\}\]

Se esiste una costante assoluta \(\alpha > 0\) tale che per un valore abbastanza grande di \(n\) il grafo \(G_n\) è un \(\alpha -\) expander, allora il suo diametro è \(O(\log n)\).

Dimostrazione: Consideriamo un grafo della famiglia \(G_n = (V_n, E_n)\).

Fissiamo un certo vertice \(s \in V\) ed eseguiamo una breadth-first-search (BFS) a partire da \(s\) al fine di calcolare le varie distanze \(d_G(s, v), \,\, v \in V\). Definiamo quindi i seguenti elementi

• \(L_t := \{v \in V: \,\,\, d_G(s, v) = t \}, \,\,\, t = 0, 1, \ldots, n-1\)

• \(I_0 := L_0 = \{s\}\)

• \(I_t := I_{t-1} \bigcup L_t \,\,\,,\,\,\, t = 1, 2, \ldots, n-1\)

Notiamo che dalle definizioni segue che \(N(I_t) = L_{t+1}\) e che \(|I_t| = |I_{t-1}| + |L_t|\). Utilizzando il fatto che \(G\) è un \(\alpha -\) expander otteniamo che se \(|I_{t-1}| \leq n/2\), allora

\[\begin{split} \phantom{} |I_t| = |I_{t-1}| + |L_t| &\geq |I_{t-1}| + \alpha \cdot |I_{t-1}| \\ &= (1 + \alpha) \cdot |I_{t-1}| \\ &\,\,\,\vdots \\ &\geq (1 + \alpha)^{t-1} \\ \end{split}\]

Ma allora \(|I_{\tau}| \geq n/2\) per qualche \(\tau = O(\log n)\), e quindi il numero di nodi che si trovano a distanza \(\tau\) da \(s\) sono almeno \(n/2\).

Consideriamo adesso un qualsiasi altro nodo \(w \in V - I_{\tau}\) e ripetiamo lo stesso procedimento di prima per costruirci i vari \(I^{'}_t\). Nuovamente otteniamo che dopo \(\tau^{'} = O(\log n)\) passi, il size di \(|I^{'}_{\tau^{'}}|\) è almeno \(n/2\).

Osserviamo che i due alberi costruiti dalle BFS effettuate sui nodi \(s\) e \(w\) devono necessariamente condividere almeno un nodo, oppure devono essere connessi da almeno un arco. Infatti, se condividono un nodo abbiamo fatto. Altrimenti, dal fatto che \(|I_{\tau}| \geq n/2\) e \(|I^{'}_{\tau^{'}}| \geq n/2\) ne consegue che \(N(I^{'}_{\tau^{'}}) \cap I_{\tau} \neq \emptyset\), in quanto altrimenti entrerei in conflitto con il fatto che

\[\Big( N(I^{'}_{\tau^{'}}) \subseteq V = I_{\tau} \cup I_{\tau^{'}} \Big) \land \Big(N(I^{'}_{\tau^{'}}) \cap I^{'}_{\tau^{'}} = \emptyset \Big)\]

Ma allora data una qualsiasi coppia di nodi \(u, v \in V\), possiamo sempre trovare un cammino di lunghezza \(O(\log n)\) tra \(u\) e \(v\). Da questo segue che il diametro di \(G_n\) è \(O(\log n)\).

\[\tag*{$\blacksquare$}\]