Thread by @aprobandomates

El mundo es un pañuelo... según Facebook y las matemáticas.

Seguro que habéis oído hablar de la Hipótesis de los seis grados de separación, que dice que dos personas cualquiera estarían interconectadas siempre por un máximo de 6 relaciones. Es decir, con a lo sumo 5 intermediarios entre ellos.

En 2011 Facebook hizo un estudio llamado “Anatomy of Facebook” cuya conclusión fue que la gran mayoría de sus usuarios estaban conectados con incluso menos grados de separación.

Vamos a hacer un estudio dentro de un grupo pequeño de personas como excusa para hablaros de lo apasionante que es la Teoría de Grafos.

Tomemos un grupo de 6 personas con distintas relaciones entre ellas, por ejemplo de amistad.

Representamos en un grafo las relaciones de amistad entre esas seis personas. Como podéis ver, A y B son amigos, C y E también lo son, A y D no se conocen, B y F tampoco aunque tienen un amigo (A) en común...

También podemos representarlo con una tabla de doble entrada como la que os dejo a continuación: como A y B son amigos, se marca la casilla que comparten, y lo mismo con los demás (no consideramos que ninguno sea amigo de sí mismo).

Y si en vez de hacerlo así, marcamos con un 1 las amistades, y con un 0 cuando no se conocen... obtenemos lo que se llama matriz de adyacencia (aquí empiezan los números, pero que nadie se asuste).

Tampoco es para venirse arriba ¿no? Solo tenemos una tabla con números que representa lo mismo que teníamos antes con dos colores. Si lo queremos llamar matriz... pues vale.

Aquí viene lo bueno: vamos a elevar esa matriz al cuadrado. Es decir, la vamos a multiplicar por sí misma (no, no es lo mismo que elevar cada número al cuadrado). Vamos a recordar brevemente cómo hacerlo.

Para multiplicar dos matrices tenemos que multiplicar cada fila de la matriz de la izquierda por cada columna de la matriz de la derecha y sumar todos esos resultados.

Os dejo un ejemplo con una matriz más pequeña.

Si multiplicamos nuestra matriz de adyacencia por sí misma obtenemos dicha matriz al cuadrado, que es la que os pongo a continuación.

Una matriz al cuadrado, tampoco hemos inventado la sopa de ajo... a no ser que podamos sacar algo de ella.

Pues resulta que esta matriz nos dice cuántos caminos con un intermediario (longitud 2) unen dos vértices. Por ejemplo, vemos que hay un camino de longitud 2 que une A con D, pasando por C.

Y que no hay ningún camino de longitud 2 que una B con D. Si nos fijamos en el dibujo vemos que para ir desde B hasta D necesitamos tres relaciones.

También vemos que existen caminos que van de cada vértice a sí mismo, pero esto no tiene mucha gracia: desde B podemos ir a A, y a continuación podemos volver a B. Pero esto solo es útil en caso de que uno quiera ser su propio amigo.

¿Y que pasa si volvemos a multiplicar por la matriz de adyacencia para calcular dicha matriz elevada al cubo?

Efectivamente, tendremos una matriz que representa el número de caminos de longitud 3 que unen cada par de vértices.

Y si esto os parece poco, vamos a rematar sumando las tres matrices obtenidas A+A²+A³, y como resultado tendremos todos los caminos de longitud menor o igual que 3 que unen cada par de vértices.

Es decir, hay 5 caminos de longitud menor o igual a 3 que unen A con B, 8 que unen A con C, solo uno que une B con D...
Si alguien tiene paciencia (y tiempo) puede entretenerse intentando buscarlos.

Podemos comprobar que en esta matriz no queda ni un 0, lo que significa que existe al menos un camino de longitud menor o igual que tres que une a cada par de personas. En este universo reducido el número de grados de separación sería 3.

Si añadimos un par de amigos más al grafo, como en la siguiente imagen, necesitaremos calcular hasta A⁵ para eliminar los ceros de la matriz, porque no hay ningún camino de longitud menor de 5 que una G con H.

Obviamente hemos puesto un ejemplo sencillo con un número muy limitado de personas. Probad a dibujar un grafo representando las amistades de vuestro entorno y veréis cómo se complica en un caso real.

Si alguien quiere probar, como me imagino que no le apetece multiplicar matrices tan grandes, puede hacerlo en matrixcalc.org/es/

Con este método podríamos comprobar si la hipótesis de los seis grados de separación es cierta, aunque para ello tendríamos que multiplicar matrices enormes (7000 millones por lado), y además tendríamos que disponer de todos esos datos.

Si la hipótesis fuera cierta, al sumar todas las potencias de la matriz de adyacencia hasta A⁶ deberíamos obtener una matriz (gigantesca) en la que no hay ningún 0.

Y si fuéramos dueños de una red social podríamos sugerir a un usuario que sea amigo de otro, viendo que están unidos por muchos caminos de poca longitud. Es decir, que tienen varios amigos cercanos en común.

Imaginad el poder que nos daría ser dueños de toda esa información y además saber utilizarla para sacarle rendimiento. Y no solo datos de amistad, sino de cualquier relación o interés en común que pudiera unir a nuestros usuarios.

Menos mal que nadie usaría algo así en su beneficio, ni solemos dejar nuestra información en la red cuando navegamos... ¿o sí?