Densidad (teoría de grafos)

(Redirigido desde «Grafo disperso»)

En teoría de grafos, la densidad de un grafo es una propiedad que determina la proporción de aristas que posee. Un grafo denso es un grafo en el que el número de aristas es cercano al número máximo de aristas posibles, es decir, a las que tendría si el grafo fuera completo. Al contrario, un grafo disperso es un grafo con un número de aristas muy bajo, es decir, cercano al que tendría si fuera un grafo vacío.

La distinción entre grafos dispersos y densos es relativamente vaga. De acuerdo con Preiss,[1]​ dado un grafo , este es denso si , para , y es disperso si la misma igualdad se cumple para , donde refiere a la cota superior asintótica.

Definición formal

editar

Sea   un grafo simple (sin bucles) con   vértices y   aristas.

Si el grafo es no dirigido, su densidad   se define formalmente como:

 

La densidad varía entre  , para grafos vacíos con  , y  , para grafos completos con el máximo número de aristas posibles, a saber,  .[2]

Si el grafo es dirigido, su densidad se define como:

 

En este caso, la densidad alcanza valor   para el máximo número de aristas posibles en un grafo dirigido completo, a saber,  .[3]

Si el grafo es además ponderado, sean   los pesos de las aristas, entonces la densidad del grafo se define como el promedio de los valores asignados a las aristas:[3]

 

Relación con el grado modal medio

editar

El grado modal medio   de un grafo es el grado promedio de los nodos del grafo. Para un grafo simple no dirigido, sea   el grado del vértice  , se define formalmente como:[3]

 

Por lo tanto, a partir de ambas ecuaciones, la densidad de un grafo simple no dirigido también equivale a la proporción media de aristas incidentes con los vértices del grafo, es decir, formalmente:[3]

 

Aplicaciones

editar

Para grafos dirigidos,Zeleny (1941) definió el índice de sociación de un nodo como la diferencia entre la densidad o media de la «intensidad» total de la red, y el grado de salida o «elecciones» realizadas por el nodo. Denotemos   el índice de sociación del nodo  . Entonces lo anterior se define formalmente como:[4][5]

 

La densidad se utiliza en análisis de redes sociales desde sus inicios en los años 1950,[6]​ al menos a partir de Kephart (1950) y Proctor y Loomis (1951) (estos últimos responsables de la centralidad de grado).[7][8]​ La densidad es una propiedad relevante para las redes sociales representadas como grafos, que se puede considerar como una medida de centralización de la red.[5]Bott (1990) la propuso como una forma de cuantificar los niveles de «entrelazado» de una red,[9]​ y Barnes (1969) para determinar la «estrechez» de las uniones de redes empíricas,[10]​ importante en modelos de bloque y otras técnicas algebraicas de análisis.[5]​ Además, la densidad de un subgrafo sirve para evaluar la cohesión de subgrupos dentro de una red social.[11][3]

Referencias

editar
  1. Preiss, 1998, p. 534.
  2. Coleman, Thomas F.; Moré, Jorge J. (1983). «Estimation of sparse Jacobian matrices and graph coloring Problems». SIAM Journal on Numerical Analysis 20 (1): 187-209. 
  3. a b c d e Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
  4. Zeleny, L. D. (1941). «Measurement of sociation». American Sociological Review 6 (2): 173-188. doi:10.2307/2085548. 
  5. a b c Wasserman y Faust, 2013, «Centralidad y prestigio», pp. 191-240.
  6. Bott, E. (1990) [1957]. Familia y red social: roles, normas y relaciones externas en las familias urbanas corrientes [Family and Social Network]. Madrid: Taurus. 
  7. Kephart, W. M. (1950). «A quantitative analysis of intragroup relationships». American Journal of Sociology 55: 544-549. 
  8. Proctor, C. H.; Loomis, C. P. (1951). «Analysis of sociometric data». En Jahoda, M.; Deutsch, M.; S. W. Cook, eds. Research methods in social relations. Nueva York: Dryden Press. 
  9. Bott, E. (1990) [1957]. Family and social network [Familia y red social: roles, normas y relaciones externas en las familias urbanas corrientes] (en inglés). Madrid: Taurus. 
  10. Barnes, J. A. (1969). «Graph theory and social networks: A technical comment on connectedness and connectivity». Sociology 3: 215-232. 
  11. Blau, P. M. (1977). Inequality and heterogeneity. Nueva York: Free Press. 

Bibliografía

editar