Redes: cómo se conecta y se propaga todo

El problema de los puentes de Königsberg pregunta si se puede dar un paseo por la ciudad cruzando cada uno de sus siete puentes exactamente una vez. Leonhard Euler demostró en 1736 que no, y la manera en que lo demostró —olvidándose de la ciudad y quedándose solo con qué está conectado con qué— es el acta de nacimiento de la teoría de grafos, la rama de las matemáticas con la que hoy se describen las redes sociales, las rutas de internet, las cadenas de contagio y los mapas de carreteras.

Königsberg, hoy Kaliningrado, estaba partida por el río Pregel en cuatro trozos de tierra: la orilla norte, la orilla sur, la isla de Kneiphof en medio y la isla de Lomse al este, donde el río se bifurca. Siete puentes las unían: dos entre Kneiphof y cada orilla, uno entre Kneiphof y Lomse, y uno entre Lomse y cada orilla. Los vecinos se preguntaban desde hacía tiempo si existía un recorrido que pasara por los siete sin repetir ninguno, y en 1735 el alcalde de Danzig, Carl Ehler, se lo planteó por carta a Euler, que tenía entonces veintiocho años y trabajaba en la Academia de San Petersburgo. Euler respondió al principio que el problema «apenas tenía que ver con las matemáticas», pero lo resolvió, lo presentó ante la Academia el 26 de agosto de 1736 y lo publicó, con el título Solución de un problema relativo a la geometría de posición, en 1741.

Lo primero que hizo Euler fue tirar el mapa. Da igual la forma de las islas, la longitud de los puentes o por qué calle se vaya: lo único que cuenta es qué trozo de tierra está unido con cuál y por cuántos puentes. Llamó A, B, C y D a los cuatro trozos y describió un paseo como una secuencia de letras, una por cada vez que se pisa un trozo de tierra: cruzar siete puentes son ocho letras. Después contó. Cada vez que un paseo entra en un trozo de tierra y vuelve a salir gasta dos puentes; por eso un trozo con un número impar de puentes tiene que ser el principio o el final del paseo, porque el puente sobrante solo puede usarse para llegar o para irse. Y un paseo solo tiene un principio y un final. En Königsberg, los cuatro trozos de tierra tenían un número impar de puentes: cinco la isla de Kneiphof, tres cada uno de los otros. Cuatro candidatos a extremo para un paseo que solo tiene dos. Imposible, sin necesidad de probar recorridos.

La figura deja comprobarlo por la vía lenta: se puede cruzar cinco puentes con facilidad, seis con suerte, y el séptimo siempre queda al otro lado del río. Cuando uno se atasca, la lectura dice dónde y por qué, y la cuenta de grados —así se llama al número de aristas que tocan un vértice— muestra los cuatro impares. La condición de Euler no depende del mapa: cualquier grafo con más de dos vértices de grado impar es imposible de recorrer así. Con exactamente dos, si el recorrido existe tiene que empezar en uno y terminar en el otro; con ninguno, puede empezar en cualquier sitio y acabar donde empezó. Euler afirmó también el recíproco —que si hay como mucho dos vértices impares y el grafo está conectado, el paseo siempre existe—, pero lo dio por evidente y no lo demostró. Lo hizo Carl Hierholzer en 1873, en un artículo publicado tras su muerte y reconstruido de memoria por un colega, y su prueba es además un procedimiento para construir el recorrido, el que usan hoy los algoritmos que planifican rutas de reparto de correo o de recogida de basura, donde hay que pasar por todas las calles una vez.

La ciudad no se quedó quieta. En 1905 se construyó un octavo puente, el Kaiserbrücke, entre la isla de Lomse y la orilla sur, y con él los grados pasaron a ser tres, cinco, cuatro y cuatro: solo dos impares, así que el paseo por fin era posible, siempre que empezara en la orilla norte y terminara en Kneiphof, o al revés. El segundo botón de la figura permite encontrarlo. Los bombardeos de 1944 destruyeron dos de los puentes originales, otros dos fueron sustituidos después por una autovía, y el Kaiserbrücke se reconstruyó en 2005; el grafo de la Kaliningrado actual, con cinco puentes, tiene dos vértices impares y admite un paseo de Euler, aunque no un circuito que vuelva al inicio. El problema de los vecinos de 1735 se resolvió en dos ocasiones: una en el papel, en 1736, y otra en el terreno, en 1905.

El tercer botón, «tu propio grafo», es la parte que Euler no pudo ofrecer a sus lectores: seis vértices y quince aristas posibles que se encienden y se apagan pulsándolas. Sirve para comprobar que la regla de los grados no tiene excepciones —añadir una sola arista cambia la paridad de dos vértices a la vez, así que el número de vértices impares siempre es par— y para ver que la condición necesita también que el grafo esté conectado. Con eso, la pregunta de un paseo dominical se convierte en la primera pregunta de una disciplina: dado un conjunto de cosas y de conexiones entre ellas, qué se puede saber sin mirar las cosas y mirando solo las conexiones. El resto de este itinerario —el mundo pequeño, el umbral de Granovetter, la conexión preferencial, la epidemia en una red, el algoritmo de Dijkstra, PageRank— son respuestas a esa pregunta.

El mundo pequeño es la propiedad de una red en la que casi todo el mundo se relaciona en su vecindario —los amigos de mis amigos suelen ser amigos entre sí— y, sin embargo, cualquier persona está a pocos pasos de cualquier otra. Las dos cosas parecen incompatibles: un mundo de vecindarios cerrados debería ser un mundo de distancias largas. Que no lo sea es el hallazgo del experimento de Stanley Milgram de 1967 y la explicación del modelo de Duncan Watts y Steven Strogatz de 1998, y lo que hace que un rumor, un virus o una moda puedan recorrer un país en semanas aunque cada persona solo hable con las de siempre.

La idea es anterior a la ciencia. En un cuento de 1929, Láncszemek («Eslabones»), el escritor húngaro Frigyes Karinthy apuesta que puede conectarse con cualquier habitante del planeta a través de no más de cinco conocidos. Milgram convirtió la apuesta en experimento: dio a casi trescientas personas de Nebraska y Boston una carpeta con el nombre, la profesión y la ciudad de un agente de bolsa de Sharon, Massachusetts, y la instrucción de enviársela a un conocido de primer nombre que pudiera estar más cerca de él. Cada eslabón añadía una tarjeta y la carpeta seguía. De las 296 cadenas que empezaron, 64 llegaron, y la longitud media de las que llegaron fue de 5,2 intermediarios: los «seis grados de separación» que después dieron título a una obra de teatro, a una película y a un juego sobre actores de Hollywood. Judith Kleinfeld revisó los archivos de Milgram en 2002 y recordó lo que la leyenda había olvidado: la mayoría de las cadenas no llegó, y las que empezaban en personas con pocos recursos llegaban menos. El mundo es pequeño para quien tiene por dónde salir de su barrio.

Watts y Strogatz explicaron por qué el mundo puede ser pequeño sin dejar de ser local con un modelo de una sencillez desarmante, el de la figura. Se parte de un anillo en el que cada nodo conoce solo a sus vecinos inmediatos: el agrupamiento es alto, porque los vecinos de un nodo son vecinos entre sí, y la distancia media es enorme, porque para llegar al otro lado hay que ir de vecino en vecino. Después se recablea cada enlace con una probabilidad p hacia un nodo elegido al azar. Con p = 0 no pasa nada; con p = 1 la red es aleatoria, con distancias cortas pero sin vecindarios. Lo interesante está en medio, y es asimétrico: basta con recablear un enlace de cada cien para que la distancia media caiga a la mitad, porque un solo atajo acorta el camino de todos los pares de nodos que estaban lejos, mientras que el agrupamiento apenas lo nota, porque un vecindario pierde un enlace de muchos. Hay un intervalo ancho de valores de p en el que la red es a la vez tan agrupada como el anillo y tan corta como la red aleatoria. Watts y Strogatz comprobaron que tres redes reales muy distintas —la de actores que han compartido película, la red eléctrica del oeste de Estados Unidos y las trescientas dos neuronas del gusano C. elegans— vivían en ese intervalo.

El deslizador de la figura recorre p en escala logarítmica, porque la caída ocurre en los valores pequeños, y la lectura cuenta cuántos atajos hay en cada momento. Con seis o siete atajos entre ciento veinte aristas, la distancia media de sesenta nodos ha bajado de siete pasos y medio a cuatro; el agrupamiento sigue por encima del 80 % del original. Esa es la escala: un puñado de enlaces «equivocados» basta. Y como los enlaces recableados apuntan a cualquier parte, la mayoría une trozos de la red que no tenían nada en común. Eso conecta el modelo con un artículo de sociología anterior en veinticinco años.

En 1973 Mark Granovetter publicó La fuerza de los lazos débiles. Había preguntado a personas que acababan de cambiar de trabajo cómo se habían enterado de la oferta, y la respuesta más frecuente no era un amigo íntimo sino un conocido: alguien a quien veían poco. La explicación es estructural. Los lazos fuertes viven dentro de los vecindarios, donde todo el mundo sabe lo mismo; la información nueva llega por los lazos débiles, que son los únicos que cruzan de un grupo a otro. Los atajos del modelo de Watts y Strogatz son exactamente los lazos débiles de Granovetter: pocos, poco intensos y responsables de que el mundo sea pequeño. Quitarlos alarga las distancias mucho más de lo que su número haría pensar; quitar el mismo número de lazos fuertes no cambia casi nada.

Las mediciones posteriores confirmaron a Milgram con más datos y menos épica. Peter Dodds, Roby Muhamad y Watts repitieron el experimento por correo electrónico en 2003, con 24.163 cadenas hacia dieciocho destinatarios en trece países: las que llegaron tenían de cinco a siete pasos, pero llegaron 384, y el motivo principal de que una cadena muriera no era la distancia sino la desgana de reenviar. En 2012 Backstrom y sus colegas midieron la red entera de Facebook, 721 millones de personas, sin depender de que nadie enviara nada: la distancia media era de 4,74 pasos, y de 3,57 cuatro años más tarde con el doble de usuarios. El mundo era aún más pequeño de lo que decía la leyenda, y por la razón que Watts y Strogatz habían mostrado con un anillo: no hace falta que la gente conozca a mucha gente, basta con que unos pocos conozcan a alguien de fuera.

La propiedad tiene un lado oscuro que explora la epidemia en una red: lo que acorta el camino de la información acorta el de la enfermedad, y un contagio que en un anillo avanzaría como una mancha de aceite salta de un extremo al otro por el mismo atajo que llevó el rumor. Y tiene una limitación que el siguiente artículo, la conexión preferencial, pone al descubierto: el modelo reparte los enlaces de forma bastante igualitaria, y las redes reales no lo hacen. Algunos nodos tienen miles de contactos y la mayoría, un puñado, y esa desigualdad explica cosas que el anillo recableado no puede.

El modelo de umbral de Mark Granovetter explica por qué dos multitudes idénticas en casi todo pueden acabar una en disturbio y la otra en nada. Cada persona tiene un umbral: el número de participantes que necesita ver antes de sumarse. Hay quien se lanza solo, hay quien se suma cuando ya hay diez y hay quien no se movería aunque estuvieran los noventa y nueve restantes. El resultado colectivo no depende de la media de esos umbrales, ni de cuánta gente esté a favor, sino de si la distribución tiene o no una cadena sin huecos: alguien de umbral cero que arrastre al de umbral uno, que arrastre al de dos, y así hasta el final. Un solo eslabón que falte detiene todo.

Granovetter lo publicó en 1978 con un ejemplo que se ha repetido desde entonces en todas las aulas de sociología, y que es el primer botón de la figura. Cien personas en una plaza, con umbrales 0, 1, 2, …, 99. La de umbral 0 empieza; la de umbral 1 ve a una y se suma; la de umbral 2 ve a dos; al final participan las cien. Ahora se cambia a una única persona: la de umbral 1 pasa a tener umbral 2. La de umbral 0 empieza, mira alrededor, no hay nadie con umbral 1 que se le sume, la de umbral 2 ve a una sola y se queda quieta, y ahí se acaba. Una persona participa. Dos multitudes indistinguibles para un periodista, para un sondeo y para la policía —la misma media de umbrales con un decimal de diferencia— producen un disturbio de cien y un disturbio de uno. Y el observador que llega después dirá que la primera plaza estaba «más radicalizada», cuando lo que tenía era una distribución sin huecos.

La figura hace visible el mecanismo. La gráfica de la derecha dibuja, para cada número x de participantes que ya hay, cuántas personas tienen un umbral menor o igual que x, es decir, cuántas participarían si vieran a x. Si esa curva está por encima de la diagonal, hay más gente dispuesta a sumarse que gente sumada, y el proceso crece; el crecimiento se detiene en el primer punto en que la curva toca la diagonal, porque ahí el número de participantes es exactamente el número de personas dispuestas a participar con ese número, y nadie más se anima. En el ejemplo de los umbrales 0 a 99, la curva va justo por encima de la diagonal en todo su recorrido y solo la toca en 100. Al cambiar el 1 por un 2, la curva toca la diagonal en 1, y el proceso muere ahí. El botón «Un paso» recorre la escalera y la lectura dice quién se ha sumado y a quién esperan los que faltan.

El tercer botón sustituye la escalera por una campana —umbrales repartidos alrededor de una media, con cierta dispersión— y es donde el modelo se parece a las situaciones reales, en las que nadie asigna los umbrales de uno en uno. Con la media alta y poca dispersión no arranca nadie: la curva sale de cero pegada al eje y toca la diagonal en el origen. Al ensanchar la dispersión aparecen personas de umbral cero en la cola izquierda de la campana, y con suficientes de ellas la curva despega y puede llegar hasta cien. Lo que cambia el resultado no es la opinión media del grupo, que es la misma, sino cuánta gente hay en las colas: la cantidad de personas dispuestas a empezar solas y la cantidad de las que no se moverían nunca. Thomas Schelling, el mismo año, describió el mismo tipo de puntos de inflexión en Micromotives and Macrobehavior con ejemplos de aulas, barrios y fiestas, y el dibujo de la curva contra la diagonal es suyo tanto como de Granovetter; su modelo de segregación es un primo cercano.

El modelo deja tres lecciones que van más allá de los disturbios. La primera es que la agregación de decisiones individuales sensatas no tiene por qué parecerse a ninguna de ellas: la plaza de cien personas no estaba llena de radicales ni la de una llena de moderados. La segunda es la imprevisibilidad. Timur Kuran la aplicó en 1991 a las revoluciones de 1989 en Europa del Este: como la gente ocultaba sus preferencias, los umbrales eran invisibles, y nadie —ni los regímenes, ni la CIA, ni los propios manifestantes— pudo prever que unas concentraciones de unos cientos en Leipzig serían la cola izquierda de una campana que acabaría en cientos de miles. La tercera es que los umbrales dependen de a quién se ve. Granovetter suponía que cada persona veía a la plaza entera; Duncan Watts en 2002 y Damon Centola después pusieron el modelo sobre una red, en la que cada uno solo cuenta a sus vecinos, y encontraron que la estructura de esa red decide si una cascada es posible. Los atajos de el mundo pequeño que aceleran un rumor pueden frenar un comportamiento que exige ver a varios conocidos hacerlo antes: un lazo débil trae una noticia, pero no trae la confirmación de tres amigos. Para una vacuna basta un contacto; para cambiar de costumbre hace falta un vecindario.

Una consecuencia práctica, y algo incómoda, es que la búsqueda de «la causa» de una movilización, un boicot o un pánico bancario puede ser una pregunta mal planteada. El modelo produce resultados opuestos con causas casi idénticas, así que la explicación no está en los motivos de los participantes —que eran los mismos en las dos plazas— sino en la forma exacta de la distribución de umbrales y en quién vio a quién. Es una explicación menos satisfactoria que un villano o un héroe, y suele ser la correcta.

La conexión preferencial es la regla por la que, en una red que crece, los nodos nuevos tienden a enlazarse con los que ya tienen muchos enlaces. Una página web nueva enlaza a Wikipedia antes que a un blog desconocido; un artículo científico cita los trabajos que ya se citan; una persona que llega a una ciudad conoce antes a quien conoce a todo el mundo. La regla es local y modesta —nadie decide que haya concentradores—, pero su efecto acumulado es una red con unos pocos nodos gigantes y una mayoría de nodos casi aislados, muy distinta de la que produce el azar. Albert-László Barabási y Réka Albert le dieron nombre y modelo en 1999, y con ello explicaron por qué la web, las redes de colaboración científica y las de proteínas se parecían tanto entre sí y tan poco a las redes aleatorias.

La figura deja compararla con la alternativa. En las dos variantes la red crece igual: cada nodo nuevo trae dos enlaces, así que el grado medio es el mismo, cerca de cuatro. Lo que cambia es a quién se conecta. Con la regla preferencial —la probabilidad de recibir el enlace es proporcional a los enlaces que uno ya tiene—, los nodos que empezaron con ventaja la agrandan a cada paso, y al llegar a ciento cincuenta nodos los tres mayores acaparan una parte desproporcionada de todos los enlaces mientras la mayoría se queda con los dos que trajo. Con la regla al azar, todo el mundo recibe enlaces a un ritmo parecido y los grados se apiñan alrededor de la media; nadie destaca. La gráfica de la derecha convierte esa diferencia en una forma: con conexión preferencial, la fracción de nodos con grado k cae siguiendo una recta en escala logarítmica doble, es decir, una ley de potencias, proporcional a k⁻³; sin ella, cae en picado en cuanto pasa de la media. Es la diferencia entre una distribución con «cola pesada» —donde los valores extremos, aunque raros, existen y pesan— y una sin ella, la misma que separa la distribución de Pareto de la campana de Gauss.

El ingrediente decisivo es el tiempo. En el modelo, la ventaja de los nodos grandes no viene de ninguna cualidad propia sino de haber llegado antes: un nodo que existe desde el principio ha tenido más ocasiones de recibir enlaces, cada enlace recibido aumenta su probabilidad de recibir el siguiente, y el interés compuesto hace el resto. Al detener la figura en ciento cincuenta nodos se puede comprobar que los tres nodos naranjas casi siempre están entre los más antiguos. Robert Merton describió el mismo mecanismo en la ciencia en 1968 y lo llamó efecto Mateo, por el versículo «al que tiene se le dará»: los científicos reconocidos reciben más crédito por el mismo trabajo, lo que les da más recursos, más estudiantes y más visibilidad, lo que les da más crédito. Derek de Solla Price lo formalizó en 1976 para las citas entre artículos con el nombre de ventaja acumulativa y obtuvo, veintitrés años antes que Barabási y Albert, la misma ley de potencias. Y la matemática es más vieja aún: Udny Yule la había usado en 1925 para explicar por qué unos pocos géneros de plantas tienen cientos de especies y la mayoría una o dos, y Herbert Simon en 1955 para las frecuencias de palabras, los tamaños de ciudades y las rentas. La conexión preferencial es una idea que se ha descubierto al menos cinco veces con cinco nombres.

Lo que aportó el artículo de 1999 fue aplicarla a la red que todo el mundo tenía delante. Barabási y Albert habían medido la distribución de enlaces entrantes de una porción de la web y encontraron una ley de potencias en lugar de la campana que predecían los modelos aleatorios; después comprobaron lo mismo en la red de actores de cine y en la red eléctrica, y propusieron el modelo de crecimiento con conexión preferencial como explicación común. Llamaron a estas redes «libres de escala», porque no tienen un grado típico: la media existe, pero no describe a casi nadie. La consecuencia práctica más citada es la doble cara de la robustez. Una red libre de escala aguanta bien la pérdida de nodos al azar —lo más probable es perder uno de los muchos nodos pequeños—, pero se desmorona si se le quitan los pocos concentradores. Internet sobrevive a fallos aleatorios de routers y es vulnerable a un ataque dirigido; y, como muestra la epidemia en una red, una enfermedad que llegue a un concentrador se propaga mucho más deprisa que una que empiece en cualquier otro sitio, lo que cambia a quién conviene vacunar primero.

La historia posterior es una lección sobre cómo se comprueban las leyes. Durante una década se declararon «libres de escala» decenas de redes a partir de una recta trazada a ojo sobre puntos en escala logarítmica, que es un procedimiento generoso: muchas distribuciones que no son leyes de potencias parecen rectas en ese papel. Aaron Clauset, Cosma Shalizi y Mark Newman publicaron en 2009 el método estadístico para hacerlo bien, y Anna Broido y Clauset lo aplicaron en 2019 a casi mil redes reales: solo una minoría pequeña superaba la prueba estricta, aunque la mayoría tenía colas más pesadas que una red aleatoria. Barabási respondió que el modelo describía un mecanismo, no un ajuste exacto, y en eso el debate sigue. Lo que nadie discute es lo que enseña la figura: cuando la probabilidad de ganar depende de lo que ya se ha ganado, la desigualdad no es una anomalía que haya que explicar sino el resultado que hay que esperar, y la pregunta interesante pasa a ser qué la frena. En una red, los nodos envejecen y dejan de atraer; en la economía, esa pregunta es el tema del itinerario La desigualdad, medida.

Una epidemia en una red es un contagio que solo puede pasar entre personas conectadas, y la forma de las conexiones decide casi todo: cuánto dura, a cuántos alcanza, y a quién conviene proteger primero. Los modelos clásicos de epidemias, los de las curvas que se hicieron familiares en 2020, suponen que todo el mundo puede contagiar a todo el mundo, como las bolas de un bombo. En una red no: cada persona solo contagia a sus vecinos, y en una red donde unos pocos tienen cientos de contactos y la mayoría tiene tres, la misma enfermedad se comporta de otra manera, y las medidas que funcionan son otras.

La idea de que una epidemia sigue una red es anterior a la teoría de redes y anterior al descubrimiento de los microbios. En el verano de 1854 el cólera mató a más de quinientas personas en diez días en el barrio del Soho de Londres. El médico John Snow, convencido contra la opinión dominante de que la enfermedad se transmitía por el agua y no por el aire, marcó cada muerte en un plano y encontró que se apilaban alrededor de una bomba pública de Broad Street; interrogó a las familias de los muertos que vivían lejos y descubrió que iban a beber de esa bomba porque el agua les sabía mejor; y encontró que los obreros de la cervecería de la misma calle, que bebían cerveza, se habían salvado. Convenció a la junta parroquial de quitar la manivela de la bomba. El brote ya declinaba y el efecto de la manivela se discute todavía, pero el método —trazar quién estaba conectado con qué y cortar la conexión— es el de la epidemiología moderna.

El modelo de la figura es el más sencillo de todos, el SIR que William Kermack y Anderson McKendrick propusieron en 1927, puesto sobre una red. Cada persona está en uno de tres estados: susceptible, infectada o recuperada. Cada día, cada infectado contagia a cada vecino susceptible con una probabilidad fija, y pasados unos días se recupera y ya no contagia ni se contagia. Sin red, con todo el mundo mezclado, el modelo tiene un número que lo resume: el número reproductivo básico R₀, cuántas personas contagia por término medio un infectado en una población sin inmunidad. Es el producto de la probabilidad de contagio por contacto, la duración del periodo contagioso y el número de contactos. Si R₀ es menor que uno, cada infectado deja menos de un sucesor y el brote se apaga; si es mayor, crece hasta que la inmunidad de los recuperados lo frena. La lectura de la figura calcula ese R₀ de libro, y calcula también el que manda en la red.

Porque en la red hay un segundo número, y suele ser mayor. Lo que importa para la propagación no es el número medio de contactos sino el número medio de contactos de los contactos, que es más grande: un infectado elegido al azar tiene tantos vecinos como cualquiera, pero las personas a las que contagia no son cualesquiera, son sus vecinos, y ser vecino de alguien es más probable cuantos más contactos se tienen. En una red con concentradores, como la de la conexión preferencial, esa diferencia es enorme. Romualdo Pastor-Satorras y Alessandro Vespignani mostraron en 2001 que en una red libre de escala el umbral desaparece: no hay una tasa de contagio por debajo de la cual el brote se apague seguro, porque siempre hay un concentrador que multiplica los contagios en cuanto lo toca. La figura lo permite comprobar bajando la probabilidad de contagio hasta que en la red aleatoria el brote muere casi siempre, y viendo que en la red con concentradores sigue prendiendo a veces. Lo mismo, con personas, es el fenómeno de los supercontagiadores que James Lloyd-Smith y sus colegas midieron en 2005 para el SARS y otras enfermedades: la mayoría de los infectados no contagia a nadie y unos pocos contagian a decenas, y una epidemia así avanza a saltos, en brotes, no como una mancha uniforme.

De ahí sale la consecuencia práctica, que es el segundo deslizador. Vacunar al 30 % de la población al azar en la red con concentradores cambia poco: casi todos los vacunados son personas con dos o tres contactos, que ni contagiaban mucho ni servían de puente. Vacunar al 30 % más conectado corta la red en pedazos y el brote se queda en el vecindario donde empezó. Reuven Cohen, Shlomo Havlin y Daniel ben-Avraham publicaron en 2003 la versión aplicable de la idea, para cuando no se sabe quién es concentrador: vacunar no a personas al azar sino a un contacto elegido al azar de cada persona al azar, porque ese contacto, por el argumento del párrafo anterior, tiene más conexiones que la media. Es la lógica con que se prioriza a sanitarios, a personal de residencias y a los que atienden al público: no porque enfermen más sino porque están en más caminos.

Los contagios no son solo de virus. El mismo modelo describe la propagación de un fallo en la red eléctrica, de un rumor, de un impago entre bancos que se prestan entre sí, y de un programa malicioso entre ordenadores; Pastor-Satorras, Castellano, Van Mieghem y Vespignani revisaron en 2015 dos décadas de resultados en todos esos frentes. Hay una diferencia con las modas y las protestas que estudia el umbral de Granovetter: un virus basta con que lo traiga un contacto, mientras que un comportamiento suele exigir ver a varios, y eso hace que las mismas redes que aceleran lo uno frenen lo otro. Lo que comparten es lo que Snow entendió sin microscopio en 1854: para detener lo que se propaga, no hace falta entender lo que se propaga; basta con entender por dónde.

El algoritmo de Dijkstra encuentra el camino más corto entre un punto de partida y todos los demás puntos de una red cuyas conexiones tienen un coste no negativo: kilómetros entre ciudades, milisegundos entre routers, minutos entre paradas de metro. Lo publicó Edsger W. Dijkstra en 1959 en tres páginas, y sigue siendo el procedimiento que hay debajo de la mayoría de los navegadores, de los protocolos que encaminan el tráfico de internet y de casi cualquier sistema que tenga que responder a la pregunta «¿por dónde?». Su idea es tan sencilla que se puede ejecutar a mano sobre un mapa, y la figura de esta página está hecha para eso.

La regla es una sola, repetida. Se lleva una lista de distancias provisionales, que al empezar son cero para el origen e infinito para todos los demás. En cada paso se toma, de entre los nodos que aún no están fijados, el que tiene la distancia provisional más pequeña, y se declara fijada: ya no puede mejorar. Después se miran sus vecinos y, para cada uno, se comprueba si llegar a él pasando por el nodo recién fijado sale más barato que la distancia provisional que tenía; si es así, se apunta la nueva. Cuando el nodo que se fija es el destino, se ha terminado, y el camino se reconstruye hacia atrás siguiendo, desde cada nodo, el vecino por el que le llegó su mejor distancia.

Lo que hay que ver en la figura es por qué un nodo, una vez fijado, no puede mejorar. Cuando sale de la cola, su distancia provisional es la menor de todas las pendientes. Cualquier otro camino hasta él tendría que pasar por algún nodo todavía no fijado, y todos esos nodos están, por definición, al menos tan lejos como él. Como las conexiones no restan —eso es lo que significa que los costes sean no negativos—, alargar el recorrido a partir de ahí no puede acortarlo. Por eso la cola es el corazón del algoritmo y por eso la lectura de la figura la muestra en cada paso: el orden en que salen los nodos es el orden creciente de sus distancias definitivas, y lo que parece una búsqueda por el grafo es en realidad una onda que se expande desde el origen y va alcanzando los nodos por distancia.

Esa misma condición marca el límite del método. Si alguna conexión tiene coste negativo —cosa que no ocurre en mapas, pero sí en problemas de finanzas o en grafos que codifican ganancias como costes negativos—, un nodo ya fijado podría mejorarse más tarde, y Dijkstra dará respuestas equivocadas sin avisar. Para esos casos existen algoritmos más lentos, como el de Bellman-Ford, que revisan todas las conexiones varias veces. La otra limitación es que el algoritmo, en su forma original, explora en todas las direcciones por igual: para ir de Madrid a Barcelona calcula también la distancia a Badajoz, porque Badajoz está más cerca que Barcelona y sale antes de la cola. En la figura se ve cuando el destino está al otro extremo del mapa: la mitad de los nodos se fijan antes de llegar a él.

Dijkstra contó en varias ocasiones cómo se le ocurrió. En 1956 trabajaba en el Centro Matemático de Ámsterdam y tenía que preparar una demostración pública del ARMAC, el nuevo ordenador del centro, con un problema que un público no especializado pudiera entender: el camino más corto entre dos de las sesenta y cuatro ciudades de un mapa de los Países Bajos. Según relató en una entrevista de 2001 publicada por Communications of the ACM en 2010, diseñó el algoritmo una mañana en la terraza de un café, tomando un café con su prometida, en unos veinte minutos y sin papel ni lápiz, y añadió que una de las razones de su elegancia era precisamente que se había pensado sin escribir. No lo publicó hasta 1959, y lo hizo casi como una nota al margen, en el primer volumen de una revista nueva, porque en la época los algoritmos apenas se consideraban material publicable.

La eficiencia del algoritmo depende de cómo se organice la cola. La versión de 1959 recorría toda la lista de nodos para encontrar el más cercano en cada paso, lo que para una red de n nodos supone un tiempo proporcional a n². Con un montículo binario, que es la estructura que la figura simula con sus fichas ordenadas, el coste baja a algo proporcional al número de conexiones multiplicado por el logaritmo del número de nodos. Michael Fredman y Robert Tarjan introdujeron en 1984 los montículos de Fibonacci, que llevan el coste teórico a su mínimo conocido para este tipo de algoritmos, aunque en la práctica los montículos binarios suelen ser igual de rápidos por ser más simples.

Sobre Dijkstra se construyó lo que vino después. El algoritmo A*, propuesto por Peter Hart, Nils Nilsson y Bertram Raphael en 1968 para el robot Shakey del instituto de investigación de Stanford, añade a la distancia provisional de cada nodo una estimación de lo que le falta hasta el destino, de manera que la onda se expande preferentemente hacia donde interesa; es el algoritmo de los videojuegos y de la robótica. Para los mapas de carreteras de un continente, con decenas de millones de nodos, ni siquiera eso basta, y desde 2008 los navegadores usan técnicas como las jerarquías de contracción de Robert Geisberger y sus colegas, que preprocesan la red una vez para poder responder después cualquier consulta en menos de un milisegundo. Debajo de todas ellas, en algún nivel, sigue ejecutándose la regla de la terraza del café: sacar el más cercano, fijarlo, revisar a sus vecinos.

PageRank es el algoritmo con el que Google ordenó los resultados de búsqueda en sus primeros años y que le permitió desplazar a los buscadores anteriores. Su idea es que la importancia de una página web se puede medir por los enlaces que recibe, pero no contándolos sin más, sino ponderando cada uno por la importancia de la página que lo emite: un enlace desde una página muy enlazada vale más que cien enlaces desde páginas que nadie enlaza. La definición es circular a propósito —la importancia se define en términos de la importancia—, y la elegancia del método está en que esa circularidad tiene una solución única que además se calcula con facilidad.

La forma más intuitiva de entenderlo es la que sus autores llamaron el surfista aleatorio. Imagínese a alguien que navega sin criterio: en cada página elige al azar uno de los enlaces salientes y lo sigue, y de vez en cuando —con una probabilidad fija, típicamente el 15 %— se aburre y salta a una página cualquiera de toda la red. El PageRank de una página es la fracción del tiempo que ese surfista pasaría en ella si navegara eternamente. Las páginas a las que llegan muchos caminos, y caminos que a su vez son muy transitados, acumulan tiempo; las páginas a las que nadie apunta solo reciben las visitas del salto aleatorio. En la figura, el botón que suelta un surfista lo hace exactamente así, y las barras naranjas que cuentan sus visitas se van acercando, salto a salto, a las barras negras del cálculo exacto.

El cálculo directo es el que hace el botón de iterar. Se empieza dando a todas las páginas el mismo valor. En cada ronda, cada página reparte su valor actual en partes iguales entre las páginas a las que enlaza, y el nuevo valor de cada página es lo que recibe de las demás, multiplicado por 0,85, más una pequeña cantidad fija que representa al surfista que llega saltando. Al cabo de unas decenas de rondas los valores dejan de cambiar: se ha alcanzado el punto en el que cada página tiene exactamente el rango que le corresponde por los rangos de quienes la enlazan. En términos de álgebra lineal, ese vector estable es el vector propio dominante de la matriz de enlaces de la red, y el método de iterarlo se conoce desde el siglo XIX como método de las potencias. Larry Page y Sergey Brin informaron en 1998 de que para los veinticuatro millones de páginas que habían rastreado el cálculo convergía en unas cincuenta iteraciones.

El parámetro de amortiguación, la probabilidad de seguir un enlace en vez de saltar, es lo que hace que el sistema funcione, y el deslizador de la figura permite ver por qué. Sin salto aleatorio, una página sin enlaces salientes —un documento PDF, una imagen— sería un agujero: el surfista llegaría y no podría irse, y todo el rango de la red acabaría escurriéndose por ahí. La red preconfigurada con un callejón sin salida lo muestra: con la amortiguación cerca de 1 el rango se acumula en el circuito cerrado y el resto de la red se vacía. Con el 15 % de saltos, el surfista sale del atolladero y la distribución se reparte. Brin y Page eligieron 0,85 sin más justificación que la de que funcionaba bien, y el valor se ha mantenido en casi toda la literatura posterior.

La red llamada «granja de enlaces» ilustra la primera manera de engañar al algoritmo, y por qué no funciona tan bien como parece. Un grupo de páginas que se enlazan mutuamente en círculo se pasa el rango de una a otra sin perderlo, y si alguna de ellas recibe además un enlace del exterior, todo el grupo se infla. Pero el rango que un grupo puede retener está limitado por el salto aleatorio, que se lo va llevando en cada ronda, y una granja aislada acumula poco más de lo que le corresponde por su tamaño. Las estrategias que sí funcionaron durante años —comprar enlaces en páginas ya importantes, colar comentarios con enlace en blogs ajenos— atacaban la premisa del modelo, no su matemática: el algoritmo supone que un enlace es un voto sincero de quien lo pone, y eso dejó de ser cierto en cuanto los enlaces empezaron a valer dinero.

La idea no era nueva cuando Page y Brin la aplicaron a la web. Leo Katz había propuesto en 1953 medir el prestigio de una persona en una red social por las personas que la nombraban, ponderadas por el prestigio de estas. Gabriel Pinski y Francis Narin habían hecho lo mismo en 1976 con revistas científicas, resolviendo el mismo problema de vector propio para decidir qué revista de física era más influyente contando citas ponderadas por la influencia de quien cita. Lo que aportó PageRank fue aplicarlo a una red de cientos de millones de nodos que crecía sin control, demostrar que el cálculo era factible a esa escala y, sobre todo, convertirlo en un producto. La patente, presentada en 1998 a nombre de Page y propiedad de la Universidad de Stanford, se licenció en exclusiva a Google; Stanford vendió las acciones que recibió a cambio en 2005 por 336 millones de dólares.

PageRank dejó de ser el criterio dominante de Google hace tiempo. Los sistemas actuales combinan cientos de señales —el texto, la conducta de los usuarios, la frescura, la autoridad temática— y la barra verde que mostraba el PageRank de cada página en la barra de herramientas del navegador desapareció en 2016. Pero el algoritmo sobrevive fuera del buscador, en todos los sitios donde una red de referencias necesita convertirse en una lista ordenada: para identificar las proteínas más importantes de una red metabólica, los artículos científicos más influyentes de un campo, las especies clave de un ecosistema o las calles más transitables de una ciudad. En todos esos casos la pregunta es la misma que se hicieron dos estudiantes de doctorado en Stanford: dado quién apunta a quién, ¿quién importa?

El modelo de segregación de Schelling es una simulación que muestra cómo una ciudad puede acabar dividida en barrios homogéneos aunque ninguno de sus habitantes quiera vivir en un barrio homogéneo. Lo propuso el economista Thomas Schelling en 1969, con monedas de dos tipos sobre un tablero de ajedrez, y es el ejemplo canónico de un fenómeno emergente: un resultado colectivo que no está en las intenciones de nadie y que surge de la interacción de decisiones individuales modestas. Schelling recibió el premio del Banco de Suecia en Ciencias Económicas en memoria de Alfred Nobel en 2005, sobre todo por su trabajo en teoría de juegos y disuasión nuclear, pero este modelo de tablero es probablemente su idea más difundida.

Las reglas caben en tres frases. Una rejilla representa la ciudad; cada casilla es una casa, ocupada por una persona de uno de dos grupos o vacía. Cada persona mira a sus ocho vecinos y está satisfecha si al menos una cierta fracción de ellos es de su propio grupo; si no lo está, se muda a una casa vacía elegida al azar. El proceso se repite hasta que nadie quiere moverse. La figura de esta página ejecuta exactamente esto, con un tablero de cuarenta por cuarenta y un deslizador para la fracción que cada persona exige.

El hallazgo que dio fama al modelo es lo que ocurre con el umbral bajo. Si cada persona exige que al menos un tercio de sus vecinos sea de su grupo —es decir, si está dispuesta a vivir siendo minoría en su propio entorno, con dos vecinos de cada tres del otro grupo—, el tablero, que empieza mezclado, termina dividido en manchas casi puras, y la fracción media de vecinos del propio grupo sube del 50 % inicial a más del 75 %. Nadie ha pedido eso. Cada persona estaría satisfecha con mucho menos, y sin embargo el resultado agregado es una segregación muy superior a la que cualquiera de ellas prefería. La gráfica de la figura registra ese desplazamiento ronda a ronda.

El mecanismo es una cadena de reacciones. Al principio, con la distribución aleatoria, unos pocos habitantes tienen mala suerte y caen en un entorno donde son minoría por debajo de su umbral. Se mudan. Su marcha cambia el vecindario que dejan —ahora hay un vecino menos de su grupo para los que se quedan— y el vecindario al que llegan, y algunos de los que antes estaban satisfechos dejan de estarlo. Cada movimiento provoca otros, y el tablero se va ordenando en regiones donde los habitantes se sienten seguros porque están rodeados de iguales. Dejan Vinković y Alan Kirman mostraron en 2006 que la dinámica es matemáticamente análoga a la separación de dos líquidos que no se mezclan, con las fronteras entre barrios comportándose como una tensión superficial que tiende a alisarlas y a fusionar las manchas pequeñas en grandes.

El modelo también dice algo sobre el papel de las casas vacías y de la proporción entre grupos, que los otros dos deslizadores de la figura controlan. Con pocas casas vacías, quien quiere mudarse tiene pocas opciones, el proceso se atasca y el tablero final es menos segregado pero con más insatisfechos. Con una minoría pequeña, la segregación es más severa para ella: sus miembros tienen menos probabilidades de encontrarse rodeados de iguales por azar, se mudan más y acaban concentrados en pocos enclaves. Schelling anticipó ambas cosas en el artículo de 1971 con cálculos a mano, y la tolerancia asimétrica —un grupo más exigente que el otro— produce dinámicas parecidas.

La interpretación del modelo es donde empieza la discusión, y conviene ser preciso sobre lo que demuestra y lo que no. Demuestra que la preferencia individual suave es suficiente para producir segregación fuerte. No demuestra que sea la causa de la segregación real en ninguna ciudad concreta, y el propio Schelling insistió en que su tablero no incluía discriminación, diferencias de renta, políticas de vivienda ni instituciones, todos ellos factores documentados de la segregación residencial estadounidense que era su referencia. William Clark y Mark Fossett revisaron en 2008 las encuestas de preferencia residencial de varias ciudades y encontraron que las preferencias declaradas de los distintos grupos son, en efecto, del orden que el modelo necesita, y asimétricas; concluyeron que el mecanismo de Schelling es plausible como uno de los ingredientes, no como explicación completa.

El segundo deslizador de la figura recoge una de las extensiones más estudiadas. En el modelo original nadie se queja de tener demasiados vecinos iguales; si se introduce un límite superior —personas que prefieren la mezcla y se van cuando el barrio se vuelve demasiado uniforme—, aparecen configuraciones intermedias: barrios mixtos estables que conviven con barrios homogéneos. Erez Hatna e Itzhak Benenson mostraron en 2012 que el resultado del modelo no es una dicotomía entre integrado y segregado sino todo un abanico de estados mixtos, y que la proporción de habitantes con cada tipo de preferencia decide cuál se alcanza. Con el techo al 70 % en la figura, la línea negra se detiene mucho antes que sin él.

Lo que el modelo enseña con más fuerza es una lección de método, y por eso se estudia fuera de la sociología urbana, en economía, en física y en ciencias de la computación. No se puede inferir la preferencia individual a partir del patrón colectivo: un tablero muy segregado es compatible con habitantes muy tolerantes. Tampoco se puede inferir el patrón colectivo a partir de la preferencia: saber que cada persona acepta ser minoría no permite predecir que la ciudad se dividirá. Entre lo micro y lo macro hay una dinámica, y la única manera de conocerla es ejecutarla. Schelling lo hizo con monedas; la figura de esta página lo hace con mil seiscientas casillas, y la conclusión es la misma que en el tablero de ajedrez de 1969.