Coeficient de grupare

În teoria graficelor , coeficientul de grupare (sau tranzitivitate ) este măsura gradului în care nodurile unui grafic tind să fie conectate între ele.

Dovezile sugerează că în majoritatea rețelelor din lumea reală, și în special în rețelele sociale , nodurile tind să creeze grupuri puternic unite, cu densitate de legătură relativ mare; coeficientul de grupare a rețelelor reale tinde, prin urmare, să fie mai mare decât cel al graficelor în care legăturile sunt generate aleatoriu. ^[1]^[2]

Poate fi măsurat în două moduri diferite: global și local. Cel global descrie, în general, intensitatea fenomenului de grupare în rețea, în timp ce cel local privește nivelul de înrădăcinare a nodurilor unice.

Coeficient local de clusterizare

Exemplu de coeficient de grupare locală într-un grafic nedirecționat:
1. În primul caz, legăturile dintre vecinii nodului albastru sunt trei din trei, deci coeficientul este 1.
2. În al doilea caz, conexiunile sunt una din trei, deci coeficientul este 1/3.
3. În al treilea caz, legăturile sunt inexistente, deci coeficientul este zero.

Coeficientul de grupare local al unui nod într-un grafic este o măsură a cât de mult au vecinii să formeze o fisură (sau un grafic complet ). Duncan J. Watts și Steven Strogatz au introdus această măsură în 1998 pentru a determina dacă un grafic este sau nu o rețea în cadrul teoriei lumii mici .

Un grafic $G=(V,E)$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle G = (V, E)}$ constă formal dintr-un întreg $V.$ ${\ displaystyle V}$ $V.$ de vârfuri și un set $ȘI$ ${\ displaystyle E}$ $ȘI$ de legături. O legătură $e_{ij}$ ${\ displaystyle e_ {ij}}$ ${\ displaystyle e_ {ij}}$ conectează un vârf $v_{i}$ ${\ displaystyle v_ {i}}$ $tu}$ cu un vârf $v_{j}$ ${\ displaystyle v_ {j}}$ $v_ {j}$ .

Întregul $N_{i}$ ${\ displaystyle N_ {i}}$ $N_ {i}$ a vecinilor unui summit $v_{i}$ ${\ displaystyle v_ {i}}$ $tu}$ este definit ca setul de noduri conectate direct la acesta:

N_{i}=\{v_{j}:\left\langle e_{ji},e_{ij}\right\rangle \in E^{2}\}.

{\ displaystyle N_ {i} = \ {v_ {j}: \ left \ langle e_ {ji}, e_ {ij} \ right \ rangle \ în E ^ {2} \}.}

{\ displaystyle N_ {i} = \ {v_ {j}: \ left \ langle e_ {ji}, e_ {ij} \ right \ rangle \ în E ^ {2} \}.}

Noi definim $k_{i}$ ${\ displaystyle k_ {i}}$ $k_ {i}$ ca cardinalitate a $|N_{i}|$ ${\ displaystyle | N_ {i} |}$ ${\ displaystyle | N_ {i} |}$ , care este numărul vecinilor unui vârf $v_{i}$ ${\ displaystyle v_ {i}}$ $tu}$ .

Coeficientul local de clusterizare

C_{i}

{\ displaystyle C_ {i}}

Acolo}

a unui vârf

v_{i}

{\ displaystyle v_ {i}}

tu}

este dat de numărul de legături dintre membrii

N_{i}

{\ displaystyle N_ {i}}

N_ {i}

împărțit la numărul de conexiuni potențiale dintre ele.

Într-un grafic orientat , $e_{ij}$ ${\ displaystyle e_ {ij}}$ ${\ displaystyle e_ {ij}}$ este distinct de $e_{ji}$ ${\ displaystyle e_ {ji}}$ ${\ displaystyle e_ {ji}}$ , deci pentru fiecare $N_{i}$ ${\ displaystyle N_ {i}}$ $N_ {i}$ Sunt $k_{i}(k_{i}-1)$ ${\ displaystyle k_ {i} (k_ {i} -1)}$ ${\ displaystyle k_ {i} (k_ {i} -1)}$ conexiuni posibile între membrii săi. În consecință, coeficientul de cluster local pentru graficele orientate este dat de:^[2]

C_{i}={\frac {|\{e_{jk}:v_{j},v_{k}\in N_{i},e_{jk}\in E\}|}{k_{i}(k_{i}-1)}}.

{\ displaystyle C_ {i} = {\ frac {| \ {e_ {jk}: v_ {j}, v_ {k} \ in N_ {i}, e_ {jk} \ in E \} |} {k_ { i} (k_ {i} -1)}}.}

{\ displaystyle C_ {i} = {\ frac {| \ {e_ {jk}: v_ {j}, v_ {k} \ in N_ {i}, e_ {jk} \ in E \} |} {k_ { i} (k_ {i} -1)}}.}

În schimb, proprietatea caracteristică a unui grafic nedirecționat este aceea $e_{ij}$ ${\ displaystyle e_ {ij}}$ ${\ displaystyle e_ {ij}}$ Și $e_{ji}$ ${\ displaystyle e_ {ji}}$ ${\ displaystyle e_ {ji}}$ sunt considerate identice, deci pentru fiecare $N_{i}$ ${\ displaystyle N_ {i}}$ $N_ {i}$ Sunt ${\frac {k_{i}(k_{i}-1)}{2}}$ ${\ displaystyle {\ frac {k_ {i} (k_ {i} -1)} {2}}}$ ${\ displaystyle {\ frac {k_ {i} (k_ {i} -1)} {2}}}$ conexiuni posibile între membrii săi. În consecință, coeficientul de cluster local pentru graficele neorientate este dat de:

C_{i}={\frac {2\cdot |\{e_{jk}:v_{j},v_{k}\in N_{i},e_{jk}\in E\}|}{k_{i}(k_{i}-1)}}.

{\ displaystyle C_ {i} = {\ frac {2 \ cdot | \ {e_ {jk}: v_ {j}, v_ {k} \ în N_ {i}, e_ {jk} \ în E \} |} {k_ {i} (k_ {i} -1)}}.}

{\ displaystyle C_ {i} = {\ frac {2 \ cdot | \ {e_ {jk}: v_ {j}, v_ {k} \ în N_ {i}, e_ {jk} \ în E \} |} {k_ {i} (k_ {i} -1)}}.}

Coeficient global de grupare

Conceptul de coeficient global de grupare se bazează pe tripluri de noduri. Un triplu constă din trei noduri conectate prin două legături (triplu deschis) sau trei (triplu închis). Fiecare triplu este centrat în jurul unui nod. Un triunghi este format din trei tripluri închise centrate pe aceleași trei noduri care le compun.

Coeficientul global de grupare este, prin urmare, numărul de triple închise (sau de 3 ori numărul de triunghiuri) împărțit la numărul total de triple (suma celor deschise și închise). Prima încercare de măsurare a fost făcută de Robert D. Luce și Albert D. Perry (1949). ^[3] Această metodă poate fi aplicată atât graficelor direcționate, cât și celor neorientate. ^[4]

Watts și Strogatz, pe de altă parte, au definit coeficientul de grupare ca medie a coeficienților locali: ^[5]

Să presupunem un nod

v

{\ displaystyle v}

v

avea

k_{v}

{\ displaystyle k_ {v}}

{\ displaystyle k_ {v}}

vecini; atunci pot exista maxim

k_{v}(k_{v}-1)/2

{\ displaystyle k_ {v} (k_ {v} -1) / 2}

{\ displaystyle k_ {v} (k_ {v} -1) / 2}

conexiuni între ele (acest lucru se întâmplă atunci când toți vecinii din

v

{\ displaystyle v}

v

sunt conectate între ele). Denotând cu

C_{v}

{\ displaystyle C_ {v}}

CV}

este definită fracțiunea de astfel de conexiuni care există de fapt

C.

{\ displaystyle C}

C.

ca medie a

C_{v}

{\ displaystyle C_ {v}}

CV}

împărțit la numărul de noduri.

Ultima definiție este echivalentă cu prima dacă se utilizează media ponderată , cântărind fiecare $C_{v}$ ${\ displaystyle C_ {v}}$ $CV}$ cu numărul de triple în care nodul este central:

C={\frac {3\cdot n_{\Delta }(G)}{n_{\land }(G)}}={\frac {\sum _{i=1}^{n}(C_{i}\cdot w_{i})}{\sum _{i=1}^{n}w_{i}}}

{\ displaystyle C = {\ frac {3 \ cdot n _ {\ Delta} (G)} {n _ {\ land} (G)}} = {\ frac {\ sum _ {i = 1} ^ {n } (C_ {i} \ cdot w_ {i})} {\ sum _ {i = 1} ^ {n} w_ {i}}}}

{\ displaystyle C = {\ frac {3 \ cdot n _ {\ Delta} (G)} {n _ {\ land} (G)}} = {\ frac {\ sum _ {i = 1} ^ {n } (C_ {i} \ cdot w_ {i})} {\ sum _ {i = 1} ^ {n} w_ {i}}}}

.

Unde este:

$n_{\Delta }(G)$ ${\ displaystyle n _ {\ Delta} (G)}$ ${\ displaystyle n _ {\ Delta} (G)}$ este numărul de triunghiuri din grafic;
$n_{\land }(G)$ ${\ displaystyle n _ {\ land} (G)}$ ${\ displaystyle n _ {\ land} (G)}$ este numărul total de tripluri ale graficului;
$w_{i}$ ${\ displaystyle w_ {i}}$ $w_ {i}$ este greutatea vertexului $v_{i}$ ${\ displaystyle v_ {i}}$ $tu}$ (numărul de triple în care nodul este central);

Rețineți că $\sum _{i=1}^{n}w_{i}\equiv n_{\land }(G)$ ${\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} \ equiv n _ {\ land} (G)}$ ${\ displaystyle \ sum _ {i = 1} ^ {n} w_ {i} \ equiv n _ {\ land} (G)}$ .

Exemplu

Grafic nedirectat cu șase noduri. Vârfurile încercuite în roșu sunt triple triple închise.

În exemplul din dreapta există un singur triunghi, format din vârfurile 1, 2 și 5. Caracteristicile graficului sunt următoarele:

Vârf	Conexiuni între vecini	Greutate	Triple în care nodul este central
1	1	1	⟨2.1.5⟩
2	1/3	3	⟨1,2,3⟩, ⟨1,2,5⟩, ⟨3,2,5⟩
3	0	1	⟨2,3,4⟩
4	0	3	⟨3,4,5⟩, ⟨3,4,6⟩, ⟨5,4,6⟩
5	1/3	3	⟨1,5,2⟩, ⟨1,5,4⟩, ⟨2,5,4⟩
6	0	0	-