Aproximacion Matematica y computacional del motor de busqueda Google

Índice General

I. INTRODUCCION

II. ANTECEDENTES

III. OBJETIVOS

A. OBJETIVO GENERAL

B. OBJETIVOS ESPECIFICOS

IV. JUSTIFICACION

CAPÍTULO I

MARCO TEÓRICO

1.1. FUNDAMENTOS MATEMATICOS

1.1.1. CADENA DE MARKOV

1.1.1.1. MATRIZ ESTACIONARIA

1.1.1.2. MATRIZ ESTACIONARIA EN VARIOS PASOS

1.1.1.3. CADENAS IRREDUCTIBLES

1.1.2. NORMA DE VECTORES

1.1.2.1. NORMALIZACION DE UN VECTOR

1.1.2.2. NORMA DE FROBENIUS

1.1.3. DEPENDENCIA E INDEPENDENCIA LINEAL

1.1.4. VALOR PROPIO Y VECTOR PROPIO

1.1.4.1. CALCULO DE VALORES PROPIOS

1.1.4.2. MULTIPLICIDAD ALGEBRAICA Y GEOMETRICA

1.1.4.3. CALCULO DE VECTORES PROPIOS

1.1.4.4. PROPIEDADES DE LOS VALORES PROPIOS [16] y [17]

1.1.4.5. PROPIEDADES DE LOS VECTORES PROPIOS [18]

1.1.5. MATRIZ DIAGONIZABLE

1.5.1.1. PROPIEDADES DE UNA MATRIZ DIAGONIZABLE [10] y [15]

1.1.6. TEOREMA DE PERRON-FROBENIUS

1.1.7. METODO DE LAS POTENCIAS

1.2. WEB CRAWLER

1.2.1. DEFINICION

1.2.2. BREVE HISTORIA DE LOS WEB CRAWLER

1.2.3. FUNCIONAMIENTO DE LOS WEBS CRAWLER

1.2.4. USO DE LOS WEB CRAWLERS

1.3. INTRODUCCION AL ENTORNO DE OPENWEBSPIDER(JS)V.0.2.3

1.3.1. REQUERIMIENTOS

1.3.2. CONFIGURACION

1.3.3. CONFIGURACION DE LA BASE DE DATOS

1.3.4. RASTEAR URLS

1.4. INTRODUCCION AL ENTORNO DE PAJEK

1.4.1. DEFINICIÓN

1.4.2. INICIANDO PAJEK

1.4.3. GENERANDO GRAFOS EN PAJEK

1.4.4. CENTRALIDAD

1.5. INTRODUCCION AL MATLAB

1.5.1. DEFICION

1.5.2. ENTORNO

1.5.3. OPERADORES BASICOS

1.5.4. DECLARACIÓN DE VARIABLES

1.5.5. MATRICES Y VECTORES

1.5.6. OPERACIONES ESPECIFICAS CON MATRICES

1.5.7. VALOR Y VECTOR PROPIO

1.5.8. PROGRAMACION EN MATLAB

1.6. BUSCADORES

1.6.1. DEFINICION

1.7. GOOGLE

1.7.1. BREVE HISTORIA DE GOOGLE [38].

1.7.2. MEDICION DE LA IMPORTANCIA DE UN DOCUMENTO WEB [36] y [39]

CAPÍTULO II

EL ALGOTIRMO DE ORDENACION DE GOOGLE

2.1. PLANTEAMIENTO DEL MODELO

2.2. EL ALGORITMO PAGERANK Y EL TEOREMA DE PERRON-FROBENIUS

2.3. CALCULO DEL VECTOR PAGERANK

CAPÍTULO III

PLANTEAMIENTO DE LOS CASOS DE ESTUDIO

3.1. CASO I: CALCULO DEL VECTOR DE IMPORTANCIAS

3.2. CASO II: CALCULO DEL PAGERANK CON EL METODO DE LAS POTENCIAS

CAPÍTULO IV

SIMULACIÓN

4.1. INICIAR EL RASTREO DE LA PAGINAS

4.2. CONSTRUIR EL ARCHIVO .NET DE PAJEK

4.3. CONSTRUIR EL GRAFO DE CONEXIONES EN PAJEK

4.4. CONSTRUCCIÓN DE LA MATRIZ DE ADYACENCIA

4.5. ASIGNACION DEL PAGERANK DE CADA NODO(VERTICE)

CAPÍTULO V

CONCLUSIONES Y RECOMENDACIONES

5.1. CONCLUSIONES

5.2. RECOMENDACIONES

BIBLIOGRAFÍA

Objetivos y Temas de Investigación

El objetivo principal de esta tesis es desarrollar una aproximación matemática y computacional del funcionamiento del buscador Google, centrándose especialmente en el algoritmo PageRank y su relación con la teoría de cadenas de Markov y el álgebra lineal para la ordenación de resultados web.

• Fundamentos matemáticos: Cadenas de Markov, valores y vectores propios.
• Funcionamiento de motores de búsqueda: Web Crawlers y arquitecturas de indexación.
• Simulación práctica: Integración de herramientas como OpenWebSpider, PAJEK y MATLAB.
• Modelización: Aplicación del teorema de Perron-Frobenius en el algoritmo de ordenación.

Auszug aus dem Buch

Resumen de Capítulos

MARCO TEÓRICO: Proporciona la base matemática necesaria, incluyendo cadenas de Markov, normas de vectores, autovalores, vectores propios y el funcionamiento de herramientas como Web Crawlers, PAJEK y MATLAB.

EL ALGOTIRMO DE ORDENACION DE GOOGLE: Presenta la modelización matemática del funcionamiento de búsqueda y la aplicación del teorema de Perron-Frobenius para definir la importancia de los nodos en la web.

PLANTEAMIENTO DE LOS CASOS DE ESTUDIO: Desarrolla la aplicación práctica del algoritmo PageRank en redes pequeñas para ilustrar el cálculo de importancia de páginas mediante matrices.

SIMULACIÓN: Detalla el proceso de rastreo real de un sitio web, la construcción de matrices de adyacencia y la simulación del cálculo de PageRank utilizando herramientas computacionales.

CONCLUSIONES Y RECOMENDACIONES: Sintetiza los resultados obtenidos sobre la eficacia del modelo y sugiere la integración de estas herramientas en la formación académica de la facultad.

Palabras Clave

Crawlers, PAJEK, Cadenas de Markov, Matriz estocástica, vector propio, método de las potencias, Google, PageRank, MATLAB, álgebra lineal, ordenación, simulación, teoría de grafos, matriz de adyacencia, nodos.

Preguntas Frecuentes

¿Cuál es el propósito fundamental de esta tesis?

El propósito es aproximar matemática y computacionalmente el funcionamiento del motor de búsqueda Google, explicando cómo utiliza el algoritmo PageRank para ordenar resultados basándose en la relevancia de las páginas.

¿Qué campos del conocimiento abarca el marco teórico?

Abarca principalmente el álgebra lineal, la teoría de procesos estocásticos (específicamente cadenas de Markov), el funcionamiento técnico de los Web Crawlers y el uso de software especializado para análisis de redes.

¿Qué importancia tiene el Teorema de Perron-Frobenius en el estudio?

Es crucial, ya que bajo ciertas condiciones garantiza la existencia y unicidad del vector de importancia (PageRank), permitiendo justificar matemáticamente la ordenación de los resultados de búsqueda.

¿Qué papel desempeñan las herramientas PAJEK y MATLAB?

PAJEK se utiliza para visualizar grafos de conexiones web y calcular centralidad, mientras que MATLAB se emplea para realizar los cálculos de álgebra lineal necesarios para determinar el vector PageRank mediante el método de las potencias.

¿Cómo se define la importancia de una página en el modelo propuesto?

Se define mediante un sistema de ecuaciones donde la importancia de una página es proporcional a la suma de las importancias de las páginas que la enlazan, modelado como un problema de autovector dominante.

¿Qué caracteriza a las palabras clave seleccionadas?

Los términos destacan la intersección entre el modelado matemático (vectores propios, Markov) y su aplicación técnica en la arquitectura de buscadores (Crawlers, PageRank).

¿Por qué se eligió el software OpenWebSpider para la simulación?

Se eligió por su capacidad para rastrear sitios web de forma automatizada y almacenar las relaciones entre páginas en una base de datos MySQL, facilitando así la obtención de la matriz de adyacencia necesaria.

¿Qué limitación importante sobre la irreducibilidad de la matriz se menciona?

Se observa que en casos reales la matriz de enlaces de la web puede ser reducible. Por ello, se explica cómo Brin y Page ajustaron el modelo para garantizar una matriz irreducible y estocástica que permita siempre converger a una solución.