Dibuixar hipergrafs amb Mathematica

Últimament estic treballant amb hipergrafs, i necessitava una eina per visualtizar-los fàcilment (preferentment, en Mathematica). No n’he trobat cap, així que he adaptat la funció GraphPlotHighlight, de simonjtyler. Al final del post copio les funcions necessàries, però comencem per algunes definicions matemàtiques i algun exemple.

Un hipergraph és una parella de conjunts , on és el conjunt de nodes () i és el conjunt d’hiperarestes (subconjunts de diferents del conjunt buit): . Un hipergraph és -uniforme (i escrivim ) si totes les seves hiperarestes tenen exactament elements. És a dir, . Amb aquestes definicions un graf normal i corrent és un hipergraf -uniforme.

El problema a l’hora de visualitzar un hipergraf és com dibuixar les hieprarestes. Una opció és dibuixar una àrea que inclogui els nodes continguts en l’hiperaresta. Una altra opció és dibuixar una aresta simple (és a dir, connectant només dos nodes) per cada parella de nodes dins d’una hiperaresta. En aquest cas, però, és fàcil confondre l’hipergraf amb un graf estàndard, o confondre arestes simples que corresponen a hiperarestes diferents. El que he fet amb la funció HypergraphPlotHighlight és combinar les dues opcions (dibuixant àrees i arestes simples), i a més diferenciar hiperarestes diferents amb colors diferents. El resultat encara no és òptim, però poc a poc s’hi acosta.

El següent exemple representa l’hipergraph amb E={{1, 2, 3}, {2, 3, 4}, {4, 5, 6, 9, 10}, {3, 5, 7, 8}, {1, 3, 8}, {7,  9}}:

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.

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));

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.

Mons petits

Les Small World són xarxes on dos nodes qualssevol estan separats només per un número petit de passos, de salts d’un node a un altre. Aquest efecte va començar a ser estudiat a finals dels 60, quan Stanley Milgram, un psicòleg social que va dur a terme un experiment per determinar cadenes de relacions als Estats Units.

L’experiment de Milgram consistia en repartir paquets a persones aleatòries de les ciutats de Omaha, Nebraska i Wichita, a Kansas, amb instruccions d’enviar-les directament a certes persones de Boston si les coneixien directament, o en cas contrari d’enviar-les a algú que ells pensessin que podria conèixer aquestes persones. Al final, Milgram recollia els paquets i observava quants passos havia fet abans d’arribar a destianció. Milgram va arribar a la conclusió que les persones estaven separades per només 6 passos de mitja (els famosos 6 graus de separació, tot i que ell no va utilitzar aquest terme).

Tot i que els seus experiments han rebut moltes crítiques pel que fa a la veracitat o precisió, sí que és veritat que van significar un gran impuls per l’estudi de les xarxes, no només en el camp de les xarxes socials sinó en general, i que l’”efecte small world” s’ha confirmat en diverses xarxes.

Actualment, es considera que els xarxes que presenten un efecte small world són aquelles en les quals la distància típica que separa dos nodes (el número d’enllaços que cal recórrer per arribar d’un a l’altre) creix només com el logaritme del número total de nodes de la xarxa. Hi ha diversos tipus de xarxes que satisfan aquest requisit, per exemple les xarxes completament aleatòries, però no totes són una bona representació de les xarxes socials que trobem a la realitat. Aquestes xarxes socials, en canvi, es caracteritzen també per tenir un elevat nivell de “clustering”: és més probable que dues persones (dos nodes de la xarxa social) siguin amigues si ambdues comparteixen un altre amic en comú. El 1998, Duncan Watts i Steven Strogatz van proposar un model que presentava les dues propietats: un alt nivell de clustering, i a la vegada una separació típica petita. A aquest model se l’ha anomenat tant “small-world model” com “Watts-Strogatz model”, i té diverses versions.

Una d’aquestes versions, interessant perquè se’n poden calcular diverses propietats fàcilment, és la següent. Es distribueixen els nodes en un cadena unidimensional de longitud , i cada node es connecta mitjançant un enllaç amb els seus veïns més propers fins a una distància . És a dir, un determinat node estarà connectat amb els nodes (sense incloure’s a ell mateix). Al crear aquesta “xarxa base”, es pot considerar que està tancada sobre si mateixa formant un anell, tot i que per derivar els resultats es considera llavors que tendeix cap a infinit. Una vegada tenim la xarxa base, s’afegeix un enllaç “drecera” amb probabilitat per cada enllaç original de la xarxa base, de manera que al final queden una mitjana de dreceres. Cristopher Moore i Mark Newman tenen aquest article a PRE (arXiv cond-mat/0001393), que trobo molt interessant, que analitza les propietats de percolació d’aquest model en concret.

Per a qui hi vulgui jugar una mica, aquí us poso una funció del Mathematica que genera aquest model. En aquest cas, size és la mida de la xarxa, k la distància màxima dels veïns de la xarxa base i prob la probabilitat de cada drecera.

SmallWorldAddedShortcutsGraph[size_,k_,prob_] := Module[
	{g,i,AddShortcut},

	AddShortcut[graph_] := Module[
		{v=V[graph],source,target},

		source=RandomInteger[{1,v}];
		target=RandomInteger[{1,v}];
		While[MemberQ[NeighborhoodVertices[graph,source,1],target],
			target=RandomInteger[{1,v}]
		];

		AddEdge[graph,{source,target}]
	];

	g = If[2k>=size,CompleteGraph[size],Harary[2k,size]]
	For[i=0,i<size*k,i++,
		If[RandomReal[]<prob,
			g=AddShortcut[g]
		]
	];

	g
]