Q

Non si prosegua l'azione secondo un piano.

Categoria: ciència i divulgació

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 g_{\le n} és una parella de conjunts g_{\le n} = \{V,E\}, on V és el conjunt de n nodes (n=|V|) i E és el conjunt d’hiperarestes (subconjunts de V diferents del conjunt buit): E=\{e_k=\{v_1,\dots,v_k\}:v_i\in V \land 1\le k\le n\}. Un hipergraph és k-uniforme (i escrivim g_k) si totes les seves hiperarestes tenen exactament k elements. És a dir, E=E_k=\{e_k=\{v_1,\dots,v_k\}:v_i\in V\}. Amb aquestes definicions un graf normal i corrent és un hipergraf 2-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}}:

HypergraphPlotHighlight

Llegeix la resta d’aquesta entrada »

Contra la contraciència

LaContraLVFa poc menys d’un any comentava la promoció de la pseudociència que fa La Contra de La Vanguardia. Algunes de les seves perles les podeu trobar en aquest recull d’entrevistes (que fa temps que no actualitzo, si en teniu de noves passeu-me-les!). Amb amics i companys de feina comentàvem sovint la possibilitat, o més aviat la necessitat, d’escriure’ls una carta de queixa, perquè hi va haver moments en què va arribar a ser intolerable.

Doncs bé, l’altre dia vaig veure que, amb d’altres entitats, l’Associació Catalana de Comunicació Científica havia escrit una carta (pdf) al defensor del lector de La Vanguardia que criticava aquesta manca no només de rigor científic sinó també d’ètica periodística, que hauria de posar en dubte aquest tipus de declaracions. La carta anava acompanyada d’unes 1000 adhesions. La resposta de Josep Rovirosa, el dit defensor del lector, es pot llegir aquí. Llegiu-la vosaltres mateixos i jutgeu-la.

Com a únic comentari, trobo preocupant aquesta tendència general a defensar la “llibertat d’opinió” sense posar en dubte i exigir explicacions convincents de les declaracions que fa l’entrevistat de torn. Això no és un problema limitat a l’àmbit de la ciència (o més ben dit, pseudociència o contraciència), sinó àmpliament estès i amb especial incidència en les “notícies” sobre “política”, que no fan sinó limitar-se a reproduir les opinions del “polític” que en aquell moment ha tingut ganes d’obrir la boca. Per agafar un exemple recent, m’és indiferent que en Duran i Lleida “opini públicament” que el seu partit no és culpable de finançament il·legal. El que és important, i hauria de ser notícia, és que la sentència judicial així ho declara (i, a més, el propi partit ho accepta com a cert).

Vectors linealment independents

Ecco una petita funció del Mathematica per obtenir ràpidament una llista dels primers vectors linealment independents d’una certa llista de vectors, per si a algú li pot ser útil (si ja existia alguna cosa similar, digueu-m’ho als comentaris!).

Un conjunt de n vectors \{v_1,\ldots,v_n\} és linealment independent si i només si el rang de la matriu M=(v_1\dots v_n) és n. La següent funció, doncs, retorna la llista dels primers vectors linealment independents a partir d’una llista qualsevol de vectors:

FirstLinearlyIndependent[vec_List] := Module[
  {a = {}, i = 1, n = Length[vec]},

  While[i <= n,
   If[
    MatrixRank[Append[a, vec[[i]]]] == Length[a] + 1,
    a = Append[a, vec[[i]]]
    ];
   i++;
   ];
  a
  ]

Aaron Swartz

De l’Arnau llegeixo del suïcidi de l’Aaron Swartz, copropietari de Reddit, inventor del RSS 1.0 i que fa cosa de dos anys va agafar un portàtil, el va posar a un armari del MIT i el va connectar a la seva xarxa, descarregant-se així un bon grapat d’articles acadèmics de JSTOR i aparentment posar-los en circulació. Tot com a forma de desobediència civil per defensar l’accés lliure a la ciència i al coneixement. S’enfrontava ara a una pena de 35 anys de presó, i a uns costos del judici d’un milió de dòlars. Totalment desproporcionat, oi? Ara JSTOR diu això.

El que és més interessant és el que diu, per exemple, Alex Stamos, The Truth about Aaron Swartz “Crime”, Lawrence Lessig, Prosecutor as bully, Scott Aaronson, o Glenn Greenwald a The Guardian. També hi hagut tot de gent que via twitter i #PDFtribute han penjat els pdfs dels seus articles online. Jo ja ho faig sistemàticament, animeu-vos vosaltres també a fer-ho.

Distribució d’entrellaçament en xarxes complexes quàntiques

El proper dilluns 5 de novembre, a les 10:30, a la Sala de Graus II de la Facultat de Ciències de la Universitat Autònoma de Barcelona, defensaré la tesi “Entanglement distribution in quantum complex networks”. Hi esteu tots convidats! (La imatge forma part del disseny de la portada que ha fet la Judit Armengol.)

Aquesta tesi tracta l’estudi de xarxes quàntiques amb una estructura complexa, les implicacions que aquesta estructura té en la distribució d’entrellaçament i com el seu funcionament pot ser millorat mitjançant operacions en el règim quàntic. Primer considerem xarxes complexes d’estats bipartits, tant purs com mescla, i estudiem la distribució d’entrellaçament a llargues distàncies. Després passem a analitzar xarxes de canals sorollosos i estudiem la creació i distribució de grans estats multipartits.

El treball contingut en aquesta tesi està motivat principalment per la idea que la interacció entre la informació quàntica i les xarxes complexes pot donar lloc a una nova comprensió i caracterització dels sistemes naturals. Les xarxes complexes tenen una importància particular en les infraestructures de comunicació, ja que la majoria de xarxes de telecomunicació tenen una estructura complexa. En el cas de xarxes quàntiques, que són el marc necessari per al processament distribuït d’informació i comunicació quàntica, és ben possible que en el futur adquireixin una topologia complexa semblant a la de les xarxes existents, o que fins i tot es desenvolupin mètodes per a utilitzar les infraestructures actuals en el règim quàntic.

Una tasca central en les xarxes quàntiques és dissenyar estratègies per distribuir entrellaçament entre els seus nodes. En la primera part d’aquesta tesi, considerem la distribució d’entrellaçament bipartit com un procés de percolació d’entrellaçament en una xarxa complexa. Des d’aquest enfocament, s’estableix entrellaçament perfecte de manera probabilística entre dos nodes arbitraris. Veiem que, per a xarxes grans, la probabilitat d’aconseguir-ho és una constant estrictament major que zero (i independent de la mida de la xarxa) si la quantitat inicial d’entrellaçament està per sobre d’un cert valor crític. La mecànica quàntica ofereix aquí la possibilitat de canviar l’estructura de la xarxa sense necessitat d’establir nous canals “físics”. Mitjançant una transformació local adequada de la xarxa, es pot disminuir l’entrellaçament crític i augmentar la probabilitat. Apliquem aquesta transformació a models de xarxes complexes amb una distribució de graus arbitrària.

En el cas de xarxes sorolloses d’estats mescla, veiem que per algunes classes d’estat es pot utilitzar el mateix enfocament de percolació d’entrellaçament. Per a estats mescla generals considerem una percolació de llargada de camí limitada per la quantitat de soroll de les connexions. Veiem com les xarxes complexes ofereixen encara un gran avantatge en la probabilitat de connectar dos nodes.

En la segona part, passem a l’escenari multipartit. Estudiem la creació i distribució d’estats graf amb una estructura que imita la de la xarxa de comuicació subjacent. En aquest cas, utilitzem una xarxa complexa arbitrària amb canals sorollosos, i considerem que les operacions i mesures són també sorolloses. Proposem un mètode eficient per a distribuir i purificar petits subgrafs, que després es fusionen per a reproduir l’estat desitjat. Comparem aquest enfocament amb dos protocols bipartits basats en un node central i coneixement complet de l’estructura de la xarxa. Mostrem que la fidelitat dels estats graf generats es pot escriure com la funció de partició d’un sistema desordenat de spins clàssics (un vidre de spins), i la seva taxa de decaïment és l’anàleg de l’energia lliure. Utilitzant els tres protocols en una xarxa unidimensional i en xarxes complexes veiem que són tots comparables, i que en alguns casos el protocol de subgrafs proposat, que necessita només informació local de la xarxa, té inclús un comportament millor.

Follow

Get every new post delivered to your Inbox.

Join 159 other followers