---
# System prepended metadata

title: Social Network Analysis
tags: [DataScience]

---

---
title: Social Network Analysis
tags: DataScience
description: Blocco slide parte 9
---

# Introduzione

La Social Network Analysis (SNA) è una metodologia versatile che precede Twitter e Facebook di almeno 30 anni ma che ha conosciuto grande popolarità di recente. La SNA può essere descritta come uno «studio delle relazioni umane per mezzo della teoria dei grafi». 

**La SNA si basa su un concetto centrale: le nostre relazioni, prese nel loro insieme, definiscono chi siamo e come agiamo.** Pertanto, osservando e studiando tali relazioni possiamo rispondere a molte domande riguardo al nostro comportamento sociale. **Le relazioni possono essere direzionali o simmetriche e binarie o con valori**: «Max segue Alex su Twitter» è una relazione binaria mentre «Max ha risposto a 4 tweet di Alex» è con valore. Un modo utile per misurare la relazione interpersonale è la frequenza di comunicazione. Naturalmente, ciò potrebbe non essere vero in molti contesti, ma, in molti casi, in mancanza di meglio, la frequenza di comunicazione funziona.

Un approccio inizialmente adottato per lo studio di relazioni si basava sull'analisi statistica (ad esempio facendo uso della regressione multivariata). L’approccio statistico standard, tuttavia, si basa sull’assunzione che ciascun evento è completamente indipendente dagli altri, mentre in realtà in un social network non lo sono. Ciò rende i metodi statistici tradizionali inadatti. L'approccio più moderno, invece, fa uso delle **reti**.

## La potenza dei social network

Le rivoluzioni che hanno coinvolto il mondo Arabo nell’inverno del 2011 sono spesso chiamate «Le rivoluzioni di Twitter». Esse non sono state le prime essendo state precedute dalle rivoluzioni in Moldavia e in Iran, tuttavia le rivoluzioni in Tunisia ed Egitto hanno rappresentato la più grande e pubblica sfida all’ordine mondiale esistente, a causa dell'uso dei social network. Ma perché i social media sono divenuti così potenti? La risposta sta nella loro capacità di mantenere e amplificare i **weak ties**.

Questi sono definiti come connessioni sociali tra persone che non richiedono nessun attaccamento emotivo, che concordano in alcune cose, pur potendo avere una similarità complessiva bassa. In altre parole esse non richiedono grande tempo o sforzo per mantenersi, e tuttavia sono estremamente potenti.

Mark Granovetter ha mostrato come i weak ties in una rete tra persone possono trasportare l’informazione tra grandi distanze, sia fisiche che sociali. Il basso contenuto emotivo evita il rischio di conflitti; la bassa frequenza di comunicazione fa si che quando viene attivata una comunicazione questa sia innovativa. I social media aiutano a minimizzare il tempo e il costo di mantenere un gran numero di weak ties e, quindi, ad accrescere il numero potenziale di persone che possono essere raggiunte (in quanto esiste una limitazione biologica sulle persone con cui si può mantenere un contatto).

Inoltre, la relazione asimmetrica «follow» di Twitter consente una comunicazione broadcast trasformando delle persone sconosciute in celebrità: esse devono solo essere al posto giusto al momento giusto, con la conseguenza che un piccolo numero di persone sono state capaci di generare una risposta spaventosa. Questo non dipende dal numero di follower che aveva la persona quanto dal fatto che essa era immersa in un cluster denso di persone con gli stessi pensieri. 

Più in generale le reti informali hanno una grande rilevanza, e si formano in tutti i contesti (esempio prigione sulle slide)

Per questo motivo, lo studio di social network può essere estremamente rilevante, vista la loro importanza di questi tempi.

# Teoria dei grafi

Una social network può essere vista come una collezione di frasi che descrivono relazioni; ad esempio, «Alice – Ama – Bob». Una frase di questo tipo rappresenta l’unità di base della SNA ed è chiamata diade. Ciascuna diade rappresenta una relazione – un arco nella tradizionale teoria dei grafi. I nomi nella frase rappresentano le persone coinvolte nella relazione – essi sono chiamati vertici o nodi.

Nella SNA i nodi hanno un tipo; possono rappresentare persone, hashtag, etc. Se un grafo contiene nodi di un solo tipo è chiamato 1-mode graph; se contiene nodi di due tipi esso è bimodale o 2-mode. Esistono anche grafi multi-modali. Nel seguito considereremo 1-mode graph.

Per il momento faremo un’assunzione forte, ovvero che tutti gli archi della rete utilizzino un singolo verbo consistente. Questa assunzione, molto limitativa nella pratica, può funzionare nelle social network dove la semantica di una relazione è definita fortemente dagli sviluppatori. In alcune istanze gli archi possono avere un valore numerico, ottenuto tramite scale oggettive piuttosto che soggettive.

## Modi di rappresentazione

Il modo più classico di rappresentare matematicamente una social network è tramite una matrice, detta **matrice di adiacenza**. Il principale difetto delle matrici di adiacenza è che i 0 (archi non presenti) richiedono la stessa quantità di memoria delle altre celle. In particolare 
molte social network reali (rapporto tra celle non-zero e ) hanno una densità dello 0.1%

La soluzione al problema della densità è rappresentato dalle **liste di adiacenza**. Questa rappresentazione richiede molto meno spazio ma ha lo svantaggio che consente solo di iterare sugli archi ma non di effettuare ricerche o attraversamenti veloci del grafo. Anche con strutture più agevoli, questa rappresentazione è difficile da elaborare con i database.

## Indici di base

L’indice più importante per un grafo è la sua dimensione (size), che consiste nel numero dei suoi nodi. 

Dato un nodo $v_i$, se il grafo è indiretto, il numero di archi che connettono $v_i$ agli altri nodi del grafo rappresenta il degree di $v_i$. Se il grafo è diretto, il numero di archi entranti in (risp., uscenti da) $v_i$ rappresenta l’indegree (risp., l’outdegree) di $v_i$.

Se il grafo è indiretto possiamo definire il mean degree come il rapporto tra la somma dei degree dei suoi nodi e il numero di nodi. In modo analogo, se il grafo è diretto, possiamo definire il mean indegree e il mean outdegree.

Se il grafo non è pesato, la densità è semplicemente il rapporto dei suoi archi rispetto al numero dei suoi possibili archi. Se il grafo è pesato, la densità può essere definita come il rapporto della somma dei pesi degli archi esistenti rispetto al numero dei possibili archi.

## Attraversamento di grafi e distanze

Quando parliamo di attraversamento o di crawling di un grafo intendiamo un algoritmo che, partendo da un punto iniziale, segue i link ai suoi vicini, ai vicini dei suoi vicini, e così via. Alcuni algoritmi sono progettati per trovare il percorso più breve da un punto A ad un punto B; altri tentano di percorrere l’intero grafo per comprendere o campionare la sua struttura – tutti, comunque, hanno delle proprietà comuni. 

### Depth-First Traversal e Breadth-First Traversal

Depth-First Search (DFS) è una ricerca che attraversa sistematicamente i nodi fino a quando non raggiunge il suo obiettivo. Nel contesto di un albero, la DFS esplora in profondità: attraversa sempre un nodo figlio fino a raggiungere una foglia, da lì, tramite backtracking, passa allo 'zio' più vicino e riprende la discesa. In un grafo non ci sono figli o fratelli, ma solo vicini. In questo caso, la DFS può produrre un albero ricoprente dei nodi che ha visitato

Breadth-first traversal o search (BFS) è l’opposto della DFS: essa visita prima tutti i vicini immediati e solo dopo procede con i loro vicini.

### Path e walk

Un **walk** è una sequenza alternata di nodi ed archi che li connettono. E' aperto se i nodi di partenza e destinazione sono differenti, chiuso altrimenti. Se il grafo non è pesato, La lunghezza di un walk è data dal numero di archi; altrimenti la lunghezza di un wall è data dalla somma dei pesi degli archi.

Un **path** è un walk aperto e semplice (dove nessun nodo è attraversato due volte). Un walk semplice chiuso viene detto **ciclo**. Formalmente un path può avere lunghezza 0, mentre un ciclo no.

Un **trail** è un walk che include ciascun arco non più di una volta. Un **tour** è un walk chiuso che comprende ciascun arco del grafo almeno una volta

Dati due nodi di un grafo $v_i$ e $v_j$, la loro **distanza geodesica** è data dalla lunghezza dello shortest path da $v_i$ a $v_j$. Dato un nodo $v_i$, l’**eccentricità** di $v_i$ è data dalla massima distanza geodesica tra $v_i$ e ogni altro nodo del grafo. Il **raggio** di un grafo è pari alla minima eccentricità tra tutti i suoi nodi. Il **diametro** di un grafo è dato dalla massima eccentricità tra tutti i suoi nodi.

### Algoritmo di Dijkstra

Per un certo vertice trova il percorso con costo minimo verso tutti gli altri vertici, dove il «costo» viene determinato sommando i pesi degli archi.

### Distanza nei grafi

La distanza in un grafo è un’astrazione del concetto di walk – ignoriamo il processo di walk e consideriamo quanto sono lontani o vicini i nodi. La distanza in un grafo può essere misurata in vari modi:

- **Shortest path** (su un grafo non pesato); è la misura più semplice di distanza e rappresenta il numero di archi che uno deve attraversare da A a B
- **Cost-based shortest path** (su un grafo pesato). La distanza da A a B sarà pari alla somma delle distanze tra i punti intermedi. Il path più breve, in questo caso, è quello con la distanza minore e non necessariamente quello con meno nodi.
- **Distanza euclidea**. In questo caso ciascun nodo è trattato come un punto nello spazio euclideo. La distanza tra due punti in quello spazio è proporzionale al numero di vicini comuni condivisi tra i due nodi.

La distanza nelle social network ci da un’indicazione di come è probabile che si propaghi l’informazione, e tramite essa possiamo misurare l’influenza di un partecipante ad una social network:

- In un grafo non pesato, la distanza è proporzionale all’abilità dell’informazione di viaggiare da Alice a Bob. 
- In un grafo pesato con le frequenze delle singole comunicazioni, la distanza ci dice quanto velocemente l’informazione può diffondersi da Alice a Bob
- Nodi con distanze euclidee basse hanno connessioni simili sulla rete e, pertanto, possono avere ruoli simili o equivalenti. E’ possibile identificare i nodi in base alla loro distanza relativa in modo tale da costruire dei cluster

## Six degrees of separation

Ogni persona può essere collegata a qualunque altra persona attraverso una catena di conoscenze e relazioni con non più di $5$ intermediari. Questo ha senso perchè mediamente una persona ha $150$ contatti, e $150^6 >> 8\,miliardi$. In realtà mediamente servono 20 persone! 

## Small world networks

Consideriamo una rete reticolare, in cui ciascun nodo è connesso a pochi vicini in modo molto regolare. Un path da un lato all’altro di questa rete può essere piuttosto lungo. Perturbando ora la rete cancellando alcuni archi e rimpiazzandoli con altri archi random, si nota che il diametro della rete scende senza modificare in modo pesante la forma del grafo. Questo tipo di reti sono chiamate «small world networks»; essi mantengono una struttura con vicinato locale ma consentono a un piccolo numero di archi di andare lontano.

![Esempio dell'esperimento sopra descritto](https://i.imgur.com/TcP6e3o.png)

Si ritiene che reti di questo tipo dominino lo scenario delle social network. Queste reti consistono di comunità di vicinati densi che sono debolmente connessi da boundary spanners.

# Dai grafi alle social networks

Finora abbiamo considerato dei concetti astratti della teoria dei grafi. Ora iniziamo ad usare tali concetti per analizzare delle social network reali.

## Campionamento

Nella Network Analysis una dei problemi più comuni riguarda lo sforzo computazionale necessario per effettuare delle analisi, risolvibile tramite l'adozione del campionamento, che consentono l’estrazione di conoscenza su una rete analizzando soltanto una sua parte. Chiaramente, il modo in cui il campione viene scelto diventa cruciale per estrarre conoscenza senza errori o, almeno, per minimizzare l’entità degli errori.

A tal fine problematiche importanti da considerare sono le seguenti:

- Che approcci di campionamento è necessario usare?
- Di quanto il grafo campionato deve essere ridotto rispetto al grafo originario?
- Come le misure di un campione possono essere scalate per fornire le stime della rete corrispondente che, generalmente, è molto più grande?

## Centralità

Una delle prime analisi in una social network consiste nel misurare il potere o l’influenza dei componenti, sulla base delle loro connessioni. Tuttavia, non c’è unanimità in letteratura su che cosa voglia dire potere o influenza, comporanto l'esistenza di diverse soluzioni (**misure di centralità**). In ogni caso, il concetto di centralità non può prescindere dai dati.

### Ricerca delle celebrità

Ciascuna comunità ha delle persone che sono significativamente più popolari di altre. Generalmente sono molto pochi e sono di ordini di grandezza più popolari degli altri. 

La prima e più semplice metrica di centralità ci aiuterà a trovare queste celebrità, ed è chiamata **degree centrality**: il grado di un nodo rappresenta il numero di connessioni che esso ha; su Twitter è il numero di follower ad esempio. Per cui, i nodi con il massimo grado potrebbero essere quelli più influenti. (A in figura)


![](https://i.imgur.com/S79LYk4.png)

### Ricerca dei mercanti di gossip

La capacità di un nodo di ricevere e inviare informazioni agli altri dipende fortemente dalla distanza tra esso e il resto della rete, e la capacità di spostare informazioni da un lato all’altro della rete è un passo importante nell’obiettivo di stabilire una percezione condivisa del mondo. Così, la distanza dagli altri può definire il ruolo di una persona in una rete. Il principio alla base di questo fenomeno è la metrica di **closeness centrality**.

Il calcolo della closeness centrality è piuttosto costoso:
- Calcola il path più breve tra ciascuna coppia di nodi utilizzando l’algoritmo di Dijkstra, e memorizza queste distanze in una tabella
- Per ciascun nodo somma le distanze tra esso e tutti gli altri nodi. La closeness distance è pari al reciproco di questa somma.

Il risultato è un numero tra 0 e 1; numeri più alti implicano maggiori vicinanze e quindi minori distanze

### Ricerca dei colli di bottiglia o dei bridge in una comunità

La **betweennes centrality** è basata sull’assunzione che un individuo può guadagnare potere se presidia un collo di bottiglia per la comunicazione. 

Nella figura seguente, il nodo D è chiaramente in una posizione di potere in quanto tutte le comunicazioni tra i nodi A, B e C, da una parte, ed E, F e G dall’altra devono passare da D.
![](https://i.imgur.com/EyhiFY3.png)

La betweenness centrality ha anche un altro ruolo – essa è in grado di identificare gli individui che agiscono da bridge tra due o più comunità che altrimenti non riuscirebbero a comunicare l’una con l’altra.

L’algoritmo per il calcolo della betweenness centrality (piuttosto costoso) è il seguente:
- Si calcolano gli shortest path tra ciascuna coppia di nodi utilizzando l’Algoritmo di Dijkstra
- Per ciascun nodo I della rete si conta il numero di shortest path in cui I è coinvolto
-  Si normalizza tale numero in modo da portare il risultato tra 0 e 1

Nella rete precedente la betwenness centrality di tutti i nodi è 0, eccetto quella per il nodo D che è circa 0.6

### Eigenvector centrality

Un’eminenza grigia è un consigliere o un decisore potente che opera segretamente e in modo non ufficiale.

Per trovarli in una rete, Philip Bonacich propose che, invece di contare il numero di link che connettono un nodo, sarebbe necessario effettuare una media pesata pesando ciascun link sulla base del grado dell’altro nodo. L’**eigenvector centrality** si basa su tale principio, e secondo questa metrica un nodo è centrale se è connesso a molti nodi che sono, a loro volta, centrali.

L’algoritmo per il calcolo di questa centralità è il seguente:

1. Si inizia assegnando un grado di centralità pari ad 1 a tutti i nodi
2. Si ricalcolano i punteggi di ciascun nodo come una media pesata delle centralità di tutti i nodi appartenenti al suo vicinato:
$$
v_i = \sum_{j\in N} x_{ij} * v_{j}
$$
3. Si normalizzano i numeri così ottenuti dividendo ciascun valore per quello massimo
4. Si ripetono i passi 2 e 3 fino a quando i valori non cambiano o cambiano di poco

Potrebbero essere necessarie centinaia di iterazioni prima di convergere; pertanto, tale metrica non è realistica per reti molto grandi.

### PageRank

PageRank è una metrica di centralità sviluppata da google che è stata inizialmente sviluppata per indicizzare la pagine Web, ma può essere applicata anche alle social network.

PageRank ha capovolto l’idea di centralità: invece di considerare la centralità come qualcosa che si irradia da un nodo, considera la centralità partendo dai link in ingresso. Il PageRank di un nodo A, infatti, rappresenta la probabilità che una persona che sta navigando attraverso dei link arrivi ad A.

Il calcolo del PageRank è iterativo. In qualunque istante restituisce un risultato, ma se più volte restituisce lo stesso valore, la qualità dei risultati cresce fortemente. Mentre il calcolo del PageRank è per natura locale (si prendono in considerazione soltanto i vicini immediati), la sua natura iterativa consente all’influenza globale di propagarsi attraverso la rete, sebbene in modo molto attenuato, proprio come accade nel mondo reale.

PageRank è simile all’eigenvector centrality ma è molto più scalabile.

### Cosa non ci possono dire le metriche di centralità

Le misure di centralità, mentre consentono di comprendere le forze in gioco nella social network, sono essenzialmente misure di tipo puntuale. Quello che non ci dicono queste misure è come (o, meglio, perché) il visionario con un alto grado di centralità è circondato da tanti fan, cosa porta le persone a prendere una posizione in un dibattito, a mettersi insieme o ad isolarsi. Per capire queste cose bisogna andare oltre le misure di centralità. Per questo, nel seguito, esamineremo le triadi, che può essere visto come il più piccolo insieme di persone che formano una società.

## Clique, cluster e componenti

### Componenti e sottografi

Un **sottografo** è un sottoinsieme dei nodi di una rete e di tutti gli archi che collegano questi nodi. Ciascun gruppo di nodi può formare un sottografo. I **sottografi componenti** (o, semplicemente, **componenti**) sono porzioni della rete disconnessi l’una dall’altra. 

Per le reti dirette è possibile definire due diversi tipi di componenti:
- Un componente debole è un insieme di nodi che sono connessi, a prescindere dalla direzione degli archi
- Un componente forte considera anche la direzione degli archi quando verifica la connessione dei nodi

La nozione di componente può essere troppo forte per alcuni contesti, così, per i componenti, sono state proposte delle definizioni più flessibili.

### Ego network

Le ego network sono sottoreti centrate su un certo nodo, e si possono derivare applicando la BFS e limitando la profondità della ricerca (raggio della rete) ad un valore piccolo, generalmente non superiore a 3. Mentre nella BFS tradizionale si costruisce un albero considerando soltanto i link attraversati, per costruire una ego network è necessario catturare tutti i link tra i vicini di un nodo. Il vincolo di raggio pari a 3 è legato al concetto dell’Orizzonte di Osservabilità visto in precedenza. **(?)**

### Clustering coefficient

Il clustering coefficient misura la proporzione degli amici di un nodo che sono anche amici tra di loro (ovvero, quanta affidabilità reciproca hanno le persone tra loro).

Questa metrica può essere applicata a qualunque rete ma in genere la semantica è difficile da definire. Per le ego network è semplice: alto clustering coefficient implica ego network dense con molta fiducia reciproca tra i partecipanti; basso clustering coefficient è tipico di reti a stella in cui una persona invia messaggi e tutti gli altri ascoltano. 

## Triadi

Una triade non è altro che un insieme di tre nodi. Tutte le possibili triadi con archi non diretti sono mostrate nella seguente figura:

![](https://i.imgur.com/Dmxof7U.png)

Come si può notare, le prime due hanno tutti i loro nodi interconnessi e, pertanto, presentano un interesse significativo. Ci sono 16 possibili triadi dirette.
In un altro studio sociologico è stato dimostrato che:

- I vincoli asimmetrici (io amo te più di quanto tu ami me) sono i meno stabili di tutti
- I vincoli simmetrici sono significativamente più stabili
- Le strutture a triadi, però, sono le più stabili nel tempo

### Buchi strutturali

Ci sono varie situazioni in cui è necessario assicurarsi che i due estremi di una triade aperta non comunichino mai direttamente, ovvero non formano mai un link. Nel seguito chiameremo **buchi strutturali** queste triadi aperte. I buchi strutturali possono avere un’altra missione, ovvero quella di collegare intere comunità, come è possibile vedere di seguito:

![](https://i.imgur.com/9hJp0XE.png)

### Triadi dirette

La seguente figura mostra tutte le possibili triadi dirette. In questo caso abbiamo 16 possibili varianti, mostrate nella figura seguente:


![](https://i.imgur.com/U9sU9R9.png)


Un modo per catalogarle, illustrato in figura, è descritto di seguito. Le triadi sono numerate da 1 a 16 e hanno un codice ad esse associato:

- Il primo numero è il numero di archi bidirezionali
- Il secondo numero è il numero di archi singoli
- Il terzo numero è il numero di archi non esistenti
- Una lettera consente di distinguere varianti dirette della stessa triade: U sta per «up», D sta per «down», C sta per «circle» e T per «transitive» (ovvero, presenza di due path che conducono allo stesso punto finale)

Le triadi 1-3 nella figura sono non connesse, le triadi 4-8 e 11 rappresentano varianti dei buchi strutturali, le triadi 9, 10 e 12-16 sono varianti di triadi chiuse. 

Il processo delle analisi delle triadi in una rete reale viene denominato **triad census**. In questo processo, per ciascun nodo, vengono contate le occorrenze dei 16 tipi di triadi per determinare il ruolo del nodo nella struttura della rete.

Anche il rapporto tra buchi strutturali e triadi chiuse è importante – una gerarchia è largamente composta da buchi strutturali mentre delle strutture più ugualitarie avrebbero un rapporto di triadi chiuse maggiore.

## Clique

Una clique è definita come un sottoinsieme completo massimale (nessun altro nodo può essere aggiunto alla clique senza renderla meno connessa) di un certo grafo, ovvero un gruppo di nodi dove ciascuno è connesso direttamente a tutti gli altri. 

Essenzialmente, una clique consiste di diverse triadi chiuse che si sovrappongono, ed eredita molte delle proprietà di generazione di cultura e di amplificazione tipiche delle triadi chiuse. 

Questa definizione rigorosa di clique tuttavia può essere troppo forte in diverse situazioni, infatti ci possono essere dei casi in cui alcuni membri non sono così fortemente connessi. Per catturare questi casi è possibile rilassare la definizione di clique. Un modo per fare ciò è considerare come membro di una clique un nodo se esso è connesso a ciascun altro nodo della clique anche indirettamente. Questa definizione di clique viene chiamata **$N$-clique**, dove $N$ sta per la massima lunghezza per il path di collegamento tra nodi permesso.

Questa definizione di $N$-clique presenta alcune debolezze, per esempio tende a restituire delle clique lunghe e strette. Inoltre, le $N$-clique hanno delle proprietà indesiderabili in molti contesti applicativi. Per esempio, alcuni nodi delle $N$-clique potrebbero essere connessi da nodi che, a loro volta, non sono membri della $N$-clique. Per superare quest’ultimo problema, è possibile richiedere che la path distance tra due nodi qualunque di una $N$-clique soddisfi una ulteriore condizione che forza tutti i link tra i membri di una $N$-clique a coinvolgere solo altri membri della $N$-clique. La struttura così ottenuta si chiama **$N$-clan**.

Un modo alternativo di rilassare la definizione rigorosa di clique consiste nel consentire ai nodi di essere membri di una clique se essi sono collegati ad almeno $N-k$ nodi di quella clique (dove $N$ è la cardinalità del sottografo). Questo rilassamento porta alla definizione di **$k$-plex**. Mentre l’approccio ad $N$-clique porta a delle clique lunghe e strette, l’approccio a $k$-plex restituisce un gran numero di raggruppamenti più piccoli.

Un **$k$-core** è un gruppo massimale di nodi ciascuno dei quali connessi ad almeno $k$ altri nodi del gruppo. L’approccio $k$-core è più rilassato rispetto all’approccio $k$-plex; infatti, esso consente ad un nodo di unirisi al gruppo se è connesso a $k$ nodi, indipendentemente da quanti sono i nodi a cui esso non è connesso. I $k$-core sono generalmente più inclusivi dei $k$-plex. Variando il valore di k, possono emergere diverse strutture di gruppi. 

Se la rete è pesata, è possibile introdurre un ultimo concetto, ovvero il concetto di **F-groups**. Gli F-groups restituiscono i gruppi massimali formati da triadi «fortemente transitive» e «debolmente transitive». Una triade fortemente transitiva esiste se c’è un arco $(v_i, v_j, w_{ij})$, un arco $(v_j, v_k, w_{jk})$ e un arco $(v_i, v_k, w_{ik})$ e $w_{ij} = w_{jk} = w_{ik}$. Una triade debolmente transitiva esiste se $w_{ij}$ e $w{jk}$ sono entrambi maggiori di $w{ik}$, ma quest’ultimo è maggiore di un certo valore soglia. 

## Triadi, densità delle reti e conflitti

Finora abbiamo sempre supposto che in una rete ci sia un solo tipo di arco. Nella realtà le cose sono più complesse; supponiamo, ad esempio, che invece di un solo tipo di link ve ne siano due: amicizia e conflitto. 

Possiamo modellare un processo come questo usando poche regole molto semplici:

1. L’amico del mio amico è mio amico (chiusura di un buco strutturale)
2. Il nemico del mio amico è mio nemico (ottenimento di una triade bilanciata)
3. L’amico del mio nemico è mio nemico
4. Il nemico del mio nemico è mio amico

In realtà, le regole 2, 3 e 4 descrivono la stessa triade indiretta ma da diversi punti di vista; chiameremo questa regola «Regola 2»

![](https://i.imgur.com/wzuY6wU.png)

Cominciamo ad analizzare queste regole. Iniziamo con un insieme di nodi non connessi e connettiamoli via via randomaticamente; alla fine otterremo un grafo random semplice con una distribuzione normale dei gradi dei nodi. La densità della rete crescerà fino a quando ogni nodo è connesso ad ogni altro nodo (ottenendo un grafo completo o clique). 

Consideriamo, ora, la Regola 1. Se si scopre una triade aperta A-B-C, con un’elevata probabilità si potrà aggiungere anche il link A-C. Ad un certo punto della costruzione del grafo è stata creata una massa critica di connessioni e ogni nuova connessione è probabile che porti ad una triade aperta. Questa triade aperta viene quindi chiusa dalla Regola 1, che può, a sua volta, creare più triadi aperte, che poi vengono chiuse, e così via. In un certo senso, la rete passa da una crescita lineare ad una crescita esponenziale. Essa diventa virale!

![](https://i.imgur.com/6mfEQNM.png)


Naturalmente, nella realtà, c’è un limite al numero di possibili connessioni nella rete, ovvero una densità di saturazione. Questa densità può essere una proprietà della rete stessa o dell’ambiente in cui si sta sviluppando, oppure, ancora, un risultato della Regola 2. 

Il conflitto viene introdotto nella rete con una probabilità costante, cambiando un singolo arco di amicizia in un arco di inimicizia. Avere molti legami accresce la possibilità di un agente di formare più legami, ma accresce anche la probabilità che un conflitto tra due agenti si diffonda attraverso la rete. Come risultato di ciò, la densità della rete non cresce più fino a quasi il 100% ma, invece, una volta che si raggiunge un secondo valore critico, i conflitti diventano più prominenti e fanno diminuire la densità della rete. Questo tipo di comportamento è chiamato **criticità auto-organizzata**.

![](https://i.imgur.com/H8s6hc4.png)

Se la transazione da una crescita lineare ad una crescita esponenziale (virale) dipende dalle chiusure delle triadi (l’amico di un mio amico è mio amico), allora la massa critica di connessioni può essere stimata misurando la probabilità che un link da A a B creato randomaticamente formi uno o più triadi aperte con gli altri nodi. Ciò è proporzionale al numero di nodi già connessi (raddoppiamo il numero di nodi perché ciascun arco coinvolge due nodi):

$$
P(\text{open_triad}) \sim= \#\text{ties}(2\#\text{nodes})
$$

Così la probabilità di una triade aperta raggiunge il 50% quando un quarto dei nodi sono connessi. In questo caso ciascuna nuova connessione fa si che le regole di chiusura delle triadi creino ulteriori connessioni, accrescendo ulteriormente la probabilità di una cascata. Esperimenti mostrano che la transizione da una crescita lineare ad una **virale** avviene quando la densità è intorno al 7-10%.

Questo vuol dire che se il 7% delle persone di una comunità adottano un comportamento, fanno retweet di un video, si collegano ad un sito, etc. etc. il resto lo farà velocemente in modo virale. Un corollario a ciò è che è molto più facile raggiungere una massa critica in comunità più piccole.

### Esempio: Anatomia di un video virale

Supponiamo di aver fatto un video veramente carino, di averlo postato su YouTube e di aver «twittato» in merito ad esso. Avrà sicuramente successo? Dipende largamente da chi lo vede e da che cosa questo farà con esso dopo. All’inizio, le sole persone che lo vedranno sono quelle della nostra ego-network immediata, ovvero i nostri amici. Pertanto, la crescita del numero di visite è molto lenta; essa è lineare nel tempo, ovvero le visite avvengono con una velocità costante. In questo caso è possibile descrivere il numero di visite come un processo di Poisson, dove ogni atto di vedere il video è indipendente dagli altri. Alla fine, il numero totale di visite che avremmo sarebbe matematicamente correlato al numero di follower, ovvero alla degree centrality.

Ma se accade qualcos’altro e i nostri amici fanno retweet del video ai loro amici, e così via, esponendolo a un numero maggiore di persone, il video può diventare velocemente molto popolare … o forse no. Il passaggio qualitativo da una cosa che ha poco valore a una cosa che «deve essere condivisa» è un passaggio ben preciso denominato massa critica. Se il video fallisce nel raggiungere la massa critica entro un certo periodo di tempo, la sua velocità di adozione inizia a decrescere e alla fine muore. Se, invece, viene raggiunta la massa critica, esso crescerà in modo esponenziale fino a quando raggiungerà il punto di saturazione in cui quasi tutti quelli che avrebbero potuto trasmettere il video lo hanno fatto. Da quel punto in poi il video declinerà.

Una nota importante è che le nozioni di massa critica e saturazione si applicano ad ogni rete o comunità: è possibile per un video raggiungere un punto di saturazione in una comunità ed essere virtualmente sconosciuto in un’altra. Tuttavia, dal momento che le comunità sono tra loro collegate, è possibile per un video passare in una nuova comunità tramite i boundary spanner e trovare una nuova massa critica o persino un punto di saturazione più alto.

### Ancora sulla massa critica

C’è ancora una considerazione da fare sulla massa critica, ovvero il problema del costo di partecipazione. Persino nel mondo dei servizi free ogni cosa ha un costo: potrebbe essere monetario, temporale, di opportunità.

Per un adottante iniziale, il costo è molto reale e i benefici si devono ancora materializzare. Man mano che le persone si uniscono alla rete, i benefici crescono secondo una funzione del numero di connessioni, rendendo la nuova idea o il meme o il sito di social network sempre più conveniente. La massa critica sarà raggiunta allorquando i benefici dell’utilizzo del prodotto iniziano a superare i costi. A questo punto ciascuna connessione porterà, a sua volta, a più connessioni portando ad un aumento ulteriore dei benefici mentre i costi rimangono ancora costanti. Se l’intersezione costi/benefici non viene mai raggiunta, indipendentemente dal numero di connessioni presenti nella rete, quest’ultima alla fine fallirà.

### Il contenuto è (ancora) il re

Nel 1995 si era soliti dire: «Il contenuto è il re». Il contenuto guidava gli utenti al sito, li faceva stare li e li faceva tornare. L’idea è la stessa anche oggi: se il contenuto è avvincente in un modo o nell’altro, i benefici crescono e l’intersezione costi-benefici avviene prima abbassando la massa critica dal 7% al 3%-4%. Invece, se la qualità del contenuto non è molto buona, la massa critica potrebbe non essere raggiunta mai.

Questo è il punto in cui l’analisi quantitativa delle social network si ferma e le teorie su ciò che rende attrattivi i messaggi proliferano. Quando vogliamo sapere se un messaggio si diffonderà attraverso la rete, quello che vogliamo realmente chiedere è: «questo messaggio colpirà i membri della rete»? O, ancora più precisamente, «quanti individui riceveranno il messaggio»? Possiamo spezzare gli effetti del messaggio in numerose variabili:

- Rilevanza: il messaggio mi interessa?
- Salienza: il messaggio mi interessa proprio ora?
- Risonanza: il contenuto del messaggio si concilia con ciò in cui già credevo?
- Severità: quanto buono o cattivo è il contenuto del messaggio?
- Immediatezza: il messaggio richiede un’azione immediata? Combinata con la severità, qual è la conseguenza della inazione?
- Certezza: Ci sono o meno chances che gli effetti di questo messaggio causino gioia o tristezza?
- Sorgente: Da dove viene questo messaggio e mi posso fidare di questa persona? Il messaggio è rafforzato da qualche altra cosa?
- Valore di intrattenimento: il messaggio è simpatico? E’ interessante da leggere?

La valutazione mostrata in precedenza si applica ad uno specifico messaggio (m) e ad una specifica persona ( P ). Tuttavia, ogni persona che riceve il messaggio è probabile che lo giudichi secondo il proprio modo di essere. L’aggregazione di preferenze personali eterogenee è un problema difficile in economia. Per semplificare questo problema molto complesso, supponiamo che tutte le variabili precedenti possano essere scritte come numeri reali compresi tra 0 e 1. In questo caso, ciascun messaggio può essere valutato come:

$$
V_m = \beta_1 * \text{Rilevanza} + \beta_2 * \text{Salienza} + … + \beta_8 * \text{Intrattenimento} \\
\beta_1 + \beta_2 + … + \beta_8 = 1
$$

I valori $\beta$ rappresentano l’importanza di ciascuno dei fattori nell’adozione di un messaggio per uno specifico individuo.

### Come le informazioni modellano le reti (e viceversa)?

Le informazioni, le idee e i punti di vista possono cambiare con una certa rapidità e, nel fare ciò, modellano delle strutture di rete. Allo stesso tempo, la forma delle reti controlla dove si può diffondere l’informazione. Di conseguenza, abbiamo un doppio ciclo in cui la struttura sociale influenza la trasmissione delle informazioni, e le informazioni stimolano cambiamenti nella struttura social. Cerchiamo ora di capire come ciò avviene e tentiamo di costruire un semplice modello dinamico di diffusione dell’informazione.

#### Omofilia

Con il termine «Omofilia» si intende sostanzialmente la creazione di link tra nodi in funzione di quanto questi ultimi sono simili. L'omofilia può essere di due tipi:

- **L’omofilia di stato** vuol dire che gli individui che presentino similarità nella classe sociale, nel livello di benessere e nello stato è più probabile che si associno l’un l’altro
- **L’omofilia di valore** indica una tendenza, da parte di coloro che pensano in modo simile o amano le stesse cose, di associarsi l’un l’altro a prescindere dalla classe sociale o dallo stato

La cultura americana, naturalmente, tende di più verso l’omofilia di valore rispetto ad altre società dove l’appartenenza ad una classe spesso definisce in modo chiaro e non ambiguo le informazioni o gli artefatti culturali a cui uno è esposto. Questo è ancora più evidente online dove «nessuno conosce chi sei», essendo l’identità online di qualcuno infinitamente più malleabile dell’identità offline. Lo stato sociale e la classe possono essere considerati degli attributi permanenti – la mobilità sociale è generalmente un processo troppo lento per essere catturato in uno studio di social network. L’omofilia di valore, invece, viaggia «alla velocità di Internet».

I sociologi hanno osservato un altro fenomeno interessante: mentre l’omofilia rimane una grossa forza sociale, una seconda forza può entrare in gioco se due persone non sono molto simili ma non sono neppure così differenti da limitare la loro capacità di trovare argomenti su cui conservare. Questa forza è la **curiosità** o la ricerca di informazioni. Come conseguenza di queste due forze la probabilità di connessione assume una forma strana a due gobbe come mostrato nella figura seguente: 

![](https://i.imgur.com/2dHMNuU.png)

L’altezza e la locazione della «gobba della curiosità», così come la pendenza della trappola della noia, sono diverse per ciascuna persona e sono collegate al suo amore o odio verso le novità. La caratteristica rappresentata nella parte destra della figura è la «trappola della noia»: incontrare una persona che è esattamente la stessa di noi in tutto non fornisce nessuna informazione e nessun stimolo e la probabilità di connessione diminuisce vertiginosamente. 

#### Weak Ties

Mark Granovetter teorizzò che i legami forti accrescono l’omofilia, così quando uno ha bisogno di informazioni nuove (ad esempio, quando cerca un lavoro), le persone connesse a lui con legami forti probabilmente non potranno offrire nuove informazioni. Al contrario, le persone connesse da legami deboli si possono trovare in posti completamente differenti (in termini di accesso alle informazioni), portando spesso informazioni che difficilmente si otterrebbero da legami forti.

Nel suo articolo che ora è diventato un classico, Robin Dunbar mostra che la dimensione media di una rete sociale umana (ovvero, la degree centrality media) è 150. Egli dimostrò anche che questo numero è cognitivamente limitato dalla dimensione della nostra corteccia prefrontale. E' possibile sezionare tale numero nella seguente piramide:

![](https://i.imgur.com/bOBQqGx.png)

In cima, i nostri legami più forti sono quelli familiari e degli amici più stretti. Il secondo strato è quello della «famiglia estesa»; sono persone con cui non necessariamente si interagisce giornalmente e non si considerano i più vicini. Lo strato successivo, «la tribù», include i colleghi di lavoro, una cerchia di amici e di vicini più larga, e i membri della famiglia più distanti. Lo strato finale comprende tutti gli altri, essenzialmente i **weak ties**.

Come si può vedere dalla precedente descrizione delle relazioni, mano a mano che si scende nella piramide, il contenuto emozionale e la condivisione delle informazioni si abbassa mentre la quantità di persone aumenta (come si può anche osservare dagli amici di Facebook o dai follow di Twitter).

Per una compagnia che deve servire dei clienti, l’impegno di personale nei social media è di primaria importanza proprio per questa ragione. Dal momento che lo scambio avviene pubblicamente, egli sostiene non solo la relazione con un cliente esistente, ma anche un potenziale relazionale percepito con altri follower di Twitter.

Dal momento che ogni persona ha preferenze diverse in merito ai contatti, la piramide può assumere per ciascuno forme molto differenti.

# Two Mode Neworks

Gran parte dei dati disponibili attualmente si trova in formato 2-mode (o bimodale, o bipartito); secondo questo formato, ci sono due diversi tipi di nodi e i link determinano le relazioni tra un insieme di nodi e l’altro.

La seguente figura mostra una semplice rete a 2 modi:

![](https://i.imgur.com/wY0AKJl.png)

Le persone A e B sono entrambe membri di un club. Essenzialmente essi formano una triade aperta, o un buco strutturale. Tuttavia, possiamo inferire che se A e B sono membri del medesimo club, essi si possono conoscere tra loro e, così, inferire che la triade è in realtà chiusa. Questa, ovviamente, è un’inferenza piuttosto debole.  Ma comunque è un inizio. Immaginiamo, ora, che le stesse persone sono membri di più di un club, come mostrato nella parte alta della seguente figura, dove i nodi E, F e H sono co-membri in 2 club. Questa rappresenta un’associazione più forte tra le persone, e allude probabilmente ad una comune identità di gruppo. Possiamo continuare ad accumulare co-membership fino a quando siamo abbastanza certi che le connessioni sono reali, e pesare i link inferiti di conseguenza

![](https://i.imgur.com/v74b83b.png)

La parte inferiore della figura mostra due reti risultanti ottenute per proiezione di quella sopra; si ha una rete di persone i cui link sono determinati dalla co-membership ai gruppi e una rete di gruppi i cui link sono determinati dalla co-membership delle persone. Per creare queste reti, contiamo semplicemente le co-membership per ciascuna delle persone o, alternativamente, per ciascuno dei club. Queste reti possono essere utilizzate con le stesse tipologie di analisi delle altre social network, ma sono particolarmente adatte per l’analisi delle tecniche del metodo delle isole e del clustering, essendo queste essenzialmente reti di similarità o di correlazioni.

Un’altra applicazione dell’analisi delle 2-Mode Network è basata sull’idea di **omofilia**, ovvero sull’idea che le persone che condividono interessi o attributi è più probabile che si parlino l’un l’altro e formino legami rispetto alle persone che sono molto diverse. In questo caso, il grafo bipartito è composto da persone e da informazioni relative agli interessi (keyword, tag...), e può essere usato per suggerimenti di amicizie. Una rete di affiliazione inversa – attributi attraverso le persone – potrebbe anche fornire dei punti di vista interessanti.

Da un punto di vista matematico, data una matrice di adiacenza $A$ $n \times m$, la matrice di adiacenza associata alla proiezione unipartita può essere dato da $AA=A*A^T$. Questo calcolo è in genere costoso per quanto riguarda il tempo. Infatti, la complessità computazionale di questa operazione è $O(n*m*n)$, dove n è la «dimensione esterna» ed m è la «dimensione interna» della moltiplicazione.

## Espandersi alle reti multimodali

In precedenza, abbiamo visto come si lavora con le 2-mode network. Tuttavia, tutti comprendiamo che il mondo è ancora più complesso e che il numero di tipi di nodi e di archi in una rete può essere piuttosto grande. Comunque, la tecnica discussa in precedenza può essere facilmente estesa a qualunque modello di dati orientato alle reti. E’ necessario soltanto tenere traccia di cosa significa in realtà ciascuna rete e ciascuna rete proiettata.

Un esempio può essere data da una rete multimodale costituita da 4 componenti, presente nella seguente figura:

![](https://i.imgur.com/KcO96ft.png)

In formato matriciale, il modello organizzativo è come quello mostrato nella seguente tabella:

![](https://i.imgur.com/RFyTjia.png)

Possiamo trattare ciascuna tabella come una rete bipartita vista in precedenza, per fare le stesse considerazioni fatte in precedenza.

