wiki-lens は Obsidian の LLM wiki レイヤー(`wiki/{sources,entities,concepts,questions}/`)を可視化する読み取り専用プラグインである。健全性・構造・近傍・成長・多層性・間隙という6つの問いに、それぞれ専用のビューと軽量な古典的グラフアルゴリズムで答える設計になっている。本ノートは各機能を支えるアルゴリズムの知識を、教科書的な出自と採用理由の両面から整理する。 参照実装: `.obsidian/plugins/wiki-lens/src/core/`(`cluster.ts`, `gap.ts` ほか)、設計判断の記録は `.obsidian/plugins/wiki-lens/docs/design.md` および `docs/implementation.md`。 ## 1. Louvain法によるコミュニティ検出(クラスタ抽出) **問題**: 4000ページ・数万リンクのグラフに、人間が読める「テーマの塊」はあるか。 **手法**: Louvain法は、各ノードを「自分をどのコミュニティに属させればモジュラリティ(コミュニティ内の辺密度が偶然より高い度合いを表す指標)が最大化するか」という基準で貪欲に付け替え、収束したらコミュニティをひとつのノードに畳み込んで同じ操作を再帰する、という2段階を繰り返す手法である。計算量はほぼ線形で、数千ノード程度なら一瞬で終わる。 **使い所**: Backbone Graph のクラスタ表示、Gap Finder のクラスタ間隙検出、3D Layers のレイアウト前処理。frontmatter の `domain` フィールド(表記ゆれが300種類以上あり実用に耐えない)の代わりに、リンク構造そのものから「テーマ」を計算で導いている。 ## 2. Personalized PageRank(個人化PageRank, PPR)— Local Lens **問題**: 「今開いているノートの近傍」を見せたいが、ハブ概念(被リンク200本超)では BFS(幅優先探索)の深さ制限がすぐ頭打ちになり、カットオフが恣意的になる。 **手法**: 通常の PageRank は「ランダムサーファーがどのページに居つくか」をグラフ全体の視点で解くが、PPR は再起動先を毎回「中心ノード」に固定する。α=0.15(85%の確率でリンクを辿り、15%の確率で中心ノードに戻る)のべき乗反復を30回実行する。無向グラフとして扱い(有向リンクを両方向に張る)、行き止まり(dangling node)の確率質量は中心ノードに還元する。 これにより「中心からの関連度」が連続値のスコアになり、「上位N件を選ぶ」という選び方が恣意的な深さ制限より原理的なものになる。実装は `Float64Array` によるフラット配列でベクトル演算しており、4000ノード・5.8万本の有向弧規模でもアクティブノート切り替えのたびに再計算できる速度が出ている。 同心円レイアウトの「輪」はこの PPR で選ばれた部分グラフの中で改めて BFS の深さを取り、内側の輪では PPR 降順に並べ、外側の輪は「最も PPR が高い親ノードの角度」でソートすることで線の交差を減らしている。 ## 3. ForceAtlas2 — 力学モデルによるレイアウト **問題**: グラフを2次元(または3次元)平面上に「意味のある配置」で置きたい。 **手法**: ノード同士を反発させるクーロン力的な斥力と、リンクで繋がったノードを引き寄せるバネ的な引力を同時にシミュレーションし、力が釣り合う準安定状態まで反復計算する、力学モデル系のレイアウトアルゴリズムである。似たノードが自然に近くに集まる。 **工夫**: メインスレッドをブロックしないよう、1フレームあたり5イテレーションずつ実行し、合計反復数はグラフの大きさに応じて `min(600, 150 + ノード数/10)` に制限している。3D Layers ではこの2Dレイアウトの (x, y) 座標をそのまま再利用し、Z軸には力学ではなく「ページ種別」という意味を持たせている。自由な3D力学配置は見た目こそ派手だが遮蔽が起きて読みにくくなるため、あえて採用しなかった。 ## 4. コンフィギュレーションモデル(次数保存ランダムグラフ)— クラスタ間隙検出 **問題**: 「2つのクラスタは実際どのくらい疎か」を測るには、比較対象となる期待値が要る。 **手法**: 統計物理・ネットワーク科学で使われるコンフィギュレーションモデルの考え方を応用する。各クラスタの重み付き次数の合計を `S_A`, `S_B`、グラフ全体の総辺重みを `m` とすると、「次数分布だけを保存してランダムに繋ぎ直した場合」に期待される2クラスタ間の辺重みは次式で近似できる。 ``` expected(A, B) = S_A · S_B / (2m) ``` これは「よく参照される大きなクラスタ同士は、何もしなくても偶然たくさん繋がる」という次数バイアスを補正するための古典的な近似式である。実測値 `actual` がこの期待値より大幅に低いクラスタ対を「疎な箇所」として拾い上げる。 ## 5. Adamic-Adar指数 — リンク予測 **問題**: 直接は繋がっていない2ノードが「将来繋がりそうか」を、共通の隣接ノードから予測したい。 **手法**: リンク予測の古典的指標のひとつ。共通の隣接ノード `w` を全て集め、次式でスコアを計算する。 ``` score(u, v) = Σ_w 1 / log₂(deg(w)) ``` 単純に共通隣接ノードの「数」を数える Common Neighbors 指標よりも、「めったに他と繋がらない稀少なノードを共有している」ことを重視する重み付けになっている(次数が低い `w` ほど `1/log₂(deg w)` が大きくなる)。実装では計算量を抑えるため中間ノード `w` を起点として列挙し(次数150超のハブは打ち切ってその旨をレポートに記録)、すでに共起関係として報告済みのペアとは重複排除している。 ## 6. 二部グラフの共起(co-citation)分析 — 概念ペアの間隙検出 **問題**: 「同じ文献から引用されている2つの概念」は人間が実際に関連づけた証拠であり、リンク予測より一段強い根拠になる。 **手法**: source(文献)ノードを中継点として見た二部グラフの共起カウントである。各 source ノードごとに、そこからリンクされている concept ノードの全ペアを数え上げ、共通の参照元が閾値以上(既定3件以上)ありながら直接リンクされていないペアを抽出する。ファンアウト(参照先の多さ)が極端なハブ source はノイズ源になるため、上限を超えたら計算をスキップしてその旨をレポートに残す(サイレントに打ち切らない設計方針)。 ## 7. 多数決によるコミュニティ帰属推定 — 橋渡し文献検出 **問題**: 「未取り込みだが引用されている文献」がどのクラスタから求められているかを知りたいが、引用元(referrer)の多くは Louvain の対象から除外されている seed stub(著者スタブページ)であることが多い。 **手法**: バックボーンに属さないノードについて、フルインデックス(除外前の全ノード)上の隣接ノードを見て、そこに割り当てられているコミュニティの多数決でコミュニティを推定する、というシンプルなフォールバックである。これにより本来は無所属扱いになるはずの参照元にも所属クラスタを与え、橋渡し候補の検出漏れを防いでいる。 ## まとめの見取り図 | アルゴリズム | 出自の分野 | wiki-lens での役割 | |---|---|---| | Louvain法 | ネットワーク科学(モジュラリティ最大化) | テーマクラスタの自動抽出 | | Personalized PageRank | Web検索(グラフ上のランダムウォーク) | 「今の文脈に関連する近傍」の選定 | | ForceAtlas2 | 情報可視化(力学シミュレーション) | 意味のある2D/3D配置 | | コンフィギュレーションモデル | 統計物理・ランダムグラフ理論 | クラスタ間の疎さの統計的検定 | | Adamic-Adar指数 | リンク予測(社会ネットワーク分析) | 未リンクだが繋がりそうなペアの予測 | | 二部グラフ共起分析 | 推薦システム(協調フィルタリングの基礎) | 引用証拠に基づく概念ペアの発見 | | 多数決帰属 | ヒューリスティック(自前設計) | 除外ノードへのクラスタ割り当て補完 | いずれも巨大で厳密な機械学習モデルではなく、**グラフの次数・隣接関係だけから計算できる軽量な古典的手法**を選んでいる点が共通している。これは wiki-lens の設計原則(ローカル完結・高速な全再計算・読み取り専用)と直接対応している。