DEIM Forum 2017 E2-3

エッジの合流を用いた有向グラフ可視化手法
十枝菜穂子†

中澤 里奈†

伊藤 貴之†

齋藤 隆文††† お茶の水女子大学大学院人間文化創成科学研究科 〒 112-0012 東京都文京区大塚 2-1-1†† 東京農工大学大学院生物システム応用科学研究科 〒 183-0057 東京都府中市晴見町 3-8-1
E-mail: †{toeda,leena}@itolab.is.ocha.ac.jp, ††itot@is.ocha.ac.jp, †††txsaito@cc.tuat.ac.jp
あらまし 有向グラフによって論文の参照関係や SNS 上の人間関係などのデータが表現されるが，これらのデータは情報量が膨大になることが多い．そのため大規模な有向グラフデータの全体の構造を短時間で理解するための可視化手法は有用である．その一手法として，ノードに対してクラスタリングを適用し，接続するクラスタが同じ束同士を合流させる形で描画することでクラスタ間同士の関係を曖昧性なく表示する手法が提案されている. 本報告ではこの手法をもとに，3 本以上の束の合流に適するように合流する束群を選択するアルゴリズムや，より多くの束を合流させるためのノード配置アルゴリズムを適用させた有向グラフ可視化手法について提案する．
キーワード 可視化, グラフ可視化, 有向グラフ, エッジバンドリング, ノード配置, クラスタリング

1. 概要

2. 関 連 研 究

SNS 上の人間関係や論文の参照関係などのさまざまなデータ

グラフ可視化におけるエッジのバンドリング（束化）とは，が，ノードとそれを連結し方向を持つエッジから構成される有近隣するノードを接続する複数のエッジが束として可視化され向グラフで表現される．これらのデータは情報量の規模が大きるように変形または統合する処理を指す．Holten は，同一クラく，さらに日々情報量が増加したり内容が変化したりする性質

スタペアに属する 2 ノードを連結するエッジ群をバンドリングをもつものが多い．そのため，このようなグラフ構造の全体像することでクラスタ間の関係性を強調する手法 [2] を提案してをユーザが短時間で把握できるように可視化することは有用でいる．Selassie らの手法 [3] や Holten らの手法 [4]，Ersoy らのある．

手法 [5] でも向きと距離が近いエッジをバンドリングすること

グラフ可視化の手法として，2 本以上の近接するエッジを近でグラフ全体の特徴を概観することが可能である．しかしこれづけて描画するバンドリング (束化) が広く用いられる．しからの手法ではエッジをその中央付近で合流させており，エッジし初期の多くのバンドリング手法は，エッジ群をその中央付近の両端付近には処理を施していない．そのため，各エッジの両で束ねており，両端におけるノードとの接続関係に関する視認端で接続するノード付近の視認性に関する問題は改善されない．

性を改善していない．それに対して，エッジが両端で接続する

これに対し，エッジの両端における接続関係の読み取りに曖ノード（またはノードのクラスタ）付近でエッジ束を合流させ昧性を生じさせない手法も提案されている．Luo らの手法 [6]る形で表現することで，束の接続先に関する視認性を改善する

ではエッジをその両端（特定のノードの近く）でバンドリング手法も提案されている．我々は，このようにエッジ束を両端付することで曖昧性を排除している．また，Bach らの手法 [7] で近で合流させる描画手法を，大規模な有向グラフデータに適用は共通して接続しているエッジのみを合流させることでエッジさせた可視化手法 [1] を提案した．この手法では，まずノードの曖昧性を排除している．しかし，これらの手法は無向グラフをクラスタリングし，クラスタごとにノードを配置した後になを対象としており，またノードのクラスタリングを前提としてす角が小さい束を合流させている．これにより，エッジ束の接おらず大規模なデータに適用することは困難である．

続先の読み取りの曖昧性を排除した上でエッジの描画面積を削減している．
本報告では，この手法をより多くの束を合流させることを目

また，Bach らの手法 [7] では，エッジを描画する前に，合流させることができるエッジ同士を近づけるためダミーノードを用いてノードを配置をしている．

的として改良した可視化手法について提案する．具体的には，これらの先行研究に対して我々の可視化手法 [1] では，ノー合流する束を選択する手法について，双方向に接続される束がドがクラスタリングされた大規模有向グラフに対し，合流する3 本以上隣り合っている場合に逆方向に接続されている束と交エッジの選択手法の改良およびダミーノードを用いたノード配差することを許すように変更した．また，同一クラスタに接続置によって，エッジの両端における接続関係の読み取りに曖昧する 2 つ以上のクラスタを近くに配置するために，ノード配置性を生じさせないグラフ描画を実現している．本報告はこの可アルゴリズムを適用する前にダミーノードを生成している．ま

視化手法の改良手法を提案するものである．なお，この手法は，た，本手法を論文の参照関係データに適用した実行例について重要なノードが大きなクラスタに埋もれないようなノードクラも議論する．

スタリング手法を適用した無向グラフ可視化手法 Koala [8] を拡張する形で実装されている．

3. 提 案 手 法
本章では本手法の提案手法について，データ構造および処理手順について説明する．

によって特徴量ベクタに基づくノード間距離 dvec を算出する．
隣接ノードの共通性に基づくノード間距離ノードの両方にエッジで接続されている隣接ノードの個数をnadj とする．この値を用いて3. 1 データ構造提案手法では入力データとしてノードの集合 N とエッジの集合 E からなる有向グラフ G を想定する．また本研究ではノードの接続性だけでなく任意の数値属性を加味してグラフ配置を実現できるようにするために，各ノードに対して多次元ベクタとなる特徴量を付与できるものとする．

G = {N, E}
N = {n1 , ..., nNn }E = {e1 , ..., eNe }ni = {ai1 , ..., aiN a }ei = {ni , nk }3. 2 ノードクラスタリング
提案手法では任意の 2 ノード間の距離を算出し，その距離に基づいてノードをクラスタリングする．以下にノード間距離の算出，ノードのクラスタリングそれぞれについて述べる．

3. 2. 1 ノード間距離の算出
本手法では任意の 2 ノード間の距離 d を

dvec ：特徴量ベクタに基づくノード間距離
dadj ：隣接ノードの共通性に基づくノード間距離により算出する [8]．以下に 2 種類の距離の定義を述べる．
特徴量ベクタに基づくノード間距離
各ノードに付与された特徴量ベクタを ai および aj とした
とき，inner =ni · nj|ni ||nj |により特徴量ベクタの内積 inner を求め，この値を用いて以下の式

dadj =

1.0
1 + nadj

によって隣接ノードの共通性に基づくノード間距離 dadj を算出する．

3. 2. 2 クラスタリング
提案手法では階層のないクラスタ群と 2 階層のクラスタ群を同時に生成するために，以下の手順によってクラスタリングする．
（ 1 ） 最長距離法に基づく階層型クラスタリングにより，閾値 α までノードをクラスタリングする．これを今後クラスタ群A とする．
（ 2 ） クラスタ群 A の情報を保持したまま閾値 β (α < β)までクラスタリングを続ける．
以上の処理により，クラスタ群 A のクラスタを内部に持つ二階層のクラスタ群ができる．これをクラスタ群 B とする．

3. 3 ノード配置提案手法では，クラスタごとにノードを配置するため，以下のアルゴルズムにより各ノードの配置場所を決定する．階層をもたないクラスタ群 A の場合のアルゴリズムと階層をもつクラスタ群 B の場合のそれぞれについて述べる．
階層をもたないクラスタ群 A の場合
以下のアルゴリズムによりノードの配置場所を決定する．
（ 1 ） クラスタをノードに置き換えたグラフを生成する．このとき，各クラスタペアを接続するエッジ束を構成する本数にもとづいて，生成するグラフのエッジに重みをつける．
（ 2 ） 生成されたグラフに対し，後述するグラフ配置アルゴリズムを適用する．現時点では後述する配置アルゴリズム，またはエッジにバネの力学モデルを適用した Spring-force モデルによる配置計算方法を適用する．

dvec = 1.0 − inner（ 3 ） 各クラスタのノード数からクラスタ半径を計算し，エッジ長が両端のクラスタの半径の合計値にできるだけ近づくようにスムージング処理を適用する．
（ 4 ） クラスタ内にそのクラスタを構成するノードを配置する．
エッジ合流のためのノード配置アルゴリズム
本手法では上記のアルゴリズムの 2 ステップ目で、エッジにバネの力学モデルを適用した Spring-force モデルによる配置計

図1

提案手法を用いたノード配置の一例

算方法を適用する．同一クラスタに接続する 2 つ以上のクラスタが近くに配置された場合にエッジを合流できることから (図

NyNy'

Ny'

NxNz'
図 2 提案手法によるダミーノード生成の一例

NyNr NxNz

NbNz'

図 3 ノード配置のためのダミーノード生成手法

Nz

Cx

CxCx

CyCyCyCx'

A. Edges between
two clusters of edges

Cx'
Cy'

Cw

Cy'

Cw

Cw

Cz

CzCaCzCaCa

図 5 合流するエッジ群の選択

B. Edges of pairs bidirectionalbundles connecting to thesame pair of clusters

CxCxCyPx
Py

Cy

C. Edges of pairs of bundles
start or end at same cluster

図4

エッジ描画の条件

Ca1)，本手法では以下の 3 つのアルゴリズムのうちいずれかを適Ca用する．
図 6 エッジ合流の評価値の算出（ 1 ） Spring-force モデルによる配置計算方法を適用する．
（ 2 ） 以下の手順を実行する (図 2(左)):（ a ） 任意のノード Nx を選ぶ (図 3).

をノードに置き換えたグラフを生成し，上記のエッジ合流のた（ b ） Nx が 1 つ以上のノードを参照している場合，以下のめのノード配置アルゴリズムを適用する．この大クラスタの半手順を実行する．

径は一定とする．

i. 青いダミーノードを生成する (Nb ).

（ 2 ） 各大クラスタ内部について小クラスタをノードとした

ii. Nb から，Nx が参照しているノードへ接続するエッジグラフを生成し，これに対してエッジ合流のためのノード配置(Nb Ny , Nb Nz ) を生成する．
iii. Nx から他のノードへ接続されるエッジ (Nx Ny ，Nx Nz )を削除する．

iv. Nx から Nb へ接続するエッジを生成する.

アルゴリズムを適用する．
（ 3 ） 各小クラスタのノード数からクラスタ半径を計算する．
（ 4 ） 小クラスタの半径に合わせたスムージング処理を適用
する．

（ c ） Nx が 1 つ以上のノードから参照されている場合，以（ 5 ） 各小クラスタ内にそのクラスタを構成するノードを配下の手順を実行する．

置する．

i. 赤いダミーノードを生成する (Nr ).

3. 4 エッジ描画

ii. Nx が接続しているノードから Nr へ接続するエッジ提案手法では図 4 の 3 つの条件を満たすエッジ描画を目標と(Ny′ Nr ，Nz′ Nr ) を生成する.
iii. 他のノードから Nx へ接続されているエッジ (Ny′ Nx ，Nz′ Nx ) を削除する.

する．このうち条件 A は従来のバンドリング手法と同じ目標であり，条件 B は有向グラフ描画のために条件 A を拡張したものである．条件 C を満たすために提案手法では，まず合流するiv. Nr から Na へ接続するエッジを生成する.

エッジ束を選択する．続いて，各エッジの条件に合わせて曲線（ d ） 上記の手順を全てのノードに対して繰り返す，を描画する．以下，合流するエッジ束の選択手法，曲線の描画（ e ） 上記の手順によって生成されたグラフに対し Spring-手法のそれぞれについて述べる．

force モデルによる配置計算方法を適用する．

有向グラフの描画においてエッジの向きの表現方法の選択は（ f ） 上記の手順で削除されたエッジを再度生成する．

重要である．Holten らが発表したユーザ評価 [9] では，ノード（ g ） 青および赤のダミーノードとそれと接続しているエッ数およびエッジ数の少ない単純なグラフ以外において，エッジジを削除する．の終点側にマークをつける表現はグラフの可読性を下げる，と（ 3 ） 各ノード Nx が 2 つ以上のエッジと接続されている際結論づけられている．そのため現在の我々の実装では，エッジにダミーノードを生成すると条件を変え上記のアルゴリズムをの描画に矢印などのマークを用いずに，青から赤のグラデー適用する (図 2 (右)).

ションで曲線を描画することによってエッジの向きを表現して階層をもつクラスタ群 B の場合クラスタ群 A の場合のアルゴリズムを拡張した以下のアルゴリズムによりノードの配置場所を決定する．

いる．

3. 4. 1 合流するエッジ束の選択手法
提案手法では以下のアルゴリズムによって合流するエッジ束（ 1 ） 小さいクラスタ (以下小クラスタとする) を内包するを選択する (図 5)．

大きなクラスタ (以下大クラスタとする) 群に対して，クラスタ（ 1 ） 1 つのクラスタを取り出す (Ca )．
（ 2 ） 時計回りに 1 つずつエッジ束を参照する (Cy )．

CxbBPxBCxyy

P1P3Cz

C'abCabP2Cy'PaCaPa

図 8 Bezier 曲線の制御点の決定手法

図 7 双方向の束の向きの決定

Pa（ 3 ） 左隣のエッジ束 (Cx ) を参照する．Cy と Cx に同じ向きのエッジが含まれている場合，2 つのベクトル Ca Cy ，Ca CxPa
P4から合流する価値があるかどうかの評価値を以下の (a)〜(c) にP4より算出する (図 5 (左))．評価値の算出方法については後述す

Ca'Pa'Cb'
P5Pb'

る．また，この評価値が閾値より高い場合には以下の (d)(e) を実行する．
（ a ） Ca と Cx および Cy がそれぞれ Ca と他のクラスタをP5接続している束と合流している場合，それらのクラスタ群の重心を算出する (Cx′ ，Cy′ )．

Pb（ b ） Cx と Cy の両方に Ca へ接続している束が存在していPb

る場合，その 2 つの束 (Cx Ca ，Cy′ Ca ) の間の評価値を算出す
る (図 5 (中央))．この評価値を Sa とする．

図 9 Bezier 曲線の制御点の決定手法（ c ） Ca から Cx に接続する束と Cy に接続する束の両方が存在する場合，その 2 つの束 (Ca Cx′ ，Ca Cy ) の間の評価値を計算する．

算出する (図 5 (右))．この評価値を Sb とする．

（ 3 ） α > β の場合，束 Ca Cx は右回りに描画すると設定す（ d ） Sa > Sb の場合，Ca に接続する 2 本の束を合流させる．α < β の場合は左回りに描画すると設定する．.

るように設定する．
（ e ） Sb > Sa の場合，Ca から接続する 2 本の束を合流させるように設定する．
（ 4 ） 全ての束およびクラスタに対して同じ処理を適用する．
ここで評価値の算出は以下の 2 つの評価方法から算出する．
エッジ束の角度2 本のエッジ束がなす角度が閾値よりも大きい場合は，これらが合流されないように評価値を 0 とする (図 6 左)．
合流できる部分の長さ2 本のエッジ束の角度の二等分線 (Ca Px ) に両クラスタから

3. 4. 3 エッジの曲線描画手法
本手法では全てのエッジを以下の 3 パターンに分類し，それぞれの曲線を Bezier 曲線によって描画する．
他の束と合流するエッジ

2 本のエッジの垂直二等分線上に Bezier 曲線の制御点 (P1 )を設定する (図 8(左))．
他の束と合流はしないが双方向に伸びているエッジ

2 つのクラスタ間の垂直二等分線上に Bezier 曲線の制御点(P2 ，P3 ) を設定する (図 8(右))．
その他のエッジ垂線を伸ばし，その交点と基準となるクラスタとの距離のうち以下の a または b によって制御点 (P4 ,P5 ) を決定する [8]．

短い方の長さ (Ca Py ) を評価値とする (図 6 右)．

（ 1 ） クラスタの中心点を連結する線分上の 2 点を制御点と3. 4. 2 双方向に接続される束の向きの決定する (図 9(左))．

本手法では，他の束と合流はしないが双方向に伸びている束（ 2 ） 2 ノードを連結する線分とクラスタの中心点を連結す

Ca Cx それぞれについて以下の手順を実行し，描画の向きを決る線分について，それぞれを 3 分割した点を生成し，これらの定する (図 7).

点を連結する線分上に 2 点の制御点を生成する (図 9(右))．

（ 1 ） Ca Cx とその右隣の束 (Ca Cz ) の角度 β ′ を計算する．

Ca Cx と Ca Cz の向きが逆の場合，β ′ の半分の値 β を計算する.

4. 適 用 事 例（ 2 ） Ca Cx とその左隣の束 (Ca Cy ) の角度 α′ を計算する．

本章では適用事例として，1990 から 94 年，2000 から 2010

Ca Cx と Ca Cy の向きが逆の場合，α′ の半分の値 α = 0.5α′ を年までに ACM SIGGRAPH で発表された論文に対して，論文

be

図 10 提案手法による可視化例bcをノード，参照関係をエッジとしたグラフを可視化した事例 [10]を示す．このグラフにおいてノード (論文) は 1072 個，エッジd(参照関係) は 5498 本であった．また本事例では LDA (LatentDirichlet Allocation) を適用して論文群から 10 個のトピック

図 11 (上) 提案手法による可視化例 (下) クラスタ b 付近の拡大図を抽出した。このトピックを 10 の研究分野とみなし、各論文がそれぞれ各研究分野にどの程度当てはまるかを算出し，その参照関係から，クラスタ b の論文の内容が，さまざまな分野に結果を各論文に対する 10 次元の特徴量として用いた．

適用される汎用的な内容であると読み取ることができる．

また本事例では，10 個の次元の各々に固有の色を割り当て，各論文について 10 次元の特徴量の中で最も値の高い次元に対応した色で各ノードを描画した．

4. 1 クラスタ群 A を用いた可視化例

4. 3 エッジ描画の条件についての考察
図 12 は本手法による可視化結果の一部を拡大したものである．
双方向のエッジ束に対する描画 (図 4 条件 B) のみを適用し

図 10 はクラスタ群 A(非階層型) を用いた可視化結果の一例

た場合 (図 12 左) には，クラスタ D からクラスタ A へ接続すである．クラスタ a に接続されているエッジがバンドリングるエッジ束とクラスタ C からクラスタ D へ接続するエッジ束され太い束になっており，このクラスタの論文が多数の論文かが重なって描画されてしまう．また，起点・終点のクラスタがら参照されていることを読み取ることができる．しかし，他の共通するエッジ束どうし合流させる描画 (図 4 条件 C) のみをエッジが太い束に重なって描画されてしまっている．ユーザの適用した場合 (図 12 右) には，クラスタ A からクラスタ D に操作によってエッジが動くことで構造を理解することが可能と接続するエッジ束とその逆方向のエッジ束が重なって描画されなっているが，最適な曲線の描画をユーザ操作ではなく自動でてしまう．一方，両方のエッジ描画を同時に適用させると (図推定する手法が必要である．

4 中央)，全てのエッジ束が重なることなく表示される．

4. 2 クラスタ群 B を用いた可視化例
図 11 はクラスタ群 B(階層型) を用いた可視化結果の一例で5. まとめと今後の課題ある．多くのクラスタが同分野 (同色) のクラスタとの参照関係

本報告では，ノード配置と合流する束の選択手法の改善にで結ばれている中，テクスチャの自動生成・自動加工に関するよって，より多くのエッジどうしの合流を可能とする有向グラ

論文のクラスタ b が他の多くの分野のノードから参照されていフのエッジ描画手法を提案した．本手法では，誤読の可能性をることを読み取れる．レンダリング分野である c では，3D モ排除しながらクラスタ間の関係性を概観することを可能とし，デルに貼り付けるテクスチャの生成のために，クラスタ b で提さらに多くのエッジどうしの合流を行うことで重要なクラスタ案されたテクスチャ生成が用いられている．また，テクスチャ・の発見を容易にしたと考えられる．

形状特徴分野の d や形状処理・変形分野の e では，画像補完に今後の課題として，ノード配置の際のダミーノードの生成手使うテクスチャの生成や 3D モデルに貼り付けるテクスチャの順について再検討したい．また，合流する価値のあるエッジ束生成のために，クラスタ b の技術が用いられている．これらのの組み合わせの選出方法，およびその組み合わせを合流して描画するために適切なノード配置手法について検討したい．さらAAABCBCDBCDD

図 12 提案手法による可視化例の一部の拡大図に，エッジの曲線の制御点それぞれについて最適な位置を自動算出する手法についても再検討の余地がある．

文献[1] 有向グラフ可視化のためのバンドリングとノード配置，十枝 菜穂子, 中澤 里奈, 伊藤 貴之, 齋藤 隆文, 第 8 回データ工学と情報マネジメントに関するフォーラム (DEIM 2016)，2016[2] Danny Holten, Hierarchical Edge Bundles: Visualizationof Adjacency Relations in Hierarchical Data , IEEE Trans.
on Visualization and Computer Graphics, Vol. 12, No. 5,
pp. 741-748, 2006
[3] David Selassie, Brandon Heller and Jeﬀrey Heer, Divided
Edge Bundling for Directional Network Data , IEEE Trans.
on Visualization and Computer Graphics, Vol. 17, No. 12,
pp. 2354-2363, 2011[4] Danny Holten, Jarke J. van Wijk, Force-Directed Edge
Bundling for Graph Visualization , Computer Graphics Forum, Vol. 28. No. 3. Blackwell Publishing Ltd, 2009[5] Ozan Ersoy, Christophe Hurter, Fernando V Paulovich,
Gabriel Cantareira, Alexandru Telea, Skeleton-based edge
bundling for graph visualization , IEEE Trans. on Visualization and Computer Graphics, Vol. 17, No. 12, pp. 23642373, 2011[6] Sheng-Jie Luo, Chun-Liang Liu, Bing-Yu Chen, Member, IEEE, and Kwan-Liu Ma, Senior Member, IEEE,
Ambiguity-Free Edge-Bundling for Interactive Graph Visualization , IEEE Trans. on Visualization and Computer
Graphics, Vo.18, No. 5, pp. 810-821, 2011[7] Benjamin Bach, Nathalie Henry Riche, Christophe Hurter,
Kim Marriott, Tim Dwyer, ”Towards Unam- biguous Edge
Bundling: Investigating Confluent Drawings for Network
Vi- sualization”, IEEE Trans. on Visualization and Computer Graphics, 2016.
[8] T. Itoh, K. Klein, Key-node-Separated Graph Clusteringand Layout for Human Relationship Graph Visualization ,IEEE Computer Graphics and Applications, Vol. 35, No. 6,
pp. 30-40, 2015[9] Danny Holten, Jarke J. van Wijk, ”A User Study on Visualizing Directed Edges in Graphs”, In Proceedings of theSIGCHI Conference on Human Factors in Computing Systems, pp. 2299-2308, 2009.
[10] R. Nakazawa, T. Itoh, T. Saito, A Visualization of Research Papers Based on the Topics and Citation Network ,18th International Conference on Information Visualisation(IV2015), pp. 283-289, 2015.