Modularità (reti)
La modularità è una funzione usata nell'analisi dei grafi o delle reti per esempio in reti di computer o social network. Il suo valore quantifica la qualità della divisione della rete in moduli o comunità. Una buona suddivisione possiede alti valori di modularità; all'interno dei moduli la densità sarà alta ma fra un modulo e l'altro ci saranno pochi collegamenti e quindi una densità inferiore. L'uso più comune della modularità è fatto per l'ottimizzazione delle tecniche per determinare le comunità nelle reti.
Definizione
[modifica | modifica wikitesto]Consideriamo una rete composta da n nodi connessi da m archi; sia ai,j un elemento della matrice di adiacenza della rete. Il valore di ai,j è quindi l'insieme degli archi che connettono i nodi i e j. Supponiamo di stabilire una divisione dei vertici in un certo numero di gruppi, la modularità di questa divisione è definita come la frazione degli archi che vanno verso questo gruppo meno quello che ci si aspetterebbe se gli archi fossero distribuiti casualmente.
Nella versione più comune di questo concetto, la casualità degli archi è stabilita in modo da preservare il grado di ogni nodo. In tal caso il numero di archi che collegano i due vertici seguendo la casualità è:
dove ki è il grado di un vertice i.
Il minor numero di archi attesi tra i due nodi è:
Sommando tutte le coppie di vertici nello stesso gruppo, la modularità (chiamata Q) è:
Il suo valore può muoversi nell'intervallo [-1/2,1]: è positivo se il numero degli archi presenti è maggiore del numero di quelli attesi e negativo in caso contrario.
Voci correlate
[modifica | modifica wikitesto]Collegamenti esterni
[modifica | modifica wikitesto]- M. E. J. Newman, Modularity and community structure in networks, in PNAS, vol. 103, n. 23, 2006, pp. 8577–8582, DOI:10.1073/pnas.0601602103, PMID 16723398, PMC 1482622. URL consultato l'11 luglio 2008.