La Community detection, chiamata anche partizione del grafo, aiuta a rivelare le relazioni nascoste tra i nodi della rete e svolge un ruolo chiave nella comprensione della funzionalità di reti complesse. L’identificazione delle comunità è fondamentale per comprendere la struttura delle reti complesse e, in definitiva, per estrarre informazioni utili da esse. Le applicazioni sono diverse: dall’assistenza sanitaria alla geografia regionale, dalle interazioni umane alla mobilità e all’economia.
Una rappresentazione grafica simbolica rappresentativa di un esempio esplicativo di raggruppamento
di nodi in community ottenibile con un algoritmo di community detection
Le formazione di community è un fenomeno naturale nelle reti reali, come ad esempio le reti sociali; se pensiamo, ad esempio, ai social media come Facebook, Instagram o Twitter, dove gli utenti cercano di connettersi con altre persone, alla fine, si finisce per essere connessi con persone appartenenti a diversi circoli sociali. Questi circoli sociali possono essere un gruppo di parenti, compagni di scuola, colleghi, ecc., e rappresentano a tutti gli effetti diverse comunità presenti nella piattaforma social.
Un esempio di rete sociale dove gli utenti sono raggruppati secondo strutture
e sottostrutture in base ai loro interessi e relazioni sociali
Il rilevamento delle comunità in una rete è uno dei compiti più importanti nell’analisi di rete. In una rete su larga scala, come un social network online, potremmo avere milioni di nodi e di connessioni. Rilevare le comunità in tali reti diventa un compito di dimensioni molto elevate. Pertanto, abbiamo bisogno di algoritmi di rilevamento della partizione in grado di suddividere la rete in più comunità.
Le tecniche tradizionali di rilevamento della comunità sono diverse; tra queste, le principali sono il partizionamento del grafo, il clustering gerarchico, il clustering partizionale, il raggruppamento spettrale e gli algoritmi divisivi. Il partizionamento del grafo divide il grafo in g cluster di dimensione predefinita, in modo tale che il numero di collegamenti in un cluster sia più denso del numero di bordi tra i cluster; le tecniche di clustering gerarchico si basano sulla misura della similarità dei vertici, non necessitano di una dimensione e un numero predefiniti di comunità e possono essere meglio rappresentati dai dendrogrammi; il clustering partizionale suddivide un set di dati in un numero predefinito di k cluster non sovrapposti con l’obiettivo di dividere i punti dati in k cluster al fine di minimizzare/massimizzare la funzione di costo basata sulla misura di dissimilarità tra i nodi; gli algoritmi divisivi rimuovono i link tra un cluster e gli altri basandosi sulla bassa somiglianza per separare le comunità tra di loro.
Esempio di risultato fornito dall’algoritmo kmeans nel caso in cui si chieda
all’algoritmo di identificare tre community nel grafo
Uno degli algoritmi più efficienti e citati nelle pubblicazioni scientifiche è sicuramente l’algoritmo di Louvain, basato sull’ottimizzazione della modularity (una delle più note funzioni di costo utilizzate in questo campo) e sul collassamento periodico delle community in nodi di un nuovo grafo, ogni volta che la sua esecuzione porta il sistema a trovarsi in una configurazione di massimo locale.
In sintesi l’algoritmo è composto da due parti che si alternano durante l’esecuzione: nella prima parte vengono presi in esame tutti i nodi singolarmente e, per ognuno di loro, viene valutato il guadagno di modularity che si ottiene raggruppandoli con gli altri nodi del grafo. Ogni volta che viene individuato un raggruppamento che porta al massimo guadagno possibile della modularity, allora i nodi vengono messi insieme in una stessa community. Ad un certo punto, iterando su tutti i nodi del grafo, si arriva a una configurazione di massimo locale nella quale nessuna modifica sui singoli nodi può più portare a un ulteriore guadagno della modularity.
In questo punto si passa alla seconda parte dell’algoritmo nella quale le community relativa alla configurazione trovata di massimo locale vengono collassate in dei nodi per creare un nuovo grafo dove i nodi rappresentano le community del passo precedente; dato quindi il nuovo grafo, l’algoritmo torna alla prima parte e ripete la massimizzazione della modularity su di esso, superando così il massimo relativo dove si era fermato allo step precedente.
Infine, neanche collassando le community in nodi, l’algoritmo riesce a superare più un certo valore di modularity e allora questo significa che si è raggiunto il termine dell’esecuzione.
Rappresentazione schematica riassuntiva dei due step
che costituiscono l’algoritmo di Louvain
I punti di forza che hanno reso molto famoso e utilizzato questo algoritmo risiedono nel fatto che permette di determinare in maniera automatica il numero ottimale di community (l’algoritmo termina quando la modularity raggiunge un massimo globale, non quando il grafo viene suddiviso in un numero prefissato di community), è in grado di costruire in modo naturale la struttura gerarchica della partizione (ogni massimo locale è un livello gerarchico) e l’occupazione delle risorse – e quindi il tempo di calcolo – si riduce sensibilmente dopo il primo collassamento delle community in nodi di un nuovo grado (grafi di milioni di nodi e miliardi di link passano genericamente ad avere qualche centinaio di nodi e migliaio di link, riducendo esponenzialmente il tempo necessario per arrivare alla convergenza).
Un esempio di risultato ottenibile nella ricerca di influencer su Twitter
tramite l’applicazione di tecniche di community detection
Tra le analisi di rete, questo tipo di studio dei grafi è tra quelli che restituisce il maggiore valore aggiunto per diversi motivi. Per prima cosa possiamo dire che permette di fare delle inferenze grazie alle quali possiamo determinare le caratteristiche comuni tra diversi nodi (lavoro, passioni, adorazione per un personaggio famoso, un influencer o un brand, posizione geografica, appartenenza ad un partito politico e così via): infatti, se un nodo incognito viene classificato dagli algoritmi di community detection insieme ad altri nodi dei quali sono già note le caratteristiche di sopra, è probabile che anche il nodo incognito condivida le stesse caratteristiche; per questo motivo, i risultati di questo tipo di analisi vengono spesso utilizzati per lo sviluppo di sistemi di raccomandazione.
Inoltre il raggruppamento di nodi in community permette di comprendere con maggiore profondità la struttura della rete che si sta studiando, mettendo in evidenza quali nodi sono più importanti nelle dinamiche di interazione tra i diversi gruppi e quali invece hanno il ruolo prevalente di tenere insieme queste strutture.
Infine la possibilità di ricostruire la struttura gerarchica dei diversi livelli di raggruppamento è fondamentale per comprendere la robustezza in seguito alla rottura della struttura di community, un repertorio complesso e diversificato di funzioni di sistema che promuovono l’elaborazione e la trasmissione delle informazioni ottimali ed efficienti.