La Web forma un enorme grafo dirigido: las páginas son vértices y los hipervínculos son aristas. Los motores de búsqueda recorren esa estructura, indexan contenido y combinan relevancia textual con señales de autoridad.
Un motor de búsqueda necesita descubrir documentos, procesar su contenido y ordenar resultados para una consulta. Los grafos intervienen especialmente en el descubrimiento y el análisis de enlaces.
La estructura no reemplaza el contenido: una página puede ser importante y, aun así, no responder a las palabras buscadas.
Cada página o recurso es un vértice. Un enlace desde A hacia B crea una arista dirigida A → B.
El enlace inverso no se supone: B solo apunta a A si contiene su propio vínculo.
En sistemas reales, cada etapa se distribuye entre numerosos procesos.
El rastreador comienza con URLs semilla y mantiene una frontera de direcciones pendientes. Al descargar una página, extrae enlaces y agrega destinos todavía no procesados.
El orden se ajusta con prioridades, límites por sitio, detección de duplicados y políticas de acceso.
Una BFS conceptual descubre primero páginas cercanas a las semillas. En la práctica, la frontera suele ser una cola de prioridad que considera importancia estimada, frescura y equilibrio entre sitios.
Visitar cada URL sin control produciría ciclos, descargas repetidas y una carga inaceptable.
Avanza una iteración por vez. El tamaño de cada página representa su puntuación. Agrega F → A para observar cómo un nuevo enlace redistribuye autoridad.
Puntuaciones
Acción actual
Un enlace funciona como una recomendación. Una página recibe más autoridad si es enlazada por páginas importantes y si esas páginas reparten su voto entre pocos destinos.
Para N páginas y factor de amortiguación d:
La suma recorre las páginas u que enlazan hacia v. Un valor habitual en ejemplos es d = 0,85.
PageRank puede interpretarse como la probabilidad estacionaria de un navegante que sigue enlaces con probabilidad d y salta a una página aleatoria con probabilidad 1 − d.
Los saltos evitan quedar encerrado para siempre en regiones sin salida y conectan probabilísticamente todo el sistema.
Una página colgante no tiene destinos y retendría masa de probabilidad. La solución estándar redistribuye su puntuación entre todas las páginas.
Así la suma de puntuaciones permanece igual a 1.
function iterarPageRank(enlaces, rango, d = 0.85) {
const paginas = Object.keys(enlaces);
const n = paginas.length;
const nuevo = Object.fromEntries(paginas.map(p => [p, (1 - d) / n]));
const colgante = paginas
.filter(p => enlaces[p].length === 0)
.reduce((suma, p) => suma + rango[p], 0);
for (const destino of paginas) nuevo[destino] += d * colgante / n;
for (const origen of paginas) {
for (const destino of enlaces[origen]) {
nuevo[destino] += d * rango[origen] / enlaces[origen].length;
}
}
return nuevo;
}Se repite la actualización hasta que la diferencia entre vectores sucesivos cae por debajo de una tolerancia.
La tolerancia, la precisión numérica y el tamaño del grafo determinan el costo práctico.
El grafo de enlaces no indica qué documentos contienen una palabra. Para eso se utiliza un índice invertido que asocia términos con listas de documentos y posiciones.
Permite recuperar rápidamente candidatos textualmente relevantes.
La consulta se normaliza y se buscan sus términos en el índice. Luego se combinan listas, filtros y señales de ranking.
Frases, errores ortográficos, idioma, intención y actualidad añaden capas que van más allá del grafo de enlaces.
| Señal | Pregunta |
|---|---|
| Texto | ¿El documento responde a la consulta? |
| Enlaces | ¿La estructura lo considera una referencia? |
| Frescura | ¿Está actualizado para esta intención? |
| Calidad y seguridad | ¿Es útil y confiable para mostrar? |
PageRank es una señal independiente de la consulta y necesita combinarse con relevancia.
El texto ancla describe el destino desde la perspectiva de otra página. Puede aportar términos que no aparecen literalmente en el documento enlazado.
Como cualquier señal basada en enlaces, puede manipularse y debe evaluarse junto con patrones de calidad y contexto.
El grafo web no cabe normalmente en una sola máquina. El rastreo, la indexación y las iteraciones de ranking se particionan.
Distribuir un grafo es difícil porque una arista puede conectar particiones y generar comunicación. La compresión y el procesamiento por lotes reducen costos.
Granjas de enlaces intentan crear autoridad artificial. El análisis puede detectar comunidades densas sospechosas, patrones recíprocos y crecimiento anormal.
No basta con castigar densidad alta: comunidades legítimas también pueden estar muy conectadas. Se necesitan múltiples señales.
Los motores de búsqueda integran dos visiones complementarias: documentos como contenido indexable y páginas como vértices de una red de referencias. PageRank muestra cómo convertir enlaces locales en una medida global.
En el próximo tema estudiaremos grafos en videojuegos, donde modelan mapas, navegación, estados y decisiones.