Coeficiente de agrupamiento

Coeficiente de agrupamiento
Ejemplo de coeficiente de agrupamiento en un [[[grafo no dirigido]] en el que se considera el nodo sombreado on an undirected graph for the shaded node i. Los segmentos de líneas negras son enlaces que conectan vecinos de i, y los segmentos punteados son enlaces inexistentes.

El coeficiente de agrupamiento (mencionado en la literatura también como clustering coefficient) de un vértice en un grafo cuantifica como 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 introduced the measure in 1998[1] para determinar si un grafo es una red de mundo pequeño. Se suele representar formalmente como Ci. En algunas ocasiones dentro del mundo de la teoría de redes se denomina a este coeficiente también como transitividad.

Contenido

Definición Formal

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

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

El grado, que se representa como ki 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 | Ni | .

El coeficiente de agrupamiento Ci para un vértice vi está dado por la proporción entre los enlaces conectados con sus vecinos dividido entre el número de enlaces existentes en un cliqué en el que la conectividad es máxima. Para un grafo dirigido, eij es distinto de eji, y por lo tanto para cada vecino Ni hay ki(ki − 1) enlaces que podrían existir entre los vértices de la vecindad (ki 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:

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 eij y eji son considerados idénticos. Por lo tanto, si un vértice vi posee ki vecinos, entonces existirían \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:

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

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

C_i = \frac{\lambda_G(v)}{\tau_G(v)}.

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

\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 vi 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 vi que conectan a otro vértice que es conectado a vi. 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:

\bar{C} = \frac{1}{n}\sum_{i=1}^{n} C_i.

Un grafo se considera como mundo pequeño si el coeficiente de agrupamiento de la red \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.

Empleos

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

Véase también

Referencias

  1. ↑ D. J. Watts y Steven Strogatz (June 1998). «Collective dynamics of 'small-world' networks». Nature 393:  pp. 440–442. doi:10.1038/30918. http://web.archive.org/web/20070418032327/http://www.tam.cornell.edu/SS_nature_smallworld.pdf. 

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Red de mundo pequeño — Saltar a navegación, búsqueda Las redes de mundo pequeño permiten conectar dos nodos con relativamente pocos saltos entre ellos. En la ilustración puede verse una red que sigue el modelo Watts Strogatz En matemática y física una red de mundo… …   Wikipedia Español

  • Agrupación — Agrupación, agrupamiento agrupado y agrupar puede referirse a: Grupo Colectivo (grupo social) Unidad militar Algoritmo de agrupamiento Coeficiente de agrupamiento Colegio Rural Agrupado Junco agrupado Esta …   Wikipedia Español

  • Modelo Watts y Strogatz — Red de 20 nodos construida según el modelo Watts y Strogatz (N=20, k=4, β=0.2). El modelo Watts y Strogatz en teoría de redes se emplea para la construcción de algunas redes de mundo pequeño. Genéricamente se trata de un modelo de generación de… …   Wikipedia Español

  • Red compleja — Saltar a navegación, búsqueda En el contexto de la teoría de redes una red compleja se refiere a una red (grafo) que posee cierta característica topológicas no triviales que no ocurren en redes simples. La mayoría de redes sociales, biológicas, y …   Wikipedia Español

  • La Paz (estado de México) — Para otros usos de este término, véase Los Reyes (desambiguación). Para otros usos de este término, véase La Paz (desambiguación). La Paz …   Wikipedia Español

  • Check Wikipedia — Wikiproyecto:Check Wikipedia Saltar a navegación, búsqueda Esta página contiene de forma consciente fallos ortográficos. Los bots no deben intentar corregirlos. Atajo PR:CWPR:CW …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”