Skip to content
Torna ai risultati

Centralità di intermediazione

Introdotto da
Freeman, L. C.
Anno
1977
Tipo
Centrality measure
Famiglia
Network science

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

La centralità di intermediazione, formalizzata da Linton C. Freeman nel 1977, misura quante volte un nodo si trova sul cammino minimo che connette ogni altra coppia di nodi in una rete.

I nodi con alta intermediazione agiscono come ponti o intermediari: la loro rimozione frammenta la rete in componenti disconnesse più gravemente della rimozione di qualsiasi altro nodo.

L’intuizione alla base del metodo

Si pensi a una rete stradale cittadina in cui tutte le direttrici trans-regionali convergono su un unico snodo. Quello snodo ha un'intermediazione massima anche se dispone solo di un numero moderato di strade. In una rete sociale, una persona che abitualmente trasmette informazioni tra due gruppi altrimenti disconnessi occupa la stessa posizione: potrebbe non conoscere molte persone direttamente, ma si trova sul percorso critico che tiene unita la rete. La centralità di intermediazione quantifica esattamente quel ruolo di intermediazione, indipendentemente dal numero grezzo di connessioni.

Storia

Linton Freeman ha formalizzato la centralità di intermediazione nel suo fondamentale articolo del 1977 su Sociometry, basandosi su usi informali precedenti del concetto da parte di Bavelas (1948) in esperimenti di comunicazione. La formulazione di Freeman ha unificato diverse intuizioni vaghe sull'importanza dei nodi in un'unica misura calcolabile ed è diventata la definizione canonica utilizzata nella scienza delle reti. L'algoritmo O(VE) di Ulrik Brandes del 2001 ha ridotto il calcolo da O(V^3) a O(VE), rendendo la centralità di intermediazione pratica per reti con migliaia di nodi e consolidando il suo posto come strumento standard nei software di analisi delle reti sociali.

Quando usarlo

Utilizzare la centralità di intermediazione quando la domanda di ricerca riguarda ruoli di intermediazione, gatekeeping o nodi ponte — attori la cui rimozione interromperebbe il flusso di informazioni o la coesione della rete. È appropriata per grafi diretti e non diretti, e per grafi pesati dove i pesi degli archi rappresentano distanza o costo. È particolarmente preziosa nelle reti di comunicazione, reti di citazioni, grafi di collaborazione e catene di approvvigionamento. Non usarla come unica misura di centralità quando l'intermediazione non è il focus teorico: la centralità di grado è più semplice e sufficiente per pure questioni di connettività, e la centralità di autovettore o PageRank catturano meglio la propagazione del prestigio. Evitarla per reti sparse molto grandi senza un'implementazione efficiente, poiché il calcolo ingenuo è O(V^2 E).

Limiti e considerazioni

  • Computazionalmente costoso su reti molto dense anche con l'algoritmo di Brandes; potrebbero essere necessari algoritmi di approssimazione per grafi su scala web.
  • Presuppone che gli attori utilizzino i cammini minimi, il che potrebbe non essere realistico in reti in cui i flussi attraversano percorsi più lunghi (ad es., cammini casuali nelle reti elettriche).
  • Sensibile a archi mancanti o rumorosi: anche pochi legami non osservati possono alterare drasticamente le classifiche di intermediazione.
  • Dà uguale peso a tutti i cammini minimi anche quando le capacità degli archi o le forze delle relazioni differiscono sostanzialmente.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Cattura ruoli strutturali di intermediazione e ponte che la centralità di grado e di autovettore trascurano completamente.
  • Applicabile a reti dirette, non dirette, pesate e non pesate con la stessa formula.
  • Il punteggio normalizzato consente un confronto significativo dei nodi all'interno di una rete e tra reti di dimensioni diverse.
  • L'algoritmo di Brandes rende il calcolo trattabile per reti con milioni di nodi se implementato in librerie ottimizzate come NetworkX o igraph.
  • Interpretazione teorica ben fondata: nodi con alta intermediazione sono empiricamente associati al controllo delle informazioni, al potere e ai buchi strutturali nella ricerca organizzativa e sociale.

Applicazioni

  • Identificare gatekeeper e broker di informazioni nelle reti di comunicazione organizzativa.
  • Rilevare nodi critici di infrastruttura negli studi sulla topologia dei trasporti, delle reti elettriche e di Internet.
  • Trovare autori o articoli intermedi chiave nelle reti di citazioni e collaborazioni.
  • Mappare buchi strutturali e posizioni di intermediazione nelle reti di alleanze interaziendali.
  • Individuare diffusori influenti nei modelli epidemiologici e di diffusione delle voci.
  • Prioritizzare nodi per interventi mirati (ad es., vaccinazione, interruzione) nella ricerca sulla salute pubblica e sulla sicurezza.

Come funziona

Come funziona

1

Per ogni coppia ordinata di nodi distinti (s, t) nella rete, vengono identificati tutti i cammini minimi (geodetiche) tra di essi. Per i grafi pesati, i cammini minimi sono definiti dal peso totale minimo degli archi; per i grafi non pesati, dal minor numero di salti. Questo passaggio stabilisce l'universo dei cammini su cui verrà distribuita l'intermediazione.

2

Per ogni coppia (s, t) viene contato il numero totale di cammini minimi sigma(s, t). Quando esistono più cammini di uguale lunghezza minima, ciascuno viene contato separatamente. Questo denominatore rappresenta il traffico totale sui cammini minimi tra s e t senza alcun vincolo di instradamento.

Formula
\sigma(s,t) = \text{number of shortest paths from } s \text{ to } t
3

Per ogni nodo candidato v (dove v non è né s né t), viene registrato il numero di quei cammini minimi sigma(s, t) che passano effettivamente per v, come sigma(s, t | v). Il rapporto sigma(s, t | v) / sigma(s, t) fornisce la frazione del traffico sui cammini minimi tra s e t che viene instradata attraverso v.

Formula
\sigma(s,t|v) = \text{shortest paths from } s \text{ to } t \text{ passing through } v
4

Queste frazioni vengono sommate su tutte le coppie valide (s, t) per produrre il punteggio grezzo di intermediazione C_B(v). Un nodo la cui rimozione disconnetterebbe molti cammini minimi a coppie accumula una somma elevata, segnalando una posizione di intermediazione strutturalmente critica.

Formula
C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma(s,t|v)}{\sigma(s,t)}
5

I punteggi grezzi crescono con la dimensione della rete, rendendo i confronti tra reti di dimensioni diverse privi di significato. La normalizzazione per (n-1)(n-2)/2 per grafi non diretti (o (n-1)(n-2) per grafi diretti) riscala i punteggi a [0, 1], dove 1.0 significa che il nodo si trova su ogni cammino minimo e 0 significa che non si trova su nessuno. Brandes (2001) ha introdotto un algoritmo O(VE) che calcola simultaneamente tutti i punteggi di intermediazione invece di ripetere la ricerca per ogni nodo.

Formula
C_B^{\text{norm}}(v) = \frac{C_B(v)}{(n-1)(n-2)/2}

Errori comuni

  • Trattare un'alta intermediazione come equivalente a un alto grado senza verificare entrambi; un nodo periferico può classificarsi primo per intermediazione mentre si classifica ultimo per grado.
  • Confrontare punteggi di intermediazione grezzi (non normalizzati) tra reti di dimensioni diverse.
  • Ignorare la direzione degli archi nelle reti dirette, il che può produrre un'identificazione fuorviante degli intermediari quando i flussi sono asimmetrici.
  • Applicare la standard intermediazione a reti pesate senza confermare che i pesi degli archi siano correttamente interpretati come costi (non somiglianze) nell'algoritmo dei cammini minimi.
  • Trascurare metodi di intermediazione approssimata per reti grandi e bloccare il calcolo su milioni di nodi.

Domande frequenti

In che modo la centralità di intermediazione differisce dalla centralità di grado?

La centralità di grado conta le connessioni dirette; un hub con molti legami ottiene un punteggio elevato. La centralità di intermediazione conta quante volte un nodo si trova sui cammini minimi tra altri nodi; un ponte che collega due cluster sparsi ottiene un punteggio elevato anche con pochi legami diretti. Le due misure catturano aspetti ortogonali dell'importanza strutturale.

Dovrei usare punteggi di intermediazione normalizzati o grezzi?

Utilizzare punteggi normalizzati ogni volta che si confrontano nodi tra reti di dimensioni diverse o si presentano risultati a lettori non familiari con la scala della propria rete. I punteggi grezzi sono accettabili solo per confronti all'interno di una singola rete fissa in cui il denominatore è costante.

Come gestisco gli archi pesati?

Impostare i pesi degli archi per rappresentare distanza o costo, non somiglianza. La maggior parte delle implementazioni (NetworkX, igraph) accetta un parametro di peso interpretato come distanza; se i pesi rappresentano forza o somiglianza, invertirli (ad es., peso = 1/somiglianza) prima di calcolare l'intermediazione.

La centralità di intermediazione è significativa per reti disconnesse?

Per grafi disconnessi, i cammini minimi tra nodi in componenti diverse sono indefiniti (infiniti). La maggior parte dei software tratta tali coppie come se contribuissero con zero alla somma, il che può svalutare i punteggi. Analizzare separatamente ogni componente connessa o utilizzare una variante come la centralità di stress con un trattamento esplicito delle coppie disconnesse.

La mia rete ha milioni di nodi: posso comunque calcolare la centralità di intermediazione?

Il calcolo esatto con l'algoritmo di Brandes è O(VE) e potrebbe essere troppo lento. Utilizzare approssimazioni randomizzate (ad es., campionamento di k nodi sorgente) disponibili in NetworkX (betweenness_centrality con parametro k) o librerie di grafi come graph-tool, che forniscono intervalli di confidenza sui punteggi approssimati.

Metodi correlati

Fonti

  1. Freeman, L. C. (1977). A set of measures of centrality based on betweenness. Sociometry, 40(1), 35–41.

    Apri il riferimento DOI
    Copiato.
  2. Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25(2), 163–177.

    Apri il riferimento DOI
    Copiato.