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

Consideriamo una rete composta da n nodi connessi da m archi; sia a_i,j un elemento della matrice di adiacenza della rete. Il valore di a_i,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à è:

${\displaystyle {\frac {k_{i}\cdot k_{j}}{2\cdot m}}}$

dove k_i è il grado di un vertice i.

Il minor numero di archi attesi tra i due nodi è:

${\displaystyle a_{i,j}-{\frac {k_{i}\cdot k_{j}}{2\cdot m}}}$

Sommando tutte le coppie di vertici nello stesso gruppo, la modularità (chiamata Q) è:

${\displaystyle Q={\frac {1}{2m}}\sum _{i,j}\left[a_{i,j}-{\frac {k_{i}k_{j}}{2m}}\right]\delta (c_{i},c_{j})}$

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

• Grafo
• Vertice (teoria dei grafi)
• Arco (teoria dei grafi)
• Coefficiente Adamic/Adar

Collegamenti esterni

• 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.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica