viernes, 28 de junio de 2019

LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS


PAGERANK , CONTINUACIÓN

Computacion editar ]

El PageRank se puede calcular de forma iterativa o algebraica. El método iterativo puede verse como el método de iteración de potencia [31] [32] o el método de potencia. Las operaciones matemáticas básicas realizadas son idénticas.

Iterativo editar ]

, se asume una distribución de probabilidad inicial, usualmente
.
donde N es el número total de páginas, y  es la página i en el momento 0.
En cada paso del tiempo, el cálculo, como se detalla arriba, produce
donde d es el factor de amortiguación,
o en notación matricial
, (*)
dónde  y  es el vector de columna de longitud  conteniendo solo unos.
La matriz  Se define como
es decir,
,
dónde denota la matriz de adyacencia de la gráfica y Es la matriz diagonal con los grados superiores en diagonal.
El cálculo de probabilidad se realiza para cada página en un punto de tiempo y luego se repite para el siguiente punto de tiempo. El cómputo termina cuando para algunos pequeños.
,
Es decir, cuando se asume la convergencia.

Algebraico editar ]

-Por (es decir, en el estado estacionario ), la ecuación anterior (*) lee
(**)
La solución está dada por
,
con la matriz de identidad .
La solución existe y es única para Esto se puede ver notando queEs por construcción una matriz estocástica y, por lo tanto, tiene un valor propio igual a uno como consecuencia del teorema de Perron-Frobenius.

Método de poder editar ]

Si la matriz  Es una probabilidad de transición, es decir, columna-estocástica y  es una distribución de probabilidad (es decir,  dónde es la matriz de todos los unos), ec. (**) es equivalente a
(***)
Por lo tanto PageRank  es el principal eigenvector de Una forma rápida y fácil de calcular esto es usando el método de poder : comenzando con un vector arbitrario, el operador  Se aplica en sucesión, es decir,
,
hasta
.
Tenga en cuenta que en la ec. (***) la matriz en el lado derecho entre paréntesis puede interpretarse como
,
dónde Es una distribución de probabilidad inicial. En el caso actual
.
Por último, si  tiene columnas con solo cero valores, deben reemplazarse con el vector de probabilidad inicial En otras palabras,
,
donde la matriz  Se define como
,
con
En este caso, los dos cálculos anteriores utilizando  Solo da el mismo PageRank si sus resultados están normalizados:
.

Implementación editar ]

MATLAB / Octave editar ]

% Matriz de adyacencia del parámetro M donde M_i, j representa el enlace de 'j' a 'i', de manera que para toda la 
suma de 
'j' (i, M_i, j) = 1 % Parámetro d factor de amortiguamiento 
% Parámetro v_quadratic_error error cuadrático para v 
% Return v, un vector de rangos tal que v_i es el i-th rank de [0, 1]

función  [v] = ranking2 ( M, d, v_quadratic_error ) 

N  =  talla ( M ,  2 );  % N es igual a cualquier dimensión de M y el número de documentos 
v  =  rand ( N ,  1 ); 
v  =  v.  /  norma ( v ,  1 );    % Esto es ahora L1, no L2 
last_v  =  ones ( N ,  1 )  *  inf ; 
M_hat  =  ( d  . *  M )  +  ((( 1  -  d )  / N )  . *  Unos ( N ,  N ));

while ( norm ( v  -  last_v ,  2 )  >  v_quadratic_error ) 
 last_v  =  v ; 
 v  =  M_hat  *  v ; 
        % eliminado la norma L2 del 
fin de PR iterado

 función% final
Ejemplo de código que llama a la función de rango definida anteriormente:
M  =  [ 0  0  0  0  1  ;  0.5  0  0  0  0  ;  0.5  0  0  0  0  ;  0  1  0.5  0  0  ;  0  0  0.5  1  0 ]; 
Rango2 ( M ,  0.80 ,  0.001 )

Python editar ]

# Matriz de adyacencia del parámetro M donde M_i, j representa el enlace de 'j' a 'i', de modo que para todos 'j' 
# sum (i, M_i, j) = 1 
# Factor de amortiguamiento del parámetro d (valor predeterminado 0.85) 
# Parámetro error cuadrático de eps para v (valor predeterminado 1.0e-8) 
# Devuelve v, un vector de rangos tal que v_i es el i-th rango de [0, 1]

importar  numpy  como  np

def  pagerank ( M ,  eps = 1.0E-8 ,  d = 0,85 ): 
    N  =  M . forma [ 1 ] 
    v  =  np . al azar . rand ( N ,  1 ) 
    v  =  v  /  np . Linalg . norma ( v ,  1 ) 
    last_v  =  np . unos (( N ,  1 ), dtype = np . float32 )  *  100
    
    mientras que  np . Linalg . norm ( v  -  last_v ,  2 )  >  eps : 
        last_v  =  v 
        v  =  d  *  np . matmul ( M ,  v )  +  ( 1  -  d )  /  N 
    retorno  v

M  =  np . matriz ([[ 0 ,  0 ,  0 ,  0 ,  1 ], 
              [ 0.5 ,  0 ,  0 ,  0 ,  0 ], 
              [ 0.5 ,  0 ,  0 ,  0 ,  0 ], 
              [ 0 ,  1 ,  0.5 ,  0 ,  0 ] , 
              [ 0 ,  0 ,  0.5 ,  1 ,  0]]) 
v  =  pagerank ( M ,  0.001 ,  0.85 )
Este ejemplo toma 13 iteraciones para converger.

Variaciones editar ]

PageRank de un grafo no dirigido editar ]

El PageRank de un gráfico G no dirigido está estadísticamente cerca de la distribución de grados del gráfico G, [33] pero generalmente no son idénticos: si R es el vector de PageRank definido anteriormente, y D es el vector de distribución de grados
dónde  denota el grado de vértice y E es el conjunto de bordes del gráfico, luego, con , por: [34]
es decir, el PageRank de un gráfico no dirigido es igual al vector de distribución de grados si y solo si el gráfico es regular, es decir, cada vértice tiene el mismo grado.

Generalización de PageRank y centralidad del vector propio para clasificar objetos de dos tipos editar ]

Una generalización de PageRank para el caso de clasificar dos grupos interactivos de objetos se describió en [35]En las aplicaciones puede ser necesario modelar sistemas que tengan objetos de dos tipos en los que se define una relación ponderada en pares de objetos. Esto lleva a considerar gráficas bipartitas . Para tales gráficos se pueden definir dos matrices irreductibles positivas o no negativas relacionadas correspondientes a conjuntos de particiones de vértice. Uno puede calcular clasificaciones de objetos en ambos grupos como vectores propios correspondientes a los valores propios positivos máximos de estas matrices. Los vectores propios normalizados existen y son únicos según el teorema de Perron o Perron-Frobenius. Ejemplo: consumidores y productos. La relación peso es la tasa de consumo del producto.

Algoritmo distribuido para el cálculo de PageRank editar ]

Hay simple y rápido paseo aleatorio basados en algoritmos distribuidos para calcular el PageRank de nodos en una red. [36] Presentan un algoritmo sencillo que lleva redondeos con alta probabilidad en cualquier gráfico (dirigido o no dirigido), donde n es el tamaño de la red y  es la probabilidad de reinicio (también se denomina factor de amortiguamiento) utilizado en el cálculo de PageRank. También presentan un algoritmo más rápido que llevaRondas en gráficos no dirigidos. Ambos de los algoritmos anteriores son escalables, ya que cada nodo procesa y envía solo un número pequeño de bits por polilogarítmico en n, el tamaño de la red.

Barra de herramientas de Google editar ]

La barra Google tenía una función de PageRank que mostraba el PageRank de una página visitada como un número entero entre 0 y 10. Los sitios web más populares mostraban un PageRank de 10. El menos mostró un PageRank de 0. Google no ha revelado el método específico para determinar un valor de PageRank de la barra de herramientas, que debe considerarse solo como una indicación aproximada del valor de un sitio web. En marzo de 2016, Google anunció que ya no admitiría esta función, y la API subyacente pronto dejará de funcionar. [37]

Rango SERP editar ]

La página de resultados del motor de búsqueda (SERP) es el resultado real devuelto por un motor de búsqueda en respuesta a una consulta de palabras clave. El SERP consiste en una lista de enlaces a páginas web con fragmentos de texto asociados. El rango de SERP de una página web se refiere a la ubicación del enlace correspondiente en el SERP, donde una ubicación más alta significa un rango de SERP más alto. El rango SERP de una página web es una función no solo de su PageRank, sino de un conjunto de factores relativamente grande y continuamente ajustado (más de 200). [38] La optimización de motores de búsqueda (SEO) está orientada a influir en el rango de SERP para un sitio web o un conjunto de páginas web.
El posicionamiento de una página web en Google SERPs para una palabra clave depende de la relevancia y la reputación, también conocida como autoridad y popularidad. PageRank es una indicación de Google de su evaluación de la reputación de una página web: no es específica de palabras clave. Google utiliza una combinación de autoridad de página web y sitio web para determinar la autoridad general de una página web que compite por una palabra clave. [39] El PageRank de la página de inicio de un sitio web es la mejor indicación que ofrece Google para la autoridad del sitio web. [40]
Después de la introducción de Google Places en el SERP orgánico convencional, muchos otros factores además de PageRank afectan la clasificación de una empresa en Resultados de Negocios Locales. [41]

Directorio de Google PageRank editar ]

El Google Directory PageRank fue una medida de 8 unidades. A diferencia de la Barra de herramientas de Google, que muestra un valor numérico de PageRank al pasar el mouse sobre la barra verde, el Directorio de Google solo muestra la barra, nunca los valores numéricos. El Directorio de Google se cerró el 20 de julio de 2011. [42]

PageRank falso o falsificado editar ]

En el pasado, el PageRank que se muestra en la barra de herramientas fue fácilmente manipulado. La redirección de una página a otra, ya sea a través de una respuesta HTTP 302 o una etiqueta meta "Actualizar" , hizo que la página de origen adquiriera el PageRank de la página de destino. Por lo tanto, una nueva página con PR 0 y ningún enlace entrante podría haber adquirido PR 10 al redirigir a la página de inicio de Google. Esta técnica de spoofing era una vulnerabilidad conocida. La suplantación de identidad generalmente se puede detectar al realizar una búsqueda en Google de una URL de origen; Si la URL de un sitio completamente diferente se muestra en los resultados, la última URL puede representar el destino de una redirección.

Manipulando el PageRank editar ]

Para propósitos de optimización de motores de búsqueda , algunas compañías ofrecen vender enlaces de PageRank altos a los webmasters. [43] Como se cree que los enlaces de las páginas de relaciones públicas superiores son más valiosos, tienden a ser más caros. Puede ser una estrategia de marketing efectiva y viable para comprar anuncios de enlaces en páginas de contenido de calidad y sitios relevantes para dirigir el tráfico y aumentar la popularidad de enlaces de un webmaster. Sin embargo, Google ha advertido públicamente a los webmasters que si están o se descubrió que están vendiendo enlaces con el fin de conferir el PageRank y la reputación, sus enlaces serán devaluados (ignorados en el cálculo de los PageRanks de otras páginas). La práctica de comprar y vender enlaces se debate intensamente en la comunidad de webmasters. Google aconseja a los webmasters que utilicen el nofollow Valor de atributo HTML en enlaces patrocinados. Según Matt Cutts , Google está preocupado por los webmasters que intentan jugar con el sistema y, por lo tanto, reducir la calidad y la relevancia de los resultados de búsqueda de Google. [43]

Dirigido modelo de surfista editar ]

Un surfista más inteligente que, probabilísticamente, salta de una página a otra en función del contenido de las páginas y consulta los términos del surfista que está buscando. Este modelo se basa en una puntuación de PageRank dependiente de la consulta de una página que, como su nombre indica, también es una función de la consulta. Cuando se le da una consulta de varios términos, Q = {q1, q2, ...}, el internauta selecciona aq de acuerdo con alguna distribución de probabilidad, P (q) y usa ese término para guiar su comportamiento durante un gran número de pasos. A continuación, selecciona otro término según la distribución para determinar su comportamiento, y así sucesivamente. La distribución resultante en las páginas web visitadas es QD-PageRank. [44]

Componentes sociales editar ]

El algoritmo PageRank tiene efectos importantes en la sociedad, ya que contiene una influencia social. A diferencia del punto de vista científico del PageRank como un algoritmo, las humanidades lo ven a través de una lente que examina sus componentes sociales. dudoso  ] En estos casos, se analiza y revisa no por su avance tecnológico en el campo de los motores de búsqueda, sino por sus influencias sociales. [45]Laura Granka analiza el PageRank al describir cómo las páginas no se clasifican simplemente por popularidad, ya que contienen una confiabilidad que les da una calidad confiable. Esto ha conducido a un desarrollo de comportamiento que está directamente vinculado al PageRank. El PageRank se considera el rango definitivo de productos y negocios y, por lo tanto, puede manipular el pensamiento. La información que está disponible para los individuos es lo que da forma al pensamiento y la ideología y PageRank es el dispositivo que muestra esta información. Los resultados que se muestran son el foro en el que la información se entrega al público y estos resultados tienen un impacto social, ya que afectarán la forma en que una persona piensa y actúa.
[46] Katja Mayer ve a PageRank como una red social ya que conecta puntos de vista y pensamientos diferentes en un solo lugar. Las personas acuden al PageRank para obtener información y están inundadas con citas de otros autores que también tienen una opinión sobre el tema. Esto crea un aspecto social donde todo se puede discutir y recopilar para provocar el pensamiento. Existe una relación social entre el PageRank y las personas que lo usan, ya que se adapta y cambia constantemente a los cambios en la sociedad moderna. La visualización de la relación entre el PageRank y el individuo a través de la sociometría permite un análisis profundo de la conexión resultante.
[47] Matteo Pasquinelli considera que la base de la creencia de que el PageRank tiene un componente social reside en la idea de economía de la atenciónCon la economía de la atención, el valor se coloca en los productos que reciben una mayor atención humana y los resultados en la parte superior del PageRank generan una mayor cantidad de atención que en las páginas posteriores. Los resultados con el PageRank más alto, por lo tanto, entrarán en la conciencia humana en mayor medida. Estas ideas pueden influir en la toma de decisiones y las acciones del espectador tienen una relación directa con el PageRank. Poseen un mayor potencial para atraer la atención de un usuario ya que su ubicación aumenta la economía de atención asociada al sitio. Con esta ubicación, pueden recibir más tráfico y su mercado en línea tendrá más compras. El PageRank de estos sitios les permite ser confiables y son capaces de convertir esta confianza en un mayor negocio.

Otros usos editar ]

Las matemáticas de PageRank son completamente generales y se aplican a cualquier gráfico o red en cualquier dominio. Por lo tanto, el PageRank ahora se usa regularmente en bibliometría, análisis de redes sociales y de información, y para la predicción y recomendación de enlaces. Incluso se utiliza para el análisis de sistemas de redes viales, así como para biología, química, neurociencia y física. [48]

La investigación científica y el mundo académico editar ]

Pagerank se ha utilizado recientemente para cuantificar el impacto científico de los investigadores. Las redes de colaboración y citas subyacentes se utilizan junto con el algoritmo de pagerank para crear un sistema de clasificación para publicaciones individuales que se propaga a autores individuales. El nuevo índice conocido como pagerank-index (Pi) ha demostrado ser más justo en comparación con el índice h en el contexto de muchos inconvenientes exhibidos por el índice h. [49]
Para el análisis de redes de proteínas en biología, PageRank también es una herramienta útil. [50] [51]
En cualquier ecosistema, se puede usar una versión modificada de PageRank para determinar las especies que son esenciales para la salud continua del medio ambiente. [52]
Un nuevo uso similar de PageRank es clasificar los programas de doctorado académico en función de sus registros de colocación de sus graduados en posiciones de profesores. En términos de PageRank, los departamentos académicos se vinculan entre sí mediante la contratación de sus profesores entre sí (y de ellos mismos). [53]
Una versión de PageRank ha sido propuesto recientemente como un reemplazo para el tradicional Institute for Scientific Information (ISI), factor de impacto , [54] y aplicado en Eigenfactor , así como en SCImago . En lugar de simplemente contar la cita total de una revista, la "importancia" de cada cita se determina de una manera PageRank.
En neurociencia , se ha encontrado que el PageRank de una neurona en una red neuronal se correlaciona con su velocidad de disparo relativa. [55]

Uso de internet editar ]

Twitter utiliza el PageRank personalizado para presentar a los usuarios otras cuentas que deseen seguir. [56]
El producto de búsqueda en el sitio de Swiftype crea un "PageRank que es específico para sitios web individuales" al observar las señales de importancia de cada sitio y priorizar el contenido según factores como el número de enlaces de la página de inicio. [57]
Un rastreador web puede usar PageRank como una de las métricas de importancia que utiliza para determinar qué URL visitar durante un rastreo de la web. Uno de los primeros documentos de trabajo [58] que se usaron en la creación de Google es el rastreo eficiente a través del pedido de URL , [59] que analiza el uso de una serie de métricas de importancia diferentes para determinar qué tan profundamente, y qué parte de un sitio Google se arrastrará PageRank se presenta como una de varias métricas de importancia, aunque hay otras enumeradas, como el número de enlaces entrantes y salientes para una URL, y la distancia desde el directorio raíz en un sitio a la URL.
El PageRank también se puede utilizar como una metodología para medir el impacto aparente de una comunidad como Blogosphere en la Web en general. Este enfoque utiliza, por lo tanto, el PageRank para medir la distribución de la atención como reflejo del paradigma de red sin escala . cita requerida ]

Otras aplicaciones editar ]

En 2005, en un estudio piloto en Pakistán, Structural Deep Democracy, SD2 [60] [61] se usó para la selección de liderazgo en un grupo de agricultura sostenible llamado Contact Youth. SD2 utiliza PageRank para el procesamiento de los votos de proxy transitivos, con las restricciones adicionales de exigir al menos dos poderes iniciales por votante, y todos los votantes son candidatos de poder. Se pueden construir variantes más complejas sobre SD2, como agregar proxies especializados y votos directos para problemas específicos, pero SD2 como el sistema paraguas subyacente, exige que siempre se usen proxies generalistas.
En el deporte, el algoritmo PageRank se ha utilizado para clasificar el rendimiento de: equipos en la National Football League (NFL) en los Estados Unidos; [62] futbolistas individuales; [63] y los atletas en la Liga de Diamantes. [64]
PageRank se ha utilizado para clasificar espacios o calles para predecir cuántas personas (peatones o vehículos) llegan a los espacios o calles individuales. [65] [66] En la semántica léxica se ha utilizado para realizar la Desambiguación del Sentido de la Palabra , [67] Semejanza semántica , [68] y también para clasificar automáticamente las sinteestades de WordNet de acuerdo con la fuerza con que poseen una propiedad semántica dada, como la positividad o negatividad [69]

nofollow editar ]

A principios de 2005, Google implementó un nuevo valor, " nofollow ", [70] para el atributo rel del enlace HTML y los elementos de anclaje, de modo que los desarrolladores de sitios web y los bloggers puedan crear enlaces que Google no tendrá en cuenta para los propósitos de PageRank: son Enlaces que ya no constituyen un "voto" en el sistema PageRank. La relación nofollow se agregó en un intento de ayudar a combatir la indexación de spam .
Como ejemplo, las personas pueden crear previamente muchas publicaciones en el tablero de mensajes con enlaces a su sitio web para inflar artificialmente su PageRank. Con el valor nofollow, los administradores del panel de mensajes pueden modificar su código para insertar automáticamente "rel = 'nofollow" en todos los hipervínculos de las publicaciones, lo que evita que el PageRank se vea afectado por esas publicaciones en particular. Este método de evitar, sin embargo, también tiene varios inconvenientes, como la reducción del valor del enlace de los comentarios legítimos. (Ver: Spam en blogs # nofollow )
En un esfuerzo por controlar manualmente el flujo de PageRank entre páginas dentro de un sitio web, muchos webmasters practican lo que se conoce como PageRank Sculpting [71], que es el acto de colocar estratégicamente el atributo nofollow en ciertos enlaces internos de un sitio web para canalizar PageRank hacia esas páginas que el webmaster considera las más importantes. Esta táctica se ha utilizado desde el inicio del atributo nofollow, pero puede que ya no sea efectiva desde que Google anunció que el bloqueo de la transferencia de PageRank con nofollow no redirige ese PageRank a otros enlaces. [72]

Depredación editar ]

PageRank estuvo una vez disponible para los mantenedores de sitios verificados a través de la interfaz de las Herramientas para webmasters de Google. Sin embargo, el 15 de octubre de 2009, un empleado de Google confirmó que la compañía había eliminado PageRank de su sección de Herramientas para webmasters , y dijo que "Hemos estado diciéndole a las personas que no deberían centrarse en el PageRank tanto. Muchos sitios los propietarios parecen pensar que es la métrica más importante que deben rastrear, lo que simplemente no es cierto ". [73] Además, el indicador de PageRank no está disponible en el navegador Chrome de Google .
El rango de la página visible se actualiza muy poco. Se actualizó por última vez en noviembre de 2013. En octubre de 2014, Matt Cutts anunció que no se enviaría otra actualización de página visible. [74]
A pesar de que el PageRank de la "barra de herramientas" es menos importante para los propósitos de SEO , la existencia de vínculos de retroceso de los sitios web más populares continúa impulsando una página web más arriba en los rankings de búsqueda. [75]
Google explicó los motivos de la desaprobación de PageRank en Q&A #March y anunció Enlaces y contenido como los Factores de Clasificación más importantes. RankBrain fue anunciado como el Factor de Clasificación # 3 en octubre de 2015, por lo que Google ya confirmó oficialmente los 3 factores principales. [76]
El 15 de abril de 2016, Google ha cerrado oficialmente sus datos de PageRank de la barra de herramientas de Google al público. Google había declarado su intención de eliminar la puntuación de PageRank de la barra de herramientas de Google varios meses antes. [77] Google seguirá utilizando la puntuación de PageRank al determinar cómo clasificar el contenido en los resultados de búsqueda.

No hay comentarios:

Publicar un comentario