Coeficiente de agrupamiento

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En la teoría de grafos, un coeficiente de agrupación es una medida del grado en que los nodos de un gráfico tienden a agruparse. La evidencia sugiere que en la mayoría de las redes del mundo real, y en particular en las redes sociales, los nodos tienden a crear grupos muy unidos caracterizados por una densidad relativamente alta de lazos; esta probabilidad tiende a ser mayor que la probabilidad media de un empate establecido aleatoriamente entre dos nodos (Holland y Leinhardt, 1971; Watts y Strogatz, 1998).

Existen dos versiones de esta medida: la global y la local. La versión global fue diseñada para dar una indicación general de la agrupación en la red, mientras que la versión local da una indicación de la integración de nodos individuales.

Coeficiente de agrupamiento local

El coeficiente de agrupamiento local de un vértice (nodo) en un gráfico cuantifica qué tan cerca están sus vecinos de ser una camarilla (gráfico completo). Duncan J. Watts y Steven Strogatz introdujeron la medida en 1998 para determinar si un gráfico es una red de mundo pequeño.

Un grafo $G=(V,E)$ consta formalmente de un conjunto de vértices $V$ y un conjunto de aristas $mi$ entre ellos. Una arista $e_{ij}$ conecta vértice $v_{i}$ con vértice $v_{j}$ .

La vecindad $n_{i}$ de un vértice $v_{i}$ se define como sus vecinos inmediatamente conectados de la siguiente manera: ${displaystyle N_{i}={v_{j}:e_{ij}in O e_{ji}in E}.}$

Definimos $k_{yo}$ como el número de vértices, $|N_{yo}|$ , en la vecindad, $n_{i}$ , de un vértice.

El coeficiente de agrupamiento local $C_{yo}$ para un vértice $v_{i}$ viene dado por una proporción del número de enlaces entre los vértices dentro de su vecindad dividido por el número de enlaces que posiblemente podrían existir entre ellos. Para un grafo dirigido, $e_{ij}$ es distinto de $e_{{ji}}$ , y por lo tanto para cada vecindad $n_{i}$ hay $k_{i}(k_{i}-1)$ vínculos que pueden existir entre los vértices dentro de la vecindad ( $k_{yo}$ es el número de vecinos de un vértice). Por lo tanto, el coeficiente de agrupamiento local para gráficos dirigidos se da como $C_{i}={frac {|{e_{{jk}}:v_{j},v_{k}en N_{i},e_{{jk}}en E}|}{k_ {i}(k_{i}-1)}}.$

Un grafo no dirigido tiene la propiedad de que $e_{ij}$ y $e_{{ji}}$ se consideran idénticos. Por lo tanto, si un vértice $v_{i}$ tiene $k_{yo}$ vecinos, ${frac{k_{i}(k_{i}-1)}{2}}$ podrían existir aristas entre los vértices dentro del vecindario. Por lo tanto, el coeficiente de agrupamiento local para gráficos no dirigidos se puede definir como $C_{i}={frac{2|{e_{{jk}}:v_{j},v_{k}en N_{i},e_{{jk}}en E}|}{ k_{i}(k_{i}-1)}}.$

Sea $lambda _{G}(v)$ el número de triángulos en el $ven V(G)$ gráfico no dirigido $GRAMO$ . Es decir, $lambda _{G}(v)$ es el número de subgrafos de $GRAMO$ con 3 aristas y 3 vértices, uno de los cuales es $v$ . Sea $tau _{G}(v)$ el número de triples en $ven G$ . Es decir, $tau _{G}(v)$ es el número de subgrafos (no necesariamente inducidos) con 2 aristas y 3 vértices, uno de los cuales es $v$ y tal que $v$ es incidente en ambas aristas. Entonces también podemos definir el coeficiente de agrupamiento como $C_{i}={frac {lambda _{G}(v)}{tau _{G}(v)}}.$

Es simple mostrar que las dos definiciones anteriores son la misma, ya que $tau _{G}(v)=C({k_{i}},2)={frac {1}{2}}k_{i}(k_{i}-1).$

Estas medidas son 1 si cada vecino conectado a $v_{i}$ también está conectado a todos los demás vértices dentro del vecindario, y 0 si ningún vértice conectado a $v_{i}$ conecta a cualquier otro vértice conectado a $v_{i}$ .

Dado que cualquier gráfico está completamente especificado por su matriz de adyacencia A, el coeficiente de agrupamiento local para un gráfico no dirigido simple se puede expresar en términos de A como: ${displaystyle C_{i}={frac {1}{k_{i}(k_{i}-1)}}sum_{j,k}A_{ij}A_{jk}A_{ki}}$

dónde: ${displaystyle k_{i}=sum_{j}A_{ij}}$

y C _i = 0 cuando k _i es cero o uno. En la expresión anterior, el numerador cuenta el doble del número de triángulos completos en los que interviene el vértice i. En el denominador, k _i cuenta el número de pares de aristas en los que interviene el vértice i más el número de aristas individuales atravesadas dos veces. k _i es el número de aristas conectadas al vértice i, y restando k _iluego elimina este último, dejando solo un conjunto de pares de aristas que posiblemente podrían conectarse en triángulos. Por cada par de aristas, habrá otro par de aristas que podría formar el mismo triángulo, por lo que el denominador cuenta el doble de la cantidad de triángulos concebibles en los que podría estar involucrado el vértice i.

Coeficiente de agrupamiento global

El coeficiente de agrupamiento global se basa en tripletes de nodos. Un triplete son tres nodos que están conectados por dos (triplete abierto) o tres (triplete cerrado) lazos no dirigidos. Por lo tanto, un gráfico triangular incluye tres tripletes cerrados, uno centrado en cada uno de los nodos (nota: esto significa que los tres tripletes en un triángulo provienen de selecciones superpuestas de nodos). El coeficiente de agrupamiento global es el número de tripletes cerrados (o 3 x triángulos) sobre el número total de tripletes (tanto abiertos como cerrados). El primer intento de medirlo fue realizado por Luce y Perry (1949). Esta medida da una indicación de la agrupación en toda la red (global) y se puede aplicar tanto a redes dirigidas como no dirigidas (a menudo denominada transitividad, consulte Wasserman y Faust, 1994, página 243).

El coeficiente de agrupamiento global se define como: ${displaystyle C={frac {mbox{número de tripletes cerrados}}{mbox{número de todos los tripletes (abiertos y cerrados)}}}}$ .

El número de tripletes cerrados también se conoce como 3 × triángulos en la literatura, por lo que: ${displaystyle C={frac {3times {mbox{número de triángulos}}}{mbox{número de todos los trillizos}}}}$ .

Opsahl y Panzarasa (2009) propusieron una generalización a redes ponderadas, y Opsahl (2009) una redefinición a redes de dos modos (tanto binarias como ponderadas).

Dado que cualquier gráfico está completamente especificado por su matriz de adyacencia A, el coeficiente de agrupamiento global para un gráfico no dirigido se puede expresar en términos de A como: ${displaystyle C={frac {sum_{i,j,k}A_{ij}A_{jk}A_{ki}}{sum_{i}k_{i}(k_{i}-1)}}}$

dónde: ${displaystyle k_{i}=sum_{j}A_{ij}}$

y C =0 cuando el denominador es cero.

Coeficiente de agrupamiento medio de la red

Como alternativa al coeficiente de agrupamiento global, Watts y Strogatz miden el nivel general de agrupamiento en una red como el promedio de los coeficientes de agrupamiento locales de todos los vértices $norte$ : ${bar {C}}={frac {1}{n}}sum_{{i=1}}^{{n}}C_{i}.$

Vale la pena señalar que esta métrica otorga más peso a los nodos de bajo grado, mientras que la relación de transitividad otorga más peso a los nodos de alto grado.

Un grafo se considera de mundo pequeño, si el grafo tiene una longitud de ruta más corta media pequeña que escala con el logaritmo natural del número de nodos en la red, ${ estilo de visualización ln {N}}$ . Por ejemplo, un gráfico aleatorio es un mundo pequeño, mientras que una red no lo es, y los gráficos sin escala a menudo se consideran un mundo ultrapequeño, ya que su longitud de ruta media más corta se escala con ${ estilo de visualización ln { ln {N}}}$ .

Barrat et al. propusieron una generalización a redes ponderadas. (2004), y una redefinición de grafos bipartitos (también llamados redes de dos modos) por Latapy et al. (2008) y Opsahl (2009).

Fagiolo (2007) y Clemente y Grassi (2018) han proporcionado generalizaciones alternativas a los gráficos ponderados y dirigidos.

Esta fórmula no está definida por defecto para gráficos con vértices aislados; ver Kaiser (2008) y Barmpoutis et al. Se encuentra que las redes con el mayor coeficiente de agrupamiento promedio posible tienen una estructura modular y, al mismo tiempo, tienen la menor distancia promedio posible entre los diferentes nodos.

Percolación de redes agrupadas

Para una red aleatoria tipo árbol sin correlación grado-grado, se puede demostrar que dicha red puede tener un componente gigante, y el umbral de percolación (probabilidad de transmisión) está dado por ${displaystyle p_{c}={frac{1}{g_{1}'(1)}}}$ , donde ${ estilo de visualización g_ {1} (z)}$ es la función generadora correspondiente a la distribución de exceso de grado.

En redes con agrupamiento bajo ${displaystyle 0<Cll 1}$ , el punto crítico se escala de ${ estilo de visualización (1-C) ^ {-1}}$ tal manera que:

{displaystyle p_{c}={frac {1}{1-C}}{frac {1}{g_{1}'(1)}}.}

Esto indica que para una distribución de grado dada, el agrupamiento conduce a un umbral de filtración mayor, principalmente porque para un número fijo de enlaces, la estructura de agrupamiento refuerza el núcleo de la red con el precio de diluir las conexiones globales. Para redes con alta agrupación, la agrupación fuerte podría inducir la estructura de núcleo y periferia, en la que el núcleo y la periferia podrían filtrarse en diferentes puntos críticos, y el tratamiento aproximado anterior no es aplicable.

Para estudiar la solidez de las redes agrupadas, se desarrolla un enfoque de percolación.

Contenido relacionado

Más resultados...