複数のレイアウトアルゴリズムの選択的適用 による階層型グラフのレイアウト最適化 | ポスター

複数のアルゴリズムによる階層型グラフのレイアウト最適化 片岡春菜 村上綾菜 伊藤貴之 お茶の水女子大学 1. 研究背景 3. 結果 • グラフはレイアウトによって可読性が左右される • それぞれの配置手法には異なる特性がある 複数の手法を組み合わせれば 汎用的で視認性の高い レイアウトが得られるのでは Koala • Clutter(配置の乱雑度)で改善が顕著に見られた • Sprawl(空間の浪費)では数値上改善が見られるが、 視覚的な差異はほとんど無い 最適化前はノードが 重なっている 階層型グラフの可読性の向上 先行研究 最適化後は重なりが 解消されている ✓ 村上綾菜, 階層型グラフのレイアウト最適化, 2022 Koala によるレイアウト描画を反復し、 複数の階層型グラフレイアウトを生成、 それらに遺伝的アルゴリズムを適用し､レイアウトの最適解を探索 Sprawlterをレイアウトの評価に採用して最適化を行い、 最終的に解として得られた階層型グラフレイアウト群の中から 任意の階層型グラフレイアウトを選択 ◼ ◼ ◼ 配置手法 最適化手法 目的関数 Koala & PH • Koalaの遺伝子が強いケースではClutterの基準で改善 • PHの遺伝子が強いケースではSprawlの基準で悪化 → Koalaのみ → 遺伝的アルゴリズムNSGA-II → Sprawlter Koalaによるグラフの例 「Sprawlter」 階層型グラフ可視化のための数値評価手法 SprawlとClutterの値が小さい方が良いグラフ レイアウト0番 ノードとノード ノードとエッジ レイアウト18番 エッジとエッジ 最適化後 「Sprawl」 空間の浪費を評価 「Clutter」 配置の乱雑度を評価 2. 研究概要 • 2つの配置手法アルゴリズムを選択的に実行 • それらを遺伝的アルゴリズムを用いて最適化 • 最適化の目的関数にはSprawlterを用いる レイアウト9番 レイアウト9番 2つの レイアウト アルゴリズム を使う 4. 考察 • Koala単体ではClutterでの改善が顕著に見られた • （PH単体では視覚的には改善があまり見られなかった） • 組み合わせた場合 • Koalaの遺伝子が強いケースではClutterの基準で改善 • PHの遺伝子が強いケースではSprawlの基準で悪化 5. 今後の課題 • まとめ • Sprawlterによる評価を用いたレイアウト最適化の改良 • KoalaとPH, 2つのレイアウト手法の組み合わせ • レイアウト手法の選択的な決定 • 今後の課題 • 目的関数の再設計（先行研究で残っている課題） • 他のアルゴリズムも採用し、組合せについての検証 レイアウト13番