Skip to content

Più amici di quanti ne hai te

3 marzo 2014

Le reti sociali esistono da sempre ma la traduzione inglese della locuzione è ormai carica dello specifico riferirsi alle piattaforme informatiche che collegano le persone attraverso il web. Come diceva un filosofo, un mondo di solitudini legate via Internét.

L’uso di questi strumenti non è privo di rischi, alcuni peculiari delle reti virtuali, altri comuni alle reti sociali tradizionali. Ad esempio, potrebbe essere causa di emozioni negative constatare che i tuoi amici hanno, in media, più amici di te. A parte il tuo caso, questo è mediamente vero per i membri di ogni rete. Vediamo due dimostrazioni per due diversi modi di interpretare quel “in media”, per adesso troppo vago.

Da un articolo di sociologia

Nell’articolo intitolato Why your friends have more friends that you do, scritto nel ’91 da Scott Feld, il fenomeno è stato riscontrato tra i legami di amicizia degli studenti di una scuola. Per fissare le idee, traduciamo nel linguaggio della teoria dei grafi le considerazioni dell’autore. Un grafo è un modello molto comodo per le reti di amicizia: comprende un insieme V di vertici, che chiamiamo u, v, ecc, che in questo caso rappresentano singoli studenti, e un insieme E di archi, come (u, v), che indicano amicizia tra u e v.

Il numero di archi che partono dal vertice v è indicato con \mbox{deg}(v). Nel nostro caso, \mbox{deg}(v) rappresenta il numero di amici di v. Quanti sono, in tutto, gli amici di amici? Lo studente u ha \mbox{deg}(u) amici. Questi sono amici di amici per ognuno di questi \mbox{deg}(u), per un totale di \mbox{deg}(u)^2. Sembra uno scioglilingua, quindi facciamo un caso concreto: u è legato ad a, b e c, quindi \mbox{deg}(u) = 3. Questi 3 individui sono amici di u, che a sua volta è amico di a, di b e di c, quindi la presenza di u apporta al grafo ben 9 amici di amici. L’amicizia è riflessiva, e ogni nodo è amico di un suo amico.

Considerando tutti i nodi, in totale ci sono \sum_u \mbox{deg}(u)^2 amici di amici, avendo indicato con \sum_u la somma estesa a tutti i nodi del grafo. Per i nodi dello stesso grafo ci sono in tutto \sum_v \mbox{deg}(v) amici, che si spartiscono questi amici di amici. Ne concludiamo che

\frac{\sum_u \mbox{deg}(u)^2}{\sum_v \mbox{deg}(v)}

è la media degli amici posseduti da ogni amico. Vediamo come questo numero non può essere minore della media degli amici posseduti da ogni nodo.

Indichiamo con |V| il numero totale di nodi del grafo e con X la variabile che rappresenta il numero di vicini di un nodo. Il termine vicino è più tecnico, ma da qui in avanti lo usiamo in modo intercambiabile con quello di amico. Il numero medio di vicini è dato dal rapporto tra il numero totale dei vicini e il numero dei nodi,

\mu(X) = \frac{1}{|V|} \sum_v \mbox{deg}(v).

Ricordiamo che la varianza di una variabile può essere calcolata come differenza tra la media dei quadrati della variabile e il quadrato della media. La varianza di X è

\sigma^2(X) = \mu(X^2) - \left( \mu(X) \right)^2 = \frac{1}{|V|} \sum_u \mbox{deg}(u)^2 - \left( \mu(X) \right)^2.

Dividendo per \mu(X), operazione valida perché per un grafo con almeno un arco il numero medio di amici per nodo è strettamente positivo, abbiamo

\frac{\sigma^2(X)}{\mu(X)} = \frac{\frac{1}{|V|} \sum_u \mbox{deg}(u)^2}{\frac{1}{|V|} \sum_v \mbox{deg}(v)} - \mu(X)

e dunque la media degli amici degli amici è una funzione della media e della varianza degli amici, cioè

\frac{\sum_u \mbox{deg}(u)^2}{\sum_v \mbox{deg}(v)^2} = \mu(X) + \frac{\sigma^2(X)}{\mu(X)}.

La varianza di una variabile è un un numero nonnegativo, e quindi

\frac{\sum_u \mbox{deg}(u)^2}{\sum_v \mbox{deg}(v)} \geq \mu(X).

In questo senso, in media, i vicini di un nodo hanno più vicini di quanti ne abbia il nodo stesso.

Dalla pigrizia nel reperire la fonte

Prima di leggere l’articolo di Feld ho provato a immaginarmi cosa volesse dire l’affermazione sugli amici di amici. Presento quindi un’interpretazione alternativa e relativo tentativo di dimostrazione.

Prima di iniziare, torniamo un secondo alla media dei vicini, calcolata con \frac{1}{|V|} \sum_v \mbox{deg}(v). La sommatoria conta ogni arco (u, v) del grafo due volte, perché attraversato una volta partendo da u e una partendo da v. Questo fatto, noto come il lemma delle strette di mano, ci permette di scrivere

\frac{1}{|V|} \sum_v \mbox{deg}(v) = 2 \frac{|E|}{|V|}.

Il nodo v ha \mbox{deg}(v) amici. Indicando con u \sim v il generico nodo u amico di v, il numero totale e medio degli amici di amici di v è rispettivamente \sum_{u\sim v} \mbox{deg}(u) e \sum_{u\sim v} \frac{\mbox{deg}(u)}{\mbox{deg}(v)}. Sommando tutte le medie e dividendo per il numero di nodi si ottiene la media del numero medio di amici di amici. Terribile. Eccola:

\frac{1}{|V|}\sum_v \sum_{u\sim v} \frac{\mbox{deg}(u)}{\mbox{deg}(v)}.

Stiamo sommando il rapporto \frac{\mbox{deg}(u)}{\mbox{deg}(v)} per ogni coppia ordinata di nodi v e u\sim v, quindi alternativamente possiamo considerare le coppie non ordinate che costituiscono gli archi del grafo, e per ognuna di queste sommare due rapporti invertendo i ruoli dei nodi:

\frac{1}{|V|}\sum_v \sum_{u\sim v} \frac{\mbox{deg}(u)}{\mbox{deg}(v)} = \frac{1}{|V|} \sum_{(u, v) \in E} \left( \frac{\mbox{deg}(u)}{\mbox{deg}(v)} + \frac{\mbox{deg}(v)}{\mbox{deg}(u)} \right).

Adesso, tanto per introdurre un po’ di varietà alla nostra vita quotidiana, usiamo la disuguaglianza aritmetico-geometrica, nella sua forma che dice che se x e y sono numeri positivi, allora x+y \geq 2\sqrt{xy}. Usando per x e y i due rapporti, il cui prodotto è convenientemente uguale a 1, si ha che per ogni addendo della sommatoria

\frac{\mbox{deg}(u)}{\mbox{deg}(v)} + \frac{\mbox{deg}(v)}{\mbox{deg}(u)} \geq 2

e siamo così giunti a dire che

\frac{1}{|V|}\sum_v \sum_{u\sim v} \frac{\mbox{deg}(u)}{\mbox{deg}(v)} \geq \frac{2}{|V|} \sum_{(u, v) \in E} 1 = 2\frac{|E|}{|V|}

perché ora la sommatoria conta semplicemente il numero di elementi di E. L’ultimo valore a destra, come visto, corrisponde alla media dei vicini, e abbiamo così provato la tesi.

Una conclusione e un problema

Le due definizioni di numero medio di amici degli amici non sono identiche, perché non è lo stesso fare la media di rapporti o fare il rapporto tra numeratore e denominatore medi. Sono tuttavia abbastanza simili e catturano entrambe una proprietà, quella di essere almeno pari al numero medio di amici per nodo, che è valida per tutti i grafi e per tutte le reti, sociali e non.

La disuguaglianza dimostrata non è stretta. Quand’è che diventa un’uguaglianza? Quando ogni nodo ha lo stesso numero di vicini. In questo caso succede, nella prima formula, che \sigma^2(X) = 0, e nella seconda che è sempre \frac{\mbox{deg}(u)}{\mbox{deg}(v)} = 1.

Per ultimo, un calcolo di \mu(X) su un grafo molto semplice, che si costruisce per passi successivi. Al primo passo c’è un singolo nodo che capricciosamente decidiamo di chiamare uomo e di farlo passare per una strada di Camogli.

Questo nodo è collegato a sette altri nodi. Stiamo descrivendo un grafo ad albero con fattore di ramificazione pari a 7, e questi nodi sono genericamente chiamati nodi figli. Tuttavia, per proseguire il capriccio, li chiamiamo nodi mogli.

Ogni moglie è collegata, oltre all’uomo, a sette nodi detti sacche, con dentro sette gatte, con sette gattini… Continuiamo all’infinito ad aggiungere sette nodi per ogni nodo del passo precedente. Quanto vale in media il numero di vicini per i nodi di questo grafo?

Più amici di quanti ne hai te


Un grafo è formato da un nodo radice, collegato con 7 nodi figlio, ciascuno dei quali a sua volta è collegato con 7 nodi figlio e così via per k iterazioni. Qual è il numero medio di vicini di un nodo preso a caso di questo grafo se k\rightarrow \infty?

Annunci
No comments yet

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: