Densidad (teoría de grafos)

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 ${\displaystyle G=(V,E)}$, este es denso si ${\displaystyle |E|=O(|V|^{k})}$, para ${\displaystyle k\geq 2}$, y es disperso si la misma igualdad se cumple para ${\displaystyle 1<k<2}$, donde ${\displaystyle O}$ refiere a la cota superior asintótica.

Definición formal

Sea ${\displaystyle G=(V,E)}$  un grafo simple (sin bucles) con ${\displaystyle n=|V|}$  vértices y ${\displaystyle m=|E|}$  aristas.

Si el grafo es no dirigido, su densidad ${\displaystyle \Delta }$  se define formalmente como:

${\displaystyle \Delta ={\frac {m}{n(n-1)/2}}={\frac {2m}{n(n-1)}}}$ 

La densidad varía entre ${\displaystyle 0}$ , para grafos vacíos con ${\displaystyle m=0}$ , y ${\displaystyle 1}$ , para grafos completos con el máximo número de aristas posibles, a saber, ${\displaystyle m=n(n-1)/2}$ .^[2]​

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

${\displaystyle \Delta ={\frac {m}{n(n-1)}}}$ 

En este caso, la densidad alcanza valor ${\displaystyle 1}$  para el máximo número de aristas posibles en un grafo dirigido completo, a saber, ${\displaystyle m=n(n-1)}$ .^[3]​

Si el grafo es además ponderado, sean ${\displaystyle W=\{w_{1},\ldots ,w_{m}\}}$  los pesos de las aristas, entonces la densidad del grafo se define como el promedio de los valores asignados a las aristas:^[3]​

${\displaystyle \Delta ={\frac {\sum _{i=1}^{m}w_{i}}{n(n-1)}}}$ 

Relación con el grado modal medio

El grado modal medio ${\displaystyle {\bar {g}}}$  de un grafo es el grado promedio de los nodos del grafo. Para un grafo simple no dirigido, sea ${\displaystyle g(v)}$  el grado del vértice ${\displaystyle v}$ , se define formalmente como:^[3]​

${\displaystyle {\bar {g}}={\frac {\sum _{v\in V}g(v)}{|V|}}={\frac {2|E|}{|V|}}={\frac {2m}{n}}\,}$ 

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]​

${\displaystyle \Delta ={\frac {\bar {g}}{|V|-1}}={\frac {\bar {g}}{n-1}}}$ 

Aplicaciones

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

Referencias

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. Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
4. Bott, E. (1990) [1957]. Familia y red social: roles, normas y relaciones externas en las familias urbanas corrientes [Family and Social Network]. Madrid: Taurus. 
5. Kephart, W. M. (1950). «A quantitative analysis of intragroup relationships». American Journal of Sociology 55: 544-549. 
6. 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. 
7. Wasserman y Faust, 2013, «Centralidad y prestigio», pp. 191-240.
8. 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. 
9. Barnes, J. A. (1969). «Graph theory and social networks: A technical comment on connectedness and connectivity». Sociology 3: 215-232. 
10. Blau, P. M. (1977). Inequality and heterogeneity. Nueva York: Free Press. 

Bibliografía

• Paul E. Black, Sparse graph, from Dictionary of Algorithms and Data Structures, Paul E. Black (ed.), NIST. Del 29 de septiembre de 2005.
• Preiss, Bruno (1998). Data Structures and Algorithms with Object-Oriented Design Patterns in C++. John Wiley & Sons. ISBN 0-471-24134-2. 
• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053. 

•   Datos: Q3085841