複数のレイアウトアルゴリズムの選択的適用による階層型グラフのレイアウト最適化
片岡春菜 (指導教員：伊藤貴之)

1

はじめにPersistent Homology Guided Force-Directed Graph
Layouts （以下 PH とする）[4] を用いる．これらを選択的に適用し，遺伝的アルゴリズムを用いてレイアウトの最適解を探索する．最適化の過程にて，階層型グラフレイアウトに特化した数値評価指標である Sprawlterをレイアウトの評価に採用する．

グラフはノードとエッジの集合で構成されており，エッジはノードとノードの接続を表す．グラフはノードのレイアウトによって可読性が左右される．本稿が対象とする階層型グラフとは，複数のノードの集合であるメタノードから構成されているグラフであり，大規模なグラフの概要を効果的に可視化する手法である．
階層型グラフでは特に，接続構造が複雑である点や，各々のメタノードが固有の面積を有することで，可読性の高いレイアウトの生成が難しい．ノードに付与されたメタ情報の可読性も考慮する必要がある場合には，レイアウトの生成はさらに難しくなる．
階層型グラフのレイアウトを向上させる手法としては，レイアウト手法自体の改善もさることながら，既存手法によるレイアウト結果を最適化するアプローチも考えられる．そのような手法として村上らは，各々のレイアウト結果を数値評価し，遺伝的アルゴリズムを用いてレイアウトの最適化する手法 [1] を提案している．本稿では，村上らの手法に対し，複数のレイアウト手法を組み合わせることで，汎用的で視認性の高いレイアウトを生成し，階層型グラフの可読性を向上する方法を提案する．

2

関連研究

ノードが位置情報を有さないグラフを可視化する際には，各ノードの位置を適切に算出する必要があるた
め，グラフのレイアウト手法が活発に議論されている．
一方で，多数のノードを集めたメタノードの集合で構成されるグラフを階層型グラフという．Itoh ら [2] は，階層型グラフレイアウト手法 Koala を提案した．Koala
では，多くのノードと接続しているノードをクラスタから独立させる．
グラフレイアウトの評価は重要な課題だが，階層型グラフに特化したグラフレイアウトの評価指標は少なかった．Liu ら [3] は，階層型グラフレイアウトの数値評価指標として Sprawlter を提案した．Sprawlter は，空間の浪費度を評価する Sprawl と，配置の乱雑度を評価する Clutter からなる．村上ら [1] は，Sprawlterを遺伝的アルゴリズムの目的関数として設定し，遺伝的アルゴリズムによるレイアウトの最適化手法を提案した．階層型グラフの可読性において Clutter の基準で改善が顕著に見られた．本研究では，村上らの手法を踏襲しつつ，レイアウト手法に複数の異なるアルゴリズムを用いる最適化を試みた．

3

図 1: 処理手順

3.1

遺伝的アルゴリズム: NSGA-II

本手法では，レイアウトの最適化において遺伝的アルゴリズムの一種である NSGA-II[5] を採用する．

3.2

遺伝子の設計

遺伝的アルゴリズムにおいて，遺伝情報を伝える実態を染色体とよび，その形質を決定するコードを遺伝子と呼ぶ．解の候補は染色体で表現され 1 つの個体が1 つの解に対応する．本稿では，メタノードの座標値を遺伝子とし，1 つの個体は 1 つのグラフレイアウトに対応する．メタノード x 座標と y 座標のペアを，交互に 1 次元配列に格納し 1 次元の遺伝子を生成する．

3.3

アルゴリズムの選択適用されるレイアウト手法を選択的に決定するために，本手法では遺伝子に生成元のレイアウト手法を識別するための変数を持たせる．初期集団の生成において，変数には複数のレイアウト手法をそれぞれを同じ確率で設定する．交叉が行われる際には，2 つの遺伝子の識別変数の値が同じ場合はレイアウト手法を変更せず，識別変数の値が異なる場合にはいずれかの値をランダムに設定する．

提案手法

本手法の処理手順を図 1 に示す．本手法では全体的な処理手順は村上ら [1] の手法を踏襲する．階層型グラフのレイアウト手法の部分で，村上らの手法で用いられた階層型グラフレイアウト描画手法 Koala に加え，同じく階層型グラフレイアウト描画手法である

1

4

実行例

4.1

レイアウト最適化結果

4.1.1

Koala のみの場合

村上らの研究 [1] 同様の結果が得られた．

4.1.2

PH のみの場合

村上らの研究とは異なるアルゴリズムである PH を用いて，同様の最適化を実行した．数値上は Sprawl とClutter どちらも一定の改善があったのものの，視覚的にはどちらも改善がほとんど見られなかった．

4.1.3

図 4: 最適化後：（左）レイアウト 9 番，（右）レイアウ

Koala と PH を選択的に用いた場合

ト 13 番

Koala と PH を選択的に用いて最適化を実行した．
最適化の過程として図 2 に初期世代と最終世代の評価値の比較を示す．横軸は Sprawl の評価値，縦軸はClutter の評価値であり，どちらも値が小さいほど 評価は高い．それぞれの点が 1 つの階層型グラフレイア
ウトを示す．赤い点が初期世代， 青い点が最終世代の個体の評価値である．なお，初期世代の番号と該当世代の番号に対応関係はない．
最適化前と最適化後のレイアウトの一例を図 2 に示す．

2 種類のレイアウト手法を組み合わせて最適化を実行した．2 種類のレイアウトを組み合わせた場合，初期集
団を PH でレイアウトしたケースにおいては，Sprawlの基準での改善が顕著であった．今後は村上らの研究[1] の課題であった目的関数の再設計について見直しつ
つ，PH 以外のアルゴリズムを採用し，複数のレイアウト手法の他の組み合わせについて検証したい．

謝辞
本研究にて多くの助言を賜りました伊藤研究室博士
後期 1 年村上綾菜氏に感謝いたします．

参考文献[1] A. Murakami, et al., Optimization of Hierarchical Graph Layout with a Genetic Algorithm andSprawl/Clutter Metrics, 27th International Conference on Information Visualisation, 166-171,2023.
[2] T. Itoh, et al., Key-node-Separated Graph
Clustering and Layout for Human Relationship
Graph Visualization, IEEE Computer Graphics
and Applications, 35(6), 30-40, 2015.
[3] Z. Liu, et al., The Sprawlter Graph Readability
Metric:Combining Sprawl and Area-aware Clutter, IEEE Tramsactions on Visualization andComputer Graphics, 26(6), 2180-2191, 2020.

図 2: 初期世代と最終世代終了後の評価値の比較[4] A. Suh, et al., Persistent Homology Guided
Force-Directed Graph Layouts, in IEEE Transactions on Visualization and Computer Graphics, 26(1), 697-707, 2020.
[5] K. Deb, et al., A Fast and Elitist Multiobjective
Genetic Al- gorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182197, 2002.
図 3: 最適化前：（左）レイアウト 0 番，（右）レイアウ
ト 18 番

5

まとめと今後の展望

本研究では，遺伝的アルゴリズムを用いた階層型グラフのレイアウト最適化の過程において，Koala と PH の2