Redes complejas y Big Data: de la centralidad a los autovectores

8/6/2023
AUTOR
Colegio de matemáticas Bourbaki

Las redes son un objeto matemático con una enorme flexibilidad para poder modelar fenómenos complejos tanto dentro de la naturaleza como dentro de nuestra sociedad o nuestras herramientas tecnológicas.

No alt text provided for this image
Red del Metro en la CDMX

Desde el punto de vista más ingenuo una red es un grafo, es decir un conjunto de nodos conectados con aristas que representan la relación entre los nodos, algunos ejemplos célebres de una red son los siguientes:

  • Redes de transporte: imaginemos un distribuidor de mercancías a través de un país en el que los centros de distribución se representan por nodos y las aristas modelan cuando dos centros de distribución están conectados por un medio de transporte.
  • Redes sociales: pensemos en una plataforma como LinkedIn donde los nodos son usuarios y las aristas representan cuando dos usuarios hayan trabajado en algún momento en la misma empresa.

Es importante mencionar que utilizar un grafo simple no es la única manera de definir a una red, en algunos casos podríamos incluir más estructura, por ejemplo suponer que las aristas son dirigidas, tienen algún peso o que una misma arista une a más de dos nodos.

No alt text provided for this image

La teoría de las redes complejas es fundamental en nuestros días pues el fenómeno de Big Data ha permeado en absolutamente todos los ámbitos de nuestra vida, por lo anterior el estudio de las redes complejas se ha convertido en una herramienta indispensable para el análisis de los grandes volúmenes de información.

Centralidad de intermediación

No alt text provided for this image
Linton Freeman

La primera definición de centralidad fue propuesta por Alex Bavelas en 1950 sin embargo en los años 70 Linton Freeman quien es un sociólogo estadounidense propuso una definición de centralidad que captura mejor esta noción. Para definirlo correctamente necesitamos definir previamente el concepto de geodésica.

  • Una geodésica entre dos nodos es el camino mínimo que existe entre ellos viajando únicamente por aristas del grafo.
  • La medida de centralidad de intermediación de un nodo V es el promedio de la cantidad de geodésicas entre cualesquiera dos nodos que pasan V. El promedio es sobre todas las parejas de nodos distintos a V y sobre todas las geodésicas entre ellos.

Fijemos por ejemplo un centro de distribución de Amazon V que está cerca de nuestra casa. Para calcular la medida de centralidad debemos de considerar cualquier par de otros centros de distribución W, Z. Las geodésicas son los caminos más cortos entre W y Z pasando por otros centros de distribución conectados por algún transporte. Evidentemente podrían existir más de dos caminos distintos con la misma longitud dentro del grafo. Entre todas estas geodésicas, algunas de ellas pasarán por V y estas son las que nos interesan, para terminar el cálculo se debe dividir sobre todas las geodésicas entre W y Z y después sumar sobre todas las parejas posibles centros.

Recurrencia y autovectores (eigenvectores)

No alt text provided for this image

Existen otras nociones de centralidad que incluyen información que la centralidad de intermediación no está utilizando. Imaginemos por ejemplo que deseamos calcular la centralidad de un centro de distribución V, de acuerdo a la noción anterior, todas los centros W (o Z) son igualmente importantes pues se promedian.

Para solucionar este problema se propuso una definición de centralidad recurrente, es decir que la medida de centralidad de un nodo esté en función de las medidas de centralidad de otros nodos, bien entendido esta recurrencia es exactamente la multiplicación de matrices y si c es el vector con las centralidades de los nodos, entonces estamos buscando un vector c que sea el autovector de alguna matriz M que en algunos casos podría ser simplemente la matriz de adyacencias que determinan las aristas.

No alt text provided for this image

Esta idea fue utilizada por Larry Page para proponer el algoritmo de búsqueda de Google que hizo mundialmente famosa a la plataforma por su eficacia, en este caso los valores de centralidad que estamos buscando son la importancia de cada uno de los sitios web.

Oferta académica