17.2: Longitud de trayectoria más corta
- Page ID
- 115758
El análisis de redes puede medir y caracterizar diversas características de topologías de red que van más allá del tamaño y la densidad. Muchas de las herramientas utilizadas aquí son en realidad prestadas del análisis de redes sociales desarrollado y utilizado en sociología [60].
La primera medida que vamos a discutir es la longitud de ruta más corta de un nodo a otro nodo, también llamada distancia geodésica en una gráfica. Si la red está desdirigida, la distancia entre dos nodos es la misma, independientemente de qué nodo es el punto de partida y cuál es el punto final. Pero si la red está dirigida, ya no es así en general.
La longitud de ruta más corta se puede medir fácilmente usando NetworkX:
La ruta real también se puede obtener de la siguiente manera:
La salida anterior es una lista de nodos en la ruta más corta desde el nodo 16 al nodo 25. Esto se puede visualizar usando draw_networkx_edges de la siguiente manera:
El resultado se muestra en la Fig. 17.2.1.
Podemos usar esta longitud de ruta más corta para definir varias métricas útiles para caracterizar las propiedades topológicas de la red. Vamos a denotar una longitud de ruta más corta de nodo\(i\) a nodo\(j\) como\(d(i → j)\). Claramente,\(d(i → i) = 0\) para todos\(i\). Entonces podemos construir las siguientes métricas:
Longitud de trayectoria característica
\[L =\frac{\sum_{i,j}{d(i \rightarrow{j})}}{n(n-1)} \label{(17.15)} \]
donde n es el número de nodos. Esta fórmula funciona tanto para redes no dirigidas como dirigidas. Calcula la longitud promedio de las rutas más cortas para todos los pares de nodos posibles en la red, dando una distancia esperada entre dos nodos elegidos aleatoriamente. Esta es una caracterización intuitiva de cuán grande (o pequeño) es el mundo representado por la red.
Excentricidad
\[\epsilon{(i) = \max_{j}{d(1 \rightarrow{j})}} \label{(17.16)} \]
Esta métrica se define para cada nodo y da la longitud de ruta máxima más corta que un nodo puede tener con cualquier otro nodo de la red. Esto indica qué tan lejos está el nodo hasta el punto más lejano de la red.
Diámetro
\[D= \max_{i}{\epsilon(i)} \label{(17.17)} \]
Esta métrica da la máxima excentricidad en la red. Intuitivamente, nos dice hasta qué punto pueden llegar dos nodos cualquiera entre sí dentro de la red. Los nodos cuya excentricidad\(D\) se llama periferias.
Radio
\[R= \min_{i}{\epsilon{i}} \label{(17.18)} \]
Esta métrica da la mínima excentricidad en la red. Intuitivamente, nos indica el menor número de pasos que necesitarás para llegar a cada nodo si puedes elegir un nodo óptimo como punto de partida. Los nodos cuya excentricidad\(R\) se llama centros.
En NetworkX, estas métricas se pueden calcular de la siguiente manera:
Visualiza la gráfica del Club de Karate usando las excentricidades de sus nodos para colorearlos.
Aleatorizar la topología de la gráfica de Karate Club manteniendo su tamaño y densidad, y luego medir la longitud de trayectoria característica, diámetro y radio de la gráfica aleatoria. Repita esto muchas veces para obtener distribuciones de esas métricas para gráficos aleatorios. Después compara las distribuciones con las métricas de la gráfica original de Karate Club. Discutir qué métrica es más sensible a las variaciones topológicas.
Nota: Las gráficas aleatorizadas pueden estar desconectadas. Si es así, todas las métricas discutidas anteriormente serán infinitas, y NetworkX te dará un error. Para evitar esto, debes verificar si la red aleatoria está conectada o no antes de calcular sus métricas. NetworkX tiene una función nx.is_connected para este propósito.