Coeficiente de agrupamiento

En ciencia de redes, el coeficiente de agrupamiento (clustering coefficient, en inglés) de un vértice en un grafo cuantifica qué tanto está de agrupado (o interconectado) con sus vecinos.Si el vértice está agrupado como un clique (subgrafo completo), entonces 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 comoEn el análisis de redes sociales, en ocasiones a este coeficiente se le conoce también como transitividad.formalmente consiste en un conjunto de vérticesy en un conjunto de enlacesse define como aquellos vértices inmediatamente conectados de tal forma que: El grado, que se representa comode un vértice, es definido como el número de vértices enlazados con uno dado.En esta expresión además se tiene queEl coeficiente de agrupamientoestá 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., y por lo tanto para cada vecinoenlaces 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 enlacesson considerados idénticos.enlaces entre los vértices de su vecindad.De esta forma el coeficiente de agrupamiento de grafos no dirigidos pueden ser definidos como: Seael número de triángulos enpara un grafo no dirigidoel número de tripletes enes número de sub-grafos (no necesariamente inducidos) con dos enlaces y 3 vértices, uno de los cuales esy tal quees 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 aestá conectada igualmente a cada uno de los otros vértices en la vecindad, y 0 si no hay vértices que están conectados aque conectan a otro vértice que es conectado aes 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.