ForceAtlas 2 | 永田晴久

ForceAtlas は Gephi の標準として使われているグラフ可視化アルゴリズムである．数あるアルゴリズムの中でもなかなかイケてる絵を返してくれると個人的には思っていて，MASW を作るときにも採用させていただいた．今回はそのアルゴリズムを簡単に紹介したい．

ドキュメント

ForceAtlas のドキュメントとしては，次のテクニカルレポート（？）が唯一のものと思われる．論文としては出ていないようだ．

ちなみに，Gephi では Force Atlas と ForceAtlas 2 が分かれているが，基本的な計算は同じで，2 では計算を高速化したりオプショナルな機能が付け加えられていたりする．

基本的なモデル

Force Atlas は，ノードにかかる力を計算してその方向へ少しだけ移動するというステップを繰り返す，よくある力学ベースの反復アルゴリズムである．計算する力の種類も，エッジの張られたノード同士に働く引力とすべてのノード間で働く反発力の 2 つで，とくに目新しくはないが，働く力の大きさに工夫がされている．

いま，グラフの隣接行列が $N$ 次正方行列 $A$ で与えられているとし， $i = 1, \dots, N$ について，ノード $n_i$ の座標が $\bm{p}_i$ であるとする．ノード $i$ の次ステップでの移動量 $\Delta\bm{p}_i$ は，次の式から計算される．

(1) $\begin{eqnarray*} \Delta\bm{p}_i &=& \sum_{\substack{j = 1\\j \neq i}}^N A_{ij} F_a(i, j) \bm{e}_{ij} + \sum_{\substack{j = 1\\j \neq i}}^N F_r(i, j) \bm{e}_{ji} \\ \bm{e}_{ij} &=& -\bm{e}_{ji} = \frac{\bm{p}_j - \bm{p}_i}{\|\bm{p}_j - \bm{p}_i\|} \\ F_a(i, j) &=& k_a \|\bm{p}_i - \bm{p}_j\| \\ F_r(i, j) &=& k_r \frac{({\it deg}(n_i) + 1)({\it deg}(n_j) + 1)}{\|\bm{p}_i - \bm{p}_j\|} \end{eqnarray*}$

ここで ${\it deg}(n_i)$ はノード $n_i$ の次数で， $\|\cdot\|$ は通常のユークリッド距離．

1つ目の summation が引力項，2つ目が反発力項で， $k_a$ ， $k_r$ はそれぞれの大きさを調整するパラメータである．実際には $k_a$ と $k_r$ の比が決まれば自由度はスケーリングだけになるので，ForceAtlas 2 では $k_a = 1$ に固定されている．

引力項は距離に比例して引っ張る力が増える，通常のばねモデルである．反発力項の方は，距離の逆数に各ノードの次数が掛かっていて，次数の大きいハブ同士にはより強い反発力が働くようになっている．これが Force Atlas の特徴で，ドキュメントの中では「ハブは周辺の末端ノードと合わせてひとつのクラスタを形成するので，これを引き離すことでクラスタ構造が見えやすくなる」と説明されている．

ところで，この手のアルゴリズムでは $F_a$ や $F_r$ のことを力と呼ぶことが多いが，実際の物理でいえばこれは力ではなく速度ないし運動量である．何も知らず $F_a$ を加速度として使うと大変なことになる（なった）．

オプション

ForceAtlas 2 では，上の基本式に加えて，いくつかの追加的なセッティングが用意されている．

LinLog mode

基本式では $F_a$ は距離に対して線形に取るが，これを log スケールとするモデル．これで作られるレイアウトは Newman の Modularity と関係しているらしく，非常に興味深いが，まだ確認はしていない．

Gravity

基本式では，非連結成分どうしには引力が働かず反発力だけが働くため，お互いがどんどん遠ざかってしまうという欠点がある．これを防ぐために，適当な一点に引きつけられる力を基本式に加えるのが Gravity である．ドキュメントではノードの次数に比例して重力を強くする方法が提案されている．MASW で採用．

Prevent overlapping

図を描くときには，ノードは適当な半径をもつ円として描かれることが多いので，この円が重ならないようにするオプション．2つのノードが一定距離内に近づいた場合に，より大きい反発力係数を使う．MASW で採用．

その他，重みつきエッジや反発力計算の簡略化などの方法が提案されているが，ここでは割愛．

ステップ調整

ForceAtlas 2 で導入された大きな目玉のひとつに，ステップサイズの自動調整がある．この機能は，収束スピードが遅いときには移動量を増やし，発散しそうなときには移動量を減らして細かく移動することで，レイアウトの収束を加速させる．もともとが非常に不安定な最適化問題なので，ヒューリスティックとはいえ非常に役立つ機能である．

ForceAtlas 2 におけるステップ調整は，まず全体としてのステップ調整係数を求め，さらにノードごとにも調整をし，最終的に基本式の $\Delta \bm{p}_i$ にステップ調整用の係数 $s_i$ を掛けた分だけノードを移動させる．

全体のステップ調整

ステップ調整の基本的なアイディアは，前ステップの移動量と今ステップの移動量を比較して，変化が小さければ収束が遠いとして加速させ，変化が大きければ発散しそうだとして減速させることである．これを次のように定式化する．

(2) $\begin{eqnarray*} S_i &=& \|\Delta\bm{p}_i^{(t)} - \Delta\bm{p}_i^{(t - 1)}\| \\ S &=& \sum_{i = 1}^N ({\it deg}(n_i) + 1) S_i \\ T_i &=& \frac{1}{2}\|\Delta\bm{p}_i^{(t)} + \Delta\bm{p}_i^{(t - 1)}\| \\ T &=& \sum_{i = 1}^N ({\it deg}(n_i) + 1) T_i \\ s &=& \tau \frac{T}{S} \end{eqnarray*}$

最後に出てくる $s$ が全体のステップ調整係数となる．ドキュメントでは， $S$ のことを swing， $T$ を traction と呼んでいる． $s$ はスケール標準化された swing の逆数であり，swing が大きくなればなるほど移動量が制限されるのが上の式からわかる． $\tau$ はユーザーパラメータ．

個人的には，単純な平均でなくノード次数の重みつき平均をとる意味がいまいち明快でないのと，和をとってからスケール標準化するより，標準化してから和をとったほうが自然なんじゃないかと思ったりした．まあ，こうすると経験的にうまく動くということなのだろう．

実際のアルゴリズムでは，前ステップからの $s$ の変化が 50% を超えないように制限される．

ノードごとのステップ調整

$s$ が求まったら，ノード $i$ に対するステップ調整係数 $s_i$ を次の式から計算する．

(3) $\begin{eqnarray*} s_i = k_s \frac{s}{1 + s \sqrt{S_i}} \end{eqnarray*}$

$k_s$ はユーザーパラメータで， $i$ にはよらない． $k_s$ は $\tau$ によって吸収されるので，Gephi の実装では $k_s = 0.1$ に固定されている．分数部分はノード $i$ の swing が 0 のときに $s$ となり，swing が大きいほど 0 に近づいていく．

$s_i$ についても，変化が大きくなりすぎないように上限がとられることになっており，この上限は $\frac{k_{smax}}{\|\Delta\bm{p}_i\|}$ で与えられている．実際のところ，最終的な移動量はこれに $\Delta\bm{p}_i$ を掛けたものなので，この上限は単にノードの移動量を定数 $k_{smax}$ 以下に制約しているだけである．それなら最初から移動量の上限として設定すればいいような……．ちなみに $k_{smax}$ は，Gephi では 10 に固定されている．

MASW でのステップ調整

ForceAtlas 2 でのステップ調整は上の通りだが，なんだか複雑だし，もっとシンプルな方法があるのではと思って，MASW では違ったステップ調整を行うことにした．MASW では，全体のステップ調整は使わず，ノード個別のステップ調整係数 $s_i$ を次のように計算する．

(4) $\begin{eqnarray*} s_i = k_s \frac{T_i + k_t}{(S_i + 1)(\|\Delta\bm{p}_i^{(t)}\| + 1)\sqrt{{\it deg}(n_i) + 1}} \end{eqnarray*}$

基本的には traction を swing で割る方針は同じだが，次の点が異なる．

移動量が大きくなりすぎないよう，移動量で割る． $\|\Delta\bm{p}\|$ が大きいときには，最終的な移動量が $T_i / S_i$ に比例し， $\Delta\bm{p}$ の大きさに依らなくなる． $\|\Delta\bm{p}\|$ が小さいときには，この効果は消える．
次数で割る．観察していると，次数の大きいノードほど不安定になる傾向があったので，これを調整．
移動量が小さいときに振動しないよう，ユーザーパラメータ $k_t$ を設定．移動量が小さいときには， $s_i$ は $S_i$ にも $T_i$ にも影響されず，単に $k_t$ に比例する．

自分で試したところでは，オリジナルと同じくらいの精度で，ずっと速く収束するようになった．シンプルかどうかはわからないが，各項の意味づけもできるし，使い勝手はよさそう．

Posted: 2014-02-02 02:20

最終更新日時: 2014-02-18 17:54