Force-Directed Graph

PID_00233252

Autor: Álex GonzálezCoordinació: Julià Minguillón

Introducció

El Force-Directed Graph és un tipus de visualització orientat a representar les relacions entre entitats mitjançant un graf. Cadascun dels nodes del graf és una entitat i cada aresta (línia) indica que hi ha una relació entre dos dels nodes o entitats i, opcionalment, la intensitat d'aquesta. La idea subjacent és utilitzar un model de forces en què es recalculan iterativament les posicions dels nodes en funció de la influència dels altres, combinant atracció i repulsió. Després d'n iteracions, el sistema s'estabilitza i mostra la posició més estable trobada durant el procés. D'aquesta manera es revelen estructures com comunitats, els nodes més importants (centrals, hubs...), entre d'altres.

Es poden assignar diferents grandàries, colors i etiquetes als nodes en funció d'algun atribut per a mostrar grups i/o la seva importància relativa. També és possible activar la funcionalitat d'arrossegar un dels nodes (i amb això tot el graf), però no és una cosa que tingui molta aplicació en l'anàlisi.

Aquest exemple, de Mike Bostock, mostra un graf de xarxa que representa les relacions entre els diferents personatges de l'obra de Victor Hugo Els miserables. Cada node representa un personatge i la línia que uneix dos personatges indica que aquests personatges estan relacionats per aparicions simultànies en l'obra. El color de cada node es correspon amb el capítol en el qual apareixen. El gruix de cada aresta mostra el volum d'aparicions simultànies dels dos personatges.

Exemple: xarxa de m'agrades entre fanpages de la UOC

La visualització següent mostra com usar force-directed per a visualitzar la xarxa de relacions entre un conjunt d'entitats, en aquest cas fanpages de Facebook, que han fet m'agrada en la fanpage de la UOC o viceversa.

Els atributs de què es disposa per cada fanpage són els següents:

username: el nom «curt» de la pàgina
id: ID únic intern de Facebook per a la pàgina
label: nom de la pàgina
category: categoria a la qual pertany la pàgina
fan_count: nombre de «likes» de la pàgina
talking_about_count: mètrica d'audiència que ofereix Facebook
link: enllaç a la pàgina

Funcionament

Per a cada entitat (fanpages de Facebook en aquest cas) es dibuixa un node; i per a cada relació entre nodes, una línia. En aquest cas en particular, la relació de m'agrada entre pàgines solament pot donar-se una vegada, i, per tant, no hi ha variació en l'ample dels enllaços. L'algorisme calcula de manera iterativa la posició més estable del graf tenint en compte les forces d'atracció (nodes enllaçats) i repulsió (nodes no enllaçats). Es poden establir diversos paràmetres per a adaptar el procés de càlcul, i per tant l'estructura final, al dataset que es vol visualitzar. Per exemple, es podrien definir la distància mínima entre nodes, la força de repulsió...

Es mostra la grandària del node, com el nombre de fans de cada pàgina i el color segons el tipus d'entitat, entre els següents: Arts/Humanities Website, Community, Education, Local Business, Non-Profit Organization, Sports Event, Teacher, TV Show i University.

Finalment, mantenint el punter sobre un node, es mostra un «title» amb el nom abreujat de la pàgina. Els nodes poden ser arrossegats un a un per ressituar-los, movent automàticament els enllaços a altres nodes.

Anàlisi mitjançant la visualització

La visualització mostra algunes de les característiques del graf, com la presència de comunitats i els nodes que ocupen posicions més centrals o bé que connecten diferents comunitats (anomenats concentradors). Encara que la posició absoluta realment no importa (el mateix graf podria representar-se intercanviant esquerra i dreta, per exemple), sí és fonamental la relativa, que dona importància a la proximitat o llunyania entre nodes.

En concret, es pot observar la presència de grups d'entitats fortament enllaçades entre elles, mentre que hi ha entitats que no estan enllaçades amb cap altra (a causa del filtre portat a terme per poder representar el graf de manera adequada).

Limitacions

Al contrari que en el cas del diagrama Chord, un elevat nombre d'entitats (nodes) o relacions (enllaços) no comportaria un problema a l'hora d'interpretar el graf excepte si el nombre d'enllaços és excessiu.

Encara que el detall de cada entitat pot ser complicat de mostrar, en ser un gràfic orientat a mostrar comunitats o grups d'entitats relacionades la lectura general no és un problema.

Detalls tècnics (how to?)

Aquesta visualització consisteix en una pàgina HTML (enllaç) que incorpora codi D3.js i pot ser utilitzada com a base per a reproduir-la usant qualsevol altre conjunt de dades.

És necessari disposar de la llibreria d3.v4.min.js (v4, descarregable també des de D3.js), la qual ha d'estar en el mateix directori de treball que la pàgina web esmentada en el subdirectori «js».

El fitxer usat en aquest exemple pot descarregar-se des d'aquest enllaç. Es recomana utilitzar alguna eina d'edició de fitxers JSON (per exemple, aquest) per a manipular-los.

El fitxer parallel-sets_base.html que conté el codi D3.js pot ser modificat per a reutilitzar la visualització amb altres fitxers JSON, de la manera següent:

Les línies
```
var force = d3.forceSimulation()
            .alphaTarget(0.1);

force.force(d3.forceLink())
```
instancien el layout i li especifiquen el tipus de forces per aplicar en els càlculs, indicant que l'objectiu per al factor de moviment no és zero, per la qual cosa el graf es mourà lentament una vegada estabilitzat.
La línia
```
d3.json("./data/redFBUOC_2level.json", function(error, graph) {
```
és la que carrega el fitxer JSON per alimentar la visualització.
Les línies
```
  var linksForce = d3.forceLink(graph.links)
      .distance(100);


  force
      .nodes(graph.nodes)
      .force("link", linksForce)
      .force("charge", d3.forceManyBody().strength(-1000))
      .force("x", d3.forceX())
      .force("i", d3.forceY())

  force.restart();
```
estableixen alguns paràmetres tant del comportament dels enllaços com del layout en general: en aquest cas, primer la longitud dels enllaços, i en el segon grup d'instruccions la «càrrega de repulsió» entre nodes no connectats i les forces que controlaran el desenvolupament dels càlculs en l'eix X i Y. Finalment s'«arrenca» l'algorisme.

Finalment, les línies:

  force.on("tick", function() {
    link.attr("x1", function(d) { return (width/2)+d.source.x; })
        .attr("i1", function(d) { return (height/2)+d.source.i; })
        .attr("x2", function(d) { return (width/2)+d.target.x; })
        .attr("i2", function(d) { return (height/2)+d.target.i; });
    node.attr("cx", function(d) { return (width/2)+d.x; })
        .attr("cy", function(d) { return (height/2)+d.i; });
  });

són les que defineixen la posició tant de nodes com d'enllaços en cada pas del procés de càlcul. Podríem dibuixar-ho tot al final dels càlculs, però així generem la xarxa mostrant els moviments.

Exercici

Es planteja repetir l'exemple utilitzant un altre fitxer JSON que tingui el format adequat, comprovant què succeeix amb la visualització quan el nombre de nodes i enllaços mostrats és molt elevat (p. ex., més de 1.000 o 10.000).

Referències

Aquesta pàgina ha estat creada a partir del treball de Mike Bostock.
Funcionalitat basada en els treballs de Tim Dwyer i Thomas Jakobsen.
Network Diagram en el Data Visualization Catalogue.

Materials creats per Álex González (outliers) i Julià Minguillón, publicats amb una llicència Creative Commons CC-BY-SA 3.0, Universitat Oberta de Catalunya (FUOC), 2016.