domingo, 13 de enero de 2019

ARS 101: Amistad, redes y distribución de frecuencia de grados

Cómo la matemática de las redes puede ayudarte a hacer amigos

Estudiar la estructura de las amistades existentes en su comunidad puede ayudarlo a forjar las mejores conexiones al formar un nuevo círculo de amigos.


8



Patrick Honner | Quanta Magazine



Cuando comienzas en una nueva escuela o trabajo, o te mudas a una nueva ciudad, ¿cómo haces para hacer nuevos amigos? Podrías adoptar un enfoque activo, forjando conexiones estratégicas con los niños populares y los que hacen movimientos. O podría dejar las cosas al azar, confiando en agrupaciones y asociaciones aleatorias. Sea cual sea su enfoque, comprender la estructura de las amistades existentes en su nueva comunidad puede ayudarlo a hacer las mejores conexiones, que en última instancia definirán su círculo de amigos.

Imagínese mudarse a una ciudad nueva y extraña, Regulartown, que tiene una regla extraña: todos pueden tener a lo sumo cuatro amigos, y todos quieren maximizar sus amistades. ¿Cómo será la estructura de las amistades en Regulartown? Para explorar esta pregunta, usaremos un objeto matemático llamado red.

En pocas palabras, una red es un conjunto de objetos, llamados "nodos", y las conexiones entre ellos. Las redes son matemáticamente versátiles: pueden representar computadoras y los cables que las conectan, los autores y sus colaboraciones, o los estados de un cubo de Rubik y los movimientos que los transforman, esencialmente cualquier conjunto de conexiones, reales o abstractas. Para estudiar amistades en Regulartown, crearemos una red donde los nodos son personas y las conexiones son las amistades entre ellos.

Una forma útil de representar redes es imaginar los nodos como puntos y las conexiones como segmentos de línea, lo que también llamaremos enlaces. Este diagrama de red nos puede dar una idea de su estructura. Entonces, ¿cómo será la red de amistades en Regulartown? En algún momento puede parecer algo como esto:




Cada persona intentará encontrar a sus cuatro amigos y, a medida que nuevas personas se muden a la ciudad, buscarán a alguien con menos de cuatro amigos para conectarse. De esta manera, la red seguirá creciendo con el tiempo, expandiéndose continuamente en los enlaces a medida que se agregan nuevos nodos. (También es posible que se formen camarillas independientes, pero ignoraremos esa posibilidad en nuestro ejemplo).

Los diagramas de redes pueden iluminarse cuando indican una estructura clara. Pero cuando las redes se vuelven grandes o no exhiben el tipo de estructura regular de un Regulartown, los diagramas pueden ser menos útiles. Ayuda a desarrollar diferentes formas de analizar la estructura de una red. Una forma es pensar en la distribución del grado de la red.

En una red, el número de conexiones que tiene un nodo se conoce como el "grado" de ese nodo. Un nodo con un alto grado está conectado a muchos otros nodos; un nodo con un grado bajo está conectado a algunos otros nodos.



El grado de un nodo es una medida importante en una red, pero es local: solo describe la estructura de una red en un solo nodo. Pero al pensar en los grados de todos los nodos a la vez, podemos crear una herramienta útil para comprender la estructura global de una red.

En nuestra red de amistad, el grado de cada nodo es el número de amigos que tiene cada persona. En Regulartown, la mayoría de las personas tendrá cuatro amigos, por lo que la mayoría de los nodos tendrán el grado 4. Los residentes no tendrán más de cuatro amigos, pero algunos tendrán menos, por lo que habrá nodos con los grados 3, 2 o 1. Podemos resumir la distribución de grados como este:



Este histograma transmite información importante sobre la estructura de nuestra red. En este simple ejemplo, puede que no nos diga tanto como nuestro diagrama de red, pero veremos cómo las distribuciones de grado pueden ser herramientas poderosas para comprender diferentes tipos de redes.

Vayamos a una nueva ciudad. En Randomville, las amistades suceden al azar. Dado que la aleatoriedad puede ser un asunto complicado, seamos claros sobre lo que queremos decir: imaginaremos a cada persona de la ciudad como un nodo en una red, lo que hace que cada posible ventaja sea una posible amistad. Para generar una amistad aleatoria, elegiremos uno de esos posibles enlaces al azar y lo dibujaremos, estableciendo una conexión entre esos dos nodos y, por lo tanto, una amistad entre esas dos personas.

¿Cómo sería la red de Randomville? Suponiendo que comencemos con un grupo de nodos y agregamos al azar un grupo de enlaces, la imagen puede verse así:


Puede ser difícil ver la estructura en este diagrama. Pero el grado de distribución de esta red es esclarecedor. Si bien no es fácil calcular directamente, podemos razonar a través de algunas propiedades importantes usando un ejemplo simple.

Imagina que eres una de las 10 personas en Randomville. ¿Cuántas amistades posibles hay? Cada una de las 10 personas podría estar conectada a las otras nueve, por lo que parece que potencialmente podría dibujar 10 × 9 = 90 enlaces. Pero esto en realidad cuenta cada amistad posible dos veces: una para cada amigo. Entonces, el número total de amistades posibles es realmente 90 dividido por 2, o 45.

Ahora digamos que elegimos al azar una amistad, es decir, seleccionamos al azar uno de los 45 enlaces posibles en nuestra red. ¿Cuál es la probabilidad de que se conecte con usted? Bueno, hay nueve enlaces posibles que se extienden desde usted a cada uno de los otros nueve nodos. Dado que nueve de los 45 enlaces se conectan con usted, la probabilidad de que un enlace seleccionado al azar se conecte con usted es de 94515, o 20 por ciento.

Pero este mismo argumento se aplica a todos en Randomville, por lo que cada nodo tiene un 20% de probabilidad de estar conectado al enlace seleccionado al azar. Ahora, a medida que se agregan los enlaces (y los nodos), estas probabilidades cambiarán ligeramente, pero a la larga seguirán siendo aproximadamente las mismas. Esto significa que las amistades se distribuirán de manera bastante uniforme alrededor de Randomville. Habrá algunas variaciones leves aquí y allá, pero tener pocos amigos o muchos amigos será poco probable. En Randomville, es probable que casi todos terminen con algo parecido a un número promedio de amigos.

 Estas características familiares están incorporadas en la distribución de grado "binomial" de una red aleatoria típica.

 

Al observar solo la distribución en grados de esta red, podemos inferir un tipo particular de uniformidad: cuando se trata de conectividad, la mayoría de los nodos son promedio y muy pocos son extremos. Esta es una información útil cuando se trata de entender la estructura de la red. (A medida que se agregan nodos, digamos, cuando nuevas personas vienen a la ciudad, la distribución cambiará ligeramente, pero las características generales persistirán).

Ahora, ninguno de estos dos ejemplos, la regla de la mayoría de los cuatro amigos de Regulartown o las amistades seleccionadas al azar de Randomville, son modelos realistas de amistad. Las personas pueden tener más de cuatro amigos, y tener muchos amigos no es tan inusual como sugiere la distribución binomial. Entonces, ¿qué es un modelo de amistad más realista?

A medida que establezca conexiones con amigos y amigos de amigos, la estructura de sus amistades probablemente compartirá características comunes a otras redes del mundo real como redes de alimentos, interacciones de proteínas e Internet. Estas características caracterizan las llamadas redes "sin escala", un modelo de conectividad que ha llegado a dominar la ciencia de redes en los últimos 20 años. Investigadores de matemáticas, física, economía, biología y ciencias sociales han visto los signos reveladores de redes sin escala en sus campos dispares.



Una compleja red sin escala que representa los metadatos de una red social.
Martin Grandjean

La estructura de las redes sin escala depende del principio simple de "conexión preferencial". La conexión preferencial es una regla de crecimiento de la red rica en riqueza: un nodo con muchas conexiones existentes es más probable que obtenga nuevas conexiones que un nodo con pocas conexiones Conexiones existentes. Las nuevas conexiones muestran una preferencia por los nodos de alto grado.

¿Tiene sentido esto en el contexto de la formación de la amistad? En general, parece razonable argumentar que una persona con muchos amigos tendrá más probabilidades de hacer nuevos amigos. Como ya están conectados a más personas, es más probable que conozcan a nuevas personas a través de esas conexiones existentes. Tener más amigos crea más oportunidades para hacer nuevos amigos. Y el hecho de que ya tengan muchos amigos sugiere que pueden tener algún tipo de capacidad o afinidad para hacer amigos. Esto probablemente atraerá a otros, al igual que los sitios web populares dibujan enlaces de otros sitios y blogs, y las ciudades establecidas invitan a nuevas líneas de ferrocarril y rutas aéreas.

Si bien hay múltiples factores que intervienen en el desarrollo de redes sin escala, muchos consideran que el vínculo preferencial es el más fundamental. Y tiene una consecuencia fascinante en la distribución de un grado de red.



El apego preferencial predice una distribución de grados "de cola gruesa". La mayoría de los nodos en la red serán de grado bajo, pero habrá nodos de grado cada vez más alto. Esto contrasta con las redes de amistad de Regulartown y Randomville, que tenían pocos o ningún nodo de alto grado.

Estos nodos de alto grado, que actúan como centros, son una característica crítica de las redes sin escala. Son las mariposas sociales de las redes de amistad, los bancos en el centro de las economías, los enrutadores centralizados que recorren las líneas regionales de Internet, los Kevin Bacons del mundo en funciones. Los hubs pueden aportar una sensación de pequeño mundo a una red enorme; por ejemplo, dos usuarios seleccionados al azar de los dos mil millones de personas en Facebook son, en promedio, menos de cuatro amigos. Y la cantidad y diversidad de hubs también proporciona a las redes sin escalas resistencia frente a ciertos tipos de fallas: por ejemplo, incluso si fallan muchas conexiones a Internet, los mensajes aún se pueden transmitir, en parte porque todavía habrá muchas formas de llegar y salir de la red. muchos centros (hubs).

Si bien parece haber acuerdo sobre la utilidad de las redes sin escala y sus características de alto nivel, esta área de estudio no está exenta de controversia. Las características matemáticas precisas de estas distribuciones de grados pueden ser difíciles de interpretar. En su libro Linked: The New Science of Networks, el pionero de la ciencia en redes y físico Albert-László Barabási argumentó que las redes que exhiben un apego preferencial tendrán distribuciones de grado que esencialmente siguen una "ley de poder". Las distribuciones de la ley de poder se ven en muchas situaciones físicas, Como las leyes de la inversa al cuadrado de la gravitación y los campos eléctricos. Pueden representarse como funciones de la forma  f(x)=axk, y sus gráficas suelen tener este aspecto:



Las distribuciones de la ley de poder tienen colas gruesas. ¿Pero qué tan gordo? Es decir, ¿cuántos concentradores de cada grado deberíamos esperar en una red de este tipo? Un estudio publicado a principios de este año analizó 1,000 redes del mundo real y concluyó que solo un tercio tenía distribuciones de grado que podrían ser descritas razonablemente por una distribución de ley de poder. Muchas de las redes tenían distribuciones de grado que podrían describirse con mayor precisión utilizando distribuciones "exponenciales" y "log-normal". Pueden tener las características de alto nivel características de las redes sin escala, pero sin la distribución de grado esperada, ¿pueden realmente considerarse sin escala? ¿Y realmente importa?

Importa si queremos conectar nuestras teorías a nuestros datos. ¿Es el apego preferencial realmente el factor principal en la formación de redes sin escala? ¿O hay otros factores que también desempeñan roles sustanciales, factores que pueden impulsar las distribuciones de grados en diferentes direcciones? Responder a estas preguntas y descubrir cuáles son las preguntas correctas que se formulan a continuación, es parte de comprender completamente la naturaleza y la estructura de las redes, cómo se desarrollan y cómo evolucionan.

Y la controversia también nos recuerda que, al igual que nuestras redes, las matemáticas en sí mismas son un conjunto de conexiones en evolución. La investigación contemporánea está desafiando las conjeturas de 20 años en el campo relativamente joven de la ciencia de redes. A medida que las nuevas ideas se unen a la red, nos conectan a las matemáticas del pasado y del futuro. Entonces, cuando se trata de matemáticas, al igual que en las amistades, harás bien en encontrar los centros y maximizar tu título.

Ejercicios
  1. ¿Cómo sería una red de amistad si cada persona tuviera exactamente dos amigos?
  2. En Regulartown cada persona puede tener hasta cuatro amigos. Es posible que se formen camarillas en Regulartown, pequeños grupos en los que cada persona tiene exactamente cuatro amigos. ¿Cuántas personas podrían estar en tal pandilla? (Sugerencia: la respuesta está relacionada con un sólido platónico).
  3. Nuestras redes de amistad confían en que la amistad sea una relación simétrica, es decir, si A es amigo de B, entonces B es amigo de A. ¿Cómo podríamos ajustar nuestro modelo de red para adaptarse a una noción no simétrica de amistad, donde A podría ser amigo de B pero B no ser amigos con A?
  4. En Friendville, todos son amigos de todos los demás. Si hay n personas en Friendville, ¿cuántas amistades hay?





No hay comentarios:

Publicar un comentario