LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

El diseño espectral es una clase de algoritmo para dibujar gráficos . El diseño utiliza los vectores propios de una matriz, como la matriz de Laplace de la gráfica, como coordenadas cartesianas de los vértices de la gráfica.

La idea del diseño es calcular los dos valores propios más grandes (o más pequeños) y los vectores propios correspondientes de la matriz laplaciana de la gráfica y luego usarlos para colocar realmente los nodos. Por lo general, los nodos se colocan en el plano bidimensional, se puede encontrar una inserción en más dimensiones utilizando más vectores propios. Para colocar realmente un nodo desde un gráfico que corresponde a una fila / columna i en la matriz laplaciana (simétrica), la coordenada x es el valor de la coordenada i-th del primer vector propio. Correspondientemente, el componente i-th del segundo vector propio describe la coordenada y del punto i.

algoritmo de Girvan-Newman (llamado así por Michelle Girvan y Mark Newman ) es un método jerárquico utilizado para detectar comunidades en sistemas complejos . ^[1]

Intermediación borde y estructura de la comunidad [ editar ]

El algoritmo de Girvan-Newman detecta comunidades mediante la eliminación progresiva de bordes de la red original. Los componentes conectados de la red restante son las comunidades. En lugar de tratar de construir una medida que nos diga qué bordes son los más centrales para las comunidades, el algoritmo de Girvan-Newman se centra en los bordes que son más probables entre las comunidades.

El intervalo entre vértices es un indicador de nodos altamente centrales en las redes. Para cualquier nodo$${\ displaystyle i}, el intervalo entre vértices se define como el número de rutas más cortas entre pares de nodos que lo atraviesan. Es relevante para los modelos en los que la red modula la transferencia de bienes entre los puntos de inicio y final conocidos, bajo el supuesto de que dicha transferencia busca la ruta más corta disponible.

El algoritmo de Girvan-Newman extiende esta definición al caso de los bordes, definiendo la "distancia de borde" de un borde como el número de rutas más cortas entre pares de nodos que se ejecutan a lo largo. Si hay más de una ruta más corta entre un par de nodos, a cada ruta se le asigna un peso igual, de manera que el peso total de todas las rutas sea igual a la unidad. Si una red contiene comunidades o grupos que solo están conectados de forma flexible por unos pocos bordes intergrupales, entonces todas las rutas más cortas entre diferentes comunidades deben ir a lo largo de uno de estos pocos bordes. Por lo tanto, los bordes que conectan a las comunidades tendrán una alta separación entre los bordes (al menos uno de ellos). Al eliminar estos bordes, los grupos se separan entre sí y, por lo tanto, se revela la estructura de la comunidad subyacente de la red.

Los pasos del algoritmo para la detección de la comunidad se resumen a continuación.

1. La separación entre todos los bordes existentes en la red se calcula primero.
2. Se elimina el borde con el intervalo más alto.
3. Se recalcula el intervalo entre todos los bordes afectados por la eliminación.
4. Los pasos 2 y 3 se repiten hasta que no queden bordes.

El hecho de que las únicas diferencias que se recalculan solo sean las afectadas por la eliminación, puede disminuir el tiempo de ejecución de la simulación del proceso en las computadoras. Sin embargo, la centralidad intermedia debe recalcularse con cada paso, o se producirán errores graves. La razón es que la red se adapta a las nuevas condiciones establecidas después de la eliminación del borde. Por ejemplo, si dos comunidades están conectadas por más de un borde, entonces no hay garantía de que todos estos bordes tengan una alta separación. Según el método, sabemos que al menos unaDe ellos tendremos, pero nada más que eso se sabe. Al recalcular las distancias después de la eliminación de cada borde, se garantiza que al menos uno de los bordes restantes entre dos comunidades siempre tendrá un valor alto.

El resultado final del algoritmo Girvan-Newman es un dendrograma . A medida que se ejecuta el algoritmo Girvan-Newman, el dendrograma se produce de arriba hacia abajo (es decir, la red se divide en diferentes comunidades con la eliminación sucesiva de enlaces). Las hojas del dendrograma son nodos individuales.

La búsqueda de temas inducida por hipervínculos ( HITS ; también conocido como centros y autoridades ) es un algoritmo de análisis de enlaces que califica las páginas web, desarrollado por Jon Kleinberg . La idea detrás de los Centros y Autoridades surgió de una visión particular de la creación de páginas web cuando originalmente se estaba formando Internet; es decir, ciertas páginas web, conocidas como hubs, sirvieron como grandes directorios que no tenían autoridad en la información que tenían, pero se usaron como compilaciones de un amplio catálogo de información que llevó a los usuarios directamente a otras páginas con autoridad. En otras palabras, un buen concentrador representaba una página que apuntaba a muchas otras páginas, y una buena autoridad representaba una página que estaba vinculada por muchos concentradores diferentes.^[1]

Por lo tanto, el esquema asigna dos puntuaciones para cada página: su autoridad, que estima el valor del contenido de la página, y su valor central, que estima el valor de sus enlaces a otras páginas.

Historia [ editar ]

En revistas [ editar ]

Se han usado muchos métodos para clasificar la importancia de las revistas científicas. Uno de estos métodos es el factor de impacto de Garfield . Revistas como Science y Nature están llenas de numerosas citas, lo que hace que estas revistas tengan factores de impacto muy altos. Por lo tanto, cuando se comparan dos revistas más oscuras que han recibido aproximadamente el mismo número de citas, pero una de estas revistas ha recibido muchas citas de Science and Nature , esta revista debe tener una clasificación más alta. En otras palabras, es mejor recibir citas de una revista importante que de una no importante. ^[2]

En la web [ editar ]

Este fenómeno también ocurre en internet . Contar el número de enlaces a una página puede darnos una estimación general de su importancia en la Web, pero una página con muy pocos enlaces entrantes también puede ser prominente, si dos de estos enlaces provienen de las páginas de inicio de sitios como Yahoo! , Google, o MSN . Debido a que estos sitios son de gran importancia pero también son motores de búsqueda , una página puede clasificarse mucho más alto que su relevancia real.

Algoritmo [ editar ]

Expandiendo el conjunto raíz en un conjunto base

En el algoritmo HITS, el primer paso es recuperar las páginas más relevantes para la consulta de búsqueda. Este conjunto se denomina conjunto raíz y se puede obtener tomando las páginas principales que devuelve un algoritmo de búsqueda basado en texto. Un conjunto basese genera al aumentar el conjunto raíz con todas las páginas web que están vinculadas desde él y algunas de las páginas que lo enlazan. Las páginas web en el conjunto base y todos los hipervínculos entre esas páginas forman un subgrafo enfocado. El cálculo de HITS se realiza solo en este subgrafo enfocado . Según Kleinberg, la razón para construir un conjunto base es asegurar que se incluya a la mayoría (o muchas) de las autoridades más fuertes.

Los valores de autoridad y concentrador se definen en términos de uno al otro en una recursión mutua . Un valor de autoridad se calcula como la suma de los valores de hub escalados que apuntan a esa página. Un valor de concentrador es la suma de los valores de autoridad escalados de las páginas a las que apunta. Algunas implementaciones también consideran la relevancia de las páginas enlazadas.

El algoritmo realiza una serie de iteraciones, cada una de las cuales consta de dos pasos básicos:

• Actualización de autoridad : actualice la puntuación de autoridad de cada nodo para que sea igual a la suma de las puntuaciones centrales de cada nodo que lo apunta. Es decir, a un nodo se le otorga una puntuación de autoridad alta al estar vinculado desde páginas que se reconocen como concentradores para información.
• Actualización del concentrador : actualice la puntuación del concentrador de cada nodo para que sea igual a la suma de los puntajes de autoridad de cada nodo al que apunta. Es decir, a un nodo se le otorga una alta puntuación de concentrador al vincularlo a los nodos que se consideran autoridades en el tema.

La puntuación de Hub y la puntuación de Autoridad para un nodo se calculan con el siguiente algoritmo:

• Comience con cada nodo que tenga un puntaje central y un puntaje de autoridad de 1.
• Ejecutar la regla de actualización de autoridad
• Ejecutar la regla de actualización del hub
• Normalice los valores dividiendo cada puntaje del Hub por la raíz cuadrada de la suma de los cuadrados de todos los puntajes del Hub, y dividiendo cada puntaje de la Autoridad por la raíz cuadrada de la suma de los cuadrados de todos los puntajes de la Autoridad.
• Repita desde el segundo paso según sea necesario.

HITS, como Page y Brin 's PageRank , es un algoritmo iterativo basado en el enlace de los documentos en la web . Sin embargo, tiene algunas diferencias importantes:

• Es dependiente de la consulta, es decir, los puntos de búsqueda influyen en las puntuaciones (Hubs y Autoridad) que resultan del análisis del enlace;
• Como corolario, se ejecuta en el momento de la consulta, no en el momento de la indexación, con el impacto asociado en el rendimiento que acompaña al procesamiento del tiempo de consulta.
• No es comúnmente utilizado por los motores de búsqueda. (Aunque se dijo que Teoma usaba un algoritmo similar , que fue adquirido por Ask Jeeves / Ask.com ).
• Calcula dos puntuaciones por documento, centro y autoridad, a diferencia de una sola puntuación;
• Se procesa en un pequeño subconjunto de documentos "relevantes" (un "subgrafo enfocado" o conjunto básico), no todos los documentos como en el caso de PageRank.

En detalle [ editar ]

Para comenzar el ranking, $${\ displaystyle \ forall p}, $${\ displaystyle \ mathrm {auth} (p) = 1} y $${\ displaystyle \ mathrm {hub} (p) = 1}. Consideramos dos tipos de actualizaciones: Regla de actualización de autoridad y Regla de actualización de concentrador. Para calcular los puntajes del hub / autoridad de cada nodo, se aplican repetidas iteraciones de la Regla de Actualización de Autoridad y la Regla de Actualización del Hub. Una aplicación de k-step del algoritmo Hub-Authority implica aplicar k veces la Regla de Actualización de Autoridad y luego la Regla de Actualización de Hub.

Autoridad actualización regla [ editar ]

$${\ displaystyle \ forall p}, actualizamos $${\ displaystyle \ mathrm {auth} (p)} para ser la suma

$${\ displaystyle \ mathrm {auth} (p) = \ displaystyle \ sum _ {i = 1} ^ {n} \ mathrm {hub} (i)}

donde n es el número total de páginas conectadas a p e i es una página conectada a p. Es decir, el puntaje de Autoridad de una página es la suma de todos los puntajes de Hub de páginas que lo señalan.

Actualización Hub regla [ editar ]

$${\ displaystyle \ forall p}, actualizamos $${\ displaystyle \ mathrm {hub} (p)} para ser la suma

$${\ displaystyle \ mathrm {hub} (p) = \ displaystyle \ sum _ {i = 1} ^ {n} \ mathrm {auth} (i)}

donde n es el número total de páginas a las que p se conecta y i es una página a la que p se conecta. Por lo tanto, la puntuación de Hub de una página es la suma de las puntuaciones de Autoridad de todas sus páginas vinculadas

Normalización [ editar ]

Las puntuaciones finales de autoridad de los nodos se determinan después de infinitas repeticiones del algoritmo. Como la aplicación directa e iterativa de la Regla de actualización del concentrador y la Regla de actualización de la autoridad conduce a valores divergentes, es necesario normalizar la matriz después de cada iteración. Así los valores obtenidos de este proceso eventualmente convergerán.

Pseudocódigo [ editar ]

1 G  : = conjunto de páginas
 2 para cada página p en G  do 
 3    p .auth = 1 // p .auth es el puntaje de autoridad de la página p 
 4    p .hub = 1 // p .hub es el puntaje central de la página p 
 5 función HubsAndAuthorities ( G )
 6    para el paso de 1 a k do // ejecuta el algoritmo para k pasos
 7 norma = 0
 8      para cada página p en G  do   // actualizar todos los valores de autoridad primero
 9        p .auth = 0
10        para cada página q en p.incomingNeighbors  do // p.incomingNeighbors es el conjunto de páginas que enlazan con p 
11           p .auth + = q .hub
12 norm + = cuadrado ( p .auth) // calcula la suma de los valores de autenticación al cuadrado para normalizar
13 norma = sqrt (norma)
14      para cada página p en G  do   // actualizar las puntuaciones de autenticación
15        p .auth = p .auth / norm // normalizar los valores de autenticación
16 norma = 0
17      para cada página p en G  do   // luego actualice todos los valores del hub
18        p .hub = 0
19        para cada página r en p.outgoingNeighbors  do // p.outgoingNeighbors es el conjunto de páginas a las que se enlaza p
20          p .hub + = r .auth
21 norm + = square ( p .hub) // calcula la suma de los valores de hub square para normalizar
22 norma = sqrt (norma)
23      para cada página p en G  do   // luego actualice todos los valores del hub
24        p .hub = p .hub / norm // normalizar los valores del hub

Los valores de hub y de autoridad convergen en el pseudocódigo anterior.

El código a continuación no converge, porque es necesario limitar el número de pasos que ejecuta el algoritmo. Sin embargo, una forma de solucionar esto sería normalizar los valores de hub y autoridad después de cada "paso" dividiendo cada valor de autoridad por la raíz cuadrada de la suma de los cuadrados de todos los valores de autoridad, y dividiendo cada valor de hub por el raíz cuadrada de la suma de los cuadrados de todos los valores de hub. Esto es lo que hace el pseudocódigo anterior.

Pseudocódigo no convergente [ editar ]

1 G  : = conjunto de páginas
 2 para cada página p en G  do 
 3    p .auth = 1 // p .auth es el puntaje de autoridad de la página p 
 4    p .hub = 1 // p .hub es el puntaje central de la página p 
 5 función HubsAndAuthorities ( G )
 6    para el paso de 1 a k do // ejecuta el algoritmo para k pasos
 7      para cada página p en G  do   // actualizar todos los valores de autoridad primero
 8        p .auth = 0
 9        para cada página q en p.incomingNeighbors  do // p.incomingNeighbors es el conjunto de páginas que enlazan con p 
10          p .auth + = q .hub
11      para cada página p en G  do   // luego actualice todos los valores del hub
12        p .hub = 0
13        para cada página r en p.outgoingNeighbors  do // p.outgoingNeighbors es el conjunto de páginas a las que se enlaza p
14          p .hub + = r .auth