¿Cuál es el elemento más importante o influyente en una red?

Escrito por Nicolas Poza Moreno , Alejandro Alvarez, Tomas Vera, kilver campos

La detección de los nodos más importantes en una base de datos en formato red (o grafo) es un problema de amplio interés en diversas disciplinas científicas, particularmente en las ciencias de datos. Su relevancia ha ido aumentando en los últimos años gracias a los avances en almacenamiento y poder de cálculo de los ordenadores modernos [1] en la década de los 90’s, junto con el auge explosivo de la teoría de redes a principio del año 2000 [2,3,4].

Básicamente cualquier conjunto de datos que podamos describir a través de un conjunto de nodos o entes, y un conjunto de enlaces que describen la forma en que estos entes interactúan o se relacionan entre sí. Algunos ejemplos de este tipo de sistema (o bases de datos) son:

• Redes sociales: En donde las personas son representadas por nodos, y los enlaces representan las diversas relaciones sociales entre ellas (amistad, colaboración, pasatiempos comunes, etc.). Ejemplos de estas las podemos ver en creaciones tecnológicas como Facebook, Twitter, LinkedIn, Instagram, TikTok, etc. En estas últimas, los nodos más importantes están relacionados con personas de alta influencia social “influencers”, los cuales son de interés para los departamentos de marketing modernos [15].
• Organismos biológicos: El metabolismo de un organismo puede representarse a través de redes, en la que los nodos son biomoléculas (metabolitos o enzimas) y un metabolito está conectado con una enzima si el primero es el educto o producto de la reacción enzimática mediada por la enzima (metabolómica). También podemos relacionar todas las proteínas que interactúan físicamente en un organismo a través de una red de interacción entre proteínas (proteómica). Los nodos más importantes están relacionados con posibles blancos de drogas, que son de mucho interés para el diseño de nuevos tratamiento en enfermedades parasitarias [16].
• Redes de transporte: En este caso los nodos representan típicamente lugares geográficos (ciudades, aeropuertos, puertos, etc.) y dos nodos están conectados si existe una ruta que los conecte. Por ejemplo, en el caso de los aeropuertos, dos de estos están conectados si existe un vuelo directo de uno al otro. Los nodos más importantes están relacionados con los aeropuertos por los que fluyen más personas, si suponemos vuelos comerciales estándares, y por tanto son de amplio interés para evitar o minimizar la difusión de una pandemia, colocando en tales aeropuertos, puntos de control y campañas de vacunación [17].
• Redes de computadores y dispositivos IoT : Aquí los nodos están compuestos por todos los dispositivos del ecosistema IoT (smartphones, sensores basados en arduino, raspberry, tablets, dispositivos inteligentes, computadoras, etc) y las conexiones pueden ser cableadas y/o abstractas, e.g., wifi , 3G, 4G, 5G, bluetooth, etc.
• Sismicidad y clima: La versatilidad de las redes se muestra también vía la representación de datos de naturaleza temporal como la sismicidad o el clima, que se mide con respecto al tiempo en formato de redes de correlaciones o de causalidad, en la que los nodos son zonas geográficas en las que se colocan sensores (sismicidad, temperatura, etc.) y dos zonas estarán conectadas si sus comportamientos temporales están correlacionados (obteniendo así una red no-dirigida) o el comportamiento de una de las zonas influencia el comportamiento de la otra (obteniendo así una red dirigida) [18].
• Tiendas Online: Podemos representar los productos de una tienda electrónica como una red, en la que dos productos están conectados si ambos fueron buscados o comprados por el mismo usuario, o bien por las relaciones que estos productos tengan (metadatos). Por ejemplo, una raqueta de tenis y unos calcetines pueden compartir los atributos: deportes, aire libre, hobbie, por lo que podrían estar conectados, pero no así una raqueta y un sofá.
• Internet: En este caso, los routers son los nodos de esta red, y los enlaces las conexiones cableadas o inalámbricas que permiten su comunicación [19].
• La WWW (o World Wide Web): permite describir el universo de páginas web a través de nodos, y dos de estos nodos están conectados si existe un hipervínculo de una página web a la otra. Observar que en este caso, la WWW es una red dirigida (pues puede existir un hipervínculo desde la página A a la página B, pero no necesariamente de la B a la A). Podemos decir que una página web es influyente si una gran cantidad de páginas “apunta” a esta. El concepto de influencia o importancia de una página web es utilizado en el diseño de motores de búsqueda como el de google.

Todos los ejemplos anteriores nos permiten mirar la información de un punto de vista diferente, i.e., a través del mapa de interacciones que describen, logrando posteriormente, a través de diversas herramientas de la minería de datos y de la inteligencia artificial, develar jerarquías, patrones, puntos de vulnerabilidad, etc., lo cual sería sumamente difícil desde el tradicional esquema de base de datos compuesto por una lista de registros.

Concretamente, ¿Qué nos puede ofrecer el análisis de una red?

Contestaremos esta pregunta a través de ejemplos. Imaginemos que intentamos emprender en el mundo del transporte de encomiendas, e.g., negocios como Chilexpress, Starken, Globo. Minimizar costos es de suma importancia, tanto para macro-empresas como para empresas que inician un emprendimiento. La primera pregunta que nos planteamos es ¿dónde colocar el almacén central?. Si bien este problema tiene sus orígenes en una disciplina matemática conocida como investigación de operaciones, los nuevos métodos que ofrece la teoría de redes permiten abordarlo desde un nuevo punto de vista, e.g., en el nodo (sitio) que es más cercano a cualquier punto de la ciudad (red), o bien, por el que es más fácil fluir desde cualquier origen hacia cualquier destino. Este es uno de miles de ejemplos en donde encontrar el nodo más central es valioso para una empresa.

“En el siguiente artículo estaremos interesados en detectar los nodos más importantes, relevantes, influyentes o centrales.”

Dependiendo del sistema bajo estudio, el concepto de importancia, relevancia o influencia puede variar, sin embargo, para la mayoría de los sistemas, el nodo más importante es

• El más conectado o el con mayor número de enlaces con los demás nodos (centralidad de grado [5]).
• El más cercano al resto de los nodos en promedio (closeness o cercanía [6]).
• Por el que pasa más información (betweenness o intermediación [7]).
• el que está conectado con nodos importantes (Centralidad de vector propio [8]).
• Entre muchas otras [9].

En lo siguiente estaremos interesados en los métodos basados en flujo de información. Observar típicamente un taxista no va del punto A al punto B por el camino más corto, pues estos sufren del efecto cuello de botella (o están saturados), sino que viajan por otras rutas que terminan siendo más eficientes que el camino más corto. Lo mismo en el contexto informacional, no siempre la información viaja por el camino más corto. De manera que la medida de intermediación clásica no explota toda la información que ofrece la diversidad de caminos que hay entre dos puntos en una red.

Inspirados en el paper de Mark Newman [13] en lo siguiente exploramos su metodología desde un enfoque más simple, es decir, modelando el flujo de un paquete de información en una red a través de un paseo aleatorio uniforme absorbente. Este método lo denominaremos de aquí en adelante como el método de Newman.

Metodología de los paseos aleatorios

Partimos con la heurística de que los nodos más visitados son aquellos por los que pasa más información, y por tanto, los más relevantes desde el punto de vista informacional. Para aclarar más esta idea, imaginemos tres paseos aleatorios que parten desde el conjunto de nodos grises. Para llegar a los nodos azules deben pasar irremediablemente por los nodos rojo y verde, de manera que estos últimos tendrán una estadística de visitas ligeramente superior al resto.

Fig. 1 Paseo aleatorio entre dos conjuntos de nodos (gris y azul).

Matemáticamente, el paseo aleatorio lo podemos describir a través de su matriz de transición Pij :

donde, la matriz de adyacencia A es la representación matricial del grafo, cuya entrada Aij es igual 1 si los nodos i y j están conectados y 0 en el caso contrario (ver figura)

Fig. 2 Grafo o red y su matriz de adyacencia.

y ki , que es el número de conexiones que posee un nodo, llamado grado del nodo. Por ejemplo en la figura 2, el nodo A tiene grado 2, mientras que el nodo B tiene grado 3.

Resultados Comparativos

La tabla 1 muestra una comparación entre los diferentes métodos aplicados a la red de co-apariciones entre los personajes de la novela “Los Miserables” de Victor Hugo. Se despliegan los primeros 10 personajes más importante según cada medida. Cabe destacar que casi todas las medidas logran detectar al protagonista “Jean Valjean” como el elemento más importante, así como también al personaje antagónico Javert, y a personajes claves en la trama como Gavroche y Marius. Solo closeness/cercanía incluye también en el ranking a Cosette.

.

Tabla 1. Análisis comparativo de las diferentes medidas de centralidad.

Es notable también que los ranking tengan tan buen nivel, considerando que para este análisis solo se tomó la topología de interacción (sin pesos), ignorando la frecuencia de interacciones. Esto podría explicar porqué los Thenardier aparecen tan arriba en el ranking, quitándole protagonismo a Cosette.

Implementación del método de Intermediación de paseos aleatorios

Iniciamos importando el conjunto de librerías necesarias para la implementación del método de Newman basado en paseos aleatorios.

Se utilizaron las librerías:

(i) networkx para utilizar la clase grafo/red pre-implementada en esta, y aprovecharnos de los métodos de la clase, así como también de diversas funciones clásicas de la teoría de redes pre-implementadas, e.g., la construcción de la matriz de adyacencia, o la lectura de archivos de datos en formato grafo.

(ii) Numpy para poder aprovechar los métodos y funciones propias del álgebra lineal pre-implementadas en estas.

(iii) matplotlib para todo los referido a visualización de los resultados.

(iv) random para utilizar el método choice, para seleccionar un elemento del vecindario de un nodo de forma aleatoria al que transitar.

Implementamos también una función para leer archivos sif (simple interaction file)

Esta función nos permite leer los datasets en formato .sif y construir un grafo de networkx. Luego, mediante nx.to_numpy_matrix(G) creamos su correspondiente matriz de adyacencia.

La función “transition” nos permite calcular las probabilidades de ir del nodo i al nodo j (matriz de transición). Notar que esto no es otra cosa que la ecuación (1). Se trabaja los nodos del grafo como una lista para moverse por su indices (i,j) y ésta retorna la división de la matriz de adyacencia con el grado de sus nodos. Llegados a este punto se requiere simular el flujo de información en la red, por lo que necesitamos generar o bien muchas órbitas o trayectorias pequeñas (habilitando así el paradigma del paralelismo para este algoritmo) o bien una órbita muy larga sobre la cual hacer análisis estadístico. Por simplicidad, elegiremos la segunda opción.

Dada la posición del paseo, la función “step” genera el siguiente paso, haciendo una elección aleatoria sobre sus vecinos. Esto se hace utilizando una distribución uniforme, i.e., todos los vecinos tienen la misma probabilidad de ser visitados por el caminante, en concordancia con la Ec. (1).

Para cada paso que realiza el paseo aleatorio, almacenamos el nodo visitado en una lista denominada Orbit. Luego, calculamos la frecuencia de visitas del paseo aleatorio sobre cada nodo i del grafo G a través del método count sobre la lista. En este punto, ya hemos calculado la centralidad de cada nodo, y con fines de visualización, usamos este valor para denotar la centralidad en una escala de colores particular.

El despliegue de la red es realizado gracias a la función nx.draw, y las posiciones de los nodos se calcula utilizando alguno de los algoritmos disponibles. En el código comentado anteriormente se utilizó el algoritmo Kamada Kawai, el cual ofrece una buena representación de la red. La escala de colores representa a los nodos más centrales con tonalidades rojas, y los menos centrales y periféricos con tonalidades azules.

Finalmente, el siguiente bloque de código tiene como objetivo exportar el top 10 del ranking obtenido con el método, así como también almacenarlo en un dataframe de pandas para los posteriores análisis y comparaciones mostradas en la tabla 1.

Se normalizó el valor de la centralidad y se diseñaron gráficos de barra para comparar como escala y distribuye la importancia cada una de las medidas de centralidad acá estudiadas.

Aplicaciones en Diversos Datasets

Grafo de la red de Los miserables.

Destaca Valjean como el nodo más central, mostrado en rojo. A continuación se verán las gráficas obtenidas de los diferentes métodos estudiados, que tienen como ejes el nodo involucrado y su influencia o centralidad (de 0 a 1) en la red respecto a la densidad obtenida a partir de una histograma H de la lista las órbitas generadas por los nodos dividido en el valor max de las órbitas.

Centralidad de autovector: Considera a Gavroche como el nodo más influyente, seguido de Valjean.

Centralidad de grado: Considera a Valjean como el nodo más influyente de la red seguido de Gavroche. Más cercano a lo esperado.

Centralidad de cercanía: Muestra a Valjean como nodo más central, luego se muestra que los siguientes 4 forman un plateau con aproximadamente el mismo valor de importancia. Destacan Javert (personaje antagónico a Valjean), Marius y Gavroche.

Centralidad de Intermediación: Muestra a Valjean como nodo más influyente, y debido a lo restrictivo del concepto de geodésica utilizado en su heurística, los siguientes valores de centralidad presentan valores bastante bajos en comparación con Valjean.

Intermediación de Newman basada en paseos aleatorios: Da un buen ranking, mostrando en este top 4 a los cuatro de los protagonistas de la obra: Valjean, Javert, Marius y Gavroche. Este resultado es mejorable considerando por ejemplo, frecuencia de co-apariciones, pasando a un enfoque de redes pesadas.

Red de las familia Florentinas en la época del renacimiento.

Esta red fue tomada del trabajo de Padgett et al [10] , y fue construida a partir de documentos históricos en donde se describen la red de matrimonios entre las diferentes familias. De [10,11] tenemos evidencia que sostiene que La familia Medici era la más poderosa en el siglo quince en Florencia.

Red del club de karate de Zachary

Esta red fue tomada de un estudio realizado por Wayne Zachary sobre fisión en pequeños grupos sociales[12]. Los nodos son los miembros de un club de karate universitario, y los enlaces entre ellos denotan la interacción social entre estos fuera del club. Del trabajo de Zachary se desprende que los nodos más importantes son el 33, 32 y el 0, que son el presidente del club, el vicepresidente y el sensei respectivamente. Sabiendo esto, notamos que al aplicar el algoritmo de Newman, se obtiene que el presidente del club y el sensei son los nodos más influyentes para esta red.

Conclusiones

• Se implementó un método de análisis de nodos importantes en bases de datos tipo red basado en paseos aleatorios.
• Se comparó su rendimiento con otros métodos de centralidad reportados en la literatura, en varias redes de prueba en las que se tenía información parcial o total de las jerarquías o importancia de los nodos, mostrando el método de Newman mejores resultados.
• Dada su naturaleza, este puede ser paralelizable, tomando muchas órbitas en lugar de una sola.
• Un enfoque más práctico es considerar el análisis asintótico de la matriz de transición, que es equivalente a tomar paseos aleatorios de longitud infinita. Sin embargo, se pierde la información sobre los estados estadísticos transitorios, que son de mucho interés.

Códigos

Todos los códigos están disponibles en el repositorio:

https://github.com/ajalvarez/Centralidad-Paseo-Aleatorio

Referencias.

1. Grochowski, E. G., Hoyt, R. F. & Heath, J. S. Magnetic Hard Disk Drive Form Factor Evolution. IEEE Transactions on Magnetics 29, 4065–4067 (1993).
2. A. Barabasi, E. Bonabeau (2003). “Scale-Free Networks”. Scientific American: 50–59.
3. S. H. Strogatz, D. J. Watts (1998). “Collective dynamics of ‘small-world’ networks”. Nature. 393 (6684): 440–442.
4. Amaral, L. A. N., Scala, A., Barthélémy, M. & Stanley, H. E. Classes of small-world networks. in Proceedings of the National Academy of Sciences of the United States of America 97, 11149–11152 (2000).
5. Wasserman, S. & Faust, K Social Network Analysis Methods and Applications. (Cambridge University Press, 1944).
6. Sabidussi, G. The centrality index of a graph. Psychometrika. 31, 4, 581–603 (1996).
7. Brandes, U. A faster algorithm for betweenness centrality. The Jour. Math. Socio. 25, 163–177 (2001).
8. Bonacich, P. Power and Centrality: A family of measures. Am. Jour. Soc. 92, 1170 (1987).
9. Lü, L. et al. Vital nodes identification in complex networks. Physics Reports 650, 1–63 (2016).650,
10. Padgett, J.F. & Ansell, C. K. Robust action and the rise of the Medici, 1400–1434. Am. Jour. Soc. 98, 1259 (1993).
11. Matthew, J. Social and Economic Networks. (Princeton University Press, 2010).
12. Zachary W. W. An information flow model for conflict and fission in small groups. Jour. Anth. Res. 33,452–473 (1977).
13. Newman, M.E.J. (2005). “A measure of betweenness centrality based on random walks”. Social Networks 27: 39–54.
14. Knuth D. E. The Stanford GraphBase: A Platform for Combinatorial Computing. (Addison-Wesley, Reading, MA, 1993).
15. https://medium.com/swlh/what-is-influencer-marketing-the-complete-guide-2ef95a6eb4a3
16. Herrera-Almarza G., et al. Properties of essential genes in the protein-protein interaction network of Escherichia coli from the perspective of network theory, Journal of Computational Methods in Sciences and Engineering 17 (1), 209–216 (2017).
17. Pastor-Satorras, R., Castellano, C., Van Mieghem, P. & Vespignani, A. Epidemic processes in complex networks. Reviews of Modern Physics 87, (2015).
18. Yook, S. H., Jeong, H. & Barabási, A. L. Modeling the internet’s large-scale topology. Proceedings of the National Academy of Sciences of the United States of America 99, 13382–13386 (2002).
19. Bottinelli, A., Perna, A., Ward, A. & Sumpter, D. Proceedings of the European Conference on Complex Systems 2012. in Proceedings of the European Conference on Complex Systems 2012591–606 (2013). doi:10.1007/978–3–319–00395–5