Visualisation de 13 millions d’utilisateurs de Bluesky

 (joelgustafson.com)
1 points par GN⁺ 2024-11-14 | 1 commentaires | Partager sur WhatsApp
  • Grâce au flux public d’événements, il a été possible de construire sur Bluesky une carte complète du graphe social à l’échelle de 13 millions d’utilisateurs, ce qui serait difficile à réaliser avec Twitter
  • Le pipeline de collecte filtre uniquement les follows et unfollows depuis le firehose WebSocket de bsky.network et les stocke dans SQLite ; à l’époque, la table follows contenait plus de 500 millions de lignes et pesait environ 30 Go
  • Pour disposer 13 millions de nœuds et 500 millions d’arêtes, un moteur de force-directed layout multithread basé sur Zig, Andromeda, a été créé, mais les grands graphes sociaux ont révélé ses limites : les structures locales y sont écrasées
  • La combinaison des embeddings GGVec et d’UMAP permet d’obtenir davantage de structures intermédiaires ; le chevauchement des points d’UMAP est ensuite affiné en simulant quelques ticks supplémentaires avec Andromeda pour lisser les clusters denses
  • La carte finale affiche 7,7 millions de nœuds après filtrage au 7 novembre 2024, et permet d’explorer des anneaux de bots, des clusters par pays, ainsi que des groupes de comptes médias/politiques à grand nombre d’abonnés

Pourquoi une carte complète du réseau Bluesky était possible

  • Twitter ne donne pas accès à l’ensemble des données, et le scraping y est difficile, voire potentiellement illégal, ce qui rend une carte complète difficile à produire
  • BlueSky permet d’obtenir les données nécessaires et a fortement grandi pendant plusieurs mois en 2024
    • Cette croissance s’explique notamment par les conflits persistants entre Twitter et sa base d’utilisateurs, ainsi que par le blocage de Twitter au Brésil en octobre 2024
  • Le résultat peut être exploré sous forme de carte interactive sur aurora.ndimensional.xyz
    • Comme elle utilise WebGPU, Chrome/Chromium sur ordinateur de bureau est nécessaire

Méthode de collecte du graphe des abonnements

  • Pour réduire le périmètre du travail, seul le graphe des abonnements est utilisé au lieu de l’ensemble de l’activité
    • Chaque follow est traité comme une arête non orientée
    • Si deux comptes se suivent mutuellement, deux arêtes sont créées, ce qui revient en pratique à doubler le poids
  • BlueSky repose sur l’AT Protocol et est conçu pour permettre aux utilisateurs d’héberger leur propre PDS (personal data server)
  • La collecte effective utilise le firehose WebSocket du relais bsky.network, opéré par l’équipe BlueSky
    • Il agrège les événements du PDS principal *.bsky.social et des PDS indépendants ayant demandé l’indexation
    • Les événements de l’ensemble du réseau sont diffusés en temps réel, actuellement à environ 500 événements par seconde
    • Parmi eux, seuls les follows et unfollows sont filtrés puis stockés dans une base SQLite locale
  • Au départ, l’indexer était déployé sur fly.io et la base de données était répliquée en temps réel vers AWS S3 avec litestream, mais le coût de 40 dollars par mois a conduit à passer à un serveur domestique
    • Par la suite, le service a tourné sur un desktop System76 à domicile, avec une combinaison de services systemd, logrotate, un moniteur tmux et TailScale
  • Au moment de la rédaction, BlueSky dépassait 13 millions d’utilisateurs, et la table follows comptait plus de 500 millions de lignes, pour environ 30 Go d’espace disque

Le goulot d’étranglement du calcul pour un graphe de 13 millions de nœuds

  • Il existe plusieurs méthodes de layout de graphe, mais le point de départ ici est un force-directed layout, qui se comporte comme une simulation physique
    • Tous les nœuds exercent une force de répulsion les uns sur les autres
    • Les arêtes créent une force d’attraction entre la source et la cible
    • À chaque tick de simulation, la force nette de chaque nœud est calculée, mise à l’échelle par un paramètre de température, puis utilisée pour le déplacer
  • Le goulot d’étranglement tient moins à la taille du graphe elle-même qu’à la complexité de calcul du problème à N corps
    • Un algorithme naïf nécessite O(n^2) + O(e) par tick
    • À l’échelle de millions de nœuds, ce n’est pas réaliste, même sur GPU
  • Comme dans les moteurs de force-directed layout classiques, l’optimisation Barnes-Hut réduit cela à O(n log(n)) + O(e)
    • Cela se paie par une approximation de l’effet des nœuds lointains
    • La construction et les requêtes du quadtree étant hiérarchiques, il est difficile de calculer simplement les forces sur les nœuds via GPU
  • Pour paralléliser, le quadtree est divisé en 4 ou 16 parties, reconstruites en parallèle au début de chaque tick, puis la plage de nœuds est répartie entre les threads pour calculer les forces
    • La force nette de chaque nœud est la somme des forces apportées par chaque quadtree et par les arêtes entrantes et sortantes
    • Cela permet d’exploiter presque tout le CPU disponible avec très peu d’overhead

Andromeda et les limites de l’approche force-directed

  • Un moteur de graph layout force-directed multithread, Andromeda, a été créé en Zig, avec une GUI construite avec GTK4 et OpenGL
  • Andromeda est fortement influencé par Gephi et par l’article ForceAtlas2
    • Dans la visualisation de grands graphes, l’interactivité — voir le graphe évoluer et ajuster dynamiquement les paramètres de simulation — est importante
    • Il est difficile d’obtenir de bons résultats avec des outils opaques et aux itérations longues
  • Andromeda comporte aussi un widget d’interface appelé “natural slider”
    • Il vise à réduire la difficulté de connaître à l’avance la bonne plage de valeurs lorsqu’on travaille avec un nouveau graphe, une nouvelle version du moteur ou de nouveaux paramètres
    • Il ajuste dynamiquement la plage de valeurs par puissances de e
    • Les puissances de 2 ont été jugées trop petites et celles de 10 trop grandes
  • En appliquant un layout ForceAtlas2 au snapshot de 5 millions d’utilisateurs BlueSky de septembre 2024, la masse et la densité des grands clusters apparaissaient, mais l’ensemble restait fortement aggloméré
    • La plupart des nœuds étaient dispersés autour du supercluster dans une large zone difficile à distinguer
    • Seules quelques dizaines de petites communautés, principalement nationales, étaient nettement séparées
  • Lors de la publication d’une version à 2 millions de comptes en février 2024, la vue globale suscitait de l’intérêt, mais la vue locale était décevante
    • Il arrivait qu’un utilisateur trouve son propre compte sans reconnaître les comptes environnants
    • Il est difficile de capturer entièrement la structure de connexion d’un réseau complet avec un simple placement sur un plan 2D

UMAP, couleurs et carte finale

  • Un layout de graphe peut aussi être vu comme une réduction de dimension, c’est-à-dire comme le problème de projeter une matrice d’adjacence de 13 millions × 13 millions sur un plan 2D
  • t-SNE et UMAP sont de puissantes techniques non linéaires de réduction de dimension pour la visualisation 2D
    • Injecter directement la matrice BlueSky dans UMAP était trop lourd à l’échelle d’un serveur domestique
    • À la place, un embedding d’environ 32 dimensions est créé pour chaque utilisateur, puis le résultat est fourni à UMAP
  • L’outil open source d’embedding de nœuds nodevectors a été choisi, et l’algorithme non publié GGVec semblait offrir les meilleures performances parallèles sur de grands graphes
    • L’embedding du snapshot de 5 millions de nœuds de septembre 2024 a été généré en 5 minutes
    • La première image UMAP a été obtenue en 10 minutes supplémentaires
    • Elle faisait apparaître davantage de structures intermédiaires que le résultat aggloméré d’Andromeda
  • UMAP avait tendance à rendre certains clusters trop compacts, entraînant un chevauchement des points
    • C’est un comportement naturel pour un objectif de réduction de dimension pure, où des points identiques dans l’espace d’origine doivent rester au même endroit dans l’espace cible
    • Mais ce n’était pas adapté à une carte affichant les photos de profil des comptes à un niveau de zoom rapproché
  • En interne, UMAP utilise aussi, à la dernière étape, un force-directed layout sur un graphe pondéré des k plus proches voisins
    • Pour des raisons de contraintes de calcul, UMAP utilise de l’échantillonnage ; tous les nœuds ne se repoussent donc pas les uns les autres, même approximativement comme dans Barnes-Hut
    • Le paramètre min_dist a été jugé incapable de contrôler de manière cohérente la séparation des points sur de grands graphes
  • Le problème de chevauchement a été atténué en injectant la sortie d’UMAP dans Andromeda, puis en exécutant quelques ticks supplémentaires avec une équation de répulsion ajustée
    • Même dans les clusters denses, les nœuds remplissent l’espace sans se superposer en couches
    • Dans une prochaine version, l’objectif est d’accéder aux poids bruts du graphe généré par UMAP et de combiner directement le quadtree parallèle d’Andromeda avec les équations de force de l’article UMAP
  • Pour les couleurs, au lieu d’appliquer HDBScan au résultat UMAP, un clustering k-means est effectué dans l’espace d’embedding
    • Une hue est attribuée à chaque cluster
    • Chaque point interpole sa hue à partir des trois centres de cluster les plus proches
    • Par rapport à une coloration basée sur PCA, cela révèle mieux la structure locale et produit, de près, une texture tachetée semblable à un vitrail
  • La hue est un unique float entre 0 et 1, mappé en RGB via l’espace colorimétrique hsluv
    • La saturation de tous les nœuds reste constante
    • La luminosité est mise à l’échelle selon le log10 du nombre de followers de l’utilisateur, de sorte que les grands comptes apparaissent comme des étoiles brillantes et les comptes ayant peu de followers comme plus ternes
    • Le rendu consistant à agrandir réellement les grands comptes a été écarté, car il rendait les grands graphes excessivement complexes
  • Au 7 novembre 2024, la carte de l’ensemble du réseau comprend 7,7 millions de nœuds, après exclusion des comptes suivant plus de 50 000 comptes et de ceux qui suivent moins de 5 comptes tout en ayant moins de 5 followers
    • Des bandes nettes de comptes médias, politiques et de commentaire à grand nombre de followers se distinguent des groupes de fond apparentés mais plus petits
    • Le cluster islandais est également visible à distance, de près et jusqu’au niveau des photos de profil
    • Les anneaux de bots ressortent aussi clairement
  • Parmi les prochaines fonctionnalités envisagées figure l’ajout, dans une barre latérale repliable, de la timeline des publications des comptes actuellement visibles à l’écran
    • L’objectif est d’en faire un nouveau type d’outil d’exploration sociale et mémétique

À lire aussi

1 commentaires

 
GN⁺ 2024-11-14
Avis de Hacker News

  • Le feed BSKY donne vraiment l’impression d’être un espace mort. J’ai essayé de participer activement en publiant, en répondant, en likant, mais j’ai l’impression que rien ne prend
    Publier « pour moi-même » a aussi ses limites, et l’intérêt retombe vite. Au début de Twitter, tout le monde était enthousiaste à l’idée de suivre de nouvelles personnes ; pour un nouveau réseau social, on pourrait s’attendre à ce qu’il soit rempli de gens cherchant à créer de nouveaux liens

    • Le compte associé à ce handle suit très peu de monde et semble plutôt diffuser du contenu comme une émission que participer à des conversations. Il vaudrait mieux essayer l’inverse
    • En ce moment, sur BSKY, les Starter Packs créent un gros problème où les riches deviennent plus riches et les pauvres plus pauvres. Si l’on figure dans un Starter Pack créé par quelqu’un d’influent, on gagne gratuitement un nombre illimité d’abonnés, mais si l’on essaie de développer sa présence soi-même dès le départ, on est quasiment introuvable
    • Je me demande si tu as aussi essayé Mastodon. Beaucoup de gens y ont une meilleure expérience

  • Bluesky et atproto semblent avoir été conçus avec l’idée de les rendre hackables
    La communauté a récemment créé un annuaire permettant de rechercher les « Starter Packs » de Bluesky. Les Starter Packs sont une fonctionnalité qui publie des lots de personnes et de feeds susceptibles d’être suivis par les utilisateurs, afin d’aider les nouveaux venus à configurer rapidement leur expérience initiale
    https://blueskydirectory.com/starter-packs/all
    Dan Abramov a aussi apprécié cela aujourd’hui, en disant : « C’est génial que ce genre de chose soit possible dans l’écosystème. Laissons l’écosystème cuisiner » [1]
    Plus incisif encore, il a aussi écrit : « Quand je vois des projets arbitraires surgir dans l’écosystème atproto, je réalise à quel point les communs du Web public ont été étouffés quand les entreprises sociales ont fermé leurs API. Tout un paysage d’outils a été abandonné et laissé en friche » [2]
    [1] https://bsky.app/profile/danabra.mov/post/3lar3sdna222d
    [2] https://bsky.app/profile/danabra.mov/post/3lar3xpuu4c2d

    • J’hésitais à faire le pas, mais ce commentaire est celui qui me convainc le plus
      À mon avis, l’une des erreurs fatales commises par les entreprises tech a été de tout enfermer. Ce qui a rendu les ordinateurs et les smartphones formidables, c’est leur possibilité d’être hackés, et le fait de créer un environnement et un écosystème. Le verrouillage ne fait que ralentir les choses. Sans les apps, combien de temps aurait-il fallu pour que les smartphones intègrent une lampe torche ou un chronomètre ? Avant d’être intégrées aux systèmes d’exploitation, ces fonctions étaient des apps
    • Il me semble que Twitter avait aussi un peu cette caractéristique à l’origine. De mémoire, des fonctionnalités populaires aujourd’hui comme le retweet étaient au départ des conventions improvisées par les utilisateurs
    • Exact, cela a été conçu volontairement pour être hackable. Nous pensons que les réseaux sociaux deviennent meilleurs quand les gens ont la liberté de construire dessus, de modifier, de forker et de remixer. L’écosystème Bluesky et atproto peut évoluer aussi vite que les utilisateurs et les développeurs le souhaitent
    • Les Starter Packs sont excellents. Pourquoi ne pas regarder les comptes qui ont actuellement le plus d’interactions : https://www.graphtracks.com
    • À l’inverse, cela pourrait aussi mener à un problème de bots dix fois pire que sur Twitter

  • Bluesky semble avoir vraiment explosé la semaine dernière dans certains domaines. Depuis samedi, mon nombre d’abonnés a été multiplié par 5 ou 6
    J’y étais assez actif depuis un an, parce que les conversations sur Twitter dans le secteur de l’énergie, où je travaille, se sont tellement dégradées qu’elles sont devenues presque inutilisables. C’était agressif à plusieurs niveaux, et le spam était délirant. À l’inverse, Bluesky était détendu mais peu réactif ; maintenant, l’ambiance commence à chauffer. J’espère que cet afflux est réel, et il m’a donné envie de l’utiliser beaucoup plus activement

    • Mon X ne s’est pas trop dégradé. J’utilise beaucoup X en japonais, et c’est peut-être un autre écosystème. Cela dit, j’utilise aussi Bluesky depuis un an, et pendant un moment c’était un réseau sympa mais assez silencieux. Il arrivait qu’il n’y ait aucun nouveau post pendant environ une heure
      Ces trois dernières semaines, Bluesky est devenu beaucoup plus actif, et il ressemble désormais à X dans le sens où je n’arrive plus à suivre tout le feed. Je crois qu’une grande communauté apporte une plus grande diversité de points de vue, donc je suis très enthousiaste. J’exploite aussi moi-même un labeler Bluesky et un collecteur Firehose, et j’ai vu le volume d’événements traité à peu près doubler au cours des 3 à 4 derniers mois
    • Les spammeurs et les trolls arriveront bientôt aussi. Les endroits populaires ne restent pas longtemps tranquilles
    • Pour moi, tout est en train de trouver sa place
      Threads est un mélange moitié Twitter, moitié Instagram, fort sur les contenus de création, de voyage et sociaux, tandis que Bluesky ressemble davantage au Twitter des débuts, fort sur l’actualité, la politique et la science. Ces jours-ci, je ne suis plus très sûr qu’il soit possible de tout faire dans une seule app. X restera alors comme le nouveau 4chan
    • Mon expérience a été la même à tous les niveaux. Un afflux soudain, beaucoup de personnes intéressantes et pertinentes à suivre, et une expérience globale qui devient rapidement plus immersive
    • Je n’ai pas encore trouvé de comptes utilitaires sur Bluesky. Sur Twitter, je suivais des comptes pour obtenir des nouvelles sur les jeux, les studios et éditeurs de jeux, les sites d’actualité, les groupes, la NASA, etc. Sur Bluesky, il n’y a pas encore ça, et les inconnus ne m’intéressent pas. C’est pareil sur Twitter
      Je vérifie de temps en temps, mais en pratique, on est proche de 0/50

  • Je fais partie de la vague d’utilisateurs qui sont passés à Bluesky la semaine dernière. Jusqu’ici, j’aime vraiment beaucoup, et ça m’a un peu surpris, parce que Mastodon m’avait déçu à l’époque. Je passe déjà plus de temps sur Bluesky que sur Twitter.
    Pour expliquer à quelqu’un qui ne sait pas ce qu’est Bluesky : c’est pratiquement un clone de Twitter vers 2015, avec une UI presque identique. Sauf qu’il n’y a pas de monétisation, de publicité ni de growth hacking, donc les principales fonctionnalités existent au bénéfice des utilisateurs. Un exemple que j’aime bien : l’app mobile est une simple app Expo/React Native, et elle permet d’ouvrir les liens dans Safari au lieu d’un navigateur intégré inutile.

    • Comme Bluesky a reçu du financement VC, ce n’est probablement qu’une question de temps avant que la monétisation, la publicité et le growth hacking commencent. Autant en profiter d’ici là.
    • J’ai essayé, et la techno a l’air chouette, mais j’aimerais qu’il y ait des contenus plus variés. Maintenant que Twitter est surtout devenu un mélange d’arnaques aux cryptoactifs et de délires politiques de l’extrême droite américaine, j’aimerais quelque chose d’un peu plus intéressant que les délires politiques de l’extrême gauche américaine.
      Le monde est bien plus vaste que les États-Unis ou les dramas de l’Internet occidental. En tant qu’Européen, lire les réseaux sociaux grand public, y compris BlueSky, me fait lever les yeux au ciel. Je ne m’intéresse pas à la politique, à l’identité de genre ni à l’activisme de clavier. Est-ce qu’on ne pourrait pas mettre autre chose au menu ? Vraiment, n’importe quoi. J’en viens à me demander si je dois apprendre le russe ou le chinois pour être exposé à quelque chose de nouveau, autre que la politique américaine ou qui est attiré par quel genre dans sa vie privée. Qui s’en soucie ?
      Nostr était techniquement amusant, mais c’est dommage qu’il n’ait jamais vraiment dépassé le stade des crypto bros.
    • Si c’est « un clone de Twitter vers 2015, sans monétisation, publicité ni growth hacking, donc avec des fonctionnalités pensées pour les utilisateurs », alors c’est exactement Mastodon.
    • Je me demande comment ça se compare à Threads.

  • Plutôt impressionnant. L’API BlueSky est bien conçue. Un collègue a créé ce genre de visualisation à partir du Firehose : https://bigmood.blue/
    Source : https://bsky.app/profile/even.westvang.com/post/3laob7tefxk2...

  • Il est difficile d’exagérer à quel point j’aime ça. Le résultat final transmet non seulement plusieurs dimensions d’information, mais il est aussi très séduisant visuellement.
    Le grain produit par le rendu d’un nombre énorme de nœuds ajoute une sensation particulièrement agréable. C’est un élément qu’on voit rarement dans d’autres visualisations de graphes.

  • Le meilleur aspect de Bluesky, c’est qu’on peut utiliser un nom de domaine comme nom d’utilisateur. J’y utilise @bradgessler.com, et si les gens veulent me « vérifier », ils voient mon site web, ce qui est bien plus significatif qu’une coche bleue.
    Même si je suis bloqué, banni ou éjecté de la plateforme, les gens peuvent voir mon domaine, s’y rendre et vérifier ce qui s’est passé. D’une certaine façon, c’est une structure qui rend la censure visible. Je pense que c’est aussi très bien pour les entreprises. Appeler une entreprise via @example.com et recevoir une réponse est beaucoup moins ambigu. J’ai aussi créé un starter pack qui regroupe des SaaS basés sur Rails qui font déjà ça : https://go.bsky.app/JQyXa2u
    J’aime vraiment ce que fait BlueSky, et j’espère que ça ne se dégradera pas avec le temps. Même si ça finit par arriver, on dirait qu’on est en ce moment dans un moment Boucle d’or, avec une ambiance juste comme il faut. Créer un compte et le relier à son propre domaine prend cinq minutes, donc je le recommande vivement.

    • La vérification d’identité de Mastodon est elle aussi ouverte à tout le monde et fondée sur des standards du Web ouvert.
      https://joinmastodon.org/verification
    • L’adresse .bsky.social attribuée par défaut à l’inscription redirige aussi, par défaut, vers le profil sur bsky.app. Même quelqu’un qui ne sait absolument pas ce qu’est Bluesky peut ouvrir cette URL et voir directement le profil social, même avec le @.

  • Il est écrit : « Que se passe-t-il si l’on met la matrice BlueSky dans UMAP ? On ne peut pas vraiment le faire, du moins pas directement. UMAP accepte techniquement des matrices creuses, mais à cette échelle, c’est trop gros pour mon serveur domestique. À la place, on peut utiliser une autre technique pour extraire les embeddings de tous les utilisateurs dans une dimension intermédiaire, comme 32, puis donner ça à UMAP. Facile ! » ; je me demande exactement comment les embeddings ont été dérivés.

  • En lisant la phrase « la génération et l’interrogation d’un quadtree sont intrinsèquement hiérarchiques », j’ai été content de voir que je ne suis pas le seul à hésiter sur hierarchy.
    C’est un travail intéressant à plusieurs niveaux. Sans jeu de mots. Il y a beaucoup de choses à voir, depuis la disponibilité des données Bluesky jusqu’au traitement et aux algorithmes de visualisation. Cela dit, il est un peu difficile de savoir où placer ce type de visualisation sur le spectre de la science des données. Les graphiques numériques traditionnels ont développé au fil du temps une grammaire assez sophistiquée, qui permet des inférences et des interprétations relativement précises. C’est pourquoi ils sont beaucoup utilisés pour transmettre réellement de l’information, dans les articles scientifiques, la finance, etc., et les gens vont même jusqu’à rétro-ingénierer des graphes pour reconstituer les données.
    Avec les réseaux et les graphes, en dehors d’une impression générale de topologie, de connectivité et de clusters, il est assez difficile de dire précisément quelle information est transmise. Je ne sais pas si une grammaire utile pour traiter ce genre de graphe à grande échelle n’a pas encore été inventée, ou si c’est simplement dans leur nature.

  • J’aimerais examiner ces données davantage sous l’angle du traitement automatique du langage naturel. Ce serait intéressant de voir, comme avec Google Trends, quels sujets de discours apparaissent régulièrement et ce qui connaît des pics sur une période donnée.
    Peut-on résumer ce dont discutent les économistes ? Je me demande aussi s’il serait possible de trouver des gens qui ne sont pas dans les réseaux les uns des autres, mais qui parlent de la même chose.