Coeficiente de agrupamiento

Un grafo ${\displaystyle G=(V,E)}$ formalmente consiste en un conjunto de vértices ${\displaystyle V}$ y en un conjunto de enlaces ${\displaystyle E}$ entre ellos. Un enlace ${\displaystyle e_{ij}}$ conecta dos vértices ${\displaystyle i}$ y ${\displaystyle j}$. La vecindad de vértices N para un vértice ${\displaystyle v_{i}}$ se define como aquellos vértices inmediatamente conectados de tal forma que:

${\displaystyle N_{i}=\{v_{j}\}:e_{ij}\in E\lor e_{ji}\in E.}$

El grado, que se representa como ${\displaystyle k_{i}}$ de un vértice, es definido como el número de vértices enlazados con uno dado. En esta expresión además se tiene que ${\displaystyle |N_{i}|}$.

El coeficiente de agrupamiento ${\displaystyle C_{i}}$ para un vértice ${\displaystyle v_{i}}$ está dado por la proporción entre los enlaces conectados con sus vecinos dividido entre el número de enlaces existentes en un clique en el que la conectividad es máxima. Para un grafo dirigido, ${\displaystyle e_{ij}}$ es distinto de ${\displaystyle e_{ji}}$, y por lo tanto para cada vecino ${\displaystyle N_{i}}$ hay ${\displaystyle k_{i}(k_{i}-1)}$ enlaces que podrían existir entre los vértices de la vecindad (${\displaystyle k_{i}}$ es el grado del vértice i para el total (entrantes + salientes)). De esta forma el grado de agrupamiento en los grafos dirigidos está dado por:

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

Un grafo no dirigido tiene la propiedad de que tanto los enlaces ${\displaystyle e_{ij}}$ y ${\displaystyle e_{ji}}$ son considerados idénticos. Por lo tanto, si un vértice ${\displaystyle v_{i}}$ posee ${\displaystyle k_{i}}$ vecinos, entonces existirían ${\displaystyle {\frac {k_{i}(k_{i}-1)}{2}}}$ enlaces entre los vértices de su vecindad. De esta forma el coeficiente de agrupamiento de grafos no dirigidos pueden ser definidos como:

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

Sea ${\displaystyle \lambda _{G}(v)}$ el número de triángulos en ${\displaystyle v\in V(G)}$ para un grafo no dirigido ${\displaystyle G}$. Esto es, ${\displaystyle \lambda _{G}(v)}$ es el número de sub-grafos de ${\displaystyle G}$ con tres enlaces y tres vértices, uno de los cuales es ${\displaystyle v}$. Sea ${\displaystyle \tau _{G}(v)}$ el número de tripletes en ${\displaystyle v\in G}$. Esto es, ${\displaystyle \tau _{G}(v)}$ es número de sub-grafos (no necesariamente inducidos) con dos enlaces y 3 vértices, uno de los cuales es ${\displaystyle v}$ y tal que ${\displaystyle v}$ es incidente a ambos enlaces. De esta forma se puede definir también el coeficiente de agrupamiento como

${\displaystyle C_{i}={\frac {\lambda _{G}(v)}{\tau _{G}(v)}}.}$

Es muy simple mostar que de las dos definiciones precedentes son similares, ya que:

${\displaystyle \tau _{G}(v)=C({k_{i}},2)={\frac {1}{2}}k_{i}(k_{i}-1).}$

Esta medida es igual a 1 si cada vecino está conectado a ${\displaystyle v_{i}}$ está conectada igualmente a cada uno de los otros vértices en la vecindad, y 0 si no hay vértices que están conectados a ${\displaystyle v_{i}}$ que conectan a otro vértice que es conectado a ${\displaystyle v_{i}}$. El coeficiente de agrupamiento de la red se calcula mediante Watts y Strogatz como la media de los coeficientes de agrupamiento de todos los vértices de la red:

${\displaystyle {\bar {C}}={\frac {1}{n}}\sum _{i=1}^{n}C_{i}.}$

Un grafo se considera una red de mundo pequeño si el coeficiente de agrupamiento de la red ${\displaystyle {\bar {C}}}$ es significantemente mayor que el que pueda ofrecer un grafo aleatorio construido con el mismo conjunto de vértices, y si al mismo tiempo posee una distancia media de pequeño valor.

Se suele emplear el coeficiente de agrupamiento en la detección automática de tópicos.

• Agrupamiento (teoría de grafos)
• Red de mundo pequeño
• Modelo Watts y Strogatz
• Algoritmo de agrupamiento
• Equilibrio estructural

• Wikimedia Commons alberga una categoría multimedia sobre Coeficiente de agrupamiento.