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

複数のレイアウトアルゴリズムの選択的適用 による階層型グラフのレイアウト最適化 片岡春菜 村上綾菜 伊藤貴之 お茶の水女子大学 お茶の水女子大学 お茶の水女子大学 理学部数学科 大学院人間文化創成科学研究科 理学部情報科学科 1

01 用語の説明 はじめに • グラフとは • 点（ノード）が線（エッジ）で結ばれた図 エッジ ノード 2

01 用語の説明 はじめに • グラフレイアウトとは • 可読性の高いグラフ可視化のために適切なノード配置を算出する手法 • グラフの評価とは • 視認性や可読性が高いかどうかを、ある指標に基づいて評価する • 現時点では汎用的な評価手法は確立されていない 3

01 用語の説明 はじめに • 階層型グラフとは • 複数のノードがクラスタを形成するグラフ メタノード メタノード 4

01 研究背景 はじめに • グラフはレイアウトによって可読性が左右される ① ② ③ 5

01 研究背景 はじめに • グラフはレイアウトによって可読性が左右される ① ② ③ エッジやノードの重なりがある 6

01 研究背景 はじめに • グラフはレイアウトによって可読性が左右される 右の方が交差が少なく見やすい 7

01 研究背景 はじめに • レイアウト手法によって特性は異なる Koala[Itoh15] 重要なノードを強調して視認性を高める PH [Suh20] ノード同士の重なりが一切ない 8

01 研究背景 はじめに • それぞれのレイアウト手法には異なる特性がある • データによって相性の良い手法が異なる 複数の手法を組み合わせれば 汎用的で視認性の高い レイアウトが得られるのでは 階層型グラフの可読性の向上 9

02 Sprawlter[Liu20] 関連研究 overview • 階層型グラフ可視化のための数値評価指標 • SprawlとClutterの値が小さい方が好ましいグラフ Sprawlter = Sprawl × Clutter ノードとノード ノードとエッジ エッジとエッジ 「Sprawl」 空間の浪費を評価 「Clutter」 配置の乱雑度を評価 Sprawl = area(G) / area(ΣG) Clutter = αNN + βNE + γEE 12

02 階層型グラフのレイアウト最適化[村上23] 関連研究 overview 配置手法 ： Koala 最適化手法 ： NSGA-II 目的関数 ： Sprawlter ・遺伝的アルゴリズムによるレイアウトの最適化 ・レイアウトを一次元配列の遺伝子として扱う • • • • Koala のレイアウト描画を遺伝子とする いくつかのレイアウトを生成 遺伝的アルゴリズムでレイアウトを最適化 Sprawlterを目的関数とした多目的最適化問題とし て扱う • 階層型グラフレイアウト群の中から任意の階層型 グラフレイアウトを選択 最適化前 最適化後 13

02 階層型グラフのレイアウト最適化[村上23] 関連研究 overview ・処理手順 ・遺伝的アルゴリズムによる最適化について 遺伝子 グラフのレイアウトの座標を 1次元配列の遺伝子として扱う 遺伝的アルゴリズム による最適化 遺伝子操作 14

03 提案手法 提案手法 • グラフはレイアウトによって可読性が左右される • それぞれのレイアウト手法には異なる特性がある 階層型グラフの可読性の向上 • 2つの配置手法アルゴリズムを選択的に実行 • それらを遺伝的アルゴリズムを用いて最適化 • 最適化の目的関数にはSprawlterを用いる 15

03 提案手法 提案手法 KoalaとPHの性質の違い Koala [Itoh15] 重要なノードを強調して視認性を高める PH [Suh20] ノード同士の重なりが一切ない 16

03 提案手法 提案手法 開 始 遺伝子は各ノードの 座標の初期値 アルゴリズム を選択 2つのレイアウト アルゴリズムを使う Koalaで生成 PHで生成 Sprawlterで評価 終了条件 NO 次世代の 遺伝子を生成 YES 終 了 17

03 提案手法 提案手法 遺伝子のデータ構造 先行研究： values : [5.1,-2.3, 3.5, -1.7, 2.9, -0.1, 1.1, -0.9, 0.7, -0.5] レイアウトの座標データ 本研究： values : [5.1,-2.3, 3.5, -1.7, 2.9, -0.1, 1.1, -0.9, 0.7, -0.5] method : 1 親情報 ※1がKoala，2がPHとしている 18

03 提案手法 提案手法 選択的に使いたい理由 同じ配置を親から子に繋いだ方が、各レイアウト手法に とって望ましい初期位置になるため 親 Koala Koala PH PH Koala PH 子 Koala Koala PH PH ランダム ランダム 19

02 階層型グラフのレイアウト最適化[村上23] 関連研究 • Clutter(配置の乱雑度)で改善が顕著に見られた • Sprawl(空間の浪費)では数値上改善が見られるが、視覚的な差異はほとんど無い 最適化前はノードが 重なっている 最適化後は重なりが 解消されている 最適化前 最適化後 20

04 ② PHのみ 実行結果 • 最適化前からノード間の重なりが一切無い • 代わりにノードとエッジの重なりが非常に多い • 数値上はSprawlとClutterどちらも一定の改善があるが、視覚的には改善があまり見られ ない ▲ エッジの重なりが 非常に多い 最適化前 最適化後 21

04 Koala & PHを選択的に 実行結果 空間の浪費 初期世代と最終世代終了後の評価値の比較 重なり 最適化途中 Sprawl，Clutterの値が 小さくなっている 最適化後 22

04 Koala & PHを選択的に 実行結果 最適化前 ▲ ノードが 重なっている 最適化前（レイアウト0番） 最適化前（レイアウト18番） 23

04 Koala & PHを選択的に 実行結果 最適化後 最適化後（レイアウト9番） 最適化後（レイアウト13番） 24

05 考察 まとめ • 考察 • Koala単体ではClutterでの改善が顕著に見られた • （PH単体では視覚的には改善があまり見られなかった） • 組み合わせた場合 • Koalaの遺伝子が強いケースではClutterの基準で改善 • PHの遺伝子が強いケースではSprawlの基準で悪化 25

05 まとめ・今後の課題 まとめ • まとめ • Sprawlterによる評価を用いたレイアウト最適化の改良 • KoalaとPH, 2つのレイアウト手法の組み合わせ • レイアウト手法の選択的な決定 • 今後の課題 • 目的関数の再設計（先行研究で残っている課題） • 他のアルゴリズムも採用し、組合せについての検証 26