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.

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.

L’algoritme de Johnson de la BGL amb el mapa de pesos extern

Un exemple d’ús de l’algortime de Johnson implementat a la Boost Graph Library, anomenat johnson_all_pairs_shortest_paths, que serveix per a trobar la distància mínima entre totes les parelles de vèrtexs d’un graf amb .

Quan els pesos de les arestes d’un graf són totes iguals, en general no interessa arrossegar un mapa intern d’aquesta propietat amunt i avall. En el meu cas, el tipus de graf que estic utilitzant és:

typedef boost::subgraph<
boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS,
boost::no_property, boost::no_property > > Graph;

De totes maneres, johnson_all_pairs_shortest_paths necessita que el graf tingui un mapa amb els pesos de les arestes, així que cal definir-ne un d’extern i passar-lo com a argument. Heus aquí l’exemple, on defineixo totes les arestes amb pes igual a 1. Espero que us sigui útil.

int V = boost::num_vertices (gc);

// Distance matrix.
std::vector<std::vector<int> > D (V, std::vector<int> (V));

// Weights map (all edges weight 1).
typedef boost::property_map<Graph, boost::edge_index_t>::type EdgeID_Map;
EdgeID_Map edge_id = boost::get(boost::edge_index, gc);
std::vector<int> weight_vector (boost::num_edges (gc), 1);
boost::iterator_property_map<std::vector<int>::iterator, EdgeID_Map, int, int&>::iterator, EdgeID_Map, int, int&>
weight (weight_vector.begin(), edge_id);

// Named parameter version of the Johnson algorithm.
boost::johnson_all_pairs_shortest_paths (gc, D, boost::weight_map (weight));

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.

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 , és a dir, com la funció que compleix , on é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 d’un graf Erdős-Rényi. En aquests grafs, la mida relativa (o la probabilitat) de la component gegant és [1], on és el grau mig del graf. Utilitzant la funció W, la solució no trivial () d’aquesta equació trascendental és . Hi ha alguns valors exactes coneguts d’aquesta funció W que poden resultar força útils. Per exemple, sabent que veiem el resultat conegut del llindar de percolació, .

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

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.