Développement de wotmap

wotmap
graph
sigmajs

#1

Salut tout le monde,
Comme certains le savent déjà, je travaille depuis qqes tps sur Wotmap, une visualisation/exploration de la toile de confiance en mode graphique sur le web grâce à SigmaJS (auparavant D3JS).

Je crée donc ce topic pour y regrouper toutes les discussions autour de ce projet.


Renaissance animation toile de confiance de framasky
#2

Aujourd’hui, j’ai réussi à écrire un script en PHP qui interroge ma BDD duniter locale et que je compte lancer en CRON toutes les 24h sur mon nœud Duniter afin de mettre à jour les données de la wotmap. Mais, auparavant, je rajoutais une étape en passant par Cytoscape pour calculer la Betweenness centrality et pré-positionner les nœuds du graphe en fonction. Du coup, sans cette étape de pré-positionnement, les nœuds ne sont pas disposés de la même manière (ce n’est pas une simple rotation/transformation mais bien des emplacements différents des nœuds). N’étant pas un spécialiste des graphes et des théories qui tournent autour, je me demande si cela a un impact sur l’analyse de la toile de confiance.


#3

Bonjour, et bravo pour ton travail vraiment sympa à utiliser !
Il n’y a pas dans les graphes de notions topographiques au sens où on peut l’entendre sur une carte. Les données ne représentent pas des positions géographiques. Même si sur l’image les noeuds sont à des emplacements différents, on repère tout de même des zones représentant les groupes locaux. Par exemple, on voit le groupe de Lodève en haut à gauche alors qu’il était en bas à droite, mais les relations entre les membres restent identiques.
Par contre, ce qui risque de perturber “l’analyse”, c’est si les positions sont instables d’une fois sur l’autre, il faudra surveiller ça. On se fait des repères visuels, et s’ils changent trop souvent il sera plus difficile de les retrouver. S’il est possible d’automatiser l’utilisation de Cytoscape, et que ça stabilise les représentations, ça pourrait être intéressant.


#4

@Pierre_Jean_CHANCELL c’est clairement mieux avec Cytoscape, et les résulats avec Cytoscape sembles identiques aux résultats qu’avais obtenu @1000i100 avec Gephi : https://g1.1000i100.fr/TdC.svg
Ce qui signifie que c’est les mêmes algo de positionnement qui sont derrière.
Je ne sais pas précisément comment sont déterminer les positions une fois la Betweenness centrality connue pour chaque nœud mais je sais comment calculer cette Betweenness centrality (centralité d’intermédiarité en français).
Dans un avenir proche (quelques mois ?), dans le cadre de g1-monit v2 je proposerai une API permettant de récupérer la Betweenness centrality de chaque membre sur demande et ceux avec réponse instantannée (pas de calcul a l’appel), je t’en dirai plus quand j’aurais avancé, j’esspère que ça nous permettra d’avoir un jours une visualisation temps réel et bien positionnée :slight_smile:


#6

je crois que c’est possible. J’ai cru voir qu’on pouvait l’attaquer en ligne de commande via une API…A étudier. Pas sûr d’y arriver. Sinon, je pensais le calculer via une implémentation PHP. Dans tous les cas, a priori, si j’utilise toujours le même script pour mettre à jour les données, les nœuds devraient se retrouver à la même place d’une fois à l’autre…


#7

@elois

  1. J’importe les données générées par mon script PHP dans Cytoscape Desktop.
  2. Puis grâce à une fonctionnalité du menu, intégrée dans le soft, il calcule en moins de 2 plein de stats dont la centralité d’intermédiarité.
  3. Ensuite, Cytoscape Desktop permet de positionner les nœuds en fonction de différents algorithmes (il y en a un sacré paquet, je crois que je choisis un force layout mais je ne suis plus très sûr) qu’il est possible de baser sur un ou plusieurs paramètres, dont ceux précédemment calculés grâce aux stats.
  4. Enfin, grâce à un plugin, j’exporte le tout pour D3JS, y compris les coordonnées x et y de chaque noeud calculé par Cytoscape. En tous cas, à aucun moment dans mon code javascript pour D3JS je n’utilise cette centralité d’intermédiarité (j’utilise le nbre de voisins directs).

Donc la toile de la wotmap se forme en fonction des points de départ des nœuds et du nbre de voisins directs. Le pré-positionnement de Cytoscape permet d’avoir un affichage qui met plus en évidende cette centralité, à mon avis.


#8

J’ai implémenté le calcul de la Betweenness centrality avec l’algorithme d’Ulrik Brandes. C’est sacrément rapide ! Avec la toile de confiance actuelle (963 membres), j’obtiens un temps de calcul de 0,5 s au lieu de 12 s avec l’algorithme basé sur la définition actuelle de la centralité. C’est 24 fois mieux.


Un algorithme rapide pour le calcul de la centralité
#9

Super, peut tu m’indiquer a quel endroit est le code ?

De notre coté on a implémenté le calcul en Rust, je n’ai pas encore mesurer combien de temps ça prend mais je testerai ça dés que l’on aura un nœud rust synchronisé : on se base sur la méthode find_paths qui est ici : https://git.duniter.org/nodes/rust/duniter-rs/blob/43-refractor-wotb-to-have-separate-traits-for-wot-memory-layout-and-wot-calculations/wotb/operations/path.rs


#11

En discutant avec les enseignants-chercheurs de l’Université où je travaille (mathématiciens/informaticiens travaillant sur GraphStreamProject), la position finale des nœuds est déterminée par les forces d’attractions (des liens) et de repoussements (des nœuds) paramétrées dans D3JS, mais aussi par leur position initiale (que je détermine actuellement par un pré-calcul des positions [x,y] dans cytoscape. Ce calcul des positions étant lié à la EdgeBetweenness, elle-même calculée par Cytoscape). Pour le moment, je vais donc déployer une version de test de la wotmap pour, au moins, implémenter la tâche CRON qui récupèrera les données de la BDD locale de duniter toutes les 24h. Pour la centralité, je verrai après…Mais j’ai quand même regardé : Cytoscape peut être utilisé avec une API REST. Ce qui m’a l’air très intéressant pour la suite. En effet Cytoscape me calcule tout un tas de stats en moins d’une seconde : EdgeBetweenness, ClosenessCentrality, Eccentricity, Outdegree, PartnerOfMultiEdgedNodePairs, ClusteringCoefficient, Stress, BetweennessCentrality, EdgeCount, Indegree, AverageShortestPathLength, NeighborhoodConnectivity, etc.


#12

La mise à jour des données est effectuée toutes les 24h, à 03h30 (je pense que c’est l’heure locale UNIX mais j’y connais pas grand chose ^^). Les données sont accessibles ici si vous le souhaitez : https://duniter.normandie-libre.fr/wotmap/data/wot.json


#13

J’ai regardé en diagonale votre algorithme, je ne maîtrise pas encore trop bien Rust. Il me semble que ça ressemble un peu à ce que j’avais déjà écrit. Je pense que ce nouvel algo devrait être plus rapide.


#14

D’après mes collègues, je ferais mieux d’utiliser SigmaJS qui est plus adapté aux graphes. Alors que D3JS est plus générique (data vizualisation : courbes, histogrammes, nuages de points…). Donc, prochainement j’essaierai d’adapter mon code pour SigmaJS. Ce serait l’équivalent de Gephi en javascript


#15

J’appui dans ce sens. Techniquement, SigmaJs m’a l’air bien plus :

  • spécialisé graph
  • capable de gérer avec fluidité des graphe de grande taille

en revanche, j’ai l’impression qu’il est plus difficile d’interagir avec le graph qu’avec D3js (je n’ai pas vu de visualisation très dynamique en sigma (avec des noeud qui se groupe au dézoom, des fiche à la sélection de noeud, des placement personnalisable…) mais pour de la visualisation de la WOT, ça me semble l’outil web idéal en effet !


#16

J’ai commencé à étudier SigmaJS. A priori c’est possible grâce aux plugins fournis dans le code source. A priori, il serait assez facile de faire aussi ses propres plugins. Il y a d’ailleurs plein d’exemples de fournis ! Les possibilités sont bien plus importantes qu’avec D3JS c’est évident. On m’a dit aussi qu’il serait sûrement possible de faire de la “détection de communautés”. C’est-à-dire, identifier les différents ensemble de nœuds qui seraient “proches” dans la wot. Ce qui permettrait d’identifier les “groupes locaux” apr exemple. De plus, je viens d’afficher les noeuds et les links de la wot duniter grâce à SigmaJS et ça rame carrément moins dans le navigateur (sûrement grâce à WebGL) Bref, ça me semble aussi l’outil idéal en effet :wink:


#18

Suite à la présentation que j’ai réalisée lors des RML11 sur D3JS et SigmaJS (voir doc de présentation), certains (dont @cgeek) avaient demandé que je mette en ligne la version SigmaJS. C’est désormais chose faite sur ce lien. De plus, j’ai rajouté la possibilité de n’afficher qu’un noeud et ses voisins en cliquant dessus. Et les données sont aussi mises à jour toutes les 24H.
J’ai commencé à regarder ce qui se faisait sous SigmaJS concernant les détections de communautés (algorithme Louvain), mais je n’ai pas encore trouvé de solutions… Je continue de chercher.


#20

@Moul nous signale que la WoT affichée avec SigmaJS peut faire planter votre machine.

Si c’est le cas, soit c’est un pb lié à la carte graphique (SigmaJS utilise WebGL) soit le navigateur ne supporte pas WebGL et SigmaJS passe automatiquement en SVG (là les navigateurs ont du mal à supporter la charge parfois)


#26

La page ne se charge plus et l’activité cpu est a zéro donc j’ai penser qu’il ne se passait rien, bizarrement il faut que je le laisse l’onglet ouvert et que je switche sur un autre onglet pour que ça se lance \o/


#27

Désormais vous pouvez faire de la détection de communauté avec l’algo de Louvain :https://duniter.normandie-libre.fr/wotmap2


#29

En essayant de l’orienter avec la carte :


#34

En fait nous ne formons pas des communautés, c’est plutôt que nous sommes des membres a la jonction de plusieurs communautés. Tu me dira que Benoît aussi mais non, il appartient clairement a la communauté de Mayenne, même s’il fait le pont avec d’autres communautés.

Le fait que cgeek et moi soyons a part peu s’expliquer par notre faible intégration dans nos communautés locales respectives (Montpel et Rennes). Nous sommes d’avantage en lien avec le reste de la toile qu’avec notre groupe local, alors que Benoit est bien ancré dans son groupe local.

Quand a toi moul bah tu est trop loin de tout le monde donc tu n’appartient a aucune communauté, moul reviiieeens !