LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

TrustRank es una técnica de análisis de vínculos descrita en el artículo Combatiendo el spam web con TrustRank por los investigadores Zoltan Gyongyi y Hector Garcia-Molina de la Universidad de Stanford y Jan Pedersen de Yahoo! . La técnica se utiliza para la separación semiautomática de páginas web útiles de spam .

Muchas páginas web de spam se crean solo con la intención de engañar a los motores de búsqueda . Estas páginas, creadas principalmente por razones comerciales, utilizan diversas técnicas para lograr clasificaciones más altas de lo merecido en las páginas de resultados de los motores de búsqueda . Si bien los expertos humanos pueden identificar fácilmente el correo no deseado, una revisión manual de Internet no es práctica.

Un método popular para mejorar las clasificaciones es aumentar la importancia percibida de un documento a través de complejos esquemas de vinculación. El PageRank de Google y otros algoritmos de clasificación de búsqueda han sido sometidos a tal manipulación.

TrustRank busca combatir el spam filtrando la web según la confiabilidad. El método requiere seleccionar un pequeño conjunto de páginas semilla para que las evalúe un experto. Una vez que las páginas semilla acreditadas se identifican manualmente, un rastreo que se extiende hacia afuera desde el conjunto semilla busca páginas confiables y confiables de manera similar. La confiabilidad de TrustRank disminuye con el aumento de la distancia entre los documentos y el conjunto de semillas.

La lógica también funciona de manera opuesta, lo que se denomina Rango Anti-Trust. Cuanto más cerca esté un sitio de los recursos de spam, más probable será que también sea spam. ^[1]

Los investigadores que propusieron la metodología TrustRank han continuado refinando su trabajo mediante la evaluación de temas relacionados, como la medición de la masa de spam .

El algoritmo de Dinic o el algoritmo de Dinitz es un algoritmo fuertemente polinomial para calcular el flujo máximo en una red de flujo , concebido en 1970 por el científico informático israelí (anteriormente soviético) Yefim (Chaim) A. Dinitz. ^[1] El algoritmo se ejecuta en$${\ displaystyle O (V ^ {2} E)}y es similar al algoritmo de Edmonds-Karp , que se ejecuta en$${\ displaystyle O (VE ^ {2})}Tiempo, en el sentido de que utiliza rutas de aumento más cortas. La introducción de los conceptos del gráfico de nivel y el flujo de bloqueo permiten que el algoritmo de Dinic alcance su rendimiento.

Historia [ editar ]

Yefim Dinitz inventó este algoritmo en respuesta a un ejercicio previo a la clase en la clase de algoritmos de Adelson-Velsky . En ese momento no estaba al tanto de los hechos básicos relacionados con el algoritmo Ford-Fulkerson . ^[2]

Dinitz menciona haber inventado su algoritmo en enero de 1969, que se publicó en 1970 en la revista Doklady Akademii Nauk SSSR . En 1974, Shimon Even y (su entonces estudiante de doctorado) Alon Itai en el Technionen Haifa se mostraron muy curiosos e intrigados por el algoritmo de Dinitz, así como por la idea relacionada de bloqueo del flujo de Alexander V. Karzanov . Sin embargo, fue difícil para ellos descifrar estos dos documentos, cada uno limitado a cuatro páginas para cumplir con las restricciones de la revista Doklady Akademii Nauk SSSR. Incluso no se rindió, y después de tres días de esfuerzo, logró comprender ambos documentos, excepto el problema de mantenimiento de la red en capas. Durante los siguientes dos años, Even dio conferencias sobre el "algoritmo de Dinic", pronunciando mal el nombre del autor y lo popularizó. Even e Itai también contribuyeron a este algoritmo al combinar BFS y DFS , que es la versión actual del algoritmo. ^[3]

Durante aproximadamente 10 años después de que se inventó el algoritmo Ford-Fulkerson, no se sabía si se podía hacer que terminara en tiempo polinomial en el caso general de capacidades de borde irracional. Esto causó la falta de cualquier algoritmo de tiempo polinómico conocido para resolver el problema de flujo máximo en casos genéricos. El algoritmo de Dinitz y el algoritmo de Edmonds-Karp (publicado en 1972) mostraron de forma independiente que, en el algoritmo de Ford-Fulkerson, si cada ruta de aumento es la más corta, entonces la longitud de las rutas de aumento no disminuye y el algoritmo siempre termina.

Definición [ editar ]

Dejar $${\ displaystyle G = ((V, E), c, f, s, t)} ser una red con $${\ displaystyle c (u, v)} y $${\ displaystyle f (u, v)} La capacidad y el flujo del borde. $${\ displaystyle (u, v)}respectivamente.

La capacidad residual es un mapeo.$${\ displaystyle c_ {f} \ colon V \ veces V \ a R ^ {+}} definido como,

1. Si $${\ displaystyle (u, v) \ en E},

   $${\ displaystyle c_ {f} (u, v) = c (u, v) -f (u, v)}

   $${\ displaystyle c_ {f} (v, u) = f (u, v)}

2. $${\ displaystyle c_ {f} (u, v) = 0} de otra manera.

El gráfico residual es un gráfico no ponderado.$${\ displaystyle G_ {f} = ((V, E_ {f}), c_ {f} | _ {E_ {f}}, s, t)}, dónde

{\ displaystyle E_ {f} = \ {(u, v) \ en V \ times V: c_ {f} (u, v)> 0 \}}.

Un camino de aumento es un$${\ displaystyle st} ruta en el grafo residual $${\ displaystyle G_ {f}}.

Definir $${\ displaystyle \ operatorname {dist} (v)} para ser la longitud del camino más corto de $${\ displaystyle s} a $${\ displaystyle v} en $${\ displaystyle G_ {f}}. Luego el gráfico de nivel de$${\ displaystyle G_ {f}} es la gráfica $${\ displaystyle G_ {L} = ((V, E_ {L}), c_ {f} | _ {E_ {L}}, s, t)}, dónde

$${\ displaystyle E_ {L} = \ {(u, v) \ en E_ {f}: \ operatorname {dist} (v) = \ operatorname {dist} (u) +1 \}}.

Un flujo de bloqueo es un$${\ displaystyle st} fluir $${\ displaystyle f} tal que la gráfica $${\ displaystyle G '= ((V, E_ {L}'), s, t)} con {\ displaystyle E_ {L} '= \ {(u, v): f (u, v)  no contiene $${\ displaystyle st}camino. ^[4] [5]

Algoritmo [ editar ]

Algoritmo de Dinic

Entrada : una red$${\ displaystyle G = ((V, E), c, s, t)}.

Salida : Un$${\ displaystyle st} fluir $${\ displaystyle f} de máximo valor.

1. Conjunto $${\ displaystyle f (e) = 0} para cada $${\ displaystyle e \ en E}.
2. Construir $${\ displaystyle G_ {L}} desde $${\ displaystyle G_ {f}} de $${\ displaystyle G}. Si$${\ displaystyle \ operatorname {dist} (t) = \ infty}parada y salida $${\ displaystyle f}.
3. Encuentra un flujo de bloqueo $${\ displaystyle f \; '} en $${\ displaystyle G_ {L}}.
4. Añadir flujo de aumento $${\ displaystyle \ f} por $${\ displaystyle f \; '} y volver al paso 2.

Análisis [ editar ]

Se puede mostrar que el número de capas en cada flujo de bloqueo aumenta en al menos 1 cada vez y, por lo tanto, hay como máximo $${\ displaystyle | V | -1}Bloqueo de flujos en el algoritmo. Para cada uno de ellos:

• la gráfica de nivel $${\ displaystyle G_ {L}}Se puede construir por primera búsqueda de amplitud en$${\ displaystyle O (E)} hora
• Un flujo de bloqueo en el gráfico de nivel. $${\ displaystyle G_ {L}} se puede encontrar en $${\ displaystyle O (VE)} hora

con el tiempo total de ejecución $${\ displaystyle O (E + VE) = O (VE)}para cada capa. Como consecuencia, el tiempo de ejecución del algoritmo de Dinic es$${\ displaystyle O (V ^ {2} E)}.

Usando una estructura de datos llamada árboles dinámicos , el tiempo de ejecución para encontrar un flujo de bloqueo en cada fase se puede reducir a$${\ displaystyle O (E \ log V)} y por lo tanto el tiempo de ejecución del algoritmo de Dinic se puede mejorar para $${\ displaystyle O (VE \ log V)}.

Casos especiales [ editar ]

En redes con capacidades unitarias, se mantiene un límite de tiempo mucho más fuerte. Cada flujo de bloqueo se puede encontrar en$${\ displaystyle O (E)} tiempo, y se puede demostrar que el número de fases no excede $${\ displaystyle O ({\ sqrt {E}})} y $${\ displaystyle O (V ^ {2/3})}. Así el algoritmo se ejecuta en$${\ displaystyle O (\ min \ {V ^ {2/3}, E ^ {1/2} \} E)}hora. ^[6]

En las redes que surgen del problema de coincidencia bipartita , el número de fases está limitado por$${\ displaystyle O ({\ sqrt {V}})}, lo que lleva a la $${\ displaystyle O ({\ sqrt {V}} E)}limitados en el tiempo. El algoritmo resultante también se conoce como algoritmo Hopcroft-Karp . De manera más general, este límite se mantiene para cualquier red unitaria : una red en la que cada vértice, a excepción de la fuente y el sumidero, tiene un solo borde de entrada de capacidad uno o un solo borde de salida de capacidad uno, y todas las demás capacidades son enteros arbitrarios . ^[5]

Ejemplo [ editar ]

Lo siguiente es una simulación del algoritmo de Dinic. En el gráfico de niveles.$${\ displaystyle G_ {L}}, los vértices con etiquetas en rojo son los valores. $${\ displaystyle \ operatorname {dist} (v)}. Los caminos en azul forman un flujo de bloqueo.

	$${\ displaystyle G}	$${\ displaystyle G_ {f}}	$${\ displaystyle G_ {L}}
1.
	El flujo de bloqueo consiste en $${\ displaystyle \ {s, 1,3, t \}} con 4 unidades de flujo, $${\ displaystyle \ {s, 1,4, t \}} con 6 unidades de flujo, y $${\ displaystyle \ {s, 2,4, t \}} Con 4 unidades de flujo. Por lo tanto, el flujo de bloqueo es de 14 unidades y el valor de flujo. $${\ displaystyle | f |}es 14. Tenga en cuenta que cada ruta de aumento en el flujo de bloqueo tiene 3 bordes.
2.
	El flujo de bloqueo consiste en $${\ displaystyle \ {s, 2,4,3, t \}} Con 5 unidades de flujo. Por lo tanto, el flujo de bloqueo es de 5 unidades y el valor del flujo. $${\ displaystyle | f |} es 14 + 5 = 19. Tenga en cuenta que cada ruta de aumento tiene 4 bordes.
3.
	Ya que $${\ displaystyle t} no puede ser alcanzado en $${\ displaystyle G_ {f}}, el algoritmo termina y devuelve un flujo con un valor máximo de 19. Tenga en cuenta que en cada flujo de bloqueo, el número de bordes en la ruta de aumento aumenta en al menos 1.

algoritmo Edmonds-Karp es una implementación del método Ford-Fulkerson para calcular el flujo máximo en una red de flujo en$${\ displaystyle O}$${\ displaystyle (| V || E | ^ {2})}hora. El algoritmo fue publicado por primera vez por Yefim Dinitz en 1970 ^[1] [2] y publicado independientemente por Jack Edmonds y Richard Karp en 1972. ^[3] El algoritmo de Dinic incluye técnicas adicionales que reducen el tiempo de ejecución a$${\ displaystyle O (| V | ^ {2} | E |)}.

Algoritmo [ editar ]

El algoritmo es idéntico al algoritmo Ford-Fulkerson , excepto que se define el orden de búsqueda al encontrar la ruta de aumento . La ruta encontrada debe ser una ruta más corta que tenga capacidad disponible. Esto se puede encontrar mediante una búsqueda en primer lugar , donde aplicamos un peso de 1 a cada borde. El tiempo de ejecución de$${\ displaystyle O (| V || E | ^ {2})}se encuentra al mostrar que cada camino de aumento se puede encontrar en $${\ displaystyle O (| E |)} tiempo, que cada vez al menos uno de los $${\ displaystyle E} los bordes se vuelven saturados (un borde que tiene el máximo flujo posible), que la distancia desde el borde saturado a la fuente a lo largo del camino de aumento debe ser más larga que la última vez que se saturó, y que la longitud es como máximo $${\ displaystyle | V |}. Otra propiedad de este algoritmo es que la longitud del camino de aumento más corto aumenta monótonamente. Hay una prueba accesible en Introducción a los Algoritmos . ^[4]

Pseudocódigo [ editar ]

La implementación del algoritmo Wikibook tiene una página sobre el tema de: Edmonds-Karp

entrada del algoritmo EdmondsKarp
     :
        gráfico    (gráfico [v] debe ser la lista de bordes que salen del vértice v en el 
                gráfico original y sus correspondientes bordes inversos construidos 
                que se utilizan para el flujo de retroceso. 
                Cada borde debe tener una capacidad, flujo, fuente y sumidero como parámetros , 
                así como un puntero al borde inverso.) 
        s        (vértice de fuente) 
        t        (vértice de sumidero) de 
    salida :
        flujo     (Valor del flujo máximo)
    
    flujo: = 0    (Inicializar flujo a cero) 
    repita 
        (Ejecute bfs para encontrar la ruta st más corta. 
        Usamos 'pred' para almacenar el borde tomado para llegar a cada vértice, 
        para poder recuperar la ruta más adelante) 
        q: = cola ()
        q.push (s)
        pred: = array (graph.length)
         mientras  no está vacío (q)
            cur: = q.pull ()
            para el borde e en el gráfico [cur]
                  if pred [et] = null  and et ≠ s y e.cap> e.flow
                    pred [et]: = e
                    q.push (et)
    
        si  no (pred [t] = nulo)         
             (Encontramos una ruta de aumento. 
            Vea cuánto flujo podemos enviar)  
            df: = ∞ 
            para (e: = pred [t]; e ≠ nulo; e: = pred [es] )
                df: = min (df, e.cap - e.flow)
             (Y actualizar los bordes en esa cantidad) 
            para (e: = pred [t]; e ≠ null; e: = pred [es])
                e.flow: = e.flow + df
                e.rev.flow: = e.rev.flow - df
            flujo: = flujo + df
    
    hasta que pred [t] = nulo   (es decir, hasta que no se haya encontrado una ruta de aumento) 
    devuelva el flujo

Ejemplo [ editar ]

Dada una red de siete nodos, fuente A, sumidero G y capacidades como se muestra a continuación:

En los pares $${\ displaystyle f / c} escrito en los bordes, $${\ displaystyle f} es el flujo de corriente, y $${\ displaystyle c}es la capacidad La capacidad residual de$${\ displaystyle u} a $${\ displaystyle v} es $${\ displaystyle c_ {f} (u, v) = c (u, v) -f (u, v)}, la capacidad total, menos el flujo que ya se utiliza. Si el flujo neto de$${\ displaystyle u} a $${\ displaystyle v}Es negativo, contribuye a la capacidad residual.

Capacidad	Camino	Red resultante
{\ displaystyle {\ begin {alineado} & \ min (c_ {f} (A, D), c_ {f} (D, E), c_ {f} (E, G)) \\ = & \ min ( 3-0,2-0,1-0) = \\ = & \ min (3,2,1) = 1 \ end {alineado}}}	$${\ displaystyle A, D, E, G}
{\ displaystyle {\ begin {alineado} & \ min (c_ {f} (A, D), c_ {f} (D, F), c_ {f} (F, G)) \\ = & \ min ( 3-1,6-0,9-0) \\ = & \ min (2,6,9) = 2 \ end {alineado}}}	$${\ displaystyle A, D, F, G}
{\ displaystyle {\ begin {alineado} & \ min (c_ {f} (A, B), c_ {f} (B, C), c_ {f} (C, D), c_ {f} (D, F), c_ {f} (F, G)) \\ = & \ min (3-0,4-0,1-0,6-2,9-2) \\ = & \ min (3,4 , 1,4,7) = 1 \ final {alineado}}}	$${\ displaystyle A, B, C, D, F, G}
{\ displaystyle {\ begin {alineado} & \ min (c_ {f} (A, B), c_ {f} (B, C), c_ {f} (C, E), c_ {f} (E, D), c_ {f} (D, F), c_ {f} (F, G)) \\ = & \ min (3-1,4-1,2-0,0 - (- 1), 6 -3,9-3) \\ = & \ min (2,3,2,1,3,6) = 1 \ end {alineado}}}	$${\ displaystyle A, B, C, E, D, F, G}

Observe cómo la longitud del camino de aumento encontrado por el algoritmo (en rojo) nunca disminuye. Los caminos encontrados son los más cortos posibles. El flujo encontrado es igual a la capacidad a través del corte mínimo en el gráfico que separa la fuente y el sumidero. Solo hay un corte mínimo en este gráfico, que divide los nodos en los conjuntos$${\ displaystyle \ {A, B, C, E \}} y $${\ displaystyle \ {D, F, G \}}, con la capacidad

$${\ displaystyle c (A, D) + c (C, D) + c (E, G) = 3 + 1 + 1 = 5. \}