ネットワークの 3 次元可視化と集合可視化の重ね描きの一手法
佐々日向子

1

(指導教員：伊藤貴之)

はじめにネットワーク可視化が抱えるノードとエッジの描画結果の複雑さを緩和している．しかしこの手法では，ある程度の大規模なネットワークも描画が可能である反面，タグによってノードの配置領域を決定するため，タグの種類が多くなるにつれて視認性を損なうことがある．特に，各ノードに複数のタグが付与されているようなデータセットはこの手法は不向きである．また，この手法は注目ノードをユーザ自身の操作で選択する必要があるため，データの内容についての知識がない
ユーザにはどれが重要なノードなのかをこの可視化からは読み取ることはできない．
伊藤ら [2] による手法は，ネットワークを構成するノードをクラスタリングする際に，多数のエッジを持つ重要なノードを分離させることで，このような重要なノードに着目しやすくする可視化手法である．従来の手法ではネットワークをクラスタリングすることで重要なノードが大きなクラスタに分類され，見つけにくくなってしまうことがあったが，この手法ではあえて重要なノードを独立させることで重要なノードを見つけやすくしている．また，この手法ではノードに特徴量ベクトルが付与されていることを想定し，そのベクトル間距離をクラスタリングに加味することもできる．

ネットワークの可視化は情報科学の幅広い分野への適用が進んでいる．例えばソーシャルネットワークでは，ユーザ間の友人関係が複雑なネットワークを形成している．多くの場合において，それぞれの人物は，職場，親戚，趣味などの多種多様なコミュニティに同時に身を置いている．このコミュニティと友人関係との相関を可視化することで，ソーシャルネットワークの分析に大いに役に立つことが期待される．また，コミュニティの関係を分析することで，ソーシャルネットワークにおける情報の拡散の分析やレコメンド機能の精度の向上に利用できると期待される．
「コミュニティと友人関係」に代表されるネットワー
ク上の「ラベルと接続構造」を可視化するために，本研究では以下の 2 種類の可視化を組み合わせた手法を提案する．

• ネットワークを 3 次元空間に配置して対話的な視点操作とともに可視化する手法．
• ネットワークの接続構造にもとづいたクラスタリングを適用せず，ノードにあらかじめ付与されたラベル情報にもとづいて 2 次元空間上でノードの集合を可視化する手法．

3

ネットワークの接続構造とは独立なラベル情報によって集合を形成し，これとネットワークの接続構造を重ね描きするように表示することで，集合を構成する各ラベルがどのような接続構造につながっているか，といった点を視認できる．なお，提案手法ではノードに複数のラベルを付与できることを想定する．これにより，ノードが複数のコミュニティに属している状況を表現できる．現時点での実装では各集合を単純に凸包で描いているが，集合の可視化手法は多数提案されているので，それらを適用することも可能である．
さらに我々の実装では，ネットワーク中のユーザが注目したい局所を重点的に可視化し，それ以外の集合やエッジの描画を対話的に省略できるようにする．これによって可視化結果を単純化できるので，視認性を維持しやすくなる．このような機能によって，可視化の工程に慣れていないユーザが，特定の集合に関する分布や接続構造との関係を理解しやすくなると考えられる．

2

提案手法

本章では提案手法の処理手順について述べる．本手法の手順は大きく分けて 2 つの段階で構成される．3.1
節ではネットワークの 3 次元可視化について，3.2 節では集合の描画について説明する．

3.1

ネットワークの 3 次元可視化

本手法では与えられたノード，エッジ，ラベルのデータセットからネットワークを構築し，これを 3 次元空間に配置する．本手法では伊藤ら [2] の手法に実装されたクラスタリング手法を適用し，他ノードへの接続が多い重要なノードを他のノード群から距離をおいて配置されるようなクラスタリングを施す．続いて本手法ではネットワークの接続構造からクラスタ間距離を算出し，これに多次元尺度構成法 (MDS: MultiDimensional Scaling) を適用することで各クラスタの3 次元空間上の位置を算出する．
ノードとエッジを描画する際に，全てのエッジを描画するとエッジが絡まり合って視認性を損なうことが多い．そこで我々の現時点での実装では，対話操作によってユーザに指定されたノードに接続されたエッジのみを描画している．

関連研究

タグや特徴量などの追加情報をノードに付与されたネットワークの 2 次元可視化手法は，従来からいくつか提案されている．
Shneiderman ら [1] による手法では，ネットワークの大局的な接続構造を可視化するのではなく，ノードに付与されているタグの種類や数値にもとづいてノードを配置することでネットワークを可視化している．
ユーザの対話的操作によりノードのタグなどを指定することで，興味をもったノード周辺の接続構造のみを描画することを可能にしている．これにより，従来の3.2

集合の描画続いて，特定のラベルを付与されたノードの集合を凸包で表現し，可視化されたネットワーク上に重ねて描画する．現時点での実装では暫定的に，集合の可視化に凸包を適用している．なぜなら本研究ではネットワークの 3 次元可視化結果に対して手動回転操作によって視線方向を制御することを想定しており，回転操作のたびに集合可視化を反復する．そのため，対象とな77るノード数が多くなっても高速に集合を描画できる必要があるからである．現時点での実装では，QuickHullのアルゴリズムにより生成された凸包を描画している．
ここで，全てのラベルに対応する全ての凸包を同時に描画すると，複数の凸包が重なることで視認性が低下することがある．ゆえに現時点での実装では，ユーザが選択した特定の凸包のみを描画することで視認性を維持する．

4

い図 1(左) からはこのノードは重要そうに見えないが，図 2(左) のように視点操作することでこのノードが特異なノードであることがわかる．このように，複数の視点からネットワークを可視化することによって，特異なノードを発見しやすくなる．

実行結果

本手法を Java Development Kit (JDK) により実装した．3 次元ネットワークの配置と描画には伊藤らのKaola[2] のプログラムを再利用した．
本報告では一例として NERC Biomolecular Analysis
Facility (NBAF) 2 の出版書誌に基づいて作られたデータセットを可視化した例を示す．このデータセットは，1821 人の著者をノード，11097 個の共同著者関係をエッジとした論文共著ネットワークである．伊藤ら [2] はこのデータセットに対して，各著者が執筆した論文のタイトルに含まれる頻度の高い 12 個の単語を選択し，それらの各単語の頻度から各ノードについて 12 次元の特徴ベクトルを算出した．そして特徴量ベクトルを構成する 12 個の値のうち最大値となる次元に対応する単語にもとづいて，各ノードに色を割り当てた．本
実験ではこの 12 個の値のうち，一定以上の大きさとなる値の次元に対応する単語をラベルとして扱う．
図 1(左) はラベルの集合を描画する前のネットワー
ク可視化結果である．赤色ノードはピンク色ノードと混ざっており，赤色ノードがどこまで分布しているか視認しにくい．また，この図からは各ノードに対して単一のラベルしか読み取れない．しかし集合可視化を施すと図 1(右) のように，図 1(左) と比べて正しく赤の分布を把握できる．さらにこの凸包の内部にはオレンジ色，ピンク色，水色などのノードが含まれており，赤色に対応する論文の分野がこの 3 色に対応する分野とも深く関係することが示唆される．

図 2: 可視化例 (2)．(左) 視点操作後．(右) 特定のノードに接続されるエッジを描画した例．

5

まとめ

本研究では，凸包を利用してラベルの集合を 3 次元ネットワークの上に描画することで，ネットワークとラベルを同時に可視化する手法を提案した.
今後の課題として，各ノードに複数のラベルを付与する機能が実装できていないので実装したい．複数のラベルを付与し複数の凸包を重ねて表示することで，各ノードが複数の集合に所属していることを明示することができる．さらには，複数の集合にまたがる重要なノードを手掛かりにしてラベル間の関係を視認しやすくなるであろう．これに関連する描画上の工夫として，ノードを単色の円で表現するのではなく，ラベルの帰属度に沿って円グラフ表示する手法を考えている．
これらの機能を実装した後に，多種なデータセットを本手法に適用したい．例として，Twitter などの SNSから取得したデータでネットワークを構築し，人物間の友人関係と所属コミュニティの可視化を実現する方向で実装を進めたい．

参考文献[1] B. Shneiderman, A. Aris, “Network Visualization
by Semantic Substrates,” IEEE Transactions onVisualization and Computer Graphics, Volume12, No. 5, pp. 733 - 740, 2006.
[2] T. Itoh, K. Klein, “Key-node-Separated Graph
Clustering and Layout for Human Relationship
Graph Visualization,” IEEE Computer Graphicsand Applications, Vol. 35, No. 6, pp. 30-40, 2015.
図 1: 可視化例 (1)．(左) 集合可視化の重ね描き前．(右)集合可視化の重ね描き後．
図 2(左) は視点操作によりネットワークを横から見た例である．この例から，ノードの群から離れたオレンジ色のノードがいくつか見られる．視点操作をもとに戻し，このオレンジ色ノードに接続するエッジを描画した例を図 2(右) に示す．エッジが描画されていな78