Métricas de Grafos y Redes
Introducción¶
Un grafo es una estructura de datos formada por nodos y enlaces que permite representar relaciones entre objetos. A modo de ejemplo, en una red social, los nodos podrían representar a los usuarios y los enlaces la conexión entre ellos.
Para comprender un grafo, es importante conocer cómo interactúan entre sí sus componentes y cómo se relacionan. En este documento, se muestran las principales métricas que permiten ontener un analisis descriptivo con el que identificar las principales características de un grafo. Para ello, se utilizará la librería networkx de Python.
✎ Nota
Si todavía no está familiarizado con los grafos, se recomienda leer el artículo Introducción a grafos y redes con Python.Librerías¶
Librerías utilizadas en este documento.
# Librerías
# ======================================================================================
import networkx as nx
import matplotlib.pyplot as plt
Matriz de adyacencia¶
Para poder analizar un grafo es neceario representarlo de forma matemática. Existen dos formas principales de hacerlo: la lista de ejes (edgelist) y la matriz de adyacencia.
La lista de ejes es simplemente una lista en la que se indican todas las conexiones. Por ejemplo, en un grafo dirigido con tres nodos {$A$, $B$ y $C$}, donde $A$ se conecta con $B$ y $C$, la lista de ejes es {($A$,$B$), ($A$,$C$)}. Si el grafo es no dirigido, la lista debe incluir las conexiones en ambas direcciones {($A$,$B$), ($B$,$A$) ($A$,$C$), ($C$,$A$)}.
Otra forma de representar un grafo es mediante lo que se conoce como matriz de adyacencia. La matriz de adyacencia es una matriz de dimensión $NxN$, siendo $N$ el número de nodos y donde aparece un 1 si la conexión entre un par de nodos existe y un 0 de lo contrario. Para grafos ponderados, en vez de un 1, la matriz presenta el valor del peso de la conexión. Debido a sus propiedades matemáticas, la matriz de adyacencia es el método de representación de grafos más utilizado.
La desventaja de la matriz de adyacencia, es que para grafos muy grandes, puede ocupar mucho espacio. Por este motivo, se utiliza con frecuencia una matriz de adyacencia sparse, que internamente únicamente almacena la información de las conexiones existentes, es decir, no almacena los ceros.
Para grafos no dirigidos la matriz de adyacencia es simétrica ya que, si existe la conexión entre los nodos $A$ y $B$, también existirá la conexión recíproca.
Con una formulación matetemática, la matriz de adyacencia de un grafo dirigido de $\mathrm{N}$ nodos tiene $\mathrm{N}$ filas y $\mathrm{N}$ columnas, siendo sus elementos:
$A_{i j}=1$ si existe un enlace que apunta desde el nodo $j$ al nodo $i$
$A_{i j}=0$ si los nodos $i$ y $j$ no están conectados entre sí
La matriz de adyacencia de una red no dirigida tiene dos entradas para cada enlace. El enlace $(1,2)$ se representa como $A_{12}$ $=1$ y $A_{21}=1$. Por lo tanto, la matriz de adyacencia de una red no dirigida es simétrica, $A_{i j}=A_{j i}.$
En la siguiente figura se representan los distintos tipos de grafos junto con sus matrices de adyacencia. Como se puede observar, los grafos dirigidos ($B$) son los únicos que no tienen una matriz de adyacencia simétrica. En el caso de los grafos bipartitos ($D$), se pueden proyectar para obtener las conexiones indirectas entre cada tipo de nodo ($E$), esto último se verá en profundidad más adelante.
Ejemplo de grafos de distintos tipos con sus matrices de adyacencia correspondientes. A) Grafo no dirigido. B) Grafo dirigido. C) Grafo ponderado. D) Grafo bipartito, con dos tipos de nodos (verde y naranja). E) Proyección del grafo bipartito en los nodos de cada tipo. Fuente: wikipedia.
Grado, grado medio y distribución de grados¶
Grado¶
Una propiedad clave de los nodos es número de enlaces que tiene con otros nodos del grafo, lo que se conoce como grado. Por ejemplo, en una grafo que representa las llamadas telefónicas, el grado de un nodo puede representar el número personas con las que ha hablado cada usuario. En un repositorio de publicaciones científicas, el grado puede representar el número de citas que recibe cada trabajo de investigación.
El grado de un nodo $i$ suele representarse con la letra $k_i$. En una red no dirigida, el número total de enlaces, $L$, es como la suma de los grados de los nodos dividida entre dos:
$$ L = \frac{1}{2}\sum_{i=1}^N k_i $$En la red no dirigida mostrada en la siguiente figura $k_1=3, k_2=3, k_3=1, k_4=3, k_5=2$. El factor 1/2 corrige el hecho de que en la suma cada enlace se cuenta dos veces. Por ejemplo, el enlace que conecta los nodos 2 y 4 se cuenta una vez en el grado del nodo 2 y una vez en el grado del nodo 4.
En un grafo dirigido, el grado de un nodo se puede definir de dos maneras: el grado de entrada ($k_i^{in}$), que es el número de enlaces que apuntan hacia el nodo, y el grado de salida ($k_i^{out}$), que es el número de enlaces que salen del nodo.
El grado $k_i$ del nodo $i$ se puede obtener de los elementos de la matriz de adyacencia. Para redes no dirigidas, el grado de un nodo es una suma sobre las filas o las columnas de la matriz, es decir: $$ k_i=\sum_{j=1}^N A_{j i}=\sum_{i=1}^N A_{j i} $$ Para redes dirigidas, las sumas sobre las filas y columnas de la matriz de adyacencia proporcionan los grados entrantes y salientes, respectivamente. $$ k_i^{i n}=\sum_{j=1}^N A_{i j}, \quad \quad k_i^{\text {out}}=\sum_{j=1}^N A_{j i} $$ Dado que en una red no dirigida el número de enlaces salientes es igual al número de enlaces entrantes, se obtiene que: $$ 2 L=\sum_{i=1}^N k_i^{i n}=\sum_{i=1}^N k_i^{\text {out}}=\sum_{i j}^N A_{i j} $$ El número de elementos distintos de cero de la matriz de adyacencia es $2 L$, o el doble del número de enlaces. De hecho, un enlace no dirigido que conecta los nodos $i$ y $j$ aparece en dos entradas: $A_{i j}=1$, un enlace que apunta desde el nodo $j$ al nodo $i$, y $A_{i i}=1 $, un enlace que apunta de $i$ a $j$.
Grado medio¶
El grado medio $\langle k\rangle$ representa el número medio de conexiones que tienen los nodos de un grafo. Se calcula como la suma los grados de todos los nodos dividida por el número de nodos. La importancia de esta medida reside en que permite comparar redes de distintos tamaños entre sí. El número de conexiones de los nodos de un grafo es igual al número de ejes multiplicado por dos. Por tanto, el número medio de conexiones de un grafo es:
$$ \langle k\rangle=\frac{1}{N} \sum_{i=1}^N k_i=\frac{2 L}{N} $$# Grafo de tipo lollypop (dos clusters dominantes unidos por un camino)
# ==============================================================================
fig, ax = plt.subplots(figsize=(8, 4))
G = nx.barbell_graph(m1=10, m2=3)
nx.draw_networkx(G, ax=ax, node_size=300, node_color='salmon')
# Numero de nodos, ejes del grafo y grado medio
# ==============================================================================
nodos = G.number_of_nodes()
ejes = G.number_of_edges()
k = ejes*2/nodos
print(f"Grafo con {nodos} nodos, {ejes} ejes y grado medio {k}")
Lo que es equivalente a la suma de los grados de entrada y salida de todos los nodos dividida por el número de nodos:
suma_grados = sum([grado for nodo, grado in G.degree()])
grado_medio = suma_grados / len(G)
print("Grado medio del grafo:", grado_medio)
Distribución de grados¶
La distribución de grados, $p_k$, proporciona la probabilidad de que un nodo seleccionado al azar en la red tenga un grado $k$. Dado que $p_k$ es una probabilidad, debe normalizarse, es decir la suma de todas las probabilidades debe ser igual a uno:
$$ \sum_{k=1}^{\infty} p_k=1 $$Para una red con $\mathrm{N}$ nodos, la distribución de grados es: $$ p_k=\frac{N_k}{N} $$ donde $N_k$ es el número de nodos de grado $k$. Por lo tanto, el número de nodos de grado $k$ se puede obtener a partir de la distribución de grados como $N_k=N p_k$.
La distribución de grados ha asumido un papel central en la teoría de redes tras el descubrimiento de las redes libres de escala. Una razón es que el cálculo de la mayoría de las propiedades de la red requiere conocer $p_k$, ya que este determina muchos de los fenómenos que ocurren en la red.
El grado promedio de una red se puede obtener como: $$ \langle k\rangle=\sum_{k=0}^{\infty} k p_k $$
Métricas para el análisis de gráfos¶
Uno de los primeros pasos en el análisis de un grafo es obtener una visión general de sus propiedades, lo que se conoce como análisis exploratorio de datos o EDA por sus siglas en inglés. En el caso de los grafos, el EDA se centra en las propiedades de los nodos, los conjuntos de nodos y las propiedades globales de la red. A continuación, se describen las principales métricas que se utilizan en el EDA de grafos.
Centralidad¶
Cuando se analizan redes, suele ser interesante identificar los nodos más importantes. Existen distintas formas de definir la importancia de un nodo, normalmente determinada por la posición que ocupa en la red. Al conjunto de métricas que permiten identificar los nodos más importantes se le conoce como centralidad.
Medidas locales¶
El adjetivo local se debe a que estas medidas solo toman en cuenta la influencia de un nodo sobre sus compañeros más cercanos. Estas medidas locales de centralidad muestran la importancia de un nodo teniendo en cuenta su posición en un contexto cercano, los nodos que tienen cerca.
Grado de centralidad (degree)¶
Para obtener esta medida basta con contar el número de enlaces relacionados con cada nodo (tanto los entrantes como los salientes de cada nodo). Tal y como está definida, esta métrica hará que destaquen aquellos nodos conectados a las sub-redes más amplias. Un valor más grande de esta medida indicará una mayor centralidad del nodo.
En un grafo no dirigido, el degree de un nodo se puede calcular directamente desde la matriz de adyacencia del grafo.
$$degree = \sum_i{A_{ij}} = \sum_j{A_{ij}}$$Esta métrica se puede presentar también de manera normalizada; es decir, dividiendo el número de enlaces relacionados con cada uno de los $n$ nodos dividido por $n-1$.
$$degree \ centrality = \frac{\sum_i{A_{ij}}}{N-1}$$Otras variantes de esta medida de centralidad solo consideran los enlaces de salida (out-degree) de cada nodo o solo los de entrada (in-degree). Estas últimas dos métricas pueden estar normalizadas o no. La normalización puede ser importante cuando se quiere comparar esta métrica entre diferentes grafos con números de nodos muy diferentes.
Para un grafo dirigido, existen dos tipos de Degree según nos refiramos a conexiones entrante o salientes:
$$inDegree = \sum_i{A_{ij}}$$$$outDegree = \sum_j{A_{ij}}$$Betweenness¶
Esta medida cuantifica el número de veces que un nodo es parte de la ruta geodésica (esto es, la de menor longitud) entre dos nodos. Su cálculo implica los siguientes pasos:
Contar el número de rutas que unen un par de nodos ($i$ y $j$).
Encontrar la proporción de esas rutas que pasan por un tercer nodo ($v$).
Repetir el cálculo para todas las parejas de nodos posibles (con la condición de que $i$ y $j$ sean diferentes de $v$) hallando en cada caso la proporción de rutas que pasan por el nodo $v$.
Sumar todas las proporciones obtenidas. Tomando $σij$ como el número de rutas de mínima distancia que unen a los nodos $i$ y $j$, y $σij(v)$ como el número de rutas de distancia mínima que unen a estos nodos y que pasan por el nodo $v$, entonces la métrica de Betweenness para el nodo $ está dada por:
donde $\delta_{i j}(v)=\frac{\sigma_{i j}(v)}{\sigma_{i j}}$.
Esta métrica solo toma valores entre cero y el número de parejas posibles dentro del grafo (excluyendo el nodo para el cual se está efectuando el cálculo). Esto es, si $N$ es el número total de nodos, entonces la cota superior toma el valor de $\frac{(N-1) !}{2 !((N-1)-2) !}$.
Por otra parte, tal y como se ha mencionado de manera implícita, entre mayor sea el Betweenness mayor será la centralidad del nodo.
Medidas Globales de Centralidad¶
Las medidas globales muestran la importancia de un nodo teniendo en cuenta su posición en el conjunto la red. De manera general, estas medidas identifican a aquellos nodos que están mejor ubicados para influir en toda la red lo más rápidamente posible. Ejemplos, de esta medida globales de centralidad son:
Closeness Centrality¶
Da una idea de "Cómo de cerca está un nodo del resto de nodos de la red". Para un nodo $x$, se calcula dividiendo el número de nodos a los que se puede ir desde ese nodo entre la suma de todas distancias de ese nodo $x$ al resto de nodos. Es decir, calcula las rutas más cortas entre todos los nodos y asigna una puntuación a cada uno en función de la suma de sus rutas. Mide cuántos pasos se requieren para conectarse a cada uno de los nodos desde un nodo determinado.
En general, es una medida de cuánto tarda en llegar la información de un nodo al resto de la red. Esta medida se calcula de la siguiente forma:
$$ClosenessCentrality = \frac{N-1}{\sum_j{d_{i,j}}}$$Es fácil deducir que esta medida estará entre cero y uno.Entre más cercana a 1 esté, mayor será la centralidad del nodo.
Así como el grado de centralidad, esta métrica puede calcularse considerando solo las rutas de salida (out) de cada nodo o solo las rutas de entrada (in). Estas últimas dos métricas pueden estar normalizadas o no.
Excentricidad¶
Mide la distancia de cada nodo al nodo más lejano.
$$Excentricidad(i)=\max [\operatorname{dist}(i, j)], \quad \forall j$$Ejemplo¶
# Crear grafo de tipo lollypop (dos clusters dominantes unidos por un camino)
# ==============================================================================
fig, ax = plt.subplots(figsize=(8, 4))
G = nx.barbell_graph(m1=10, m2=3)
nx.draw(G, ax=ax, with_labels=True)
# Grado de los nodos: el número de conexiones de cada nodo
# ==============================================================================
nx.degree(G)
print(f""""
Propiedades de los nodos
========================
Importancia de cada nodo según distintos criterios.
Locales: Importancia de un nodo teniendo en cuenta su posición en un contexto cercano (los nodos que tienen cerca).
- Degree: Número de conexiones de un nodo.
nx.degree(G)[11] = {nx.degree(G)[11]}
nx.degree(G)[17] = {nx.degree(G)[17]}
- Degree Centrality: Número de conexiones de un nodo normalizado con el número global de conexiones.
nx.degree_centrality(G)[11] = {nx.degree_centrality(G)[11]:.2}
nx.degree_centrality(G)[17] = {nx.degree_centrality(G)[17]:.2}
Globales: Importancia de un nodo teniendo en cuenta su posición en toda la red.
- Closeness Centrality: Da una idea de "Cómo de cerca está un nodo del resto de nodos de la red".
nx.closeness_centrality(G)[11] = {nx.closeness_centrality(G)[11]:.2}
nx.closeness_centrality(G)[17] = {nx.closeness_centrality(G)[17]:.2}
- Betweenness Centrality: Mide cuántas veces un nodo forma parte del camino más cercano entre dos nodos.
nx.betweenness_centrality(G)[11] = {nx.betweenness_centrality(G)[11]:.2}
nx.betweenness_centrality(G)[17] = {nx.betweenness_centrality(G)[17]:.2}
- Eccentricity: Distancia al nodo más lejano.
nx.eccentricity(G)[11] = {nx.eccentricity(G)[11]}
nx.eccentricity(G)[17] = {nx.eccentricity(G)[17]}
""")
print(f"""
Propiedades globales del grafo
==============================
- Degree medio: Número de conexiones medio de los nodos de un grafo.
{((G.number_of_edges()*2) / G.number_of_nodes()):,.3}
- Densidad del grafo: Número de conexiones / Número posible de conexiones.
{nx.density(G)}
- Diámetro: Distancia máxima entre dos nodos.
{nx.diameter(G)}
{nx.diameter(G) == max(nx.eccentricity(G))}
- Otras medidas: Transitividad, Reciprocidad.
{nx.transitivity(G)}
{nx.algorithms.clustering(G)}
"""
)
Información de sesión¶
import session_info
session_info.show(html=False)
Bibliografía¶
Instrucciones para citar¶
¿Cómo citar este documento?
Si utilizas este documento o alguna parte de él, te agradecemos que lo cites. ¡Muchas gracias!
Métricas de Grafos y Redes por Fernando Carazo y Joaquín Amat Rodrigo, disponible bajo una licencia Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0 DEED) en https://www.cienciadedatos.net/documentos/pygml04-metricas-grafos-redes-python.html
%%html
Este documento creado por Fernando Carazo y Joaquín Amat Rodrigo tiene licencia Attribution-NonCommercial-ShareAlike 4.0 International.
Se permite:
-
Compartir: copiar y redistribuir el material en cualquier medio o formato.
-
Adaptar: remezclar, transformar y crear a partir del material.
Bajo los siguientes términos:
-
Atribución: Debes otorgar el crédito adecuado, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puedes hacerlo de cualquier manera razonable, pero no de una forma que sugiera que el licenciante te respalda o respalda tu uso.
-
NoComercial: No puedes utilizar el material para fines comerciales.
-
CompartirIgual: Si remezclas, transformas o creas a partir del material, debes distribuir tus contribuciones bajo la misma licencia que el original.