Q

Non si prosegua l'azione secondo un piano.

Tag: percolació

Tallant cables

Diuen que Internet és resistent a atacs aleatoris però molt vulnerable a atacs dirigits contra els seus hubs principals. Així és, certament, per a les xarxes lliures d’escala: són molt resitents a atacs o fallades de nodes aleatoris (Cohen et al., 2000), però si en canvi els atacs es dirigeixen contra els nodes més ben connectats la xarxa es trenca ràpidament (Albert et al., 2000; Cohen et al., 2001). Tot i que internet inclou forces cicles tancats i correlacions entre els seus nodes, la seva distribució de graus és la d’una xarxa lliure d’escala, i per tant s’espera que comparteixi més o menys aquestes característiques.

Doncs bé, la setmana passada llegia que, buscant coure per revendre’l, una dona de 75 anys tallava la connexió a internet a Armènia al tallar un cable de fibra òptica subterrani. Així que, o bé la dona ha tingut molta llet de tallar justament un cable clau –i certament n’hi ha, com per exemple els cables de fibra òptica submarins–, o bé la xarxa no és tan robusta a talls aleatoris.

Referències:

Albert, R., Jeong, H., Barabási, A.-L. (2000): Error and attack tolerance of complex networks, Nature, 406, 378.

Ara (2011): Una dona de 75 anys talla la connexió a internet a Armènia, publicada al diari Ara el 07/04/2011.

Cohen, R., Erez, K., ben-Avraham, D., Havlin, S. (2000): Resilience of the Internet to Random Breakdowns, Physical Review Letters, 85, 4626.

Cohen, R., Erez, K., ben-Avraham, D., Havlin, S. (2001): Breakdown of the Internet under Intentional Attack, Physical Review Letters, 86, 3682.

La revolució egípcia al Twitter

Via el blog sobre xarxes socials i llengües d’en Natxo Sorolla —que últimament segueixo força— he descobert aquest vídeo fet per André Panisson, un investigador predoctoral a Torí, mitjançant el programa Gephi. Es tracta de l’evolució d’una xarxa dinàmica on els nodes són usuaris de Twitter, i un enllaç entre dos nodes es forma si un dels dos usuaris fa un retweet de l’altre que contingui el hashtag #jan25. Les dades són de l’11 de febrer de 2011, el dia que va caure Mubarak. Comencen a les 17:50 (hora local de El Caire) i duren una hora, de manera que enganxen de ple l’anunci de Suleiman de què Mubarak ha renunciat al càrrec. La xarxa va creixent a mesura que es publiquen nous tweets. Tot plegat ho explica el mateix André Panisson aquí. I aquest és el vídeo, resumint una hora en una mica menys de quatre minuts:

És interessant veure com va creixent la xarxa. A l’inici, els primers retweets uneixen parelles de nodes aïllats: hi ha moltíssims usuaris, i el més probable és que un nou retweet es faci entre dos usuaris que encara no n’han fet cap. Poc a poc van apareixent els primers arbres, de 3, 4 i 5 nodes, i segueixen apareixent nous enllaços aïllats. Cap a 0:40 ja passa una cosa interessant, i és que un grupet d’arbres separats s’uneix amb l’arribada de tres o quatre enllaços nous: cada vegada és més fàcil que un enllaç nou vagi a parar a un clúster, i és més probable si més gran és el clúster. Finalment, arriba un moment crític, i els clústers de mida relativament gran que hi havia s’acaben unint en un de gegant. És el punt crític que es coneix com a llindar de percolació. Aquí també apareixen els primers cicles, camins que es tanquen sobre si mateixos. Aquest clúster gegant té una mida significativa (de l’ordre de la mida de la xarxa), i a partir d’ara anirà creixent poc a poc amb l’arribada de nous enllaços que l’uniran als pocs clústers que encara queden aïllats. És gairebé un exemple “de llibre” del fenòmen de percolació.

Hi ha una cosa, però, que trobo ben curiosa: a la primera part de l’evolució (abans del punt crític) només hi ha arbres, i no cicles tancats. Això és típic dels models més senzills de xarxes aleatòries (com el d’Erdős-Rényi o el configuration model), però força estrany en les xarxes socials com ara Twitter mateix. En aquestes xarxes el nivell de clustering (a grans trets, l’amic del teu amic és fàcil que sigui també amic meu) és força alt, i en canvi en aquesta evolució això no es veu. Justament per això, seria interessant veure quina és la xarxa subjacent al graf: quins nodes —usuaris de Twitter— són seguidors de quins. De fet, xafardejant una mica a la imatge que surt al final de l’article es poden veure els noms dels nodes més influents. Buscant-los ràpidament al Twitter descobrim que són usuaris amb un munt de seguidors.

Un segon punt que potser estaria bé estudiar és que el retweet és en realitat un enllaç direccional: és un usuari que fa un retweet d’un altre usuari. Com quedaria, la xarxa, si dibuixéssim els enllaços dirigits? Els nodes influents —amb més quantitat de veïns— ho són perquè els han “retweetejat” molt, o perquè han estat ells qui han fet molts retweets? Finalment, també seria curiós, posats a demanar, veure quins han estat els tweets més influents, més que no pas quins usuaris. Sembla ser, també, que en aquest vídeo només hi ha un 10% de les dades disponibles. A veure si en tornem a sentir parlar.

Veïns de confiança

Tots haureu sentit parlar alguna vegada dels “mons petits” i els sis graus de separació. Últimament he estat mirant com evolucionen els clústers d’una xarxa quan en limitem el número màxim de passos que podem fer per anar d’un punt a un altre. Per jugar una mica, he mirat què passava en la xarxa de confiança (web of trust) del sistema criptogràfic OpenPGP.

No entraré en detalls, però a grans trets OpenPGP és un protocol de criptografia asimètrica en què cada persona té una parella de claus: la pública i la privada. La gràcia d’aquest sistema és que per enviar un missatge encriptat a una persona no ens cal haver compartit abans cap clau: n’hi ha prou amb descarregar-nos la seva clau pública de qualsevol servidor de claus i fer-la servir per encriptar un missatge que només el destinatari podrà rebre. El missatge és segur (en principi), però el que no queda tan clar és si la clau pública realment pertany a la persona amb qui ens volem communicar. Per a assegurar-nos-en tenim bàsicament dues opcions. Una és trobar-nos almenys una vegada, comprovar que la persona és qui diu ser i signar la clau pública que ens mostra. Com que la nostra firma només la podem fer nosaltres, la propera vegada que volguem utilitzar la seva clau pública només hem de comprovar que la tenim signada. Però això ens torna al problema de què en algun moment ens hem de trobar cara a cara. La segona opció utilitza la xarxa de confiança: si jo signo la clau d’un conegut, i aquest conegut firma la clau d’un desconegut, puc confiar en què el desconegut és qui diu ser. D’aquesta manera, si existeix un camí entre dues persones, aquestes dues persones poden confiar entre elles.

Aquí teniu algunes gràfiques d’exemple. Partint de la meva antiga clau 0x4C899530 (que ja no faig servir, però per desgràcia la nova clau encara no té cap firma), he mirat com creixia la seva xarxa de confiança a mesura que permetia una distància entre claus més gran. El creixement no és espectacular perquè la clau no pertany a la component gegant de la xarxa de confiança (que correspon aproximadament al 86% de la xarxa), sinó a una petita component de 1.500 claus (un 3,9% de la xarxa), però tot i així ja fa el seu efecte.

Per cert, si m’heu d’enviar missatges encriptats, no feu servir la 0x4C899530 que vaig perdre sense certificat de revocació…), sinó la 0×49116823.

La funció W de Lambert

Algú havia vist alguna vegada la funció W de Lambert? Al Mathematica potser l’heu vist amb el nom de ProductLog. Apareix en llocs força diferents, entre ells la combinatòria. Es defineix com la funció inversa de f(w) = w e^w, és a dir, com la funció W que compleix z = W(z) e^{W(z)}, on z és un número complex. I se sol utilitzar per expressar solucions d’algunes equacions trascendentals.

M’ha sortit al mirar-me la solució de la component gegant S d’un graf Erdős-Rényi. En aquests grafs, la mida relativa (o la probabilitat) de la component gegant és S = 1 - e^{-zS} [1], on z és el grau mig del graf. Utilitzant la funció W, la solució no trivial (S\neq0) d’aquesta equació trascendental és S = 1 + \frac{1}{z} W(-ze^{-z}). Hi ha alguns valors exactes coneguts d’aquesta funció W que poden resultar força útils. Per exemple, sabent que W(-e^{-1}) = -1 veiem el resultat conegut del llindar de percolació, z=1.

La mida S de la component gegant d'un graf Erdős-Rényi en funció del grau mig z.

Prometo una explicació de la percolació algun dia d’aquests… si m’hi animo…

Referències

[1] Mark E. J. Newman, Steven H. Strogatz, and Duncan J. Watts, “Random graphs with arbitrary degree distributions and their applications“, Physical Review E (Statistical, Nonlinear, And Soft Matter Physics) 64, 026118 (2001). eprint: arXiv cond-mat/0007235.

Follow

Get every new post delivered to your Inbox.

Join 158 other followers