nostr のコミュニティマップを t-SNE で描く

# なんじゃ
Nostr のフォロワーを分析してコミュニティマップを描くサイトを作りました

nostr-tsne https://koteitan.github.io/nostr-tsne/
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/176345/faf48a53-9052-69cc-392a-fd324a3afc1d.png)

この図は2024年12月9日時点での、私の選んだ５つのリレー[^1]の中の人のコミュニティマップを描いたものです。

図の黒点１つ１つがひとつのユーザーアカウント(pubkey)です。黒点は結びつき（後述）が強いほど近くに表示されます。

# 発端
発端は [Bluesky](https://bsky.app) で Bluesky のコミュニティマップを描いた [Erix さん](https://bsky.app/profile/chercher.ai/post/3jtwacym2pk2r)[^2],
[jaz さん](https://bsky.jazco.dev/atlas)[^3]のグラフを見たことでした。

どうやって書いているんだろうと思って Erix さんに聞いてみると、誰が誰をフォローしているかのフォロワー情報を [t-SNE(t分布型確率的近傍埋め込み法)](https://ja.wikipedia.org/wiki/T%E5%88%86%E5%B8%83%E5%9E%8B%E7%A2%BA%E7%8E%87%E7%9A%84%E8%BF%91%E5%82%8D%E5%9F%8B%E3%82%81%E8%BE%BC%E3%81%BF%E6%B3%95)という手法で２次元に落として書いているということでした。

# t-SNE
[t-SNE(t分布型確率的近傍埋め込み法)](https://ja.wikipedia.org/wiki/T%E5%88%86%E5%B8%83%E5%9E%8B%E7%A2%BA%E7%8E%87%E7%9A%84%E8%BF%91%E5%82%8D%E5%9F%8B%E3%82%81%E8%BE%BC%E3%81%BF%E6%B3%95) は、多次元空間上にあるノードの集まりをそれらの互いの距離情報を使って、２，３次元の低次元に落とすことによって見やすくする手法です。

ノードの集合を N として、その中のノード a, b の距離が実数
```math
\textrm{dist}(a,b)\in \mathbb{R}
```
で表されるとします。あらゆるノード対に関してこの距離が定義できているとき、t-SNE はその低次元マッピングを描いてくれます。

たとえば [MNIST](https://ja.wikipedia.org/wiki/MNIST%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9) の 8x8 の手書き数字サンプルの自動クラスタリングの課題では、$k$ 番目サンプルの $(x,y)$ 位置のドットの濃さを 0～1 の値を持つ関数 $I_k(x,y)$ で表したとしたとして、サンプル $a$ とサンプル $b$ の距離 $\textrm{dist(a,b)}$ を
```math
\textrm{dist}(a,b) = \sqrt{\sum_{x=0}^7\sum_{y=0}^7 |I_a(x,y)-I_b(x,y)|^2}
```
で表すことで、下記の二次元埋め込みが得られます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/176345/f8390204-4e2f-ccc7-bed5-17f48b99dab2.png)
１つのドットが１つの文字サンプルで、色が同じ文字サンプルは同じ数字であることを表しています。同じ文字ほど近くに描かれていることが分かりますね。

# t-SNE の Javascript 実装
t-SNE の実装は、簡単に使えそうな JavaScript ライブラリがあんまりなさそうだったので、t-SNE 本家の論文[^4]の式 1, 4, 5, 12, 13, 7 をそのまま実装しました。

TSNE.init(D, ndimY) の初期化ルーチンが式 1→4→5, 
TSNE.step() のステップルーチンが式 12→13→7 に相当します。
tsne.js は t-SNE ライブラリとしてこれ単体で使えます。

# ソーシャルグラフで距離関数って？
ではSNSのアカウント同士の距離ってどう定義すればいいのでしょうか。

ここが一番迷って、最初は[エルデシュ数](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%AB%E3%83%87%E3%82%B7%E3%83%A5%E6%95%B0)？とか考えたんですが、そもそもエルデシュ数の探索自体面倒だなと思って、もっと単純に下記の距離関数で行くことにしました

```math
\textrm{dist}(a,b) = \left\{\begin{align}
1&\mathrm{~if~}a\mathrm{~follows~}b \mathrm{~or~} b\mathrm{~follows~}a\\
10000&\mathrm{~otherwise}
\end{align}
\right.
```
つまり、どちらかがフォローしてたら距離は１、どちらもフォローしてなければ距離は 10000、という距離関数です。これによって nostr の kind:3 を探索するだけで距離関数が定義できて実装が簡単になりました。

# スパム除去のチューニング
SNS 解析で面倒なのがスパム除去です。今回はフォロワー数が 30 以上のアカウントだけを表示してスパムを除去することにしました。

# つかいかた
### リレー設定
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/176345/be194b3d-55c3-044d-1e43-9b2478f894b8.png)
上の四角の箱に、解析したいリレーのリストがあります。
最初からそこそこ面白い絵が出るようなリレーが仕込んでありますが、NIP-07 対応拡張機能をお持ちの場合は自身のリレーを kind:3、または kind:10002、からボタンで読み込むことができますし、下位行区切りで直に箱に書き込むこともできます。
### パラメータ設定
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/176345/95e20bf2-1496-9aab-a779-ea6bbf6dbc0c.png)
ユーザー数と最低フォロワー数を次の行で変えられます。
フォロワー数が最低フォロワー数以上のユーザーをユーザー数だけ集めてくる、という動作になります。リレーがN個ある場合は、それぞれのリレーからユーザー数/Nが集められてきます。
### ユーザー探索開始
設定がよければ start ボタンでユーザー探索が始まります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/176345/3e251e3c-d9e7-c8d4-9491-a1d06ff473b8.png)
遅くてしびれを切らした場合は skip ボタンで飛ばしてそこまでの探索だけでグラフを書きます。
### t-SNE 計算開始
まず初期化の ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/176345/f1ad2005-718a-9c69-53b7-b5543180e4b5.png) の画面で少し時間がかかるので少し待ってください。少し待つと黒い点々が現れて動き始めます。

黒い点はこのままずっと動き続けますが、だんだん動きが鈍くなってきて、ある形に収束することが多いです。

グラフをマウスか指でドラッグ・スワイプすることで平行移動ができます。マウスホイールか下のズーム＋－ボタンで拡大縮小ができます。

# クラスター観察記
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/176345/faf48a53-9052-69cc-392a-fd324a3afc1d.png)
真ん中に一番大きな集まりがあります。これがなんの集まりかは一言で言い表しにくいですが、ひとまず英語が離されているので英語圏と呼べると思います。

その他にちょこちょこと小さな集まりがいくつか見えますね。南のはずれにあるのは、日本語圏です（緑の丸）。他の集まりよりも英語圏からずいぶん遠いですね。英語圏から独立しているため、引力が働かないのかなと思います。

その西に少し飛び出しているのは、言語を見る限りはタイ語圏です。タイ語圏は結構英語に食い込んでいますね。

その少し西にあるのは簡体字圏。簡体字圏も日本同様遠いです。

真西にあるのはよくわからなかったのですが、濃い目の bitcoiner クラスタな気がします。同じく北のはずれにあるのもまた別の bitcoiner クラスタです。私には違いがよく分かりません。

やってみて思ったのは、なんのクラスタなのかの判断が結構難しいことでした。リレーごとに偏るかなと思ったのですが、よくわかりませんでした。使用言語ごとやリレーごとに色が変えられれば分かりやすそうですね。

私もまだあんまり試してないので、なんかおもしろいマップが書けたリレーとかあったら教えてください。

[^1]:wss://relay.damus.io, wss://nos.lol, wss://yabu.me, wss://nostr.bitcoiner.social, wss://nostr.einundzwanzig.space
[^2]:[☯︎ Erix ☯︎](https://bsky.app/profile/did:plc:ghcb54hzc5gayw6jss4mpzzj), Bluesky, 2023.4.23
[^3]:[jaz](https://bsky.app/profile/jaz.bsky.social), ["Atlas"](https://bsky.jazco.dev/atlas), bsky.jazco.dev and [github](https://github.com/ericvolp12/bsky-experiments), 2023.4.27.
[^4]:Laurens van der Maaten, Geoffrey Hinton, [”Visualizing Data using t-SNE”](http://www.cs.toronto.edu/~hinton/absps/tsne.pdf), Journal of Machine Learning Research, pp.1-48, 2008.

(この記事は [Nostr Advent Calendar 2024](https://adventar.org/calendars/10004) の 12/9 の記事です)
著者: koteitan https://nostter.app/koteitan.github.io