Hispanopedia Wiki
Articulo de referencia

Métrica de influencia del nodo

En la teoría de grafos y el 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)...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de grafos y el 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 grafo. Están relacionadas con los índices de centralidad . Entre sus aplicaciones se incluyen la medición de la influencia de cada persona en una red social , la comprensión del 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.

Origen y desarrollo

El enfoque tradicional para comprender la importancia de los nodos se basa en indicadores de centralidad . Estos índices están diseñados para generar una clasificación que identifique con precisión los nodos más influyentes. Sin embargo, desde mediados de la década de 2000, científicos sociales y físicos de redes han comenzado a cuestionar la idoneidad de los índices de centralidad para comprender la influencia de los nodos. Si bien la centralidad puede indicar los nodos más influyentes, resulta menos informativa para la gran mayoría de los nodos que no son altamente 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 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 contundentes de que los índices de centralidad subestiman considerablemente el poder de los nodos que no son hubs [ 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 adecuada para identificar nodos altamente influyentes probablemente no sea apropiada 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 cuán accesible es el resto de la red desde un nodo inicial dado, [ 6 ] y la fuerza esperada , derivada del valor esperado de la fuerza de infección generada por un nodo. [ 3 ] Ambas medidas pueden calcularse de manera significativa a partir de la estructura de la red únicamente.

Accesibilidad

La accesibilidad se deriva de la teoría de los paseos aleatorios. Mide la diversidad de paseos que evitan un nodo y que parten de él. Un paseo en una red es una secuencia de vértices adyacentes; un paseo que evita un nodo visita cada vértice como máximo una vez. El trabajo original utilizó paseos simulados de longitud 60 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 paseos de una longitud fija. [ 7 ]

Definición

El grado jerárquico mide el número de nodos alcanzables desde un nodo inicial realizando recorridos de longitudh{\displaystyle h}. Para un fijoh{\displaystyle h}y tipo de recorrido, cada uno de estos vecinos es alcanzado con una probabilidad (potencialmente diferente)pagj(h){\displaystyle p_{j}^{(h)}}. Dado un vector de tales probabilidades, la accesibilidad del nodoi{\displaystyle i}a escalah{\displaystyle h}se define

κi(h)=exp⁡(−∑jpagj(h)registro⁡pagj(h)){\displaystyle \kappa _{i}^{(h)}=\exp \left(-\sum _{j}p_{j}^{(h)}\log p_{j}^{(h)}\right)}

Las probabilidades pueden basarse en paseos aleatorios de probabilidad uniforme, o bien estar moduladas adicionalmente por pesos de aristas y/o probabilidades de transmisión explícitas (por arista). [ 7 ]

Aplicaciones

Se ha demostrado que la accesibilidad revela la estructura de la comunidad en 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 propagación del modelo epidemiológico SIR en redes con gran diámetro y baja densidad . [ 2 ]

Fuerza esperada

La fuerza esperada mide la influencia de un nodo desde una perspectiva epidemiológica. Es el valor esperado de la fuerza de infección generada por el nodo tras dos transmisiones.

Definición

La fuerza esperada de un nodo i{\displaystyle i}es dado por

κi=−∑j=1Jdjregistro⁡(dj){\displaystyle \kappa _{i}=-\sum _{j=1}^{J}d_{j}\log(d_{j})}

donde la suma se toma sobre el conjuntoJ{\displaystyle J}de todos los posibles grupos de transmisión resultantes de dos transmisiones que comienzan desdei{\displaystyle i}. Es decir, nodoi{\displaystyle i}y dos de sus vecinos oi{\displaystyle i}, uno de sus vecinos (llamado infectado) y un vecino del vecino infectado.J{\displaystyle J}Contiene todos los posibles órdenes de los eventos de transmisión, por lo que dos clústeres pueden contener los mismos nodos si se infectaron en un orden diferente.dj{\displaystyle d_{j}}es el grado de clúster normalizado del clústerj∈J{\displaystyle j\in J}, es decir, el número de aristas con exactamente un extremo en el clústerj{\displaystyle j}.

La definición se extiende naturalmente a las redes dirigidas al limitar la enumeración.J{\displaystyle J}por dirección de borde. De igual modo, la extensión a redes ponderadas , o redes con probabilidades de transmisión heterogéneas, es cuestión de ajustar la normalización dedj{\displaystyle d_{j}}para incluir la probabilidad de que se forme ese grupo. También es posible utilizar más de dos transmisiones para definir el conjunto.J{\displaystyle J}. [ 3 ]

Aplicaciones

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 ha mencionado en el contexto de los pagos digitales, [ 10 ] la ecología, [ 11 ] la aptitud física, [ 12 ] y la gestión de proyectos. [ 13 ]

Otros enfoques

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 parten de 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, sobre longitudes de caminata crecientes, 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 a otras dinámicas.

Referencias

  1. ↑ Borgatti, Steve; Everett, Martin (2006). "Una perspectiva de la centralidad basada en la teoría de grafos". Redes sociales . 28 (4): 466– 484. doi : 10.1016/j.socnet.2005.11.005 .
  2. 1 2 da Silva, Renato; Viana, Matheus; da F. Costa, Luciano (2012). "Predicción de brotes epidémicos a partir de características individuales de los propagadores". J. Stat. Mech.: Theory Exp . 2012 (7) P07005. arXiv : 1202.0024 . Bibcode : 2012JSMTE..07..005A . doi : 10.1088/1742-5468/2012/07/p07005 . S2CID 2530998 . 
  3. 1 2 3 4 5 Abogado, Glenn (2015). "Comprender el poder de propagación de todos los nodos en una red: una perspectiva de tiempo continuo" . Sci Rep . 5 : 8665. arXiv : 1405.6707 . Bibcode : 2015NatSR...5.8665L . doi : 10.1038/srep08665 . PMC 4345333. PMID 25727453 .  
  4. 1 2 Bauer, Frank; Lizier, Joseph (2012). "Identificación de propagadores influyentes y estimación eficiente de números de infección en modelos epidémicos: un enfoque de conteo de caminatas". Europhys Lett . 99 (6) 68007. arXiv : 1203.0502 . Bibcode : 2012EL.....9968007B . doi : 10.1209/0295-5075/99/68007 . S2CID 9728486 . 
  5. ↑ Sikic, Mile; Lancic, Alen; Antulov-Fantulin, Nino; Stefanic, Hrvoje (2013). "Centralidad epidémica: ¿existe un impacto epidémico subestimado de los nodos periféricos de la red?". The European Physical Journal B . 86 (10): 1– 13. arXiv : 1110.2558 . Bibcode : 2013EPJB...86..440S . doi : 10.1140/epjb/e2013-31025-5 . S2CID 12052238 . 
  6. 1 2 3 Travencolo, B. a. N.; da F. Costa, Luciano (2008). "Accesibilidad en redes complejas". Phys Lett A . 373 (1): 89– 95. Bibcode : 2008PhLA..373...89T . doi : 10.1016/j.physleta.2008.10.069 .
  7. 1 2 3 Viana, Matheus; Batista, Joao; da F. Costa, Luciano (2012). "Número efectivo de nodos accedidos en redes complejas". Phys Rev E . 85 (3 pt 2) 036105. arXiv : 1101.5379 . Bibcode : 2012PhRvE..85c6105V . doi : 10.1103/PhysRevE.85.036105 . PMID 22587147 . S2CID 643417 .  
  8. ↑ Abogado, Glenn (2014). "Informe técnico: Rendimiento de la fuerza esperada en topologías de Internet a nivel AS". arXiv : 1406.4785 [ cs.NI ].
  9. ↑ Abogado, Glenn (2016). "Medición del potencial de los aeropuertos individuales para la propagación de pandemias en la red mundial de aerolíneas" . BMC Infectious Diseases . 16 70. doi : 10.1186/s12879-016-1350-4 . PMC 4746766. PMID 26861206 .  
  10. ↑ Milkau, Udo; Bott, Jürgen (2015). "Digitalización en los pagos: ¿De la interoperabilidad a los modelos centralizados?" . Journal of Payments Strategy & Systems . 9 (3): 321. doi : 10.69554/KUAW4429 .
  11. ↑ Jordan, Lyndon; Maguire, Sean; Hofmann, Hans; Kohda, Masanori (2016). "Los costos sociales y ecológicos de un fenotipo 'sobreextendido'" . Proceedings of the Royal Society B. 283 ( 1822) 20152359. doi : 10.1098/rspb.2015.2359 . PMC 4721094. PMID 26740619 .  
  12. ↑ Pereira, Vanessa; Gama, Maria; Sousa, Filipe; Lewis, Theodore; Gobatto, Claudio; Manchado-Gobatto, Fúlvia (2015). "Los modelos de redes complejas revelan correlaciones entre las métricas de la red, la intensidad del ejercicio y el papel de los cambios corporales en el proceso de fatiga" . Scientific Reports . 5 10489. Bibcode : 2015NatSR...510489P . doi : 10.1038/srep10489 . PMC 4440209. PMID 25994386 .  
  13. ↑ Ellinas, Christos; Allan, Neil; Durugbo, Christopher; Johansson, Anders (2015). "¿Qué tan robusto es su proyecto? De fallas locales a catástrofes globales: un enfoque de redes complejas para el riesgo sistémico del proyecto" . PLOS ONE . 10 (11) e0142469. Bibcode : 2015PLoSO..1042469E . doi : 10.1371/journal.pone.0142469 . PMC 4659599. PMID 26606518 .  
  14. ↑ Klemm, Konstantin; Serrano, M Ángeles ; Eguiluz, Victor; Miguel, Maxi San (2012). "Una medida del rol individual en la dinámica colectiva" . Sci Rep . 2 292. arXiv : 1002.4042 . Bibcode : 2012NatSR...2..292K . doi : 10.1038/srep00292 . PMC 3289910. PMID 22379597 .