las matemáticas de google
A veces me preguntan para qué sirven las matemáticas y siempre se pueden dar algunas respuestas fáciles que contesten la pregunta, pero desde hace un tiempo estoy pensando en hacer alguna colección de cosas en las que las matemáticas (puras o mediante aplicaciones físicas) sean pieza clave y casi única para su existencia y casi ningún ciudadanito de a pie sepa muy bien cómo actúan en el engranaje del día a día.
Un ejemplo curioso es algo que usamos casi todos y casi todos los días: Google. Muchos de vosotros ya sabéis cómo funciona Google y probablemente sepáis todo lo que voy a decir a partir de ahora y puede que los que no lo sepan, tampoco les importe mucho, pero bueno, aquí lo dejo. El caso es que parece que antes de Google no había vida: usábamos otros buscadores como yahoo o altavista pero nada era tan eficiente como san Google, creado por dos estudiantes de Stanford, Larry Page y Sergey Brin en 1998. ¿Cuál es la gracia de Google? Pues que ordena los resultados de la búsqueda en función de que sean páginas más o menos importantes y aporten la información buscada. ¿Cómo se hace esto? Pues tienen a miles de duendecillos leyendo todas las páginas del mundo para ver cuál es más útil… ejem... casi... Bueno, si a los duendecillos les llamamos pagerank estaremos cerca.
El pagerank mide “lo importante” que es tu página. ¿Y cómo se mide eso? Pues con calma… y un poco de matemáticas. Podemos estar todos de acuerdo en que si una página está enlazada por mucha gente, esa página será probablemente más importante que otras que sólo estén enlazadas por el primo del que la ha hecho (no siempre es así, obviamente, pero tenemos que pensar en un algoritmo lo más general posible). Por tanto, el pagerank lo que va a hacer es medir cuántas personas tienen enlazada nuestra página. Sin embargo, no se limita sólo a contar cuántas son sino que les da un peso específico dependiendo del número de enlaces que tienen. Por ejemplo, si una página tiene 4 enlaces, “reparte su pagerank a partes iguales, dándole 1/4 a cada uno”. Por tanto, no es lo mismo que te haya enlazado una página con mucho pagerank y muchos enlaces u otra con el mismo pagerank y pocos enlaces (en el segundo caso, tocan a más pagerank). Vale… queda más o menos claro qué es lo que puede hacer que tu página sea más importante: hay spider (programas automáticos) que recorren todo internet pulsando todos los enlaces y comprobando quién tiene enlazado a quién en cada momento y a partir de ahí nos salen los datos… Pero… ¡estamos hablando de unas treinta mil millones de páginas web! ¿Cómo calculamos el pagerank de esa bestialidad de datos? Fácil: tirando de matrices.
Para el que no lo sepa, una matriz es simplemente una colección de datos puestos en forma de fila y columna. Tenemos por tanto una matriz de, más o menos, treinta mil millones de filas y treinta mil millones de columnas, ahí queda eso. Cada página tiene una fila y una columna asociadas: En su columna pondremos los enlaces desde esa página y en su fila, los enlaces a esa página. Tenemos que tener en cuenta lo dicho antes: si una página tiene cierta cantidad de enlaces, repartirá su pagerank de forma equitativa. Veamos un ejemplo:
Imaginemos que sólo hay 4 páginas en el mundo: A, B, C y D. Además de a sí mismas (normalmente siempre hay un autoenlace en algún sitio), los enlaces de cada una de ellas son: la A tiene enlazadas a la B y D, la B tiene enlazada sólo a la A, la C tiene a todas enlazadas y la D no tiene enlaces (sólo a sí misma). La matriz quedaría así:
1/3 1/2 1/4 0
1/3 1/2 1/4 0
0 0 1/4 0
1/3 0 1/4 1
Obviamente, todos son números no negativos y entre 0 y 1. Tenemos ahora toda la información de enlaces delante de nuestros ojos. Para ver si una página enlaza o no a otra, basta con mirar la matriz. Para ver si tras pinchar en dos enlaces consecutivos llegaríamos de una página a otra, bastaría con multiplicar esta matriz por sí misma. En general, para ver si puedo llegar de la página “x” a la página “y” de enlace en enlace, basta con ir calculando potencias de la matriz que acabamos de poner y ver si en el lugar en el que se cruzan la columna de la página “x” con la fila de la página “y” hay o no hay un 0 (bueno, esto es teoría básica de grafos, pero a mí me hace ilusión contarlo…). Total… ¿cómo calculamos el pagerank a partir de esta matriz? Muy fácil: si llamamos M a la matriz, basta buscar un vector (una matriz con una sola columna) que llamaremos v tal que
M·v=c·v
donde c es cierta constante. No me voy a parar a explicar por qué sale esto (si sabéis algo de matrices, lo veréis fácilmente en cuanto se piensa un poco) pero el caso es que todo consiste en calcular, sí, un vector propio de la matriz M. Sí, sí, eso que se da en 1º de carrera en todas las ingenierías, en matemáticas, en física y hasta en biología, sí. Hay que usar algún teorema (Perron-Frobenius) para ver que existe un vector propio con términos no negativos y con cierta unicidad. Este vector encontrado… tachán… ¡es el pagerank! Sí, se trata de una lista de unos treinta mil millones de números, cada uno asociado a cada página que existe. Hay que modificarlo un poco para que sea un número entre 0 y 10 y poco más… ¡y ya conocemos las entrañas de nuestro pagerank!
|2007-07-11 | 17:21 | algo de mates | Este post | 
| Tweet
Referencias (TrackBacks)
URL de trackback de esta historia http://lolamr.blogalia.com//trackbacks/50809
Comentarios
1
De: Lola
Fecha: 2007-07-11 17:34
Bueno... obviamente hay detalles que faltan (muchos) pero más o menos queda clara la idea... espero... :P
2
De: Peter
Fecha: 2007-07-11 17:40
Y yo cuando estudiaba algebra pensaba que aquello sólo servía para aumetnar la capacidad del cerebro, fijése usted. Eso si, la mente no me da para un vector de 30 millones de pageranks... pero por poco, que conste ;-D Muy interesante, lola.
3
De: Poulaina
Fecha: 2007-07-11 19:35
Ejem... me he perdido a partir de... bueno me he perdido. Sabes que nunca aprobe el examen de matrices en 2º de bachiller y me lo aprobaron by the face para poder hacer selectividad en junio y no quedarme sin periodismo???
Y si, los dibujitos esos muy bonitos, de hecho he entendido lo de los enlaces con los dibujitos ^_^
4
De: lordWings
Fecha: 2007-07-11 20:18
Muy interesante, Lola.
Entiendo que para conseguir alto pagerank lo ideal sería conseguir que quien enlace contigo tenga alto pagerank y no enlace con mucha más gente.
Es como triunfar en el famoseo: tiene que conocerte mucha gente, especialmente gente importante, y debes destacar y no ser uno más entre muchos.
Ya que has hecho un post matemático, no puedo resistir colgar este link, para aprender a multiplicar simplemente dibujando líneas:
http://www.youtube.com/watch?v=Zf8Srruz44I
Por cierto, Lola, ¡ya nos apetece un acertijo!
5
De: lara
Fecha: 2007-07-11 20:38
gran frase de una profesora "a la próxima queja nos pasamos el curso escribiendo un pagerank de un buscador. Y creedme que no queréis saber qué dimensiones tiene" ...cri...cri...
lordWings, a raíz del video que has puesto, encantada estoy desde que me enseñaron a calcular física estructural con lápices de colores y regla!! viva el dibujo en todos sus campos
6
De: Lola
Fecha: 2007-07-11 20:57
Peter, pues sí... a saber la de matrices que tendrá por dentro un ordenador...
Poulaina, si es que en el fondo casi todo se resuelve con un dibujo (por ejemplo, la jugada de un equipo de baloncesto :P).
lordWings, es que no te creas, lo de los acertijos se me empieza a quedar escaso... quizá empiezo a tirar de blogs amigos (más todavía) y cuelgo alguno robado, pronto, pronto...
lara, creo que si les digo eso a mis alumnos será para ellos como si les digo "a la próxima, cri cri cri"... pero sí, es una buena amenaza para alguien que quieres que se calle :P
7
De: jose
Fecha: 2007-07-11 21:24
dios, una matriz de treinta mil millones de filas y columnas... eso es imposible de multiplicar hombre. seguro que usan miles de matrices chicas. Si A no enlaza a B es inútil que estén en la misma matriz.
8
De: jose
Fecha: 2007-07-11 21:25
lo retiro, no es inútil. pero me mantengo en lo de las matrices chicas xD
9
De: Lola
Fecha: 2007-07-11 23:52
Bueno, obviamente esa matriz está llenísiiima de ceros... usarán submatrices para multiplicarlas, claro... (a todo esto, en realidad no hace falta multiplicarlas, pero sí hallar los valores propios, y supongo que en este caso sí se puede hacer a cachos por tanto cero).
10
De: belga_seg
Fecha: 2007-07-12 00:50
jo, Lola! mira que lo intento... pero no, no puedo... en el tercer párrafo he dejado de leer :(... i confess...
por cierto, que ayer iba escuchando la radio y me acordé de ti (no, no sonaba la tici :() y me dije "tengo que preguntarle esto a lola, porque es que no puede ser"........... Resulta que sonaba una canción de la Marta Sánchez y de repente oigo que la buena mujer canta algo así como "inventemos una ecuación donde dos más dos suman veintidos"............
1) mi parte: la frase no tiene ni puñetero sentido, vamos que no le veo la metáfora yo a eso de veintidos por ninguna parte... los dos patitos o qué?
2) tu parte: vamos a ver, 2+2 son 4, ahí no puede haber ecuación verdad? osea si fuesen 2x+2 pues sí, pero 2+2 es que no tiene más... no???? es una gran duda que me invade desde ayer a las 21:43...
conclusión de la ecuación: qué cojones canta esta tía?
11
De: Cluje
Fecha: 2007-07-12 04:10
Una cadena de Markov, ni más ni menos.
12
De: Lola
Fecha: 2007-07-12 09:48
Belga, supongo que será una licencia poética (lo de "ecuación" no tiene sentido). Se refiere, digo yo, a que dos y dos no sea dos más dos sino dos al lado de otro dos, digo yo (22)... en fin... jajaja...
13
De: belga_seg
Fecha: 2007-07-12 13:02
ya ya, pero qué más da 4 que 22?? bueno, la orgía es mayor.... pero solo eso...
ves? si ya decía yo que lo de la ecuación no tenía sentido...
el que hizo la canción no era ni de letras ni de números.... vamos, que el pobre no servía pa ná
14
De: Poulaina Spice xD
Fecha: 2007-07-12 21:52
Comentario friki para Anita con amor xD
*Con voz de Ginger*
"If you put two and two together
you will see what our friendship is for (Oh)
If you can't work this equation then
I guess I'll have to show you the door"
Esque su punto tenian...
15
De: Cronopio
Fecha: 2007-07-13 02:05
Muy interesante la verdad Lola. Me pregunto de donde sacas todfa esta información
16
De: belga_seg
Fecha: 2007-07-13 11:28
ginger es la geri no?... tía, otra que no sabe de matemáticas...
17
De: Seba
Fecha: 2009-01-02 03:56
Muy interesante la información, muchas gracias por compartirla :)
18
De: Anónimo
Fecha: 2019-11-06 18:40
http://www.deluxedubaiescorts.com/
http://www.pakistani-escorts.com/
http://www.pakistaniescorts.biz/
http://www.escortsdubai.club/
Un ejemplo curioso es algo que usamos casi todos y casi todos los días: Google. Muchos de vosotros ya sabéis cómo funciona Google y probablemente sepáis todo lo que voy a decir a partir de ahora y puede que los que no lo sepan, tampoco les importe mucho, pero bueno, aquí lo dejo. El caso es que parece que antes de Google no había vida: usábamos otros buscadores como yahoo o altavista pero nada era tan eficiente como san Google, creado por dos estudiantes de Stanford, Larry Page y Sergey Brin en 1998. ¿Cuál es la gracia de Google? Pues que ordena los resultados de la búsqueda en función de que sean páginas más o menos importantes y aporten la información buscada. ¿Cómo se hace esto? Pues tienen a miles de duendecillos leyendo todas las páginas del mundo para ver cuál es más útil… ejem... casi... Bueno, si a los duendecillos les llamamos pagerank estaremos cerca.
El pagerank mide “lo importante” que es tu página. ¿Y cómo se mide eso? Pues con calma… y un poco de matemáticas. Podemos estar todos de acuerdo en que si una página está enlazada por mucha gente, esa página será probablemente más importante que otras que sólo estén enlazadas por el primo del que la ha hecho (no siempre es así, obviamente, pero tenemos que pensar en un algoritmo lo más general posible). Por tanto, el pagerank lo que va a hacer es medir cuántas personas tienen enlazada nuestra página. Sin embargo, no se limita sólo a contar cuántas son sino que les da un peso específico dependiendo del número de enlaces que tienen. Por ejemplo, si una página tiene 4 enlaces, “reparte su pagerank a partes iguales, dándole 1/4 a cada uno”. Por tanto, no es lo mismo que te haya enlazado una página con mucho pagerank y muchos enlaces u otra con el mismo pagerank y pocos enlaces (en el segundo caso, tocan a más pagerank). Vale… queda más o menos claro qué es lo que puede hacer que tu página sea más importante: hay spider (programas automáticos) que recorren todo internet pulsando todos los enlaces y comprobando quién tiene enlazado a quién en cada momento y a partir de ahí nos salen los datos… Pero… ¡estamos hablando de unas treinta mil millones de páginas web! ¿Cómo calculamos el pagerank de esa bestialidad de datos? Fácil: tirando de matrices.
Para el que no lo sepa, una matriz es simplemente una colección de datos puestos en forma de fila y columna. Tenemos por tanto una matriz de, más o menos, treinta mil millones de filas y treinta mil millones de columnas, ahí queda eso. Cada página tiene una fila y una columna asociadas: En su columna pondremos los enlaces desde esa página y en su fila, los enlaces a esa página. Tenemos que tener en cuenta lo dicho antes: si una página tiene cierta cantidad de enlaces, repartirá su pagerank de forma equitativa. Veamos un ejemplo:
Imaginemos que sólo hay 4 páginas en el mundo: A, B, C y D. Además de a sí mismas (normalmente siempre hay un autoenlace en algún sitio), los enlaces de cada una de ellas son: la A tiene enlazadas a la B y D, la B tiene enlazada sólo a la A, la C tiene a todas enlazadas y la D no tiene enlaces (sólo a sí misma). La matriz quedaría así:
1/3 1/2 1/4 0
1/3 1/2 1/4 0
0 0 1/4 0
1/3 0 1/4 1
Obviamente, todos son números no negativos y entre 0 y 1. Tenemos ahora toda la información de enlaces delante de nuestros ojos. Para ver si una página enlaza o no a otra, basta con mirar la matriz. Para ver si tras pinchar en dos enlaces consecutivos llegaríamos de una página a otra, bastaría con multiplicar esta matriz por sí misma. En general, para ver si puedo llegar de la página “x” a la página “y” de enlace en enlace, basta con ir calculando potencias de la matriz que acabamos de poner y ver si en el lugar en el que se cruzan la columna de la página “x” con la fila de la página “y” hay o no hay un 0 (bueno, esto es teoría básica de grafos, pero a mí me hace ilusión contarlo…). Total… ¿cómo calculamos el pagerank a partir de esta matriz? Muy fácil: si llamamos M a la matriz, basta buscar un vector (una matriz con una sola columna) que llamaremos v tal que
M·v=c·v
donde c es cierta constante. No me voy a parar a explicar por qué sale esto (si sabéis algo de matrices, lo veréis fácilmente en cuanto se piensa un poco) pero el caso es que todo consiste en calcular, sí, un vector propio de la matriz M. Sí, sí, eso que se da en 1º de carrera en todas las ingenierías, en matemáticas, en física y hasta en biología, sí. Hay que usar algún teorema (Perron-Frobenius) para ver que existe un vector propio con términos no negativos y con cierta unicidad. Este vector encontrado… tachán… ¡es el pagerank! Sí, se trata de una lista de unos treinta mil millones de números, cada uno asociado a cada página que existe. Hay que modificarlo un poco para que sea un número entre 0 y 10 y poco más… ¡y ya conocemos las entrañas de nuestro pagerank!
| Tweet
Referencias (TrackBacks)
URL de trackback de esta historia http://lolamr.blogalia.com//trackbacks/50809
Comentarios
| 1 |
|
||
|
Bueno... obviamente hay detalles que faltan (muchos) pero más o menos queda clara la idea... espero... :P |
|||
| 2 |
|
||
|
Y yo cuando estudiaba algebra pensaba que aquello sólo servía para aumetnar la capacidad del cerebro, fijése usted. Eso si, la mente no me da para un vector de 30 millones de pageranks... pero por poco, que conste ;-D Muy interesante, lola. |
|||
| 3 |
|
||
|
Ejem... me he perdido a partir de... bueno me he perdido. Sabes que nunca aprobe el examen de matrices en 2º de bachiller y me lo aprobaron by the face para poder hacer selectividad en junio y no quedarme sin periodismo???
|
|||
| 4 |
|
||
|
Muy interesante, Lola.
|
|||
| 5 |
|
||
|
gran frase de una profesora "a la próxima queja nos pasamos el curso escribiendo un pagerank de un buscador. Y creedme que no queréis saber qué dimensiones tiene" ...cri...cri...
|
|||
| 6 |
|
||
|
Peter, pues sí... a saber la de matrices que tendrá por dentro un ordenador...
|
|||
| 7 |
|
||
|
dios, una matriz de treinta mil millones de filas y columnas... eso es imposible de multiplicar hombre. seguro que usan miles de matrices chicas. Si A no enlaza a B es inútil que estén en la misma matriz. |
|||
| 8 |
|
||
|
lo retiro, no es inútil. pero me mantengo en lo de las matrices chicas xD |
|||
| 9 |
|
||
|
Bueno, obviamente esa matriz está llenísiiima de ceros... usarán submatrices para multiplicarlas, claro... (a todo esto, en realidad no hace falta multiplicarlas, pero sí hallar los valores propios, y supongo que en este caso sí se puede hacer a cachos por tanto cero). |
|||
| 10 |
|
||
|
jo, Lola! mira que lo intento... pero no, no puedo... en el tercer párrafo he dejado de leer :(... i confess...
|
|||
| 11 |
|
||
|
Una cadena de Markov, ni más ni menos. |
|||
| 12 |
|
||
|
Belga, supongo que será una licencia poética (lo de "ecuación" no tiene sentido). Se refiere, digo yo, a que dos y dos no sea dos más dos sino dos al lado de otro dos, digo yo (22)... en fin... jajaja... |
|||
| 13 |
|
||
|
ya ya, pero qué más da 4 que 22?? bueno, la orgía es mayor.... pero solo eso...
|
|||
| 14 |
|
||
|
Comentario friki para Anita con amor xD
|
|||
| 15 |
|
||
|
Muy interesante la verdad Lola. Me pregunto de donde sacas todfa esta información |
|||
| 16 |
|
||
|
ginger es la geri no?... tía, otra que no sabe de matemáticas... |
|||
| 17 |
|
||
|
Muy interesante la información, muchas gracias por compartirla :) |
|||
| 18 |
|
||
|
http://www.deluxedubaiescorts.com/
|
|||
Van diciendo
Mail-ando
lolaberinto-arroba-gmail.comPapeles viejos
| < | Enero 2025 | |||||
| Lu | Ma | Mi | Ju | Vi | Sa | Do |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 | 31 | ||
Categorías
Otros cuentan
- 1 de 3- Acertijos y más cosas
- Comentaristas dispersas
- Cuchitril literario
- Cuentos mínimos
- Decapitado por hereje
- Efervescente2H
- El lobo rayado
- El musolari errante
- Epsilones
- Espejo Lúdico
- Gaussianos
- La ciencia para todos
- La piedra de Sísifo
- La vidriera irrespetuosa
- La zona fótica
- Lector constante
- MalaCiencia
- Por la boca muere el pez
- Trapseia
- Ventanas
