Coeficient de agrupamiento

Archiu:Clustering coefficient example.svg

Eixemple de coeficient de agrupamiento per al nodo blau $i$ en un grafo no dirigit. Les llínees negres són arestes que conecten veïns de $i$; les segmentades són arestes inexistents.

En ciència de rets, el coeficient de agrupamiento (clustering coefficient, en anglés) d'un vèrtiç en un grafo quantifica qué tant està d'agrupat (o interconectado) en els seus veïns. Si el vèrtiç està agrupat com un clique (subgrafo complet), llavors el seu valor és màxim, mentres que un valor chicotet indica un vèrtiç poc agrupat en la ret. Duncan J. Watts i Steven Strogatz varen ser els primers en idear este coeficient en 1998, per a determinar si un grafo és una ret de món menut. Se sol representar formalment com $C_i$. En l'anàlisis de rets socials, en ocasions a este coeficient se li coneix també com transitividad.

Definició

Un grafo $G=(V,E)$ formalment consistix en un conjunt de vèrtiços $V$ i en un conjunt d'enllaços $E$ entre ells. Un enllaç $e_{ij}$ conecta dos vèrtiços $i$ i $j$. El veïnat de vèrtiços N per a un vèrtiç $v_i$ es definix com aquells vèrtiços immediatament conectats de tal forma que:

$N_i=\{v_j\}:e_{ij}\in E\vee e_{ji}\in E.$

El grau, que es representa com $k_i$ d'un vèrtiç, és definit com el número de vèrtiços enllaçats en un dau. En esta expressió ademés es té que $|N_i|$.

El coeficient de agrupamiento $C_i$ per a un vèrtiç $v_i$ està donat per la proporció entre els enllaços conectats en els seus veïns dividit entre el número d'enllaços existents en un clique en el que la conectivitat és màxima. Per a un grafo dirigit, $e_{ij}$ és distint de $e_{ji}$, i per lo tant per a cada veí $N_i$ hi ha $k_i(k_i-1)$ enllaços que podrien existir entre els vèrtiços del veïnat ($k_i$ és el grau del vèrtiç i per al total (entrantes + eixints)). D'esta forma el grau de agrupamiento en els grafos dirigits està donat per:

$C_i=\frac{|\{e_{jk}\}|}{k_i(k_i-1)}:v_j,v_k\in N_i,e_{jk}\in E.$

Un grafo no dirigit té la propietat de que tant els enllaços $e_{ij}$ i $e_{ji}$ són considerats idèntics. Per lo tant, si un vèrtiç $v_i$ posseïx $k_i$ veïns, llavors existirien $\frac{k_i(k_i-1)}{2}$ enllaços entre els vèrtiços del seu veïnat. D'esta forma el coeficient de agrupamiento de grafos no dirigits poden ser definits com:

$C_i=\frac{2|\{e_{jk}\}|}{k_i(k_i-1)}:v_j,v_k\in N_i,e_{jk}\in E.$

Siga ${\lambda }_G(v)$ el número de triànguls en $v\in V(G)$ per a un grafo no dirigit $G$. Açò és, ${\lambda }_G(v)$ és el número de subgrafos de $G$ en tres enllaços i tres vèrtiços, un dels quals és $v$. Siga ${\tau }_G(v)$ el número de triplets en $v\in G$. Açò és, ${\tau }_G(v)$ és número de subgrafos (no necessàriament induïts) en dos enllaços i 3 vèrtiços, un dels quals és $v$ i tal que $v$ és incident a abdós enllaços. D'esta forma es pot definir també el coeficient de agrupamiento com

$C_i=\frac{{\lambda }_G(v)}{{\tau }_G(v)}.$

És molt simple mostrar que de les dos definicions precedents són similars, ya que:

${\tau }_G(v)=C(k_i,2)=\frac{1}{2}{k}_i(k_i-1).$

Esta mida és igual a 1 si cada veí està conectat a $v_i$ està conectada igualment a cada u dels atres vèrtiços en el veïnat, i 0 si no hi ha vèrtiços que estan conectats a $v_i$ que conecten a un atre vèrtiç que és conectat a $v_i$. El coeficient de agrupamiento de la ret es calcula per mig de Watts i Strogatz com la mija dels coeficients de agrupamiento de tots els vèrtiços de la ret:

$\overline{C}=\frac{1}{n}\sum _{i=1}^n{C}_i.$

Un grafo es considera una ret de món menut si el coeficient de agrupamiento de la ret $\overline{C}$ és significantemente major que el que puga oferir un grafo aleatori construït en el mateix conjunt de vèrtiços, i si al mateix temps posseïx una distància mija de chicotet valor.

Aplicacions

Se sol amprar el coeficient de agrupamiento en la detecció automàtica de tòpics.

Vore també

• Agrupamiento (teoria de grafos)
• Ret de món menut
• Modele Watts i Strogatz
• Algoritme de agrupamiento
• Equilibri estructural