El secreto de google
Páginas: 50 (12360 palabras)
Publicado: 3 de abril de 2011
Bol. Soc. Esp. Mat. Apl. no 30(2004), 115–141
El secreto de
´ y el Algebra lineal ´ P. Fernandez
Departamento de Matem´ticas, Universidad Aut´noma de Madrid a o pablo.fernandez@uam.es
Resumen En este art´ ıculo analizaremos algunos de los ingredientes matem´ticos a que fundamentan el algoritmo (PageRank) con el que Google ordena los ´ resultados de las b´squedas: un sabroso c´ctel deAlgebra lineal, Teor´ u o ıa de Grafos y Probabilidad que nos facilita la vida. Clasificaci´n por materias AMS: o 05C50, 15A48, 60J20. Palabras clave: Google, algoritmos de ordenaci´n, matrices positivas, teor´ o ıa de Perron-Frobenius.
1
Introducci´n o
Los editoriales de los principales peri´dicos del mundo se ocupan estos d´ de o ıas la noticia de la salida a Bolsa de Google, no s´lo porel volumen de negocio que o supone1 , sino por lo que de simb´lico tiene el ser la primera operaci´n de este o o tipo en una empresa de tal envergadura desde la “exuberancia irracional” de las llamadas “puntocom” de los a˜os 90. n Pero hay algo m´s que explica este destacado inter´s, y tiene que ver con a e las caracter´ ısticas propias de la empresa. Ya han pasado varios lustros desde que seprodujo una revoluci´n en el campo de la tecnolog´ y de la informaci´n o ıa o — y quiz´s (¿o sin duda?), una revoluci´n cultural, sociol´gica, etc.—, como a o o
Fecha de recepci´n: 09/11/04 o pondr´n a la venta acciones por valor de 2700 millones de d´lares. Quiz´s por el a o a recuerdo de los excesos y esc´ndalos que rodearon la burbuja financiera de las empresas a tecnol´gicas en a˜os pasados, laoferta se articular´ en forma de subasta on line, de manera o n a que muchos inversores tengan similares oportunidades de adquirir acciones. Se trata as´ de ı evitar grandes movimientos especulativos. . . pero nunca se sabe.
1 Se
115
116
´ P. Fernandez
fue la generalizaci´n del acceso, uso y participaci´n en la red de redes, Internet. o o La aparici´n del buscador Google ha supuestouna revoluci´n equiparable a la o o anterior, al convertirse en una herramienta capaz de poner orden en todo ese (antes inabarcable) universo de informaci´n. o El dise˜o de un buscador en la red es un problema de ingenier´ matem´tica. n ıa a N´tese el adjetivo. Se necesita primero un buen conocimiento del contexto, o que permita traducirlo a modelos, a Matem´ticas. Pero tras ese proceso a deabstracci´n, de matematizaci´n, y una vez extra´ o o ıdas las conclusiones pertinentes, se requiere tambi´n una cuidadosa y eficiente implementaci´n, un e o detallado dise˜o de las cuestiones computacionales inherentes al problema. n
2
El buscador Google
El origen del buscador Google es ya bien conocido. Fue dise˜ado n en 1998 por Sergei Brin y Lawrence Page, dos estudiantes a de doctorado enInform´tica de la Universidad de Stanford: Brin se hab´ graduado en Matem´ticas, ıa a y Page en Inform´tica. Los vemos a en las fotograf´ de la derecha2 . ıas Dos j´venes que hoy, en la o frontera de la treintena, se han convertido en multimillonarios. Brin (a la izquierda) y Page El curioso nombre del buscador es una variaci´n sobre el t´rmino googol, que alguien3 invent´ para referirse al o e oapabullante n´mero 10100 . Uno de esos n´meros que los matem´ticos manejamos u u a con comodidad pero que, quiz´s, sea mayor que el n´mero de part´ a u ıculas del Universo. Aunque sin llegar a esos extremos, las escalas de la cuesti´n que nos o interesa son tambi´n gigantescas. En 1997, cuando Brin y Page empezaban e a trabajar en el dise˜o de Google, hab´ censadas en torno a los 100 millones n ıa aa ıa de p´ginas web. Altavista, el buscador m´s popular por entonces, atend´ 20 millones de consultas diarias. Hoy, esas cifras se han multiplicado: el propio buscador Google atiende 200 millones de consultas diarias e indexa varios miles de millones de p´ginas web. a As´ que el dise˜o de un buscador ha de resolver con eficacia ciertas cuestiones ı n computacionales, como la manera en que se...
El secreto de
´ y el Algebra lineal ´ P. Fernandez
Departamento de Matem´ticas, Universidad Aut´noma de Madrid a o pablo.fernandez@uam.es
Resumen En este art´ ıculo analizaremos algunos de los ingredientes matem´ticos a que fundamentan el algoritmo (PageRank) con el que Google ordena los ´ resultados de las b´squedas: un sabroso c´ctel deAlgebra lineal, Teor´ u o ıa de Grafos y Probabilidad que nos facilita la vida. Clasificaci´n por materias AMS: o 05C50, 15A48, 60J20. Palabras clave: Google, algoritmos de ordenaci´n, matrices positivas, teor´ o ıa de Perron-Frobenius.
1
Introducci´n o
Los editoriales de los principales peri´dicos del mundo se ocupan estos d´ de o ıas la noticia de la salida a Bolsa de Google, no s´lo porel volumen de negocio que o supone1 , sino por lo que de simb´lico tiene el ser la primera operaci´n de este o o tipo en una empresa de tal envergadura desde la “exuberancia irracional” de las llamadas “puntocom” de los a˜os 90. n Pero hay algo m´s que explica este destacado inter´s, y tiene que ver con a e las caracter´ ısticas propias de la empresa. Ya han pasado varios lustros desde que seprodujo una revoluci´n en el campo de la tecnolog´ y de la informaci´n o ıa o — y quiz´s (¿o sin duda?), una revoluci´n cultural, sociol´gica, etc.—, como a o o
Fecha de recepci´n: 09/11/04 o pondr´n a la venta acciones por valor de 2700 millones de d´lares. Quiz´s por el a o a recuerdo de los excesos y esc´ndalos que rodearon la burbuja financiera de las empresas a tecnol´gicas en a˜os pasados, laoferta se articular´ en forma de subasta on line, de manera o n a que muchos inversores tengan similares oportunidades de adquirir acciones. Se trata as´ de ı evitar grandes movimientos especulativos. . . pero nunca se sabe.
1 Se
115
116
´ P. Fernandez
fue la generalizaci´n del acceso, uso y participaci´n en la red de redes, Internet. o o La aparici´n del buscador Google ha supuestouna revoluci´n equiparable a la o o anterior, al convertirse en una herramienta capaz de poner orden en todo ese (antes inabarcable) universo de informaci´n. o El dise˜o de un buscador en la red es un problema de ingenier´ matem´tica. n ıa a N´tese el adjetivo. Se necesita primero un buen conocimiento del contexto, o que permita traducirlo a modelos, a Matem´ticas. Pero tras ese proceso a deabstracci´n, de matematizaci´n, y una vez extra´ o o ıdas las conclusiones pertinentes, se requiere tambi´n una cuidadosa y eficiente implementaci´n, un e o detallado dise˜o de las cuestiones computacionales inherentes al problema. n
2
El buscador Google
El origen del buscador Google es ya bien conocido. Fue dise˜ado n en 1998 por Sergei Brin y Lawrence Page, dos estudiantes a de doctorado enInform´tica de la Universidad de Stanford: Brin se hab´ graduado en Matem´ticas, ıa a y Page en Inform´tica. Los vemos a en las fotograf´ de la derecha2 . ıas Dos j´venes que hoy, en la o frontera de la treintena, se han convertido en multimillonarios. Brin (a la izquierda) y Page El curioso nombre del buscador es una variaci´n sobre el t´rmino googol, que alguien3 invent´ para referirse al o e oapabullante n´mero 10100 . Uno de esos n´meros que los matem´ticos manejamos u u a con comodidad pero que, quiz´s, sea mayor que el n´mero de part´ a u ıculas del Universo. Aunque sin llegar a esos extremos, las escalas de la cuesti´n que nos o interesa son tambi´n gigantescas. En 1997, cuando Brin y Page empezaban e a trabajar en el dise˜o de Google, hab´ censadas en torno a los 100 millones n ıa aa ıa de p´ginas web. Altavista, el buscador m´s popular por entonces, atend´ 20 millones de consultas diarias. Hoy, esas cifras se han multiplicado: el propio buscador Google atiende 200 millones de consultas diarias e indexa varios miles de millones de p´ginas web. a As´ que el dise˜o de un buscador ha de resolver con eficacia ciertas cuestiones ı n computacionales, como la manera en que se...
Leer documento completo
Regístrate para leer el documento completo.