En la ciencia de redes , una caminata aleatoria sesgada en un gráfico es un proceso de ruta temporal en el que una variable en evolución salta de su estado actual a uno de varios estados nuevos potenciales; a diferencia de una caminata puramente aleatoria , las probabilidades de los nuevos estados potenciales son desiguales.
Los recorridos aleatorios sesgados en un gráfico proporcionan un enfoque para el análisis estructural de gráficos no dirigidos con el fin de extraer sus simetrías cuando la red es demasiado compleja o cuando no es lo suficientemente grande para ser analizada por métodos estadísticos . El concepto de paseos aleatorios sesgados en un gráfico ha atraído la atención de muchos investigadores y empresas de datos durante la última década, especialmente en el transporte y las redes sociales . [1]
Modelo
Se han escrito muchas representaciones diferentes de los paseos aleatorios sesgados en gráficos basados en el propósito particular del análisis. Una representación común del mecanismo para gráficos no dirigidos es la siguiente: [2]
En un gráfico no dirigido , un caminante da un paso desde el nodo actual, al nodo Suponiendo que cada nodo tiene un atributo la probabilidad de saltar del nodo a es dado por:
dónde representa el peso topológico del borde que va desde a
De hecho, los pasos del caminante están sesgados por el factor de que puede diferir de un nodo a otro. [3]
Dependiendo de la red, el atributo se puede interpretar de manera diferente. Podría estar implícito como la atracción de una persona en una red social , podría ser la centralidad de intermediación o incluso podría explicarse como una característica intrínseca de un nodo. En caso de una caminata aleatoria justa en el gráfico es uno para todos los nodos.
En caso de caminos más cortos, paseos aleatorios [4] es el número total de las rutas más cortas entre todos los pares de nodos que pasan a través del nodo . De hecho, el caminante prefiere los nodos con mayor centralidad de intermediación, que se define a continuación:
Según la ecuación anterior, el tiempo de recurrencia a un nodo en la caminata sesgada viene dado por: [5]
Aplicaciones
Se han desarrollado diversas aplicaciones mediante el uso de recorridos aleatorios sesgados en gráficos; control de la difusión, [6] publicidad de productos en las redes sociales , [7] explicando la dispersión y redistribución de la población de animales y microorganismos, [8] detecciones comunitarias, [9] redes inalámbricas, [10] motores de búsqueda [11] y pronto.
Ver también
Referencias
- ^ Roberta Sinatra, Jesús Gómez-Gardeñes , Renaud Lambiotte, Vincenzo Nicosia y Vito Latora (marzo de 2011). "Paseos aleatorios de máxima entropía en redes complejas con información limitada". Revisión E física . 83 (3): 030103. arXiv : 1007.4936 . Código Bibliográfico : 2011PhRvE..83c0103S . doi : 10.1103 / PhysRevE.83.030103 . PMID 21517435 .Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ J. Gómez-Gardeñes; V. Latora (diciembre de 2008). "Tasa de entropía de los procesos de difusión en redes complejas". Revisión E física . 78 (6): 065102. arXiv : 0712.0278 . Código bibliográfico : 2008PhRvE..78f5102G . doi : 10.1103 / PhysRevE.78.065102 . PMID 19256892 .
- ^ R. Lambiotte, R. Sinatra, J.-C. Delvenne, TS Evans, M. Barahona, V. Latora (diciembre de 2010). "Gráficos de flujo: entretejiendo dinámica y estructura". Revisión E física . 84 (1): 017102. arXiv : 1012.1211 . Código bibliográfico : 2011PhRvE..84a7102L . doi : 10.1103 / PhysRevE.84.017102 . PMID 21867345 .Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ Blanchard, Volchenkov, D (2008). Análisis matemático de redes espaciales urbanas . Comprensión de sistemas complejos . doi : 10.1007 / 978-3-540-87829-2 . ISBN 978-3-540-87828-5.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ Volchenkov D; Blanchard P (2011). Paseos aleatorios justos y sesgados sobre gráficos no dirigidos y entropías relacionadas . Birkhäuser. pag. 380. ISBN 9780817649036.
- ^ Chung, Zhao, Fan, Wenbo (2010). PageRank y paseos aleatorios en gráficos . Fiesta de Combinatoria e Informática . Estudios Matemáticos de la Sociedad Bolyai. 20 . págs. 43–62. CiteSeerX 10.1.1.157.7116 . doi : 10.1007 / 978-3-642-13580-4_3 . ISBN 978-3-642-13579-8.
- ^ Adal, KM (junio de 2010). "Enrutamiento basado en paseo aleatorio sesgado para redes móviles ad hoc". 2010 Congreso Internacional de Sistemas Inteligentes y Avanzados . págs. 1–6. doi : 10.1109 / ICIAS.2010.5716181 . ISBN 978-1-4244-6623-8.
- ^ Kakajan Komurov, Michael A. White, Prahlad T. Ram (agosto de 2010). "Uso de paseos aleatorios con sesgo de datos en gráficos para la recuperación de redes específicas del contexto a partir de datos genómicos" . PLOS Comput Biol . 6 (8): e1000889. Código bibliográfico : 2010PLSCB ... 6E0889K . doi : 10.1371 / journal.pcbi.1000889 . PMC 2924243 . PMID 20808879 .Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ JK Ochab; Z. Burda (enero de 2013). "Paseo aleatorio de entropía máxima en la detección de la comunidad". Temas especiales de la revista European Physical Journal . 216 : 73–81. arXiv : 1208.3688 . Código Bibliográfico : 2013EPJST.216 ... 73O . doi : 10.1140 / epjst / e2013-01730-6 .
- ^ Beraldi, Roberto (abril de 2009). "Paseos aleatorios sesgados en redes inalámbricas uniformes". Transacciones IEEE sobre informática móvil . 8 (4): 500–513. doi : 10.1109 / TMC.2008.151 .
- ^ Da-Cheng Nie, Zi-Ke Zhang, Qiang Dong, Chongjing Sun, Yan Fu (julio de 2014). "Filtrado de información a través de una caminata aleatoria sesgada en una red social acoplada" . The Scientific World Journal . 2014 : 829137. doi : 10.1155 / 2014/829137 . PMC 4132410 . PMID 25147867 .Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
enlaces externos
- Gábor Simonyi, "Graph Entropy: A Survey" . En Optimización combinatoria (ed. W. Cook, L. Lovász y P. Seymour). Providence, RI: Amer. Matemáticas. Soc., Págs. 399–441, 1995.
- Anne-Marie Kermarrec, Erwan Le Merrer, Bruno Sericola, Gilles Trédan, "Evaluación de la calidad de una topología de red mediante paseos aleatorios" en Gadi Taubenfeld (ed.) Computación distribuida