ネットワークの可視化技術
──大規模ネットワークと動的ネットワークへの挑戦──
Visualization Techniques for Networks ： The Challenges toLarge scale Networks and Dynamic Networks

三末和男

情報のはん濫が深刻になる一方で，大量の情報を理解し操作することへの期待は高い．情報可視化はこのような期待
情報のはん濫が深刻ににこたえる技術である．本稿ではネットワーク情報を連結図として描く技術について解説する．ネットワーク可視化のにこたえる技術である．
枠組みと基本技術を説明するとともに，特に大規模なネットワークの可視化技術及び動的に変化するネットワークの可視化技術に焦点を絞り，最近の研究成果を織り交ぜて説明する．
キーワード：情報可視化，ネットワーク情報，大規模ネットワーク，動的ネットワーク，グラフ描画

は

じ

め

以下の章では，まず情報可視化に関連する要素技術にについて背景説明を行う．その後の章で大規模ネットワー

図 （ ）はインターネットの様子を視覚的に描いたもの

クの可視化技術を要素技術に沿って解説する．

である．本稿ではこのような「ネットワーク情報」を「点と線で構成される図（連結図）」として描く技術について解説する．
ネットワーク情報は至る所で見られることから，様々

ネットワーク可視化技術の基礎
本稿でいうネットワーク情報とは「グラフ」によってなものが可視化の対象となり得る．古くから対象とされ抽象化できる情報である．グラフとはノードの集合ているものにファイル階層，組織階層，分類階層などがとエッジの集合

ある．プログラム構造なども古くからある描画対象であ書かれることが多い．

からなる組で，
は

上の

（

）のように

項関係として表さ

年代に入り WWW が広まると， Web のリン

れる．ノードやエッジは応用領域においてそれぞれ意味

ク構造なども可視化の対象に加わるとともに，対象の規を持つが，抽象化されたグラフにおいては具体的な意味

模もにわかに拡大した．最近では可視化研究自体が各応は特に問題にしない．ただしノードやエッジに重みを持用領域に分散しているようである．主要な国際会議の予たせる（実数値を割り当てる）ことはしばしば行われる．

る．

稿集を眺めたところ，ソーシャルネットワーク，ナレッ
ジネットワーク，及びバイオネットワークなどを対象と表現形式
情報を視覚的に表現するための形式としては様々なもした研究が活発と見受けられる．
本稿では大規模ネットワークと動的ネットワークに関のがあるが，一般的に用いられる表現形式は領域系，連連する技術に焦点を絞って説明したい．応用領域におけ

結系，配列系，座標系の四つの基本系に分類することがる期待を考えると，今後ますます巨大化する大規模なできる（ ）．ネットワークの視覚的な表現には，連結系（注 ）ネットワークを描く技術，また日々ダイナミックに変化（「網図系」と呼ばれることもある）が用いられることがするネットワークを表現する技術が重要であると考えら多い．連結系は，「ノード」と呼ばれる一つ以上の点（まれるからである．

たは図形や文字）と，それらをつなぐ「リンク」（グラフの用語では「エッジ」）と呼ばれる線分から構成される．

三末和男 正員 筑波大学大学院システム情報工学研究科コンピュータサイエン
ス専攻E mail misue＠cs tsukuba ac jp
Kazuo MISUE Member（Gr aduate School of Systems and Infor mation Engineer
ing Univer sity of Tsukuba Tsukuba shi
Japan）．

電子情報通信学会誌 Vol

No

pp

年

月

連結系の表現は，更に二次元平面上（あるいは三次元（注 ） 英文論文では node link diagr am や node link r epr esentationと呼ばれることが多い．

電子情報通信学会誌 VolNo

図Autonomous System Level のインターネットトポロジーを可視化したもの（ ）の空間上）でのノードの配置の仕方やエッジの配線の仕用されている．

方によって，様々な表現形式に分けることができる．例

力指向アルゴリズムは Eades によるスプリングモデ

えば，ノードの配置に制約を課さずエッジを直線分で描（ ）ル に端を発する．スプリングモデルでは，無向グラフ

く自由配置，ノードを直交格子の交点に配置しエッジをのノードをリング，エッジをスプリングとみなし，リン

格子に沿った折れ線として描く直交配置，ノードを（水グにかかるスプリングの力が最小になるようなノードの平な）平行線上に配置し（向きのある）エッジを下向き配置（安定状態）を求める．エッジはノードを接続するの折れ線または曲線として描く階層配置などが広く用い直線分として描かれるため，ノードの配置が決定すればられている．

グラフのレイアウトは完了である．スプリングモデルと計算機によって可視化するためには，表現形式ごとに称するもののフックの法則を満たすものではなく，仮想描画の規約を定めるとともに，美しさや読みやすさを明的な力が導入されている．実際には隣接する（エッジで確にしておく必要がある．例えば，ノードを点で表す，

つながっている）ノード間に働くスプリングの力と，隣エッジをノードに接続した折れ線で表すといった規約

接しないノード間に働く反発力が利用される．

は，これらが満足されなければ情報が読み手に正しく伝安定状態の求め方として， Eades は合力の向きに個々

わらないため，必ず満足する必要がある．これらに加えのノードを徐々に移動させ安定状態に近づける手法を採て，エッジの交差を避ける，
エッジの長さをそろえる，（対用した．つまり，適当な（ランダムな）ノードの初期配称性がある場合には）対称に配置するといった基準は，置から開始して，各時点でノードに働く合力を計算し，視覚的な表現を読み取りやすくするために重要なものでその力の向きに少しだけノードを移動させるという処理あり，美的基準あるいは可読性基準と呼ばれる．

を繰り返すものである．
結果として計算は余り速くない．
スプリングモデルで，ある瞬間における力の計算量を描画技術
ネットワーク情報の描画技術はグラフのレイアウト技

考えると，スプリングの力による合力は （）で計算できるのに対して，反発力による合力は，ノードのすべ術として発展してきた．これまでにも多くのグラフレイての組に対して計算する必要があり， （アウト技術が開発されているが，その中でも無向グラフ

を必要とする．完全グラフ（すべてのノードの組の間にを描画対象として自由配置を行うための力指向アルゴリ

エッジが存在するグラフ）であれば，その計算量は同じ

ズムが特に有名であり，実装と拡張の容易さから広く利になるが，多くのグラフは完全グラフに比べるとはるか

解説

ネットワークの可視化技術──大規模ネットワークと動的ネットワークへの挑戦──）の計算量

にエッジが少ないため，反発力の計算量が全体の計算量

るレイアウトアルゴリズムの違いによりいろいろな手法に大きな影響を与えることになる．

が提案されており，計算速度や描画の質もそれぞれ異なEades によるスプリングモデルの提案に続いて，現在まで数多くの改良手法が提案されてきた． Fr uchter man

る．これらの手法の性能比較は文献（７）などで見ることができる．

Reingold もスプリングモデルを改良した（ ）．スプリン力指向方式とは異なる，代数的なアプローチによる高グモデルがすべてのノード間の反発力を求めるのに対し速なレイアウト手法も開発されている．ラプラス行列はて，彼らの手法は近いノード間の反発力だけを計算する．

グラフの行列表現の一つ（隣接行列の変形）であり，そ描画領域を正方形の格子に分割し，同じ領域または隣接の固有ベクトルを用いることでグラフのレイアウトを求する領域に含まれるノードからの反発力だけを考慮する

め る こ と が で き る． ACE （Algebr aic multigr id Com

ことで，反発力の計算量を削減している．

putation of Eigenvector s）アルゴリズムは，固有値の計

Kawai もスプリングモデルを幾つかの点で算において，マルチレベル法と類似のアイデアに基づく改良した ．反発力を採用せず，ノードのすべてのペア

代数的マルチグリッド法を採用することで，ラプラス行の間に（隣接していないノード間にも）グラフ理論的距

列の固有ベクトルの計算を高速化しており，数百万ノー

離（最短パス長）を自然長とするスプリングを付けた．

ドのグラフのレイアウトをノードのすべてのペア間にグラフ理論的距離のスプリン

きる（ ）． ま た， HDE （High Dimensional Embedding）

グを付けたということは，すべてのノード間に理想距離は高次元空間への配置が比較的容易であることに着目を定め，その理想距離をできるだけ反映した二次元描画

し，高次元（五十次元程度）空間におけるノードのレイを目指すということである．これは多次元尺度法（MDS）

アウトを求め，主成分分析を利用して二次元に射影する

Kamada（ ）の考え方と同じであり，後に対比及び発展が議論される．
これらの描画手法はいずれもグラフ描画のコミュニ分以内に求めることがでものである．こちらも高速で，万ノードのグラフのレイアウトを数秒で計算できる（ ）．
これらの高速化手法は木やグリッドに近いグラフに対ティでは古典的手法と称されている．

しては比較的良いレイアウトを求めることができるが，大規模ネットワークの可視化

一般的なグラフに対しては必ずしも良いレイアウトを求めることができない．そのような質の問題を解決するた

ネットワーク情報の可視化には，ノード間の接続関係

めの新たなマルチレベル法も開発されている（ ）．部分という局所的な情報だけを利用して大局的な構造を描かグラフの構造に着目して粗雑化を行い，それぞれの構造

なければならないという難しさがある．このことはネッに適したレイアウト手法を適用することで，高速化ととトワークの規模が大きく複雑になるほど顕著である．

もに質の向上をねらっている．
高速化への取組みは現在でも続いている．例えば，

大規模ネットワークの高速な描画技術
レイアウト技術の進歩として大規模ネットワークへのMDS の分野で利用されている Str ess Major ization という手法を改善して高速化する取組みもある（例えば文献
Kawai の手法の発対応が挙げられる．特に力指向アルゴリズムをベースと）．これは先に述べた Kamada（ ）する手法の大規模化が顕著であり，最近では百万ノード

展系としてとらえることもできる．またハードウェアをの無向グラフを数秒で描画できる手法も現れている．

活用する手法として，近年特に高性能化してきている

より大規模なグラフを扱うためにマルチレベル法が開発された（例えば文献（６））．基本的なアイデアは次のGPU （Gr aphical Pr ocessing Unit）を利用した高速レイアウト手法も開発されている（例えば文献（））．

とおりである．与えられた大規模無向グラフに対して「粗いグラフ」を作成し（粗雑化： coar sening），まずそれ

大規模ネットワーク向け表現技術

をレイアウトして，その結果を詳細なグラフの初期配置

表現手法においても，マルチレベル的な手法が開発さに利用することで，レイアウト計算を高速化しようといれている．その手法は，ネットワークを幾つかのミクロ

うものである．もう少し手続的に説明すると次のように構造とそれらミクロ構造をノードとするマクロ構造に分とし，段々と小さくけてレイアウトや表示を行うものである．マクロ構造自を作成する．ま体が別のミクロ構造であるようなネスト表現を採用した

なる．与えられた無向グラフをなるようなグラフの系列
ず，最小のグラフ…

を古典的な力指向アルゴリズム（あものもある．

るいはその変形）でレイアウトする．次にそのレイアウ

例えば，マルチサーキュラレイアウトでは，ミクロ構の初期配置

造に関しては円周配置を行い，マクロ構造のノードを円を求め，やはり古典的な力指向アルゴリズムでレイアウで表現し一般的な力指向アルゴリズムを利用してレイアがレイアウトされるま

ウトする（ ）．エッジはミクロな構造を接続するがマクで繰り返す．グラフの系列の作成法や各レベルで利用すロなノード間をつなぐ太い線のように描かれるため，マト結果を利用して次のサイズのグラフ
トする．このプロセスを元の

電子情報通信学会誌 Vol

No

ネットワークの変化の表現技術
動的ネットワークの表現上の問題は，ノード間の位置関係をうまく表現するためには二次元（以上）必要である上に，更に時間軸を表現する必要があるということである．
一つの対策は，時間軸の表現に物理的な時間軸を利用するもので，いわゆるアニメーションによる変化の表現である．変化の様子をとらえやすいが，過去の状態は消え て な く な る た め 記 憶 に 頼 る 必 要 が あ る． ス ナッ プ
ショットを一列あるいは行列状に配置する方式も多く採用されている．全体を見渡せる反面，各スナップショッ
トは別々の図として描かれているため，スナップショッ
ト間の比較を人間が行う必要がある．
これらの基本的な表現形式に対して，この数年多く出現している形式が，二次元上に描かれたネットワーク図を時系列順に積み重ねて表現する形式である．一種の三図
電子メールのネットワークをマルチサーキュラレイアウト
で描いたもの（ ）マクロには ノード（グループ）に見えるが，実際にはノード数
，エッジ数
である．

次元レイアウトであるが，二次元の図を別の 一次元方

クロには比較的小規模なネットワークのように見える（同一性）も表現されることが特徴である（図 （ ））．

向に積み重ねていることから，次元と称される．

配列表現とは違い，スナップショット間のノードの対応（図 （ ））．

アニメーション表現，配列表現，次元表現のいずネットワークの連結度が高くエッジが密な場合には，

れも，ある瞬間のスナップショットを二次元平面で表現

ノードをどのようにレイアウトしてもエッジの混雑を避しようとしているのに対して，時間変化も含めて二次元けることは難しい．そのような状況ではエッジの配線をで表現しようという取組みもある．例えば波紋表現（ ）工夫することで可読性を向上させる試みがある．例えば

では，ネットワーク図に時間軸を表現するための局所的

個々のエッジを独立に描くのではなく，ノードを共有すな極座標を組み合わせることで，木構造の発展の様子をるエッジ同士を滑らかに束ねることで，エッジの混雑を表現している．

避ける手法が提案されている（ ）．上で紹介したマルチ
ネットワークの変化を考慮した描画技術

サーキュラレイアウトも，エッジの配線の工夫による視覚的な効果が大きい．

動的なネットワークのレイアウトに静的なグラフレイアウト技術をそのまま用いると，メンタルマップを破壊

動的ネットワークの可視化技術

する可能性がある．
ここでいうメンタルマップとは，
ネッ
トワーク図を見ることで構築される頭の中のマップであ実世界のネットワークに着目したとき，それが静的でる．画面に表示されたものとの不整合が起こると破壊さあることはまれで，むしろほとんどのネットワークが時れ，混乱に陥る危険性がある．静的なグラフレイアウト

間とともに変化する．大規模なネットワークの可視化へ

は，与えられた一つのグラフに対して，美的基準に沿っの挑戦とともに，動的なネットワークの可視化への挑戦て最適なノードの位置とエッジの配線を求めるものであも数多く行われている．

る．これを動的なグラフに適用すると，グラフの少しの変化（例えば，一つのエッジの追加）によってレイアウ

動的ネットワークの定式化
動的なネットワークをいかに定式化するかも一つの問
題 で あ る． 一 般 的 に は グ ラ フ の 離 散 的 な 系 列…

ト結果が劇的に変化する恐れがある．つまり，＋との差がただ一つのエッジであるにもかかわらず，のレイアウトと＋のレイアウトが全く異なるもの

として定式化することが多い．変化する実になりメンタルマップを破壊する可能性がある．そのた際のネットワークから離散的な列を作り出す方法としてめ，動的ネットワーク描画では，美的基準を満足するだ

は，一定時間ごとのスナップショットを抽出する方法や，けでなく，メンタルマップを保存する必要がある（ ）．

一定間隔のタイムウィンドウ内での変化を累積して離散的な時系列に対応付ける方法がある．

メンタルマップを保存するためには，グラフの系列において共通するノード（つまり，変化しないノード）の
位置あるいは位置関係をできるだけ保存することが重要である．そのためには系列に含まれるグラフを個別にで解説

ネットワークの可視化技術──大規模ネットワークと動的ネットワークへの挑戦──図
次元表現の例（ ）ワークを比較したもの．

ただしこの図は時間変化ではなく五つのネット

はなく，まとめて処理する必要がある（ ）．まとめ方の的な配置計算を行う手法が開発されている（ ）．

一つの方法はアグリゲートグラフを利用する．アグリ
ゲートグラフ（注 ）とは系列間で対応するノードやエッジ

今 後 の 動 向をそれぞれ一つのノードやエッジにまとめたものである．アグリゲートグラフのレイアウトを基準として用い

大規模グラフの描画技術に関しては，質を高める方向

ることで，対応するノードは同じ位置にレイアウトされがより重視されるものと思われる．近年マルチレベル方

るため，メンタルマップの保存が容易である．反面，系

式や代数的な方式の導入により計算速度は画期的に向上

列内の個々のグラフについて見ると，ノードの位置の制したが，実際的なネットワークに対しては，必ずしも十約が厳しいことが難点である．別の方法はマージグラフ

分な描画の質が得られない．先に紹介したとおりマルチを利用する．マージグラフでは対応するノードがあってレベル方式の発展形としてグラフの構造を意識したレイも別のノードとしておき，それらをつなぐ特別なエッジアウト手法が提案されているが，これはレイアウトの質が導入される．力指向アルゴリズム等によってその特別に重点を置いたものと考えられる．可視化の目的に立ちなエッジをコントロールすることで，対応するノードを返ると質重視の方向は不可避である．

近くに配置することが可能になる．

また，動的ネットワークの表現も含めて，更に多様な

アグリゲートグラフやマージグラフを利用するレイア

表現形式が開発されるものと思われる．例えば，連結系

ウト手法は，変化するグラフの系列が事前にすべて与えに対して他の基本系（領域系，座標系，配列系）を融合られていると仮定している．このような手法はオフライさせた複合系が幾つか出現している（ ）（ ）（ ）．表現形式

ン手法と呼ばれる．オフライン手法では，将来ノードがの融合には無限の可能性があり，可視化の目的及び対象発生する場所をあらかじめ空けておいたり，隣接するこの性質（規模，静的／動的，トポロジカルな性質など）とになるノード同士をあらかじめ近づけておいたりといに適した情報表現及び操作を可能にする表現形式の開発

うように，将来に向けて準備することでレイアウトの大が期待される．

きな変化を避けることができる．
しかしながら，実際の応用においては変化するネット
ワークを継続的に可視化したい場合もあり，そのような

お わ り に場合には現在までの系列しか利用できない．オンライン

ネットワークの可視化技術に関して，大規模ネット

手法とはそのような状況を想定した手法であり，グラフ

ワークと動的ネットワークに焦点を合わせ，表現技術との系列が事前に与えられていないと仮定する．オンライ

描画技術という観点から解説した．ここで紹介した技術

ン手法としては，例えば，系列の一つ前のレイアウトを

はネットワーク可視化技術のほんの一部である．本稿で手掛りとして，隣接ノードのうち既に決まっている位置

触れなかったトピックとしては以下のようなものがあを効果的に利用して，メンタルマップを維持しつつ効率る．表現技術に関しては円形配置や三次元配置などほかにも様々なものが開発されている．またソーシャルネッ（注 ） スーパグラフやメタグラフとも呼ばれる．

トワーク分析，バイオ情報学，セキュリティなどドメイ
電子情報通信学会誌 VolNo

ンごとの取組み，あるいはそれらに横断的なトピックと（してデータ解析やデータマイニングを応用とした可視化技術の研究も盛んである．技術を利用する立場からは（

ツールやツールキットにも関心があろう．また別の機会に紹介したい．

（

文

献（１） K. Boitmanis, U . Brandes, and C. Pich, Visualizing internet
evolution on the autonomous systems level, G raph D rawing
2007, LNCS, vol.4875, pp.365 376, 2007.
（２） 出原栄一，吉田武夫，渥美浩章，図の体系─図的思考とその表現，
日科技連， p.252, 1986.
（３） P. E ades, A heuristic for graph drawing, Congressus Nu
merantium, vol.42, pp.149 160, 1984.
（４） T.M.J. Fruchterman and E .M. R eingold, G raph D rawing byforce directed placement, Softw. Pract. E xp., vol.2, no.11,
pp.1129 1164, 1991.
（５） T. Kamada and S. Kawai, A n algorithm for drawing generalundirected graphs, Information Processing Letters, vol.31,
issue 1, pp.7 15, 1989.
（６） S. H achul and M. Junger, D rawing large graphs with apotential field based multilevel algorithm(extended abstract), G raph D rawing 2004, LNCS, vol.3383, pp.285 295,
2005.
（７） S. H achul and M. Junger, A n experimental comparison of fastalgorithms for drawing general large graphs, G raph D rawing
2005, LNCS, vol.3843, pp.235 250, 2005.
（８） Y. Koren, L. Carmel, and D . H arel, A CE : A fast multiscale
eigenvectors computation for drawing huge graphs, Pro
ceedings of the IE E E Symposium on Information Visualization
2002 (InfoVis 02), pp.137 144, 2002.
（９） D . H arel and Y. Koren, G raph drawing by high dimensional
embedding, G raph D rawing 2002, LNCS, vol.2528, pp.207
219, 2002.
（ ） D . A rchambault, T. Munzner, and D . A uber, Topolayout :Multilevel graph layout by topological features, IE E E Trans.
Vis. Comput. G raphics, vol.13, no.2, pp.305 317, March A pril
2007.
（ ） E .R . G ansner, Y. Koren, and S. North, G raph drawing by
stress majorization, G raph D rawing 2004, LNCS, vol.3383,
pp.239 250, 2005.

解説

（

（

（

（

（

（

（

） Y. Frishman and A . Tal, Multi level graph layout on the
G PU , IE E E Trans. Vis. Comput. G raphics, vol.13, no.6,
pp.1310 1317, 2007.
） M. Baur and U . Brandes, Multi circular layout of micro macro
graphs, G raph D rawing 2007, LNCS, vol.4875, pp.255 267,
2007.
） D . H olten, H ierarchical edge bundles : Visualization of ada
jacency relations in hierarchical data, IE E E Trans. Vis. Com
put. G raphics, vol.12, no.5, pp.741 748, 2006.
） T. D wyer, S. H . H ong, D . Koschutzki, and F. Schreiber, Vi
sual analysis of network centralities, Proceedings of A sia
Pacific Symposium on Information Visualization(A PVIS2006), pp.189 197, 2006.
） M. Ishihara, K. Misue, and J. Tanaka, R ipples presentation
for tree structure with historical information, Proceedings of
A sia Pacific Symposium on Information Visualization (A PVIS
2006), pp.153 160, 2006.
） K. Misue, P. E ades, W. Lai, and K. Sugiyama, Layout adjust
ment and the mental map, J. Vis. Lang. Comput., vol.6, no.2,
pp.183 210, 1995.
） C. E rten, S.G . Kobourov, V. Le, and A . Navabi, Simul
taneous graph drawing : Layout algorithms and visualization
schemes, G raph D rawing 2003, LNCS, vol.2912, pp.437 449,
2004.
） Y. Frishman and A . Tal, O nline dynamic graph drawing,
IE E E Trans. Vis. Comput. G raphics, vol.14, no.4, pp.727 740,
2008.
） N. H enry, J. D . Fekete, and M. J. McG uffin, NodeTrix : A
hybrid visualization of social networks, IE E E Trans. Vis.
Comput. G raphics, vol.13, no.6, pp.1302 1309, 2007.
） S. Z hao, M.J. McG uffin, and M.H . Chignell, E lastic heirarchies : Combining treemaps and node link diagrams, Pro
ceedings of the 2005 IE E E Symposium on Information
Visualization (InfoVis 05), p.8, 2005.
（平成

年

月

日受付

平成

年

月

日最終受付）

三末 和男（正員）
昭 東京理科大・理工・情報卒．昭 同大
学院修士課程了．同年富士通（株）入社．グラフ
自動描画及びその発想支援への応用から始まり，テキストマイニングに関する研究を経て，現在は情報可視化の研究に従事．筑波大大学院
システム情報工学研究科准教授．博士（工学）．

ネットワークの可視化技術──大規模ネットワークと動的ネットワークへの挑戦──