En teoría de grafos y análisis de redes , las métricas de influencia de nodos son medidas que clasifican o cuantifican la influencia de cada nodo (también llamado vértice) dentro de un gráfico. Están relacionados con índices de centralidad . Las aplicaciones incluyen medir la influencia de cada persona en una red social , comprender el papel de los nodos de infraestructura en las redes de transporte , Internet o las redes urbanas , y la participación de un nodo determinado en la dinámica de las enfermedades.
El enfoque tradicional para comprender la importancia de los nodos es a través de indicadores de centralidad . Los índices de centralidad están diseñados para producir una clasificación que identifique con precisión los nodos más influyentes. Sin embargo, desde mediados de la década de 2000, los científicos sociales y los físicos de redes han comenzado a cuestionar la idoneidad de los índices de centralidad para comprender la influencia de los nodos. Las centralidades pueden indicar los nodos más influyentes, pero son bastante menos informativas para la gran mayoría de los nodos que no son muy influyentes.
El artículo de revisión de Borgatti y Everett de 2006 [1] mostró que la precisión de los índices de centralidad depende en gran medida de la topología de la red. Este hallazgo se ha observado repetidamente desde entonces. (por ejemplo, [2] [3] ). En 2012, Bauer y sus colegas nos recordaron que los índices de centralidad solo clasifican los nodos pero no cuantifican la diferencia entre ellos. [4] En 2013, Sikic y sus colegas presentaron pruebas sólidas de que los índices de centralidad subestiman considerablemente el poder de los nodos no centrales. [5] La razón es bastante clara. La precisión de una medida de centralidad depende de la topología de la red, pero las redes complejas tienen una topología heterogénea. Por lo tanto, una medida de centralidad que sea apropiada para identificar nodos altamente influyentes probablemente será inapropiada para el resto de la red. [3]
Esto ha inspirado el desarrollo de métodos novedosos diseñados para medir la influencia de todos los nodos de la red. Los más generales son la accesibilidad , que utiliza la diversidad de recorridos aleatorios para medir qué tan accesible es el resto de la red desde un nodo de inicio determinado, [6] y la fuerza esperada , derivada del valor esperado de la fuerza de infección. generado por un nodo. [3] Ambas medidas pueden calcularse de manera significativa únicamente a partir de la estructura de la red.
La Accesibilidad se deriva de la teoría de los paseos aleatorios. Mide la diversidad de paseos que se evitan a sí mismos y que parten de un nodo determinado. Un paseo por una red es una secuencia de vértices adyacentes; una caminata que evita a uno mismo visita (enumera) cada vértice como máximo una vez. El trabajo original utilizó paseos simulados de 60 metros de longitud para caracterizar la red de calles urbanas de una ciudad brasileña. [6] Posteriormente se formalizó como una forma modificada de grado jerárquico que controla tanto las probabilidades de transmisión como la diversidad de caminatas de una longitud fija determinada. [7]
El grado jerárquico mide el número de nodos alcanzables desde un nodo inicial realizando recorridos de longitud . Para un tipo fijo y de caminata, se llega a cada uno de estos vecinos con una probabilidad (potencialmente diferente) . Dado un vector de tales probabilidades, se define la accesibilidad del nodo a escala .
Las probabilidades pueden basarse en paseos aleatorios de probabilidad uniforme o modularse adicionalmente mediante ponderaciones de borde y/o probabilidades de transmisión explícitas (por borde). [7]
Se ha demostrado que la accesibilidad revela la estructura comunitaria en las redes urbanas, [6] corresponde al número de nodos que se pueden visitar en un período de tiempo definido, [7] y predice el resultado de los procesos de difusión del modelo epidemiológico SIR en redes con Gran diámetro y baja densidad . [2]
La fuerza esperada mide la influencia de los nodos desde una perspectiva epidemiológica. Es el valor esperado de la fuerza de infección generada por el nodo después de dos transmisiones.
La fuerza esperada de un nodo está dada por
donde la suma se toma sobre el conjunto de todos los posibles grupos de transmisión resultantes de dos transmisiones a partir de . Es decir, el nodo y dos de sus vecinos o uno de sus vecinos (llamado infectado) y un vecino del vecino infectado. contiene todos los ordenamientos posibles de los eventos de transmisión, por lo que dos grupos pueden contener los mismos nodos si se infectaron en un orden diferente. es el grado de cluster normalizado de cluster , es decir, el número de aristas con exactamente un punto final en cluster .
La definición se extiende naturalmente a las redes dirigidas al limitar la enumeración por la dirección del borde. Asimismo, la extensión a redes ponderadas, o redes con probabilidades de transmisión heterogéneas, es una cuestión de ajustar la normalización para incluir la probabilidad de que se forme ese grupo. También es posible utilizar más de dos transmisiones para definir el conjunto . [3]
Se ha demostrado que la fuerza esperada se correlaciona fuertemente con los resultados epidémicos de SI, SIS y SIR en una amplia gama de topologías de red, tanto simuladas como empíricas. [3] [8] También se ha utilizado para medir el potencial pandémico de los aeropuertos mundiales, [9] y se menciona en el contexto de pagos digitales, [10] ecología, [11] aptitud física, [12] y gestión de proyectos. [13]
Otros sugieren métricas que codifican explícitamente la dinámica de un proceso específico que se desarrolla en la red. La influencia dinámica es la proporción de caminatas infinitas que comienzan desde cada nodo, donde los pasos de la caminata se escalan de manera que se espera que la dinámica lineal del sistema converja a un estado estacionario no nulo. [14] El Impacto suma, a lo largo de caminatas cada vez más largas, la probabilidad de transmisión al nodo final de la caminata y que el nodo final no haya sido visitado previamente por una caminata más corta. [4] Si bien ambas medidas predicen bien el resultado de los sistemas dinámicos que codifican, en cada caso los autores admiten que los resultados de una dinámica no se traducen en otras dinámicas.
