Développement de wotmap

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.

1 Like

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.

2 Likes

@Paidge 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:

4 Likes

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…

@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.

2 Likes

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.

6 Likes

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

1 Like

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.

2 Likes

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

2 Likes

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

3 Likes

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 !

3 Likes

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:

3 Likes

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.

6 Likes

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

3 Likes

On peut aller bien plus loin dans l’analyse, ces images révèles quantités passionnantes d’information : notamment la forme d’une communauté nous révèle les comportement de certification des membres de cette communauté et donc le respect plus ou moins bon de la licence Ğ1 :

Les communautés de forme ronde ou ellipsoïdale de faible excentricité respectent bien la licence Ğ1.

Plus l’excentricité de l’ellipse circonscrite a la communauté est élevée et moins la licence Ğ1 est correctement appliquée : notamment les communautés très allongés ne certifie quasiment que des nouveaux et ne se certifient pas assez entre-elles, la règle de distance finie par bloquer ces communautés la.

Une attaque sybil se visualiserai comme une communauté a excentricité très très élevée, donc très allongée, presque un trait.

Actuellement il y a 3 communautés dont la forme est douteuse, je les est encercler sur cette image :

Je vais contacter les gens de Lodève (en violet), j’ai l’impression qu’il ont besoin d’un rappel a la Licence Ğ1 :sweat_smile:

Concernant les 2 autres communautés encercler je n’ai reconnu personne, vous voyez qui c’est ? Si vous voyez qui c’est ce serait bien de les contacter.

A l’inverse les communautés les plus denses et rondes sont la Mayenne et la Bretagne, avec beaucoup de certifs internes, des exemples a suivre :grinning:

6 Likes

Je suis en train de voir pour rajouter des fonctionnalités dans la wotmap. Malheureusement, webGL ne m’offre pas bcp de flexibilité pour arriver à faire ce que je veux (à moins que je me forme à webGL ou que j’attende la v2 de SigmaJS qui risque de se faire attendre). C’est pourquoi, j’ai déployé ce matin une version de dev qui utilise canvas au lieu de WebGL.

Les fonctionnalités sont les suivantes :

  • Nouveau format des liens (certifications) : les liens sont courbés et fléchés pour bien voir le sens des certifications
  • Nouveau format des noeuds : ils possèdent dorénavant une bordure pour bien les distinguer.
  • Recherche de membres grâce à une liste déroulante : la caméra se place sur le membre puis zoome dessus en affichant les liens avec ses voisins directs
  • Affichage ou non des liens (pour afficher l’ensemble des liens, il vaut mieux attendre que la position des nœuds se stabilise, sinon le navigateur rame un peu)
  • Coloration des liens lors de la détection de communautés

Voici le lien de dev : https://duniter.normandie-libre.fr/wotmaptest/

N’hésitez pas à me remonter vos remarques

Si tu veux repasser à du webgl, quelques propositions :

Si tu sais faire des disques en webgl mais pas leur ajouter une bordure : Un disque plus large derrière un premier disque te donne le même rendu visuel.

Si faire des liens courbé en webgl est le problème, tu peux faire des liens droits, mais décentré exemple :
liens-directionnels
Si c’est le calcul de la position de la flèche en fonction du diamètre du cercle cible… C’est un peu chiant à faire manuellement je te l’accorde, mais voici comment j’ai procédé dans mycelia (et donc Gvu) staticApp/graph.js · master · mycelia / mycelia-front-app · GitLab sans garantie que ce soit transposable facilement en webgl.

EDIT :
Autre option pour distinguer les double lien des liens uni-directionnel (mais moins efficace pour identifier le sens, sauf à avoir une couleur différent selon le sens, en vu centré sur un noeud uniquement :
liens-directionnels

1 Like

SigmaJS permet de mettre des images sur les noeuds du graphe. Il serait donc possible d’interroger un noeud Cesium+ pour récupérer les photos des membres. Par contre, on avait essayé d’installer duniter4j sur mon serveur avec @Benoit_Lavenier mais nous ne sommes pas allés jusqu’au bout. Est-ce que je peux interroger un noeud distant ou je suis obligé de finir l’installation/configuration sur mon serveur ?

4 Likes

Ca devient carrément artistique la wot la :smiley:

Sinon, je pense que tu ferais plaisir à @kimamila en faisant l’effort d’installer ton propre noeud ES :wink: Quitte à ce que tu poses des questions sur le forum lorsque tu bloques. Ca enrichira tout le monde :slight_smile:

EDIT : la doc est là http://doc.e-is.pro/duniter4j/

1 Like

Plusieurs choses :

  • j’ai maintenant une image docker qui fonctionne pour lancer une noeud Cesium+. Attends quand même que @1000i100 (ou un autre dev) regarde si ca marche bien. Les lignes de commande docker sont en entête de fichier.
  • Si tu veux taper sur les noeuds existants, tu peux prendre par exemple celui du Sou (moins sollicité que celui de duniter.fr) : https://g1.data.le-sou.org/user/profile/PUBKEY/_image/avatar.png (exemple ici)
4 Likes