Blueskyの1,300万ユーザーを可視化
(joelgustafson.com)- 公開イベントストリームのおかげで、Twitterでは作りにくいソーシャルグラフ全体の地図を、Blueskyでは1,300万ユーザー規模で構築できた
- 収集パイプラインは
bsky.networkのWebSocket firehoseからフォロー・アンフォローだけを抽出してSQLiteに保存し、当時のfollowsテーブルは5億行超・約30GBだった - 1,300万ノードと5億エッジを配置するために、Zigベースのマルチスレッドforce-directed layoutエンジン Andromeda を作ったが、大規模ソーシャルグラフでは局所構造が潰れてしまう限界が見えてきた
- GGVec埋め込みとUMAPを組み合わせて、より多くの中間構造を得て、UMAPの点の重なりは Andromeda で数ティック追加シミュレーションして高密度クラスタを整えた
- 最終的な地図は2024年11月7日時点でフィルタリング後の770万ノードを表示し、ボットリング・国別クラスタ・高フォロワーのメディア/政策アカウント群を探索できる
Blueskyのネットワーク全体マップが可能だった理由
- Twitterは全データを利用できず、スクレイピングも難しく違法となる可能性があるため、全体マップを作りにくい
- BlueSkyでは必要なデータを取得でき、2024年の数か月で大きく成長した
- 成長の背景には、Twitterとユーザー基盤の継続的な対立や、2024年10月のブラジルにおけるTwitter遮断がある
- 成果物は aurora.ndimensional.xyz でインタラクティブな地図として探索できる
- WebGPUを使うため、デスクトップ版のChrome/Chromiumが必要
フォローグラフの収集方法
- 全活動ではなくフォローグラフだけを使って作業範囲を絞った
- 各フォローは無向エッジ1本として扱う
- 相互フォローなら2本のエッジが生じ、実質的に重みが2倍になる
- BlueSkyは AT Protocol ベースで、ユーザーが自分のPDS（personal data server）を自前でホストできるよう設計されている
- 実際の収集には、BlueSkyチームが運用する
bsky.networkrelay のWebSocket firehoseを使った- メインの
*.bsky.socialPDSと、インデックス化を要求した独立PDSのイベントを集約する - ネットワーク全体のイベントがリアルタイムでストリーミングされ、現在はおよそ毎秒500イベント規模
- このうちフォローとアンフォローだけを抽出して、ローカルのSQLiteデータベースに保存する
- メインの
- 当初はインデクサを fly.io にデプロイし、litestreamでAWS S3へデータベースをリアルタイム複製していたが、月40ドルの費用のためホームサーバー運用に切り替えた
- その後は systemd サービス、logrotate、tmux モニター、TailScale を組み合わせて、自宅のSystem76デスクトップで運用している
- 執筆時点でBlueSkyは1,300万ユーザーを超え、
followsテーブルは5億行超、ディスク使用量は約30GBだった
1,300万ノードグラフの計算ボトルネック
- グラフレイアウトにはさまざまな方法があるが、ここでは物理シミュレーションのように動作するforce-directed layoutが出発点となった
- すべてのノードは互いに反発する力を持つ
- エッジはソースとターゲットの間に引力を生む
- 各シミュレーションティックでノードごとの合力を計算し、温度パラメータでスケールして移動させる
- ボトルネックはグラフサイズ自体よりも、n-body problemの計算複雑性にある
- 単純なアルゴリズムでは1ティックあたり
O(n^2) + O(e)が必要 - 数百万ノード規模ではGPUでも現実的ではない
- 単純なアルゴリズムでは1ティックあたり
- 一般的なforce-directedエンジンのように Barnes-Hut 最適化を使えば、
O(n log(n)) + O(e)まで減らせる- ただし遠方ノードの効果を近似する代償がある
- quadtree の構築とクエリは階層的なため、GPUでノードの力を簡単に計算しにくい
- 並列化のため、quadtree を4個または16個に分割して各ティック開始時に並列再構築し、スレッドごとにノード範囲を分担して力を計算する
- 各ノードの合力は、各quadtreeが与える力と、入出力エッジが与える力の合計になる
- 利用可能なCPUをほぼオーバーヘッドなしで活用できる
Andromedaとforce-directed方式の限界
- Zigでマルチスレッドのforce-directed graph layoutエンジン Andromeda を作り、GUIはGTK4とOpenGLで構成した
- Andromeda は Gephi と ForceAtlas2論文 から大きな影響を受けている
- 大規模グラフ可視化では、グラフが変化する様子を見ながらシミュレーションパラメータを動的に調整する対話性が重要
- 不透明で反復時間の長いツールでは良い結果を得にくい
- Andromeda には「natural slider」というUIウィジェットもある
- 新しいグラフ、新しいエンジンバージョン、新しいパラメータを扱うとき、適切な値の範囲を事前に知りにくい問題を減らすための仕組み
- 値の範囲を e のべき乗単位で動的に調整する
- 2のべき乗は細かすぎ、10のべき乗は粗すぎると判断した
- 2024年9月時点の500万BlueSkyユーザーのスナップショットに ForceAtlas2 レイアウトを適用すると、大きなクラスタの質量と密度は見えたものの、全体として塊状の形が強かった
- ほとんどのノードはスーパークラスタ周辺の広く判別しにくい領域に散らばる
- 数十個の小さなコミュニティ、とくに国単位のコミュニティだけが明確に分離された
- 2024年2月に200万アカウント版を公開したときも、グローバルビューへの興味はあったが、ローカルビューには失望があった
- ユーザーが自分のアカウントを見つけても、周辺アカウントを見分けられないことがあった
- 2D平面配置だけでネットワーク全体の接続構造を完全に捉えるのは難しい
UMAP、色、最終マップ
- グラフレイアウトは次元削減として見ることもでき、1,300万 × 1,300万の隣接行列を2次元平面に射影する問題として扱える
- t-SNE と UMAP は2次元可視化に強い非線形次元削減手法
- UMAPにBlueSky行列を直接入れるには、ホームサーバー規模では大きすぎる
- その代わり、ユーザーごとに32次元程度の埋め込みを作り、その結果をUMAPに入力する
- オープンソースのノード埋め込みツールとして nodevectors を選び、未公開の GGVec アルゴリズムが大規模グラフで最も良い並列性能を示しそうだった
- 2024年9月の500万ノードスナップショットの埋め込みは5分で生成できた
- 最初のUMAP画像も追加10分で得られた
- Andromeda の塊状の結果よりも、はるかに多くの中間構造が現れた
- UMAPは一部クラスタを密にしすぎて、点が重なる問題があった
- 元の次元で同一の点を目標次元でも同じ位置に置くという純粋な次元削減目的には自然な挙動
- しかし、アカウントごとのプロフィール画像を近いズームで見せる地図には向いていなかった
- UMAP内部も最終段階では、重み付きk近傍グラフに対する force-directed layout を使っている
- UMAPは計算制約のためサンプリングを使うので、すべてのノードがBarnes-Hut方式のように近似的にでも相互反発するわけではない
min_distパラメータは大規模グラフで点間分離を一貫して制御できないと判断した
- 重なりの問題は、UMAP出力を Andromeda に入れ、反発力の方程式を調整して数ティック追加で実行する方法で緩和した
- 高密度クラスタでもノードが層のように重ならずに埋まる
- 次のバージョンでは、UMAPが生成したグラフの生の重みにアクセスし、Andromeda の並列 quadtree と UMAP 論文の力の方程式を直接組み合わせたいとしている
- 色はUMAP結果にHDBScanを適用する代わりに、埋め込み空間でk-meansクラスタリングを行って付与した
- 各クラスタに hue を割り当てる
- 各点は最も近い3つのクラスタ中心を使って hue を補間する
- PCAベースの色付けより局所構造をうまく表し、拡大するとまだらのステンドグラスのような質感になる
- hue は0から1の単一 float で、hsluv 色空間でRGBにマッピングする
- すべてのノードの彩度は一定に保つ
- 明るさはユーザーのフォロワー数の
log10でスケールし、大きなアカウントは明るい星のように、フォロワーの少ないアカウントは淡く見えるようにする - 大きなアカウントを実際に大きくレンダリングする方法は、大規模グラフでは複雑すぎるため除外した
- 2024年11月7日時点のネットワーク全体マップは、フォロー5万超のアカウント、フォロー5件未満かつフォロワー5人未満のアカウントを除外し、770万ノードで構成される
- 高フォロワーのメディア・政策・論評アカウントの明瞭な縞模様が、背景にある関連の薄いグループと区別される
- アイスランドのクラスタも遠景・近景・プロフィール画像レベルで確認できる
- ボットリングも明確に見える
- 次の機能としては、現在画面に見えているアカウントの投稿タイムラインを折りたためるサイドバーとして追加したいとしている
- 新しい種類のソーシャル・ミーム探索ツールへ発展させるのが目標
1件のコメント
Hacker News の意見
BSKY のフィードが完全に死んだ空間のように感じる。投稿もして、返信もして、いいねも押して積極的に参加しようとしたが、何も定着しない感じがする
「自分のために」投稿するにも限界があり、すぐに興味が薄れてしまう。初期の Twitter は、みんなが新しい人をフォローしようと盛り上がっていた雰囲気だったのに、新しいソーシャルネットワークなら本来、新しいつながりを作ろうとする人であふれているべきではないかと思う
Bluesky と atproto は、ハック可能にすることを念頭に置いているように見える
コミュニティでは最近、Bluesky の「Starter Packs」を検索できるディレクトリを作った。Starter Packs は、ユーザーがフォローするとよさそうな人やフィードの束を公開し、新規ユーザーが初期体験を素早く構成できるようにする機能だ
https://blueskydirectory.com/starter-packs/all
Dan Abramov も今日これを好意的に見ていて、「こういうものがエコシステムの中で可能だという事実が素晴らしい。エコシステムに料理させよう」と述べていた [1]
さらに鋭くは、「atproto エコシステムで任意のプロジェクトが次々出てくるのを見ると、ソーシャル企業が API を閉じてしまったことで、公共ウェブのコモンズがどれほど抑え込まれていたのかを改めて感じる。ツールの風景全体が諦められ、捨て去られていた」とも述べていた [2]
[1] https://bsky.app/profile/danabra.mov/post/3lar3sdna222d
[2] https://bsky.app/profile/danabra.mov/post/3lar3xpuu4c2d
テック企業が犯した致命的な過ちの一つは、すべてを囲い込むことだったと思う。コンピュータやスマートフォンを素晴らしいものにしたのは、ハック可能性であり、環境とエコシステムを作ることだった。ロックダウンは速度を落とすだけだ。アプリがなかったら、スマートフォンに懐中電灯やストップウォッチが入るまでどれほど時間がかかっただろうかと思う。OS に組み込まれる前、こうした機能はアプリだった
Bluesky は先週、特定分野で大きく爆発したように思う。土曜日以降、フォロワーが5〜6倍に増えた
この1年ほどある程度活動してきたのは、自分が関わるエネルギー分野の Twitter の会話があまりに壊れて、ほとんど使いものにならなくなったからだ。いろいろな意味で攻撃的で、スパムも信じられないほど多かった。一方で Bluesky はゆったりしていたが反応は大きくなかった。今は雰囲気が熱を帯びてきている。この流入が本物であってほしいし、そのおかげでずっと活発に使うようになった
この3週間で Bluesky はずっと活発になり、今ではフィードを全部追いきれないという点で X に似ていると感じる。大きなコミュニティはより多様な視点を生むと信じているので、とても期待している。自分でも Bluesky のラベラーと Firehose 収集器を運用しているが、この3〜4か月でイベント処理量がおよそ2倍になるのを見てきた
Threads は創作、旅行、ソーシャル系コンテンツに強い、半 Twitter・半 Instagram の混合体で、Bluesky はニュース、政治、科学に強い初期 Twitter に近い。最近は、すべてを1つのアプリでこなすことが可能なのかよく分からなくなっている。そうなると X は新しい 4chan として残ることになる
たまに確認するが、実質的には 0/50 に近い
先週Blueskyへ移っていったユーザーの波の一部。今のところ本当に気に入っていて、以前Mastodonには失望していたので少し驚いている。すでにTwitterよりBlueskyで過ごす時間のほうが長い。
Blueskyが何かを知らない人に説明すると、ほぼ2015年ごろのTwitterのコピーで、UIもほぼ同じ。ただし収益化、広告、グロースハックがないので、主要機能がユーザーのために存在している。気に入っている例としては、シンプルなExpo/React Nativeベースのモバイルアプリで、役に立たないアプリ内ブラウザではなくSafariでリンクを開けるようにしてくれる点がある。
世界は米国や西側圏のインターネット上のドラマよりはるかに大きい。欧州人としてBlueSkyを含む主流ソーシャルメディアを読んでいると、うんざりするほどだ。政治、性自認、キーボード・アクティビズムには関心がない。メニューに何か別のものを載せられないのかと思う。本当に何でもいい。米国政治や、私生活で誰がどの性別に惹かれるかではなく、新しいものに触れるにはロシア語か中国語を学ぶべきなのかと考えるほどだ。誰が気にするのかと思う。
Nostrは技術的には楽しかったが、結局クリプトブロ段階を抜け出せなかったのが残念。
かなり格好いい。BlueSky APIはよくできている。同僚がFirehoseベースでこういう可視化を作った: https://bigmood.blue/
出典: https://bsky.app/profile/even.westvang.com/post/3laob7tefxk2...
これがどれほど気に入っているかを大げさに言うのは難しい。最終結果が複数の次元の情報を伝えているだけでなく、視覚的にも非常に魅力的だ。
膨大な数のノードをレンダリングすることで生じる粒子感が、特に良い雰囲気を加えている。他のグラフ可視化ではあまり見られない要素だ。
Blueskyのいちばん良い点は、ドメインをユーザー名として使えること。私はそこで@bradgessler.comを使っていて、人々が私を「検証」したいなら、青いチェックマークよりはるかに意味のある私のウェブサイトを見ることになる。
ブロックされたり、禁止されたり、プラットフォームから追い出されたりしても、人々は私のドメインを見て、そこへ行き、何が起きたのか確認できる。ある意味では、検閲が可視化される仕組みだ。企業にも良さそうだ。@example.comで企業に呼びかけて返答を受けるほうが、ずっと曖昧さが少ない。RailsベースのSaaSで、すでにこうしているところを集めたスターターパックも作った: https://go.bsky.app/JQyXa2u
BlueSkyがやっていることは本当に気に入っていて、今後エンシット化しないでほしい。仮にそうなったとしても、今は雰囲気がとても良いゴルディロックス的な時期に見える。アカウントを作って自分のドメインに紐づけるのに5分で済むので、強くおすすめする。
https://joinmastodon.org/verification
「BlueSky行列をUMAPに入れたらどうなるだろう？ 少なくとも直接はできない。UMAPは技術的には疎行列を受け取るが、この規模は自宅サーバーには大きすぎる。代わりに別の手法で全ユーザーの埋め込みを32のような中間サイズの次元に抽出し、それをUMAPに入れればよい。簡単だ！」とあるが、正確には埋め込みをどう導出したのか気になる。
「四分木の生成とクエリは本質的に階層的だ」という文を見て、hierarchyで混乱するのは自分だけではないのだと思えてうれしかった。
複数のレイヤーで興味深い仕事だ。しゃれではない。Blueskyデータの可用性から処理、可視化アルゴリズムまで見どころがある。ただし、こうした可視化をデータサイエンスのスペクトラムのどこに位置づけるべきかは少し不明瞭だ。伝統的な数値グラフィックスは時間をかけてかなり洗練された文法を発展させ、比較的正確な推論と解釈を可能にしている。そのため科学論文や金融業界などで実際の情報伝達に広く使われ、人々はグラフをリバースエンジニアリングしてデータを復元することもある。
ネットワークやグラフは、トポロジー、接続性、クラスタに関する全体的な感覚以外に、何の情報が伝わっているのかを特定するのがかなり難しい。こうした大規模グラフを扱う有用な文法がまだ発明されていないのか、それとも本来そういう性質なのかはよく分からない。
このデータを自然言語処理の観点からもっと見てみたい。Google Trendsのように、どの談話トピックが定期的に現れるのか、特定の期間に何が急増するのかを見られるとよさそうだ。
経済学者たちが何を議論しているのか要約できるだろうか。互いのネットワークにはいないが同じことについて話している人たちを見つけられるのか気になる。