Jacomy, M., Venturini, T., Heymann, S., Bastian, M. (2014) ForceAtlas2, a Continuous Graph Layout Algorithm for Handy Network Visualization Designed for the Gephi Software. PLoS One, 9(6), e98679.
たまに仕事の都合でネットワーク・グラフを描くことがあるんだけど、あれはホントに怖い。ノードの位置やエッジの太さ・色などの非本質的な視覚的要素によって、ユーザが図から受ける印象ががらっと変わってしまう。正直、データの視覚化手法としては危険すぎると思うこともある。
ノードの位置を決めるアルゴリズムもいろいろあって困ってしまう。適切なアルゴリズムを選ぶのはなかなか難しいし、個々のアルゴリズムについて理解する時間も体力もないけれど、せめてよく使う奴については、中でなにをやっているのかを知っておきたいものだ。
というわけでめくってみた論文。私が愛用している視覚化ソフトGephiが主力として擁しているアルゴリズムForceAtlas2の解説論文である。ほんというと、こんなの眺めてる場合じゃないんだけどな…
1. イントロダクション
GephiはPajekとかとは違って、アルゴリズムの研究というより実装に重きを置いている。ForceAtlas2は我々が開発しGephiに実装した、ネットワーク・グラフの視覚化アルゴリズムなんだけど、それ自体にオリジナリティはない。単にfluentかつ高品質なcontinuousアルゴリズムを目指しただけである。
[というようなお気持ち表明が縷々書いてある。大幅に省略。continousアルゴリズムってヌルヌル動くって意味かなあ?]
2. ForceAtlas2を解剖する
ForceAtlas2はforce-directedアルゴリズムである。つまり、物理的な系のシミュレーションによってネットワークを空間化する。デカルト座標系への射影だと思わないように。構造的な近接性(モジュラリティ)を視覚的な近接性で表現しようというのが目的である。初期値に依存するし、決定論的ではない。決定論的なレイアウトがほしかったらハイブ・プロットとかを使うように。
2.1 エネルギー・モデル
force-directedアルゴリズムはみな、なんらかのattraction forceの式とrepulsion forceの式を考える。ノード間の距離を\(d\)として、たとえば…
- spring-electricレイアウト: \( F_a = -kd, \ \ F_r=k/d^2 \)。前者はバネの公式、後者は荷電粒子の公式になっている。
- Fruchterman-Reingold アルゴリズム: \( F_a = d^2/k, F_r = -k^2/d \)。
[物理学とのアナロジーを持ち出されると文系の私は困っちゃうんですけどね… よくわかんないけど、すべてのエッジについて\(F_a – F_r\)を求め、それが正だったら2つのノードをちょっと近づけ、負だったらちょっと遠ざける、というのを延々繰り返すということですよね、きっと。あれ？ 「すべてのエッジ」で合ってる？ エッジのない2ノードの間にも\(F_r\)はあるんとちがう？]
式は物理的にみて現実的でなくてもよい。たとえばF-Rアルゴリズムの\(F_a\)はバネになっていない。
いろんなforce-directedアルゴリズムのあいだの違いの中で大事なのは、空間における距離の役割である。
物理的な系において力は相互作用する実体のあいだの距離に依存する。距離と力の関係は線形だったり指数だったり対数だったりする。広く言うと、距離の指数についての(attraction, repulsion)-modelを考えることができる。spring-electricレイアウトは(1, -2), F-Rは(2, -1)と書ける。Noackという人が提案したLinLogは(0, -1)である(0は対数を表す)。我らがForceAtlas(ForceAtlas2の前身)は(1, -1)である。[えーっと、つまりattractionはdに対して線形、repulsionはdの逆数に対して線形、ってことですね]
attractionを\(a\), replusionを\(r\)として、\(a-r\)を小さくすると、attractionが距離に依存しにくく、repulsionが距離に依存しやすくなるので、視覚的なクラスタが構造的な密度を表現するようになる。というわけで、クラスタの表現という意味ではF-RよりForceAtlas2が良く、LinLogがもっとよい。[ふーん]
ForceAtlas2では、
- attraction forceは古典的で、ノード\(n_1, n_2\)の距離\(d(n_1, n_2)\)そのものである。つまり\(F_a(n_1, n_2) = d(n_1, n_2)\)。[後述されるが、エッジが重みを持っているときはそれも反映される]
- repulsion forceはちょっと工夫している。社会ネットワークは多くの「葉」(近隣ノードがひとつしかないノード)を持つことが多い。葉は離れていた方が見やすい。そこで、ノードの次数+1に比例させ、\(F_r(n_1, n_2) = k_r \frac{ (deg(n_1) + 1)(deg(n_2) + 1)}{ d(n_1, n_2) } \) としている。1を足すのは孤立ノードにもrepulsion forceを与えたいからである。
2.2 設定
では、ForceAtlas2の設定について説明しよう。
- LinLogモード。\(F_a(n_1, n_2) = \log(1+d(n_1, n_2))\)となる。クラスターがよりタイトになる。収束は遅くなるようだ。LinLogモードに変えたらスケーリング・パラメータを再調整すること。
- Gravity。force-directed layoutsでは島が漂流しちゃうので、空間の中心に向かう重力を与えることが多い。ForceAtlas2では \(F_g(n) = k_g(deg(n)+1)\)としており、ユーザは\(k_g\)を設定できる。なお、”Strong gravity”を設定すると、重力が中心からノードまでの距離\(d(n)\)に応じて大きくなり、\(F’_g(n) = k_g(deg(n)+1) d(n)\)となる。コンパクトなレイアウトになるが、なりすぎちゃうこともある。
- スケーリング。ForceAtlas2では\(k_a, k_r\)というパラメータを用意していたが、もっと使いやすくしたくて、\(k_a\)をとりやめた。よって、\(k_r\)がスケーリング・パラメータです。大きくするとグラフはでかくなる。[←なるほど… 疑問が氷解したぜ]
- エッジの重み。”Edge Weight Influence” \(\delta\)というパラメータを用意している。エッジの重み\(w(e)\)が指定されていたら、\(F_a = w(e)^\delta d(n_1, n_2)\)となる。
- 制止ハブ dissuade hubsモード。これをonにすると、行き先を\(n_1\)として、\(F_a(n_1, n_2) = \frac{d(n_1, n_2)}{deg(n_1) + 1}\)となる。つまり、入次数が多いノードをauthority, 出次数が多いノードをhubと呼ぶとして、authorityが中心に、hubが周縁に来る。
- 重複抑制。[メモを省略するけど、ノードが重ならないように工夫している由…] この機能は、いったんグラフの空間化が終わってから使うこと。
- repulsion近似。repulsionを近似的に計算する。グラフが大きいときのみ使うこと。
3. パフォーマンス最適化
[この論文の本題はあきらかにこの章にあり、全12pのおよそ半分を占めているんだけど、関心がないのでパス。すいませーん]
4. 考察: ジェネリックでcontinuousなレイアウト設計
ネットワークの視覚化においてはデザインの選択が必要になる。ユーザのみなさんにはその選択の帰結について意識的になっていただきたい。Gephiのコンセプトは、ユーザにその帰結をリアルタイムで表示し、試行錯誤していただく、というものである。
非専門家のユーザは、空間化のプロセスを観察し、そのプロセスと相互作用していただきたい。空間化というのはひとつの構築作業であり、そこにはユーザの責任も生じるのである。[…中略…]
ForceAtlas2は100000ノード以上のネットワークには向かない。逆に、OpenOrdは100ノード以下のネットワークには向かない。このように、アルゴリズムには、ネットワークのサイズ、密度、コミュニティ構造によって向き不向きがある。[…中略…]
5. 結論
[略]
————-
半分くらい端折っちゃったけど、なかでなにやってんだか理解できたので良しとしよう。有名なFruchterman-Reingoldアルゴリズムとのちがいもなんとなくわかったので、少しトクした気分である。まあ正直、どうでもいいような話なんだけどさ。(すいません)
ところで、エッジのウェイトを負にしたら、ForceAtlas2のattraction forceってどうなるんだろう？ いつかヒマなときに実験してみよう。(たぶんやらない。そんなヒマがあったらさ、寝たいよね)