モーフィングエッジ描画のスケジューリングを改善した話
ネットワークの可視化にはしばしば連結図が用いられますが、ノードやエッジが少し多くなると連結図ではエッジの交差がたくさん発生し、読みにくい図になってしまいます。そのような問題への対策のひとつに「部分エッジ描画」と名付けられた手法があります。エッジの一部を描かないことで、見かけ上の混雑を減らすものです。混雑は減りますが、描かれない部分を推測する必要があります。「モーフィングエッジ描画」は、描かれたエッジの一部（スタブ）をアニメーションで伸縮させることで、視覚的な混雑を抑えつつ、推測をしなくてもエッジによるつながりを読み取れるようにしたものです。ここでは、モーフィングエッジ描画においてスタブの伸縮のタイミングを決めるスケジューリングを改善した話を紹介します。これはグラフ描画に関する国際会議（GD 2022）で発表したものです。
ネットワークの構造を抽象化したものを「グラフ（graph）」とよびます。「グラフ」と言っても、棒グラフや折れ線グラフなどとは異なる概念で、ノード（node）の集合とノードをつなぐエッジ（edge）の集合から構成されます。ネットワークの可視化は、「グラフ描画（graph drawing）」とよばれています。
完全エッジ描画（連結図）
グラフの可視化にはしばしば連結図が用いられます。ノードを点あるいは点に相当する図形で表し、エッジをノードをつなぐ線分で表すものです。このような表現方法を後で紹介する表現手法と区別するために「完全エッジ描画」とよぶことにします。ノードやエッジが少し多くなると完全エッジ描画ではではエッジの交差がたくさん発生し、読みにくい図になってしまいます。
部分エッジ描画
そのような問題への対策のひとつに「部分エッジ描画」と名付けられた手法があります。エッジの一部を描かないことで、見かけ上の混雑を減らすものです。部分エッジ描画にもいろいろなバリエーションがあります。見掛け上の交差をなくすためには、エッジの中心部分を省略して、ノードにつながる部分を残す方法がしばしば利用されます。描かれたエッジの一部は「スタブ」とよばれます。ノードにつながるスタブを同じ長さだけ残す方法を「対称部分エッジ描画」とよび、エッジの長さに対するスタブの長さを「スタブ（エッジ）比」とよびます。さらにグラフ全体を通してスタブ比が均一であるような対称部分エッジ描画を「対称均一部分エッジ描画」とよびます。
図2は図1と同じグラフを、スタブ比25%の対称均一部分エッジ描画で描いたものです。
完全エッジ描画ほどではないですが、スタブ比25%でも中心付近は混雑した印象を受けます。図3はスタブ比を16%にしたものです。
混雑した感じが減り、すっきりとしてきました。部分エッジ描画では、混雑は減りますが、描かれない部分を推測する必要があります。
モーフィングエッジ描画
「モーフィングエッジ描画」は、スタブをアニメーションで伸縮させることで、推測をしなくてもエッジによるつながりを読み取れるようにしたものです。ただし、やみくもに伸縮させるのではなく、視覚的な混雑を抑えるために、部分エッジ描画によって減らした交差を増さないように、伸縮のタイミングを調整しています。ここまでは、国際会議GD 2019（Czech）で発表したものです。
グラフが大きくなるとアニメーションの周期も長くなる
図4は約7.6秒毎にアニメーションを繰り返しています。エッジの伸縮によって交差を増さないために、交差するエッジのスタブが伸びている間は、交差相手であるもう一方のエッジのスタブは短かいままで待機する必要があります。グラフが大きくなると、エッジの交差も増えるので、どうしても待機時間が長くなってしましまいます。そして、待機時間が長くなると、推測をしなくてもエッジによるつながりを読み取れるというメリットが薄れてしまいます。
そのため、アニメーションの周期をできるだけ短くする必要があります。もちろん、アニメーションの速度を速くして伸縮の時間を短くすれば周期を短かくできるのですが、それでは目が追い付かないので、アニメーションの速度をあまり速くせずに、周期を短かくすることが課題です。
改善策
伸縮のタイミングを決めることを「スケジューリング」とよんでいます。国際会議GD 2019で発表したスケジューリングの方法には三つの特徴があります。
周期の最初と最後ではすべてのスタブが最短の状態になる
一組のスタブは1周期の中で1回だけ伸縮を行う
スタブ同士の交差を許さない（回避できない交差はあきらめる）
これらに対して、下のように変更することで、周期の短縮をおこないました。図5 モーフィングエッジ描画の例（GD 2022版）許容交差数5
周期の最後を次の周期の最初と重ねることで、交差を増さずに周期を短縮する
1周期のなかで可能なだけ伸縮を行う
少しだけ交差を許す
2は全体の周期の短縮にはつながっていませんが、各スタブに着目すると、1周期内で2回伸縮できるのであれば、実質的には周期が半分になったのと同じ効果があります。3は「少しだけ」と書きましたが、実際には、指定された数までの交差を許すアルゴリズムをつくりました。図5は新しい手法でスケジューリングを行った例です。ひとつのエッジにつき、ある瞬間に5個所までの交差はよいことにしています。結果的に周期を約5.1秒まで短縮できました。さらに、図4と比較するとわかるように、1周期内で可能なだけ伸縮を行うことで、実質的な周期はもっと短縮されています。
今後の課題
先に行った実験によると、部分エッジ描画よりもモーフィングエッジ描画の方が、グラフの読み取り時間が速くなる可能性があります。今回改善したスケジューリングにより周期を短縮できそうですが、そのことがグラフの読み取りに与える影響については今後調べる必要があります。
補足
GD 2022は正式には「The 30th International Symposium on Graph Drawing and Network Visualization」という国際会議で、今回はじめて東京で（アジアでもはじめて）開催されました。
GD 2022の論文は arXiv で入手できます。
論文
Kazuo Misue and Katsuya Akasaka, Graph Drawing with Morphing Partial Edges, Proceedings of Graph Drawing and Network Visualization 2019 (GD2019, 17-20, Sept. 2019, Průhonice/Prague, Czech), 13 pages, 2019.
Kazuo Misue, Improved Scheduling of Morphing Edge Drawing, Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022, 13-16, Sep. 2022, Tokyo, Japan), 14 pages, 2022.
プレスリリース
https://www.tsukuba.ac.jp/journal/technology-materials/20220912140000.html
この記事が気に入ったらサポートをしてみませんか？