Hispanopedia Wiki
Articulo de referencia

modelo de navegación aleatoria

El modelo de navegación aleatoria es un modelo gráfico que describe la probabilidad de que un usuario aleatorio visite una página web . El modelo intenta predecir la probabilida...

Hispanopedia WikiContenido en espanolLectura gratuita

El modelo de navegación aleatoria es un modelo gráfico que describe la probabilidad de que un usuario aleatorio visite una página web . El modelo intenta predecir la probabilidad de que un internauta aleatorio llegue a una página haciendo clic en un enlace o accediendo directamente al sitio, por ejemplo, introduciendo la URL en la barra de direcciones. Por ello, se parte de la premisa de que todos los usuarios que navegan por internet acabarán dejando de seguir enlaces para cambiar a otro sitio. El modelo es similar a una cadena de Markov , donde los estados de la cadena son las páginas web que visita el usuario y las transiciones son enlaces igualmente probables entre estas páginas.

Descripción

Navegación a través de hipervínculos, después de llegar directamente a la página de inicio de un sitio.

Un usuario navega por internet de dos maneras principales: puede acceder a un sitio directamente introduciendo su URL o haciendo clic en un marcador , o puede utilizar una serie de hipervínculos para llegar a la página deseada. El modelo del navegante aleatorio supone que el enlace que el usuario selecciona a continuación se elige al azar. El modelo también supone que el número de enlaces sucesivos no es infinito; en algún momento, el usuario perderá el interés y abandonará el sitio actual para acceder a uno completamente nuevo. [ 1 ]

El modelo de navegación aleatoria se presenta como una serie de nodos que indican páginas web a las que los usuarios pueden acceder aleatoriamente. Se añade un nuevo nodo al grafo cuando se publica un nuevo sitio web. El movimiento alrededor de los nodos del grafo se modela eligiendo un nodo inicial al azar y luego realizando un recorrido corto y aleatorio de los nodos, o paseo aleatorio . Este recorrido es análogo a cuando un usuario accede a un sitio web y luego sigue un hipervínculo.t{\displaystyle t}Número de veces, hasta que el usuario abandone la página o acceda a otro sitio. Las conexiones con otros nodos de este gráfico se forman cuando se colocan enlaces salientes en la página.

Definiciones de gráficos

En el modelo de navegación aleatoria, los grafos web se presentan como una secuencia de grafos dirigidos.GRAMOt,t=1,2,…{\displaystyle G_{t},t=1,2,\ldots }de tal manera que un gráficoGRAMOt{\displaystyle G_{t}}tienet{\displaystyle t}vértices yt{\displaystyle t}aristas. El proceso de definición de grafos se parametriza con una probabilidadpag{\displaystyle p}, por lo tanto dejamosq=1−pag{\displaystyle q=1-p}. [ 2 ]

Los nodos del modelo llegan uno a uno, formandok{\displaystyle k}conexiones con el gráfico existenteGRAMOt{\displaystyle G_{t}}En algunos modelos, las conexiones representan aristas dirigidas, y en otros, representan aristas no dirigidas. Los modelos comienzan con un solo nodo.v0{\displaystyle v_{0}}y tenerk{\displaystyle k}bucles propios .vt{\displaystyle v_{t}}denota un vértice añadido en eltth{\displaystyle t^{th}}paso, ynorte{\displaystyle n}denota el número total de vértices. [ 1 ]

Modelo 1. (Caminata de 1 paso con bucle automático)

En ese momentot{\displaystyle t}, vérticevt{\displaystyle v_{t}}marcask{\displaystyle k}conexiones pork{\displaystyle k}iteraciones de los siguientes pasos:

  1. Seleccione un nodo existentev{\displaystyle v}uniformemente al azar de{v0,v1,…,vt−1}{\displaystyle \{v_{0},v_{1},\ldots,v_{t-1}\}}
  2. Con probabilidadpag{\displaystyle p}Alójate env{\displaystyle v}; con probabilidad1−pag{\displaystyle 1-p}dar un paso hacia un vecino al azar dev{\displaystyle v}
  3. Agregue un borde devt{\displaystyle v_{t}}al nodo actual

Para los grafos dirigidos, las aristas añadidas son dirigidas desdevt{\displaystyle v_{t}}en el grafo existente. Las aristas no están dirigidas en los respectivos grafos no dirigidos.

Modelo 2. (Paseos aleatorios con lanzamientos de moneda)

En ese momentot{\displaystyle t}, vérticevt{\displaystyle v_{t}}marcask{\displaystyle k}conexiones pork{\displaystyle k}iteraciones de los siguientes pasos:

  1. Seleccione un nodo existentev{\displaystyle v}uniformemente al azar de{v0,v1,...,vt−1}{\displaystyle \{v_{0},v_{1},...,v_{t-1}\}}
  2. Lanzar una moneda al aire con sesgopag{\displaystyle p}
  3. Si la moneda cae cara, añade una ventaja devt{\displaystyle v_{t}}al nodo actual y detenerse
  4. Si sale cruz, muévase a un vecino aleatorio del nodo actual y vuelva al paso 2.

Para los grafos dirigidos, las aristas añadidas son dirigidas desdevt{\displaystyle v_{t}}en el grafo existente. Las aristas no están dirigidas en los respectivos grafos no dirigidos.

Limitaciones

El modelo estándar de navegación aleatoria presenta algunas limitaciones, una de las cuales es que ignora el contenido de los sitios que los usuarios seleccionan, ya que asume que los enlaces se eligen al azar. Dado que los usuarios suelen tener un objetivo en mente al navegar por internet, el contenido de los sitios enlazados es un factor determinante para que hagan clic o no en un enlace. [ 1 ] [ 2 ]

Solicitud

La centralidad de vector propio normalizada combinada con la suposición del modelo de surfista aleatorio de saltos aleatorios creó la base del algoritmo PageRank de Google . [ 2 ] [ 3 ]

Véase también

Referencias

  1. 1 2 3 Blum, Avrim; Chan, TH. Hubert; Rwebangira, Mugizi Robert (21 de enero de 2006). Escrito en 3600 University City Science Center, Filadelfia, PA, Estados Unidos. "Un modelo de grafo web de surf aleatorio" (PDF) . Departamento de Ciencias de la Computación. ANALCO '06: Actas de la reunión sobre algoritmos analíticos y combinatoria . Universidad Carnegie Mellon: Sociedad de Matemáticas Industriales y Aplicadas: 238–246 .{{cite journal}}: CS1 mantenimiento: ubicación ( enlace )
  2. 1 2 3 Chebolu, Prasad; Melsted, Páll (1 de enero de 2008). "PageRank y el modelo del surfista aleatorio" (PDF) . Actas del decimonoveno simposio anual ACM-SIAM sobre algoritmos discretos . Departamento de Ciencias Matemáticas, Universidad Carnegie Mellon: 1010–1018 .
  3. ↑ Zaki, Mohammed J.; Meira, Jr., Wagner (2014). Minería y análisis de datos: conceptos fundamentales y algoritmos . Cambridge University Press. ISBN 9780521766333.
  • Estudio de caso sobre usuarios aleatorios de internet
  • El libro "Minería y análisis de datos: conceptos fundamentales y algoritmos" está disponible para su descarga gratuita para uso personal aquí.
  • Investigación de Microsoft sobre PageRank y el modelo Random Surfer.
  • Artículo sobre cómo la búsqueda web de Google implementa PageRank para encontrar resultados de búsqueda relevantes.
Lecturas relacionadas
6 articulos
Teoría de grafosTeoría de grafosEn matemáticas , la teoría de grafos es el estudio de los grafos , que son estructuras matemáticas utilizadas para modelar relaciones por pares ent...Página webCada artículo de Wikipedia es una página web distinta. La URL se puede ver en la barra de direcciones del navegador en la parte superior. Una págin...HiperenlaceHiperenlaceEn informática , un hipervínculo , o simplemente un enlace , es una referencia digital a datos que el usuario puede seguir o hacia los que puede se...URLUn localizador uniforme de recursos ( URL ), conocido coloquialmente como una dirección en la Web , [1] es una referencia a un recurso que especifi...Cadena de MarkovCadena de MarkovDiagrama que representa un proceso de Markov de dos estados. Los números representan la probabilidad de cambiar de un estado a otro. Una cadena de ...Página de inicioPágina de inicioUna página de inicio (o homepage ) es la página web principal de un sitio web . [1] El término también puede referirse a la página de inicio que se...