Aproximacion Matematica y computacional del motor de busqueda Google

ÍNDICE GENERAL

I. INTRODUCCION

II. ANTECEDENTES

IIL OBJETIVOS

A. OBJETIVO GENERAL

B. OBJETIVOS ESPECIFICOS

IV. JUSTIFICACION

CAPÍTULO 1
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¹⁶ y¹⁷
1.1.4.5. PROPIEDADES DE LOS VECTORES PROPIOS¹⁸
1.1.5. MATRIZ DIAGONLZABLE
1.5.1.1. PROPIEDADES DE UNA MATRIZ DIAGONLZABLE¹⁰ y¹⁵
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 PAJĖK
1.4.1. DEFINICIÓN
1.4.2. INICIANDO PAJĖK
1.4.3. GENERANDO GRAFOS EN PAJĖK
1.4.4. CENTRALID AD
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³⁸
1.7.2. MEDICION DE LA IMPORTANCIA DE UN DOCUMENTO WEB³⁶ y

CAPÍTULO II
EL ALGOTIRMO DE ORDENACION DE GOOGLE
2.1. PLANTEAMIENTO DEL MODELO
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 PAJĖK
4.3. CONSTRUIR EL GRAFO DE CONEXIONES EN PAJĖK
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

ÍNDICE DE FIGURAS

Figura 1. 1. Trayectoria de un espacio estocástico

Figura 1. 2. Oskar Perron y Ferdinand Georg Frobenius

Figura 1. 3. Arquitectura del primer Web Crawler

Figura 1. 4. Funcionamiento de un Web Crawler

Figura 1. 5. Ventana inicial de la aplicación

Figura 1. 6. OpenWebSpider(js) v0.23

Figura 1. 7. Opciones para la configuración de la base de datos

Figura 1. 8. Opciones para la configuración de la base de datos-II

Figura 1. 9. Creación de la base de datos y sus respectivas tablas

Figura 1. 10. Vista de las bases de datos y sus respectivas las tablas

Figura 1.11. Ventana principal para rastrear Urls

Figura 1. 12. Ventana para rastrear la Uri www.unapiquitos.edu.pe

Figura 1. 13. Proceso de rastreo de la uri asignada www.unapiquitos.edu.pe

Figura 1. 14. Vista de la Tabla pages de la base de datos ows_index

Figura 1. 15 Andrej Mrv ar y Vladimir Batagelj

Figura 1.16. Ventana principal de Pajėk

Figura 1.17. Creación del archivo txt para declarar los vértices y los edges

Figura 1. 18 Abrir archivos ·NET en Pajėk

Figura 1.19. Reporte del archivo ·NET seleccionado

Figura 1. 20. Acciones para Visualizar el grafo generado en Pajėk

Figura 1. 21.Grafo del archivo “Ejemplo Tesis JMRT.net” en Pajėk

Figura 1. 22. Acciones para generar un grafo con centralidad

Figura 1. 23. Grafo con centralidad del archivo “Ejemplo Tesis JMRT.net”

Figura 1. 24. Ventana principal de Matlab R2015a

Figura 1. 25. Línea de comandos del sistema

Figura 1. 26 Ventana Command history

Figura 1. 27 Ventana Workspace

Figura 1. 28.Ventana Current Folder

Figura 1. 29. Programa para resolver una ecuación de segundo grado

Figura 1. 30. Programa para resolver una ecuación de segundo grado

Figura 1. 31. Programa con función para resolver una ecuación de segundo grado

Figura 1. 32 . Esquema básico de la arquitectura de un buscador

Figura 1. 33. Lawrence Page y Sergei Brin

Figura 1. 34. Pagina principal de Google en septiembre de 1998

Figura 1. 35. Ejemplo grafico del PageRank

Figura 2. 1. Web de cinco paginas con sus respectivos enlaces

Figura 2. 2. El grafo de conexiones correspondientes

Figura 2. 3. Web de cuatro paginas con sus respectivos enlaces. Caso 1

Figura 2. 4. Web de cuatro paginas con sus respectivos enlaces. Caso 2

Figura 2. 5. Web de cuatro paginas con sus respectivos enlaces. Caso 3

Figura 3. l. Web de cinco paginas con sus respectivos enlaces. Caso práctico II

Figura 3. 1. Ventana de iniciación del rastreo

Figura 3. 2. Entorno grafico Mysql Workbench con las tablas ows_host y ows_index

Figura 3. 3. Consulta SQL para generar el archivo .net

Figura 3. 4. Mensaje indicando que la migración fue satisfactoria

Figura 3. 5. Lista de vértices del archivo .net

Figura 3. 6. Lista de los Arcs del archivo .net

Figura 3. 7. Reporte del archivo Tesis.net

Figura 3. 8. Opciones Layout Enegery/Fruchterman Reingold/3D

Figura 3. 9. Grafo del archivo Tesis.net en 3D

Figura 3. 10. Opciones Options/ Mark Vertices Using /No Labels

Figura 3. 11. Grafo del archivo Tesis.net sin etiquetas ni números

Figura 3. 12. Opciones Network/Create New Network/ Transform/Reduction/Degree/All

Figura 4. 13. Ventana Minimum degree of vertices

Figura 4. 14. Reporte del archivo Tesis.net simplificado

Figura 4. 15. Opciones Options/ Mark Vertices Using /Numbers

Figura 4. 16. Grafo del archivo Tesis.net simplificado

Figura 4. 17. Ventana para guardar el grafo simplificado

Figura 4. 18. Reporte del archivo TesisFinal.net

Figura 4. 19. Lista de los vértices del archivo TesisFinal,net

Figura 4. 20. Lista de los Arcs del archivo TesisFinal.net

Figura 4. 21. Opciones Network/Create Vector/Centrality/Weighted Degree/All

Figura 4. 22. Grafo del archivo TesisFinal.net con centralidad

ÍNDICE DE TABLAS

Tabla 1.1. Argumentos y acciones para configurar la base de datos en OpenWebSpider(js).

Tabla 1.2. Argumentos y acciones para rastrear urls en OpenWebSpider(js)

Tabla 1. 3. Vector fila y vector columna en MATLAB

Tabla 1. 4. Operación de matrices con operadores aritméticos en MATLAB

Tabla L 5 Operaciones específicas de matrices en MATLAB

Tabla 1. 6. Operaciones específicas de matrices en MATLAB

Tabla 4. 1. Lista de las 50 páginas con mejor PageRank

I. INTRODUCCION

Encontrar una página, que atienda los intereses del internauta por algún asunto específico es algo muy valioso en el internet. Hasta 1997/98, la mejor tecnología para ese fin era ofrecida por el buscador AltaVista. Esa tecnología se basaba en tres principios que pueden ser sintetizados por:

1. Uso de programas (Crawler/Spider) para recorrer las páginas web, registrando todas las palabras y los enlaces existentes de forma recursiva.
2. Registro y organización de las páginas recuperadas por el Crawler, extrae una representación interna de la misma y la vuelca en forma de índice en una base de datos.
3. Realización de un ranking de la importancia o popularidad relativa de cada página, de este modo cuando son hechas las búsquedas, las páginas que se encuentran en las listas representan contenido más útil y satisfactorio para el usuario.

AltaVista avanzo bastante en los primeros principios, pero la solución propuesta para el tercer principio no era la más adecuada. En poco tiempo diversos mecanismos fueron creados para adulterar el proceso de elaboración del ranking, disminuyendo con eso el valor de las sugestiones de las páginas ofrecidas por AltaVista.

La solución más definitiva para el tercer principio fue el mecanismo de búsqueda visto en 1997/98 con la propuesta del algoritmo del PageRank.

Este algoritmo fue creado por el matemático Sergey Brin y un informático Larry Page cuando estudiaban su doctorado en la Universidad de Stanford, ambos posteriormente fundaron la compañía Google. Gran parte del éxito se debe a la calidad de su mecanismo para establecer el ranking de importancia de las páginas sugeridas para los usuarios, fundamentado en el algoritmo de PagerRank.

EI algoritmo utiliza la basta estructura de enlaces como un indicador del valor de una pàgina individual. PageRank interpreta el enlace de una pàgina A a una pàgina в сото un voto. Pero el PageRank va más allá de contar el número de votos o enlaces que recibe una página; también analiza la página que emite el voto. Los votos emitidos por páginas que son importantes pesan más y ayudan a volver a otras páginas importantes.

Este algoritmo se fundamenta en elementos asociadas a las cadenas de Markov, siendo la solución obtenida a partir del vector propio dominante de una matriz estocástica específica, utilizando el método de las potencias.

En esta tesis se abordara al algoritmo de PageRank de forma detallada retomando la teoría de cadena de Markov, contemplando algunas definiciones y propiedades útiles para la compresión del algoritmo, bien como el método de las potencias para la obtención de los valores propios y vectores dominantes de una matriz estocástica, así como el teorema de Perron- Frobenius, que bajo ciertas condiciones nos asegura la existencia del vector buscado(vector PageRank) ; con el objetivo de proveer un principio teórico para el entendimiento del algoritmo.

Enseguida, a fin de entender las diferentes situaciones que el modelo puede enfrentar, una simulación será presentada en este trabajo. En particular estamos interesados en construir de manera aproximada un buscador tipo Google para ello se procederá a:

- Recolectar información del Web mediante un Crawler, es decir utilizaremos el software OpenWebSpider. Este Crawler recorrerá la dirección web indicada capturando e insertando en una base de datos los enlaces y las relaciones existentes entre ellas, de esta manera dispondremos toda la información de las relaciones entre las páginas web.

Enseguida, se creará un grafo de conexiones; para este fin utilizaremos el software PAJĖK. Este diseñador de grafos nos permite visualizar nuestro espacio web analizado por el Crawler.

- Concluido este proceso, mediante las relaciones entre páginas webs, generamos la matriz de adyacencia (matriz cuadrada cuyos elementos son o y 1), que nos permitirá aplicar el algoritmo de ordenamiento de PageRank de Google, mediante los principios matemáticos mencionados.

- Y finalmente simularemos el funcionamiento del motor de búsqueda Google, de este modo cuando es hecha la lista, las páginas que se encuentran ordenadas representan contenido más útil y satisfactorio para el usuario.

II. ANTECEDENTES

Debido a la prominencia de Google como mecanismo de búsqueda, su sistema de ordenación, tuvo una profunda influencia en el desarrollo y la estructuración de internet, y que tipos de información y servicios son visitados con más frecuentemente.

Pereira (2009), del Instituto de Matemática y Estadística de la Universidad de São Paulo en su tesis: “Ordenación de las Páginas de Google- “Page Rank””, en esta investigación es presentado una revisión de la cadena de Markov contemplando algunas definiciones y propiedades útiles para la comprensión del algoritmo, bien como el método de las potencias para la obtención de los autovalores y autovectores de una matriz, con el objetivo de proveer cimentación teórico para el entendimiento del PageRank.

Pais (2009), del programa de Pos-Graduación en ciencias de la computación de la Universidad Federal de Minas Gerias en su tesis: “Exploración de la popularidad para búsquedas de información en blog”, las principales contribuciones de esta tesis son:

- Investigar la capacidad de los motores de búsqueda actuales en explorar la popularidad de los blog para evidenciar posibles mejoras que pueden ser hechas debido a las características particulares de los blog.

- Presentar una nueva forma de ordenar el resultado de las consultas hechas a un motor de búsqueda para blogs utilizando el PageRank como un factor más en el cálculo de la similitud entre la consulta y el documento.

Motta (2007), del Instituto de ciencias exactas de la Universidad Federal de Itajubá en su tesis “Como funcionan los Search Engines” en este trabajo se abordará las tres grandes áreas de la arquitectura del search engine (motores de búsqueda o buscadores) y presentará un ejemplo ilustrativo de esta arquitectura. Las tres áreas de un motor de búsqueda consisten en:

- Indexación responsable por la organización y clasificación de las informaciones.
- La búsqueda, donde el usuario requisa informaciones y el search engine retorna un conjunto de datos referentes a (a los) termino(s) informados.
- Ofrecer, a raíz de esos resultados, recomendaciones prácticas para que una página web logre posiciones destacadas en los resultados de búsquedas de Google.

Adrian (2015), de la Universidad de la Rioja, Facultad de Ciencias Estudios Agroalimentarios e Informática, departamento de matemáticas y computación, en su tesis “El teorema de Perron-Frobenius y su aplicación en el algoritmo de búsqueda de Google”, el objetivo de este trabajo es mostrar como resultados matemáticos profundamente abstractos y teóricos pueden llegar a tener aplicaciones prácticas realmente sorprendentes. En concieto veremos como el algoritmo de ordenamiento de Google, sin duda una de los buscadores más potentes y utilizados que existen, basa su ñmcionamiento en el teorema de PeiToaFrobenius, un resultado de algebra lineal relacionados con matrices irxeductibles.

Torres (2016), de la Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias Físico Matemáticas, en su tesis “Cadenas de Markov aplicadas al ordenamiento de páginas web” en este trabajo se presenta una pequeña introducción de las cadenas de Markov, que luego ayudar-a a la construcción de la matriz Google, además de la obtención del vector PageRank, enseguida se mostrara que la matriz Google como es de transición entonces, convergerá a un vector propio dominante, que es el PageRank.

III. OBJETIVOS

A. OBJETIVO GENERAL

- Aproximar matemática y computacionalmente al funcionamiento del motor de búsqueda Google.

B. OBJETIVOS ESPECIFICOS

- Proveer un principio teórico matemático para el entendimiento del algoritmo PageRank.
- Adaptar un Crawler, que recorrerá las diferentes páginas de forma automática, para luego almacenar en una base de datos, toda la información de las páginas y sus enlaces existentes.
- Diseñar un grafo de conexiones, que nos permitirá visualizar las relaciones que existe entre las páginas según el espacio analizado por el Crawler.
- Diseñar la matriz adyacente, según las relaciones que existe entre las páginas.
- Mediante los principios matemáticos y técnicas de programación, se diseñará y simulará el funcionamiento del motor de búsqueda Google, en particular utilizaremos Matlab para tal fin.

IV. JUSTIFICACIÓN

Las búsquedas en los principales motores, son hoy uno de los fenómenos más importantes de Internet. Tienen importancia social, económica y política. Forman parte de la vida cotidiana de la gran mayoría de los usuarios. Entre los diferentes buscadores, Google ocupa una posición de predominio mundial.

No hemos hallado estudios académicos en la amazonia peruana y probablemente en el Perú sobre cómo funciona el buscador Google. La investigación preliminar nos indica que nadie ha abordado con rigor este tema. En la página Red Peruana de Tesis Digitales, tan solo aparece una tesis de maestría que contenga Google en su comprendido. Se trata de la tesis de Héctor Manuel Bedón Monzón “Prototipo de búsqueda en Internet basado en algoritmos genéticos” que presenta el diseño y la implementáción de un prototipo de agente inteligente para la extracción de información sobre una plataforma Linux basándose en métodos de algoritmos genéticos. Por lo tanto, no tiene ninguna relación con el funcionamiento del buscador. En la página Cybertesis, que contiene información sobre tesis de unas 16 universidades del Perú, no ofrece resultados que contenga la palabra Google o PageRank. Además, haciendo una búsqueda en la web sobre el tema, aparecen algunos artículos y páginas web del Perú, siendo la más relevante el artículo titulado “PageRank, el corazón de Google” elaborado por un miembro de la Sociedad de Estudiantes de Ciencias de la Computación en el Perú (SECC), que no aporta mucha información al respecto; lo único que hemos encontrado que aborde el tema son libros, artículos y tesis universitarias (en particular de países como EEUU, Brasil y España).

Dada la insuficiente información que existe en nuestro medio con respecto al funcionamiento del buscador Google, se consideró pertinente realizar esta tesis con el fin de dar a conocer por medio de una aproximación matemática y computacional de como Google ordena los resultados encontrados al momento de realizar una búsqueda.

V. APORTES

Un aporte que puede llegar a ofrecer esta tesis, es el de proveer conocimiento a quien lo consulte respecto de cómo implementar un buscador de tipo Google y adaptarlo a las necesidades que se le presenten según el problema al que quiera darle solución.

Un beneficio extra consiste en poder adaptar este buscador a una empresa que tenga la intención de proporcionar a sus clientes una herramienta de búsqueda dentro de su organización.

CAPÍTULO I MARCO TEÓRICO

1.1. FUNDAMENTOS MATEMATICOS

1.1.1. CADENA DE MARKOV

En esta sección se exponen algunos conceptos esenciales sobre cadenas de Markov¹ considerados necesarios para el desarrollo de la tesis. Se comenzará definiendo algunos conceptos esenciales para luego tratar brevemente las Cadenas de Markov propiamente dichas. Las definiciones y las propiedades aquí citados se encuentran en¹,² y ³

Definición. Es un proceso estocástico a tiempo discreto {xn: n = 0,1,2 ...} con espacios de estados discretos s = {0,1,...}, que sin pérdida de generalidad supondremos que consta de los primeros enteros a partir del o y que satisface la propiedad de Markov.

Abbildung in dieser Leseprobe nicht enthalten

Esto es para cualquiera estado x0, X! hasta xn+1 y para cualquier valor entero den a partir de o, la probabilidad que xn+1 tome el valor de xn+1 , dado que el proceso ha pasado por los estados x0, X1 hasta xn, es simplemente la probabilidad del mismo evento dado xn = xn.

La propiedad de Markov significa que dado que se conoce la trayectoria del proceso hasta el tiempo n, la distribución de la variable xn+1 depende únicamente del ultimo valor observado, esto es xn y no de los valores anteriores (figura 1)

Abbildung in dieser Leseprobe nicht enthalten

Figura 1.1. Trayectoria de un espacio estocástico

Supongamos que el proceso comienza en x0 mediante esta ley de probabilidad, cuando n es igual a o se genera al azar el estado del proceso al tiempo 1, a partir de X! se genera el nuevo estado x2 , a partir de x2 se genera un nuevo estado x3 y asi sucesivamente. Los valores subsecuentes se generan al azar de acuerdo a esta ley de probabilidad condicional.

El aspecto importante de este proceso es entonces, esta condición llamada propiedad de Markov la cual condicionando de manera sucesiva es equivalente a la siguiente condición:

Abbildung in dieser Leseprobe nicht enthalten

Esto significa que las probabilidades conjuntas de las primeras variables de una cadena de Markov, se pueden escribir como el producto de una distribución de probabilidad inicial, así llamaremos a la distribución de la variable x0 y las probabilidades de pasar de un estado a otro en dos tiempos sucesivos. Estos elementos son importantes; escribiremos su definición:

Abbildung in dieser Leseprobe nicht enthalten

A la distribución de probabilidad de la variable aleatoria Xq, se le llama distribución inicial de la cadena de Markov.

Entonces asociado al estado o, tenemos la probabilidad de que x0 tome el valor 0; para el estado 1 tenemos la probabilidad de que x0 tome el valor de 1 ; después la probabilidad de que x0 tome el valor de 2 y así sucesivamente, entonces a este conjunto de probabilidades se le llama distribución inicial de la cadena de Markov, en general supondremos que esta distribución es conocida, en algunas situaciones supondremos que la cadena inicia en un valor determinado y esto significa que la distribución inicial está concentrada en un solo punto.

Entonces a partir de un valor inicial de la cadena de Markov se generan al azar los subsecuentes valores de acuerdo a las siguientes probabilidades de transición:

A la probabilidad:

Abbildung in dieser Leseprobe nicht enthalten

Se le llama probabilidad de transición del estado i en el tiempo n, al estado i en el tiempo n + 1. A estas probabilidades se les conoce como probabilidades de transición en un paso.

En general estas probabilidades se mantienen constantes para cualquier valor de n , en este caso se dice que la cadena es estacionaria и homogénea en el tiempo.

Las probabilidades de transición Pu(n,n + 1) son estacionarias en el tiempo si no depende de n, es decir son idénticas a Pij(од) o bien Pij( 1,2) o de Pij(2,3) , etc.

En este caso omitiremos el argumento (n,n + 1) y le escribiremos como Pų( 1), y cuando se trata de paso en general se omite, al menos que se quiera hacer énfasis en eso. Entonces eso se escribe como:

Pij(n,n + 1) = Pij (1.5)

Considerando los distintos valores de i y j en el espacio de estados, se obtiene la matriz de probabilidades de transición en un paso.

1.1.1.1. MATRIZ ESTACIONARIA

A continuación, solo consideraremos cadenas con probabilidades de transición (estacionarias), está dada como la siguiente matriz cuadrada.

Abbildung in dieser Leseprobe nicht enthalten

Donde:

Abbildung in dieser Leseprobe nicht enthalten

La entrada i,) de esta matriz, es la probabilidad Pų(fila i, columna j) y corresponde a la probabilidad de que el proceso pase del estado i al estado i en un tiempo o un paso; es decir el estado i fila es el estado de partida y el estado i columna es el estado destino. Esta matriz presenta las siguientes 2 propiedades:

Abbildung in dieser Leseprobe nicht enthalten

Primero tenemos que las entradas de esta matriz son no negativas, esto es evidente puesto que se trata de probabilidades.

La segunda propiedad nos dice que la suma de las entradas de la matriz en una misma columna es 1, en otras palabras, esta propiedad establece que a partir de cualquier estado inicial i con probabilidad 1, la cadena pasa necesariamente algún elemento del espacio de estados al siguiente momento, entonces tenemos la siguiente definición:

A toda matriz cuadrada que cumpla las propiedades 1.7 y 1.8 se le llama matriz estocástica, de esta manera atraves de la definición de la cadena de Markov, se determinan tres elementos importantes:

- Un espacio de estados discretos s.
- Una distribución de probabilidad (inicial) sobre el espacio de estados.
- Una matriz estocástica.

Recíprocamente si tenemos un espacio de estados discreto s, una distribución de probabilidad sobre s y una matriz estocástica, se puede definir una cadena de Markov.

1.1.1.2. MATRIZ ESTACIONARIA EN VARIOS PASOS

A la probabilidad p(xm+n = i I xm = i) = Pu(m,m + n), se le llama probabilidad de transición del estado i en el tiempo m al estado i en el tiempo m + n. Esto es, dado que la cadena en el tiempo m se encuentra en el estado i, esta es la probabilidad de que después de n unidades de tiempo, la cadena se encuentre en el estado i

Observación. Como una consecuencia de la hipótesis de que las probabilidades de transición en un paso son estacionarias, tenemos que estas probabilidades de transición en n pasos también son estacionarias, esto es:

Pij (m, m + n) = Pij (0, n) (19)

La probabilidad de pasar del estado i a y en los tiempos (m) ha (m + n), coincide con la probabilidad de pasar del estado i al estado y en los tiempos о а (гг) о 1 а (гг + 1) о 2 а (гг + 2) , etc. Estas probabilidades entonces no dependen de ггг, y se escribe сото:

Pij (τη, m + n) = Pų (n)

No importando el momento en el cual se den eso n pasos; considerando los distintos valores de i y y en el espacio de estados se obtiene la matriz de probabilidades de transición en n pasos. La matriz de probabilidad de transición en n pasos para una cadena de Markov estacionaria, está dada por este arreglo:

Abbildung in dieser Leseprobe nicht enthalten

Nuevamente la entrada ij de esta matriz es la probabilidad Puiriu) y corresponde a la probabilidad de pasar del estado i al estado y en n pasos; puede comprobarse que esta matriz es estocástica es decir tiene entradas no negativas y la suma de los elementos de sus columnas es 1.

1.1.1.3. CADENAS IRREDUCTIBLES

Se dice que una cadena de Markov es irreductible si todos los estados se comunican entre sí, es decir X accede a y para todo X, у ЕС, donde c es un conjunto cerrado²

1.1.2. NORMA DE VECTORES

Sea A = (x1׳ x2,..., хпУ un vector en Mn, se define la norma o longitud de este vector, la cual denotaremos como ||i4|| al número real dado por ||i4|| = д/х!² + x2² + ■■■ + xn^{2 4}, además cumple con las siguientes propiedades para cualquier vector A y B e Mn yael⁵:

Abbildung in dieser Leseprobe nicht enthalten

1.1.2.1 .NORMALIZACION DE UN VECTOR

Sea A = (x!, x2,..., хпУ un vector* no nulo y no unitario, normalizar dicho vector es construir otro vector A a partir de este, que tenga la misma dirección, sentido y cuya norma sea la unidad. El proceso es multiplicar el vector A por el inverso de su norma. Dicho de otra manera:

Abbildung in dieser Leseprobe nicht enthalten

Ahora la norma del vector A es la unidad

Abbildung in dieser Leseprobe nicht enthalten

1.1.2.2. NORMA DE FROBENIUS

Dada una matriz A, su norma de Frobenius (llamada también la norma de Hilbert­Schmidt) [t , se define сото:

Abbildung in dieser Leseprobe nicht enthalten

Siendo A = ((a¿;)¿ j=1...n) у dř la matriz transpuesta, además la traza se define como la suma de los elementos de la diagonal principal de la matriz AłA

Ejemplo. Consideramos la matriz cuadrada:

Abbildung in dieser Leseprobe nicht enthalten

Calculamos AłA

Abbildung in dieser Leseprobe nicht enthalten

Aplicamos la ecuación 1.13

1.1.3. DEPENDENCIA E INDEPENDENCIA LINEAL

Un conjunto de vectores {r׳1׳ v2,... , vn} en un espacio vectorial V es linealmente independiente si existen escalares c1׳ c2,... cn, al menos uno de los cuales no es cero⁷, tales que

ctvt + C2V2 + —l· cnvn = 0 donde el cero (0) simboliza al vector nulo

Un conjunto de vectores que no es linealmente dependiente se dice que es linealmente independiente. Dicho de otra manera:

El conjunto de vectores {vx,v2,... , vn} es linealmente independiente en un espacio vectorial V si y solo si⁸

Abbildung in dieser Leseprobe nicht enthalten

Ejemplo. Sea los vectores и = x,y y z, que satisface la ecuación:

Abbildung in dieser Leseprobe nicht enthalten

Lo que equivale al sistema de ecuaciones siguiente:

Abbildung in dieser Leseprobe nicht enthalten

Dado que la única solución es trivial (x = y = z = 0) entonces los tres vectores son linealmente independientes.

1.1.4. VALOR PROPIO Y VECTOR PROPIO

Sea A una matriz cuadrada de orden n, se dice que un escalar λ es un valor propio, autovalores o eigenvalores de A si existe un vector V no nulo, de modo que⁹:

Αν = λν (1.14)

Si λ es valor propio de A, entonces todos los vectores V que verifican la ecuación 1.14 reciben el nombre de vectores propios, autovectores o eigenvectores de A asociados al valor propio λ. Asociados a un valor propio dado, hay infinitos vectores propios (todos aquéllos proporcionales aunó dado, no nulo). Es decir, se verifica¹⁰:

Abbildung in dieser Leseprobe nicht enthalten

Donde 7 es la matriz identidad (elemento neutro en producto de matrices) de orden nxn.

1.1.4.1. CALCULO DE VALORES PROPIOS

Teorema de Cayley-Hamilton^{3 11} y¹². Establece que cada matriz cuadrada A satisface su ecuación caracteristica, Si p(A) = det(A — 17)⁴ es el polinomio característico de A, entonces p(A) es la matriz nula. Es decir, p(A) = o (1.16)

Abbildung in dieser Leseprobe nicht enthalten

Al desarrollar el p(A) = \Α—λΙ\ = 0 obtenemos un polinomio de grado n del que tenemos que obtener los valores de λ que lo hacen cero.

Abbildung in dieser Leseprobe nicht enthalten

Eso nos asegura que el numero de valores propios de A, a lo sumo es el grado n del polinomio p(A) , si el polinomio p(A) tiene raices multiples, el número de valores propios distintos es estrictamente menor que n. Una vez obtenidas estas n raíces, digamos A1׳ λ2,λη, podemos obtener, para cada una de las que no están repetidas, un vector propio 13].

1.1.4.2. MULTIPLICIDAD ALGEBRAICA Y GEOMETRICA

Sea A¿ un valor propio de A, entonces la multiplicidad algebraica de A¿, que se denota por ma(A¿), es el número de veces que se repite como raiz del polinomio característico. Cuando la multiplicidad algebraica es 1, A¿ es llamado valor propio simple¹⁴.

El número máximo de vectores propios linealmente independientes que tienen asociados un valor propio A¿, es decir la dimension del espacio nulo N (A — A7), se llama multiplicidad geometrica y se representa por mg(Äi)¹⁵. Dicho de otra manera:

Abbildung in dieser Leseprobe nicht enthalten

Si A¿ es un autovalor de A con multiplicidad algebraica r , entonces 1 < di m(VÁJ < r, es decir:

Abbildung in dieser Leseprobe nicht enthalten

Lo que quiere decir que la multiplicidad geometrica de A¿, esta comprendida entre 1 y la multpliplicidad algebraica A¿, ademas no excede a su multiplicidad algebraica¹⁵.

Observación. Los valores propios con multiplicidad algebraica 1, su dim(yx.) esta comprendido entre 1 y 1, por lo tanto la mg(Aj) = 1 sin tener que calcular el rango de la matriz.

Abbildung in dieser Leseprobe nicht enthalten

Calculamos los valores propios y su multiplicidad algebraica, resolviendo \A — A7| = o

Abbildung in dieser Leseprobe nicht enthalten

Para cada valor propio A¿ con sus multiplicidades algebraicas ma(Aj) , calcularemos los vectores propios asociados a m5(A¿), empezaremos por el valor propio A = 5 con multiplicidad algebraica 3, resolviendo m5(A!) = n — rango(A — A!7)

Abbildung in dieser Leseprobe nicht enthalten

Las multiplicidades algebraicas y geométricas del valor propio Я! = 5 , coinciden con la relación.

Abbildung in dieser Leseprobe nicht enthalten

El valor propio я = — 1, por tener multiciplidad algebraica 1, su multiplicidad geométrica es 1 sin tener que calcular el rango de la matriz, por la tanto la relación estará comprendida.

Abbildung in dieser Leseprobe nicht enthalten

1.1.4.3. CALCULO DE VECTORES PROPIOS

Los vectores propios asociados a un valor propio я se calculan resolviendo el sistema de ecuaciones homogeneos ¹².

Abbildung in dieser Leseprobe nicht enthalten

Al resolver el sistema de ecuaciones, obtenemos los valores de хг, x2,... ,xn. Es decir:

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

- La matriz A y su transpuesta Ař tienen los mismos valores propios.

- Si A es una matriz triangular entonces sus valores propios son los elementos de la diagonal principal.

- Dado a e M, los valores propios de la matriz a A son αλγ,... , αλη.

- Dado k E N, los valores propios de la matriz Ak son А-Д... , Ánk.

- Si A es una matriz no singular entonces todos los valores propios son no nulos y los
valores propios de la matriz A-¹ son 7]
л± An
- Si A es una matriz ortogonal con valores propios reales, entonces sus valores propios son -10 1.
- Si A es una matriz idempotente entonces sus valores propios son o ó 1.
- La suma de los valores propios de A (incluidas las repeticiones) es igual a la traza de A.

Traza(Ä) = Åt + —l· λη

1.1.4.5. PROPIEDADES DE LOS VECTORES PROPIOS 18]

- Vectores propios asociados a valores propios distintos son linealmente independientes.
- Todo vector propio esta asociado a un unico valor propio.

Una matriz A cuadrada de orden nxn es diagonalizable si y solo si tiene n vectores propios linealmente independientes. En este caso, la matriz diagonala la que es semejante es aquella cuyos elementos diagonales son los valores propios correspondientes. Por último, la matriz de paso p es la matriz cuyas columnas son los vectores propios. En particular, si A tiene n valores propios distintos, entonces es diagonalizable 10]. Dicho de otra manera

Se tiene que A = PDP¹ ־ , con D diagonal, si y solo las columnas de p son vectores propios linealmente independientes de A, y los elementos diagonales de D son los valores propios de A, de modo que:

Abbildung in dieser Leseprobe nicht enthalten

Observación. Para hallar las matrices D y p, sera preciso hallar con anterioridad los valores propios y los vectores propios de la matriz en mención.

Abbildung in dieser Leseprobe nicht enthalten

Calculamos los valores propios y su multiplicidad algebraica, resolviendo \A — λΙ\ = o

Abbildung in dieser Leseprobe nicht enthalten

Como todos los valores propios de A tienen multiplicidad algebraica 1, entonces son valores propios simples

Calculamos los vectores propios de A, resolviendo los sistemas (A — λ í) x = o y dando la solución en forma vectorial paramétrica, se obtienen bases de los espacios propios.

Para λ1 = 3

Abbildung in dieser Leseprobe nicht enthalten

Para Я!

Abbildung in dieser Leseprobe nicht enthalten

Para Ā1 = 4

Las columnas de p son los vectores propios:

Abbildung in dieser Leseprobe nicht enthalten

Se colocan en la diagonal de D los valores propios en el orden correspondiente а сото están colocados los vectores propios en p.

Abbildung in dieser Leseprobe nicht enthalten

Se puede comprobar la semejanza examinando que A = PDP

Abbildung in dieser Leseprobe nicht enthalten

Como cumple que A = PDP¹ ־, entonces la matriz A es diagonizable.^{15 10}

1.5.1. 1.PROPIEDADES DE UNA MATRIZ DIAGONIZABLE y

- Si una matriz cuadrada A, de orden n, tiene n valores propios distintos (con multiplicidad algebraica y geometrica 1), entonces la matriz A es diagonizable.

- Una matriz cuadrada A, de orden n, es diagonalizable si y sólo si todos sus valores propios son reales y, además, la multiplicidad geométrica de cada uno coincide con su multiplicidad algebraica.

Abbildung in dieser Leseprobe nicht enthalten

Si la suma de las dimensiones del espacio vectorial es igual a la dimensión total (tamaño de la matriz nxn). Dicho de otra manera:

1.1.6. TEOREMA DE PERRON-FROBENIUS

EI teorema de PeiTon-Frobemus se debe a dos grandes matemáticos alemanes como son Oskar Perron (a la izquierda en la figura 1.2) y Ferdinand Georg Frobenius (a la derecha en la figura 1.2)¹⁹.

Abbildung in dieser Leseprobe nicht enthalten

Figura 1. 2. Oskar Perron y Ferdinand Georg Frobenius Fuente: ¹⁹

Oskar Perron fue un matemático alemán nacido el 7 de mayo de 1880 en Frankenthal y falleció el 22 de febrero de 1975 en Munich. Hizo numerosas contribuciones en campos tan diversos como el Análisis, las Ecuaciones Diferenciales, el Algebra, la Geómetra, la Teoría de Números, etc., en los que publico algunos textos que se convertirán en clásicos 20].

Ferdinand Georg Frobenius fue un matemático alemán, nacido en Charlottemburg (en la actualidad Berlín) el 26 de octubre de 1849 y falleció en Berlín el 3 de agosto de 1917, es uno de los matemáticos más excelsos del siglo XX con aportaciones fundamentales en el álgebra lineal y la teoría de ecuaciones diferenciales. Es sobre todo conocido por sus aportaciones a la teoría de grupos, y sus trabajos sobre las matrices no negativas pertenecen a la última etapa de su vida²⁰.

Oskar Perron publicó en 1907 un teorema que aseguraba la existencia de un valor propio simple, donde su vector propio asociado es estrictamente positivo, y fácilmente reconocible. La única inconveniencia era que las entradas de la matriz no podían ser iguales a 0. Sin embargo, en 1912 Ferdinand Georg Frobenius generalizó el teorema de Perrón para matrices no negativas²¹.

En aquel momento este resultado sobre matrices irreducibles parecía algo bastante teórico y abstracto y ninguno de estos dos celebres matemáticos podía imaginar que años más tarde este teorema se convertiría en la base de innumerables aplicaciones. Hoy en día el teorema de Perron-Frobenius ha dado como resultado una importante teoría matemática que lleva su nombre y que tiene aplicaciones en diversas ramas de la ciencia, desde aplicaciones económicas, hasta el análisis de las características demográficas de una población, pasando por el estudio de la distribución de poder en una red social. Pero se tuvo que esperar casi 90 años hasta encontrar su aplicación más famosa, el motor de búsqueda de Google 19].

Antes de dar el teorema de Perron-Frobenius vamos a presentar una definición necesaria para establecer el enunciado del mismo.

Definición 1¹⁹. Una matriz A de orden nxn se dice irreductible en uno de los siguientes casos:

- A es la matriz cero de orden lxl

- Si n > 2 y existe una matriz de permutación p tal que

Abbildung in dieser Leseprobe nicht enthalten

Donde B y D son matrices cuadradas de orden menor que n, PT denota la transpuesta de p y 0 es la matriz cero. Si no existe tal p entonces se dice que A es irreductible.

Una vez definida el concepto de una matriz irreductible, presentaremos el enunciado del teorema de Perron-Frobenius.

Teorema 1¹⁹. Sea A una matriz cuadrada de orden nxn con entradas no negativas A > o Si A es irreductible entonces:

- Existe un valor propio simple λ > o, tal que Αν = λν, donde el vector propio correspondiente es V > 0. Además:

a. λ > \μ\ para cualquier otro valor propio μ de A
b. El valor propio λ tiene multiplicidad algebraica y geométrica 1.
c. Cualquier vector propio ω > o no nulo de A es múltiplo de V.

- Si hay к valores propios de modulo máximo, entonces son las soluciones de la ecuación

xk - xk = 0

Lo que nos dice este teorema a grandes rasgos, es que una matriz no negativa e irreductible siempre tiene un valor propio positivo de modulo máximo, asociado a un vector propio también positivo y del que son múltiplos todos los demás vectores propios positivos de la matriz. Este vector propio tendrá un papel muy importante en el algoritmo de ordenación como veremos en el capítulo II.

1.1.7. METODO DE LAS POTENCIAS

El método de las potencias es un método iterativo utilizado para la obtención del valor propio de modulo máximo y su correspondiente vector propio. Las definiciones y las propiedades aquí citados se encuentran en²².

Se atribuye una aproximación inicial arbitraria para el vector propio correspondiente al valor propio dominante que es sucesivamente mejorado hasta que la precisión requerida sea encontrada. La convergencia para el valor propio dominante es simultáneamente obtenida.

Proposición. Sea A una matriz cuadrada de orden n y la cual tiene n vectores propios linealmente independientes (es decir, A es diagonizable) y un valor propio estrictamente dominante, es decir, si sus valores propios son:

Abbildung in dieser Leseprobe nicht enthalten

Entonces ocurre que:

Abbildung in dieser Leseprobe nicht enthalten

No hay pérdida de generalidad en suponerlo ordenados, de forma que el mayor modulo se corresponde con A!.

Notaremos por Vi al vector propio asociado a cada valor propio A¿ para i = 1,2,... n entonces por la hipótesis de la que hemos partido tenemos que: {Vļ, v2,... vn) son linealmente independiente. Esto significa que cualquier vector V del espacio vectorial Mn se puede expresar como combinación lineal de los vectores {Vļ, v2,... vn).

Es decir, existirán valores a¿ e M tales que:

(1.28)

Abbildung in dieser Leseprobe nicht enthalten

Por lo tanto, tenemos que:

Abbildung in dieser Leseprobe nicht enthalten

Es decir, tenemos:

Abbildung in dieser Leseprobe nicht enthalten

Si multiplicamos esta expresión de nuevo por A, tenemos:

Abbildung in dieser Leseprobe nicht enthalten

En consecuencia, tendríamos:

Abbildung in dieser Leseprobe nicht enthalten

Si continuamos multiplicando por A, de forma sucesiva tenemos:

Abbildung in dieser Leseprobe nicht enthalten

Como tenemos que le valor propio Я! es de mayor modulo, si sacamos factor común я1/с en la expresión anterior tenemos:

Abbildung in dieser Leseprobe nicht enthalten

Si tomamos límite cuando к -> 00, y tenemos en cuenta que al ser Я! el valor propio dominante entonces:

Abbildung in dieser Leseprobe nicht enthalten

Entonces en consecuencia se tiene que:

Abbildung in dieser Leseprobe nicht enthalten

Por lo tanto, tenemos que:

Es decir, la esencia del método de la potencia es multiplicar la estimación inicial por una potencia de A normalizada adecuadamente.

[...]

---

¹ Andrei Andreyevich Markov fue un matemático ruso nacido en Ryazan, el 14 de junio de 1856 y fallecido en Petrogrado (ahora San Petersburgo), Rusia, el 20 de julio de 1922

² Un conjunto de estados c en una cadena de Markov se dice que es cerrado si cualquier estado dentro de c puede alcanzarse desde cualquier otro estado de c y ningún otro estado fuera de c puede ser alcanzado desde cualquier estado dentro de c., es decir pXy = 0, X eCyřC

³ Consideramos el vector en columna, pero para facilitar la redacción de esta tesis, se escriben en filas acompañadas de un exponente t que indica la transpuesta, esto es la transformación de filas en columnas.

⁴ Arthur Cayley (Richmond. Reino Unido. 16 de agosto de 1821 - Cambridge. 26 de enero de 1895) fue un matemático británico. Es uno de los fundadores de la escuela británica moderna de matemáticas puras.

William Rowan Hamilton (4 de agosto de 1805- 2 de septiembre de 1865) fue un matemàtico, fisico, y astrònomo irlandés, que hizo importantes conüibuciones al desarrollo de la óptica, la dinámica, y el álgebra.

⁵ Otra manera de expresarlo es р(Я) = \A— λΙ\