Coeficiente de agrupamiento
El coeficiente de agrupamiento (mencionado en la literatura también como clustering coefficient) de un vértice en un grafo cuantifica qué tanto está de agrupado (o interconectado) con sus vecinos. Se puede decir que si el vértice está agrupado como un clique (grafo completo) su valor es máximo, mientras que un valor pequeño indica un vértice poco agrupado en la red. Duncan J. Watts y Steven Strogatz fueron los primeros en idear este coeficiente, en 1998[1] para determinar si un grafo es una red de mundo pequeño. Se suele representar formalmente como . En algunas ocasiones dentro del mundo de la teoría de redes se denomina a este coeficiente también como transitividad.
Definición Formal
Un grafo formalmente consiste en un conjunto de vértices y en un conjunto de enlaces entre ellos. Un enlace conecta dos vértices y . La vecindad de vértices N para un vértice se define como aquellos vértices inmediatamente conectados de tal forma que:
El grado, que se representa como 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 .
El coeficiente de agrupamiento para un vértice 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, es distinto de , y por lo tanto para cada vecino hay enlaces que podrían existir entre los vértices de la vecindad ( 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:
Un grafo no dirigido tiene la propiedad de que tanto los enlaces y son considerados idénticos. Por lo tanto, si un vértice posee vecinos, entonces existirían enlaces entre los vértices de su vecindad. De esta forma el coeficiente de agrupamiento de grafos no dirigidos pueden ser definidos como:
Sea el número de triángulos en para un grafo no dirigido . Esto es, es el número de sub-grafos de con tres enlaces y tres vértices, uno de los cuales es . Sea el número de tripletes en . Esto es, es número de sub-grafos (no necesariamente inducidos) con dos enlaces y 3 vértices, uno de los cuales es y tal que es incidente a ambos enlaces. De esta forma se puede definir también el coeficiente de agrupamiento como
Es muy simple mostar que de las dos definiciones precedentes son similares, ya que:
Esta medida es igual a 1 si cada vecino está conectado a 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 que conectan a otro vértice que es conectado a . 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:
Un grafo se considera como mundo pequeño si el coeficiente de agrupamiento de la red 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.
Empleos
Se suele emplear el coeficiente de agrupamiento en la detección automática de tópicos.
Véase también
Referencias
- D. J. Watts y Steven Strogatz (junio de 1998). . Nature 393: 440-442. doi:10.1038/30918. Archivado desde el original el 18 de abril de 2007.
Enlaces externos
- Wikimedia Commons alberga una categoría multimedia sobre Coeficiente de agrupamiento.