Modularitate (rețele)

Modularitatea este o funcție utilizată în analiza grafică sau a rețelei, de exemplu în rețele de calculatoare sau rețele sociale . Valoarea sa cuantifică calitatea împărțirii rețelei în module sau comunități. O subdiviziune bună are valori ridicate de modularitate; în interiorul modulelor densitatea va fi mare, dar între un modul și altul vor exista puține conexiuni și, prin urmare, o densitate mai mică. Cea mai obișnuită utilizare a modularității se face pentru optimizarea tehnicilor de determinare a comunităților din rețele.

Definiție

Luați în considerare o rețea formată din n noduri conectate prin m arcade ; fie a _{i, j} un element al matricei de adiacență a rețelei. Valoarea lui _{i, j} este deci setul de arcuri care leagă nodurile i și j . Să presupunem că stabilim o împărțire a vârfurilor într-un anumit număr de grupuri, modularitatea acestei împărțiri este definită ca fracțiunea marginilor care merg spre acest grup minus ceea ce s-ar aștepta dacă marginile ar fi distribuite aleatoriu.

În cea mai comună versiune a acestui concept, aleatoritatea arcurilor este stabilită în așa fel încât să păstreze gradul fiecărui nod. În acest caz, numărul de arce care leagă cele două vârfuri în urma aleatoriei este:

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

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

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

unde k _i este gradul unui vârf i .

Cel mai mic număr de arce așteptat între cele două noduri este:

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

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

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

Prin adăugarea tuturor perechilor de vârfuri din același grup, modularitatea (numită Q ) este:

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

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

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

Valoarea sa se poate deplasa în intervalul [-1 / 2,1]: este pozitivă dacă numărul de arce prezente este mai mare decât numărul așteptat și negativ în caz contrar.

Elemente conexe

linkuri externe

MEJ Newman, Modularitatea și structura comunității în rețele , în PNAS , vol. 103, nr. 23, 2006, pp. 8577–8582, DOI : 10.1073 / pnas.0601602103 , PMID 16723398 , PMC 1482622 . Adus la 11 iulie 2008 .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică