Un sistema per a analitzar Wikileaks

Via el blog de Natxo Sorolla sobre xarxes socials i llengües llegeixo que un grup de la UPC (el Data Management Group) ha proposat “un sistema d’exploració d’informació en forma de xarxa o graf que ha creat i patentat, per extreure informació de la xarxa Wikileaks”:

El director del grup DAMA-UPC, Josep Lluís Larriba, planteja fer servir aquesta tecnologia per extreure informació de la xarxa Wikileaks, des de dos punts de vista: per obtenir indicadors genèrics que aportin informació, per conèixer si la xarxa d’informació té les característiques d’una xarxa social o bé si es creen comunitats de dades que fan pensar en grups que aporten informació rellevant; i, d’altra banda, per analitzar com evoluciona una temàtica determinada en el temps, a través dels diferents documents allotjats a l’espai web; com es relaciona una persona o un grup de persones amb diferents temàtiques, o bé com s’interrelacionen els documents, entre d’altres aspectes.

El sistema també es pot aplicar en altres contexts. Un dels que trobo interessants és el de buscar referees pels articles científics: estalviaria molta feina d’editors i podria fer més factible un sistema de publicacions científiques obertes.

Network data: OpenPGP Web of Trust

Com ja he comentat, últimament he estudiat com es transmet la informació en una xarxa on el soroll entre nodes de la xarxa limita el número màxim de “salts” que es poden fer sense que la informació es degradi excessivament. I com a exemple d’una xarxa real, he treballat amb la Xarxa de Confiança (Web of Trust) del protocol OpenPGP.

Sense entrar en gaires detalls, l’OpenPGP és un protocol estàndard d’encriptació que s’utilitza per assegurar les communicacions a través d’email utilitzant criptografia de clau pública. Així, si l’Alice vol enviar un missatge segur a en Bob, ha d’utilitzar la clau pública d’en Bob per a encriptar-lo. L’objectiu de la Xarxa de Confiança, en aquest protocol, és resoldre el problema d’autentificació que es produeix quan l’Alice no pot verificar si la clau que està fent servir és realment propietat d’en Bob. Aquesta xarxa social, doncs, representa la confiança entre usuaris d’OpenPGP —confiança pel que fa a que una determinada clau correspon efectivament a una adreça de correu concreta, però no necessàriament en el que aquesta adreça digui. Tot això ho comentava, també per sobre, fa unes setmanes.

El cas és que he decidit posar l’arxiu amb el graf disponible a Internet, per a que qui vulgui el pugui utilitzar. La informació de la Xarxa de Confiança ja és pública de per si. El que penjo jo és una xarxa una mica “processada” i en un format de graf estàndard: el format GML. Espero poc a poc anar construint un petit zoo amb uns quants tipus de xarxa.

Xarxa de Confiança del protocol OpenPGP

A partir de la pàgina del Wotsap, he agafat el component fortament connectat (strongly connected component) de la Xarxa de Confiança completa del servidor de claus suís del 25 de maig de 2010, que conté 41.459 claus (nodes del graf) i 424.577 firmes (arestes). A partir d’aquesta xarxa, considero el graf format únicament per les arestes bidireccionals (és a dir, les que corresponen a dos usuaris que s’han signat les claus mútuament). Això deixa un graf no dirigit amb 38.550 claus i 145.388 firmes bidireccionals.

La xarxa està penjada aquí en un arxiu en format GML i comprimit amb el gzip. Espero que sigui útil (o si més no interessant!). Si el feu servir, podeu citar (de moment), Martí Cuquet and John Calsamiglia, “Limited path entanglement percolation in quantum complex networks”, arXiv:1011.5630v1 [quant-ph] (2010).

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.

Xarxes complexes, entrellaçament i comunicació limitada pel soroll

Les xarxes impregnen totes les estructures d’informació. Són la base de sistemes naturals, socials i artificials basats en la interacció de diversos agents, descrivint el flux d’informació entre ells. Les diferències en les característiques d’aquestes interaccions i la seva evolució en el temps donen lloc a diferents tipus d’estructures: xarxes regulars, completament aleatòries o, a mig camí entre aquests dos models, les xarxes complexes. La informació quàntica no n’és una excepció, i una de les tasques clau en aquestes xarxes és la transmissió d’informació quàntica entre dos nodes molt separats entre ells.

Tot plegat, una mica d’autopropaganda sobre aquest nou preprint: Limited path entanglement percolation in quantum complex networks, on estudiem l’avantatge que comporta l’estructura complexa d’una xarxa en la comunicació quàntica a través seu, com es pot modificar aquesta estructura per fer-la més útil quan disposem de menys entrellaçament entre nodes i com n’és d’important la seva propietat de món petit quan la presència de soroll ens fixa la distància màxima que pot recorre la informació abans de degradar-se. Aquest n’és l’abstract:

We study entanglement distribution in quantum complex networks where nodes are connected by bipartite entangled states. These networks are characterized by a complex structure, which dramatically affects how information is transmitted through them. For pure quantum state links, quantum networks exhibit a remarkable feature absent in classical networks: it is possible to effectively rewire the network by performing local operations on the nodes. We propose a family of such quantum operations that decrease the entanglement percolation threshold of the network and increase the size of the giant connected component. We provide analytic results for complex networks with arbitrary (uncorrelated) degree distribution. These results are in good agreement with numerical simulations, which also show enhancement in correlated and real world networks. The proposed quantum preprocessing strategies are not robust in the presence of noise. However, even when the links consist of (noisy) mixed state links, one can send quantum information through a connecting path with a fidelity that decreases with the path length. In this noisy scenario, complex networks offer a clear advantage over regular lattices, namely the fact that two arbitrary nodes can be connected through a relatively small number of steps, known as the small world effect. We calculate the probability that two arbitrary nodes in the network can successfully communicate with a fidelity above a given threshold. This amounts to working out the classical problem of percolation with limited path length. We find that this probability can be significant even for paths limited to few connections, and that the results for standard (unlimited) percolation are soon recovered if the path length exceeds by a finite amount the average path length, which in complex networks generally scales logarithmically with the size of the network.

Noge ikki!

Volia haver escrit algo sobre el Primavera però ha sigut una setmana una mica boja. El dilluns encara me n’estava recuperant, i el dimarts em diuen d’anar a Alemanya a una conferència que comença… dimecres! O sigui que a buscar vols i confirmar que hi hagi allotjament disponible corrents corrents. Així que res, he estat uns dies aprenent coses de random i de quantum walks prop de Freiburg i agafant idees. Les xerrades potser una mica massa concentrades: el primer dia, de 8.30 a 22 non stop! En Shlomo Havlin va presentar un nou resultat que han publicat fa poc a Nature molt interessant, sobre xarxes (clàssiques) interconnectades entre elles. L’article es pot veure sense subscripció a Nature des de la pàgina de l’autor. I també van estar bé les xerrades de l’Elena Agliari sobre quantum walks en xarxes complexes i d’en Gregor Tanner sobre algoritmes de cerca en xarxes regulars.

Tres concerts del Primavera: els concerts de Michael Rother (de Neu!), Liquid Liquid i Jeffrey Lewis & The Junkyard. Jack Lewis & The Cutoffs m’ha seguit aquests dies per Alemanya.