日本ソフトウェア科学会第 34 回大会 (2017 年度) 講演論文集

対話的なネットワーク可視化分析のシェーダー実装による高速化
高野 陸

脇田 建

社会ネットワークの可視化はデータの大規模化に伴い，視覚的に煩雑になる点とシステム描画が遅くなる点の二つの問題を抱える．対話的可視化システムである Social Viewpoint Finder (SVF) は過去の実装において視覚的煩雑さをフィルタリングで解決した一方，システム描画の遅さは依然とした問題であった．システム描画の遅さの原因として，描画のための CPU-GPU 間通信量が多い，CPU で負荷の高い計算を行なっているなどが挙げられる．そこで
本研究では CPU-GPU 間通信を軽量化するデータ配分や，負荷の高い計算を計算シェーダーで並列に実行するなどの工夫をすることでシステムの高速化を図った．過去の実装に比べ，本研究での実装はシステム全体を通して 20 倍程度の処理速度の向上を達成した．

妨げ，視覚的な分析が難しくなる．

1 はじめに

対話的可視化システムでは，対話的に可視化結果を情報可視化の手法は，様々なネットワークを分析す操作できるためネットワークの構造をより深く理解でる一つの手段として重要である [5]．しかし，世の中きる．高度な対話性ならば高度なタスクを実行可能でに存在するネットワーク，特に社会ネットワークの多あるが，相応の計算コストが掛かるため大規模なネッ

くは大規模であることが多く，可視化システムにとっトワークを可視化する性能を達成することが難しく，て大規模なネットワークを分析できるスケールを持つ

逆に簡素な対話性では大規模化が可能でも，高度なタことは難しい．またスケール可能な可視化システムでスクに対応できないという問題がある．

あっても高度な視覚的分析のタスクに対応出来るものは少ない．
ネットワーク可視化には，ネットワークを一枚の静本研究では，高度な対話性を提供しながら大規模なネットワークを可視化できるシステムを実装した．使用したシステムは高見らが提案した Social Viewpoint

止画で表す静的可視化と [3] [2] [9]，可視化結果を対話Finder (SVF ) [12] という対話的可視化システムであ的な操作によって観察できる対話的可視化がある [10]る．高見らの実装ではクラスター構造の発見に役立[8] 静的可視化システムは大規模なネットワークに対つことを示していたが，大規模なネットワークの可視応できるが複雑なタスクは難しく，これまでの対話的化には難を残していた．本研究の実装で SVF の高度可視化システムは複雑なタスクが可能であるが大規模な対話性を損ねることなく，描画と計算の工夫によっなネットワークに対応しきれないと特徴付けられる．てシステムの性能を向上させ大規模なネットワークの静的可視化システムではネットワークを一枚の静可視化を実現する．

止画で表現するが，大規模化につれて問題が生じる．
ネットワーク全体を描画すると，頂点と辺の重なりな

2 関連研究どによる視覚的な煩雑さがネットワークの構造把握をネットワーク可視化システムで静的なものと対話的なものを例示する．また，それらの利点や対応できる

This is an unrefereed paper. Copyrights belong to
the Authors.
Riku Takano, Ken Wakita, 東京工業大学 情報理工学院.

ネットワークの規模，システムの問題点にも触れる．

2. 1 静的可視化
ネットワーク可視化の手法の一つとしてノードリンク図が存在し，これはネットワークにおける人や事物を円，そのリンク関係を線で描く手法である．可視化
アルゴリズムの研究はその円と線の適切な配置を求める分野であり，可視化された配置を埋め込みと呼ぶ．
ネットワーク可視化のアルゴリズムの計算量は頂点数や辺数について線形ではないため，大規模化と共に計算コストが急激に増大する．HDE [3] という可視化アルゴリズムでは，百万頂点のネットワークの埋め込みの作成を約２分で行うことができる．他にも，

Gansner らの Maxent-Stress Model [2] や，Noack のLin-log [9] などが大規模なネットワークの可視化を達

図1

SVF による米国の政治ブログの可視化成している [7]．
静的可視化は大規模なネットワークに対応できてて，対話操作中も 5.1FPS†1 を保ち頂点や辺の選択をも，視覚的な分析を十分に行うことが困難であるとい

1.83ms で実行することができた．Muelder らの SFCう問題点がある．これは複雑なネットワークの構造が[8] はズーム機能を提供しており，他にも大規模ネッ

一目でわかる静的な配置を求める難しさと，大規模なトワークの対話的な可視化が研究されている．

ネットワークで起こる頂点や辺の重なりなどによる可視化結果の視覚的な煩雑さが原因である．

これらのような対話的可視化はアプリの応答から導かれる簡素な対話機能を備えている．しかしクラス
ター構造の発見といった高度なタスクに対応すること

2. 2 対話的可視化は難しく，アプリの応答の他にネットワークの構造を対話的可視化とはユーザーとの相互作用的に可視利用する等の高度な対話性が要求される．

化を行う手法である．頂点のラベルを表示する操作やアフィン変換，フィルタリングといった簡素な処理の3 Social Viewpoint Finder

ほか，エッジバンドリングなどの複雑な処理を対話的高見らの提案した SVF は社会ネットワークを対話に行う機能が例として挙げられる．

的に可視化し，視覚的な分析を可能にするシステムで静的な可視化では最終的に出来上がった可視化結果ある．頂点をドラッグすることで高次元回転による視で分析を行うため，過程となる描画の遅速は問題とな座の変更を対話的に行うことができ，またフィルターらなかった．しかし対話的可視化の場合は対話によっとの併用によりネットワークのクラスター構造を探索てネットワークの分析を行うため描画速度は重要であすることができる．

る．対話操作の応答は操作の種類によるが遅いもので１秒，速いもので３０ミリ秒以内の完了が求められ，

3. 1 システムの概要

対話操作に要する計算時間がこれを超えるとユーザー

Torgerson-Kluscal-Seeri 法 (TKS 法) は古典的多の対話体験を損なう．そのため対話的可視化はシステ

次元尺度法 (CMDS ) [14] [11] [13] の結果から主固有ム描画がある程度高速であることが求められる．

ベクトルからなる基底空間を平面に射影する．これにPanagiotidis らによる可視化 [10] では拡大や縮小な対し，細部が提案した Active Graph Interface(AGI )どのアフィン変換や，頂点と辺にマウス操作で手を加えるといった対話的機能を提供している．この可視化では 40 万頂点と 339 万辺のネットワークについ†1 FPS は画面描画性能の単位．5.1FPS は秒間に 5.1 画面を描画できる性能を意味する．逆に画面更新に要する時間は約 200ms となる．

は正のすべての固有値を合成して得られる基底空間

ザーがクリックした座標直下に描画された頂点の識別を平面に射影する一般化を前提とした対話機能 [4] [12]番号を同定する処理が対話操作の初めに必要となる．

である．AGI は射影された平面上の対話操作によっ

その後に選択された頂点をドラッグし，ドラッグ後のて高次元回転を行い視座を対話的に変更する機能を座標によって以下の計算に続く．
制約式は 8 元非線形連立方程式であり，高見らの実提供する．

SVF では対話操作に AGI を用いており，頂点数 n

装と本研究の実装のどちらも L-BFGS [6] によって近のネットワークを可視化するとして手法の説明を行似解を求めている．最適化によって (d × 2) 次元の新う．先ずはその描画の初期配置を求める計算の説明をしい射影行列 P ′ を得たら，新しく射影された平面上する．この計算をまとめると次の３つのステップからの頂点の配置 L′ld を，Lhd · P ′ によって求める．これなる．

らの計算はドラッグ操作のフレーム毎に発生する．

1. CMDS による高次元配置 Lhd の導出

SVF には他にも対話機能が備わっており，その中

2. 細部の方式に従って初期射影行列 P を構成の一つとして中心性によるフィルタリング機能が備

3. 射影された平面上の頂点の配置 Lld を計算わっている．ネットワークの頂点と辺について中心最初のステップは，ネットワークの隣接関係から性という種々の重みが存在し，この中心性の種類と重の全対グラフ論的距離行列とそこから導出された行みの閾値を決定することで頂点と辺の描画を制限す列の固有値分解が主要な計算である．高次元配置はることができる．これを対話的に行うことで，種々の(n × d) 次元の行列であり，d は高次元配置上の頂点指標に基づいたネットワークの要約を探索することがの次元数である．大規模なネットワークを扱う際の効でき，構造理解の一助となる．また描画する頂点と辺率化のために，描画結果への貢献度が低い頂点の次を削減することで描画処理を軽くするという意味も元を省略する．具体的には，頂点の次元 d を最大 500あり，高見らの実装ではフィルタリングなしには大規までとして高次元配置 Lhd を求める．

模なネットワークの可視化は不可能であった．

次に細部の方式に従って初期射影行列 P を構成する．行列 P の次元は (d × 2) である．

SVF は社会ネットワークの視覚的な分析を効果的に実現できたが，対話的な可視化システムとして運最後に射影された平面上の頂点の配置 Lld を，Lhd ·P

用可能な規模の限界は，約 4,000 頂点と 45,000 辺程の行列積の計算によって求め，描画の初期配置とす度のネットワークであった．高見らの実装において，る．行列 Lld の次元は (n × 2) である．

これ以上の規模では実用性を保つことは難しかった．

AGI の対話機能はドラッグ操作によって開始される．頂点をドラッグして移動させた座標について，移3. 2 高見らの実装の性能における問題点動後の位置に射影するような新しい射影行列 P ′ を求高見らの実装において言語は C++を使用し，GLUIめる．射影行列は適切な更新のための制約式を解消

によって古典的 OpenGL を使用していた．SVF が大することによって求められる．この射影行列の更新は規模なネットワークを可視化する際に，システム描埋め込みの高次元的な回転を表しており，回転によっ画が遅くなる原因となる実装を描画と計算の面で考てドラッグ後の頂点の配置 L′ld が計算される．この対える．

話操作の計算をまとめると次の３つのステップからなる．

描画については，描画フレーム毎に頂点と辺のデータが GPU へ送られる．描画には座標と色を送るの

1. 選択された頂点のドラッグ後の座標を取得′でデータ量は (28 × 頂点数 + 40 × 辺数) B に及ぶ．

2. 制約式を解消し新たな射影行列 P を計算

大規模なネットワークにおいてこの通信の負担は大新しく射影される頂点の配置 L′ld を計算きくなる．特に頂点と比べて辺は数が多く，その数は3.

対話操作の中でドラッグにより頂点を動かす前に，数倍にも登るために描画の遅延の一因となっていた．

そもそも頂点の選択を行う必要がある．つまりユー描画トランザクションが細分化されていた点も原因の

C
P
U

メモリ使用量
計算

G
P
U

フィルタ

頂点選択

ドラッグ操作と射影計算

描画トランザクション

中心性
スコア

Pick情報

射影行列

高次元配置

頂点情報

辺情報

1MB

20B

4KB

67MB

0.9MB

7.2MB

フィルター
設定

クリック

ドラッグ

射影計算

フィルター
適用

描画命令

通信…

計算(GP)

描画（VS, FS）

図2

高見らの実装において Enron データを可視化した際の SVF のシステム概観一つである．

使用量や通信量を大まかに勘定したものである．こ計算については次の三つの点に注目した．第一に射の実装では巨大なデータをほとんど CPU で処理し，影計算における行列積の計算である．これはドラッグ

また描画フレームごとに少なくとも 8.1MB のデータを通信する必要がある．PCI バス †4 の転送速度が１操作によりリアルタイムに実行されるので，この計算の遅延はシステム描画の遅延につながる．頂点の配置

L′ld を求める Lhd · P ′ の行列積での計算量は大きく，レーンあたり 1GB/sec として，描画フレームごとのデータ転送時間は最低でも 8.1ms と計算できる．†5 ．

Lhd の次元が (n × d)，P ′ の次元が (d × 2) として，計算量は O(d × n) になる．CPU 上での LAPACK†2

当然ながら描画フレームで転送するデータは他にもの利用によってある程度高速な並列計算がされていた大きな遅延を生むと推測できる．

ものの，可視化するネットワークが大規模になるにつれて遅延が目立つようになっていた．
第二にフィルタリングである．これは CPU で全て存在し，描画トランザクションの細分化も合わさって高見らの実装で大きな問題点であった描画性能の不足に焦点を当てて，本研究ではそれを踏まえた実装の改善を行う．の頂点について選ばれたフィルターの閾値に照らし合わせることで描画するかを決めており，描画フレーム4 高速化を施した SVF の実装毎にフィルタリングの処理を逐次行っていたため頂点

本節では，3 節で触れた実装の問題点を改善し，描や辺の数に比例して計算コストがかさんでいった．

画性能と計算性能を高めるために次の５つの工夫を第三に頂点選択の処理である．クリック時の座標に行なった．本研究で実装に使用した言語は Python でマッチする頂点を CPU 上で全探索しているため，大あり，PyOpenGL によって現代的 OpenGL を使用

規模なネットワークにおいて頂点選択の処理時間が大した．

きくなり，クリックに対する反応が遅れてユーザーの快適さを損う問題があった．
図 2 は 33,696 頂点と 180,811 辺をもつネットワー
クである Enron データ †3 を可視化した際のメモリ†2 http://www.netlib.org/lapack/†3 https://www.cs.cmu.edu/ ./enron/

また，本研究の実装によって 3. 2 での性能がどの†4 パソコン内部の各パーツ間を結ぶデータ伝達路．高見らの実装で使用していた PCI バスは不明のため，本研究で用いた PCI バスの性能で計算する．
†5 データ量は 8.1[MB/frame]．PCI バスの転送速度が1000[MB/s] より，データ転送にかかる時間は「データ量 [MB/frame] / (転送速度 [MB / s] * 1000[s/ms])」より 8.1[ms/frame] と計算できる．

程度改善されるのかの見通しを述べる．

並列 に 計 算 す る こ と で 高 速 化 を 図った ．本研
究 の 実 装 で は Lhd = (hd1 , ..., hdn )T と し て ，

4. 1 本研究で実装した５つの工夫

Lhd · P ′ = (hdT1 · P ′ , ..., hdTn · P ′ ) に つ い て ，

1. 役割に応じたデータの配置′
一つのスレッドごとに hdT
i · P を計算させた．

高見らの実装ではすべてのデータを CPU 上に配置し，必要なデータを都度 GPU に送信してい4. フィルタリング処理の並列化
全頂点について，ユーザーが選択している中心た．この通信は大規模なネットワークを可視化す性のスコアと選択されている閾値を GPU 上で保る際に無視できない大きさになるため，本研究で持する．これにより頂点シェーダーが並列描画をは最小限の CPU-GPU 間通信に抑えるための効実行する際，同時に頂点の中心性のスコアとフィ率的なデータの配置を行なった．例えば，頂点をルターの閾値を比較し，フィルタ対象となる頂点描画フレーム毎に送るのは手間であるので初めの描画を省いている．

から GPU に頂点座標を配置する，並列計算に用

5. 頂点選択処理の並列化いるデータを初めから GPU 上に出来るだけ配置

CPU で取得したクリック座標を GPU に送信し，するなどである．これにより CPU 上のメモリをそれを参照して画素シェーダー上で全頂点を並節約し，また CPU-GPU 間の通信量を減らすこ列に探索する．クリックされたと判定された頂点とが目的である．の ID を CPU に送り，どの頂点が選択されたか2. 描画手法の改善を知ることができる．

高見らの実装では辺の描画のために端点の座標と色を与えており，一つの座標が 12B，色が 16B

4. 2 本研究の実装における性能であるために一つの辺のデータ量は 40B であっ

図 3 は本研究の実装において Enron データを可視た．頂点の描画のために頂点座標は既に送られ化した際のメモリ消費量や通信量を大まかに勘定しているため，辺のために再び同じ座標を送るのたものである．

は二度手間である．よって本研究では辺の端点の描画フレームごとに送られるデータは軽量化され座標に頂点のインデックスを与えることでデーた辺だけであり，また一括した描画トランザクションタの軽量化を行なった．一つの頂点インデックスのために描画による遅さは改善されたと考えられる．

は 2B であるために一つの辺は 4B で表せるようになり，辺のデータサイズは 1/10 に削減できる．

描画フレームごとに送られるデータ量は 0.7MB として，PCI バス †6 の性能は１レーンあたり 1GB/sec

また，高見らの実装では頂点と辺の色も CPU かとして，描画フレームごとのデータ転送時間は 0.7ms

ら送っていたが，頂点 ID から頂点シェーダーでと計算できる．単純に高見らの実装に比べてこの転送色を設定することでこのデータの転送を省いてだけでも１１倍速くなった．他にも様々な計算を行ういる．そして描画トランザクションも一括して行ために実際の時間は遅くなるが，計算自体にも工夫をうことで通信頻度を下げ，更に描画フレームごと加えて負荷を軽減しているため全体を通してシステに大量に送られる描画命令のデータを減らすこ

ム描画の高速化が見込める．特に，高見らの実装で問とで性能向上を狙った．

題であった描画トランザクションの細分化を解消して

3. 射影計算における行列積計算の並列化
SVF は射影計算において高次元配置 Lhd と射′

影 行 列 P の 行 列 積 計 算 を 行 う．高 見 ら の 実いるため，その点でもデータ転送量が大きく抑えられていると考えられる．また描画フレーム以外での通信は頻度が少なく，データ量も多くないために現状では

装 で は そ れ を CPU 上 で 行 なって い た が ，行列積の計算量は頂点数の増加に応じて激しく増加 す る ．そ こ で 行 列 積 を 計 算 シェー ダ ー で†6 PCI Express x16 Gen3 を使用．１レーンあたりの実効データ転送速度は片方向 1.0GB/sec．

フィルタリングCPU

ドラッグ操作と射影計算

クリックした頂点の座標

メモリ
使⽤量
計算

頂点選択

辺情報

8B
フィルタ設定クリック

描画トランザクション

0.72MB
ドラッグ

射影⾏列
更新

描画命令

通信
埋め込みへの射影計算(CS)
GPU

SSB
使⽤量

中⼼性スコアPick情報

射影⾏列

⾼次元配置埋め込みの座標

0.1MB

20B

4KB

67MB

0.5MB

頂点探索
(FS)

計算(GP)

図3

描画（VS, FS）
フィルタ適⽤(VS)本研究の実装において Enron データを可視化した際の SVF のシステム概観問題視していない．
計算については，高見らの実装での計算の一部を並実装を上回った大きな理由として次の二つが挙げられる．

列計算に置き換えた．計算の多くは小さいネットワー

まず描画の改善が一つの理由である．描画のためにクの可視化においては高速に行われるため違いがわ

大量のデータを毎フレームごと GPU に送信していたからないが，大規模なネットワークでは大きな違いが問題はデータの効率的な配置によって改善され，辺の生まれると考えられる．高見らの実装のように CPU

データの重さは同等の意味をもつ他の表現を用いる

で計算を行うと大規模化に耐えられず計算資源の枯ことで軽量化し，描画トランザクションをひとまとめ渇によって遅延が生じてしまう．この問題は豊富な資にした．これらの貢献によって描画のコストを大きく源を持つ GPU を利用することで解決できる．

軽減したことが性能向上の一因と考えられる．
もう一つは，射影計算における行列積の並列化であ5 考察る．射影計算は SVF のドラッグ操作に応じてリアル

本節では初めに本研究で施した性能向上のためのタイムに計算されるため，この計算の遅延はシステ工夫を高見らの実装と比べてまとめる．そして高見ム描画の遅延につながる．高見らの実装では計算をらの実装と本研究の実装の SVF で同じネットワークアプリケーションで実行をしており，制約式の解消はデータを用いて性能比較を行う．

高速でも行列積の計算は大規模化につれて遅延が目立っていた．本研究では計算性能改善のために行列積

5. 1 本研究における改善点のまとめの計算シェーダーを用いて並列に計算した．行列積の4 節で述べた本研究の実装における工夫について，計算はベクトルの内積の和に分解して並列化を行なっ

3. 2 で述べた高見らの実装との違いをまとめると表１たのみであるが，大幅な改善が見られた．この計算を MAGMA†7 などの高性能な並列計算ライブラリにのようになる．
上記の性能評価において，本研究の実装が高見らの†7 http://icl.cs.utk.edu/magma/表1

高見らの実装と本研究の実装との比較

表2

高見らの実装と本研究の実装との描画性能の比較

|E|

FPS
(高見らの実装)

FPS(本研究の実装)

1,222

16,714

5760

1,896

26,183

3560

3,608

48,3153060

22,46348,436

1560

180,811

7.560

比較項目

高見らの実装本研究の実装データ配置

全てのデータ

役割に応じてデータ|V|を CPU 上に配CPU/GPU にUSPol

置分割して配置

4Univ

端点の座標を端点の頂点イMath

直接与えて表ンデックスを与Internet

現えて表現

Enron

33,696

CPU のマルチ

GPU の計算シ

コア，ベクトルェーダーで実装造 †10 ，Enron は Enron 社のメールデータである †11 ．

命令を利用しした並列計算

まず高見らの実装と本研究の実装について描画性能

辺の表現行列積て並列計算
フィルター

頂点選択の比較を行う．描画速度に関してはすべてのノードとCPU で逐次処頂点シェーダーエッジを表示した状態で１分間の平均 FPS を計測し理で並列に処理た．これらの計測結果をまとめたものが表２である．

CPU で全探索画素シェーダー

描画の FPS は最大で 60 であるため，本研究の実で並列に頂点装では描画に関して良い結果を得られた．高見らのを全探索実装では描画だけで精一杯であった Enron データも，本研究の実装では軽々と描画することができた．描画よって実行すれば更なる性能向上が見込める．
他にもフィルタリングや頂点選択でも改善を行っており，それらの寄与も考えられる．

に関してのみ言えば，本研究の実装は更なるスケールアップが見込める結果となった．
次に高見らの実装と本研究の実装について，対話操作を含めたシステムの性能比較を行う．高見らの実装

5. 2 性能評価の対話操作の実行速度は計測されていなかったので，高見らの実装での SVF の実行環境は CPU が Intel

次のように希望的な観測からおよその FPS を導出す

Core i5 (3.1GHz)，メモリ 16GB，グラフィックスはる．対話操作中の FPS を便宜的に FPS’ と表記する．

AMD Radeon HD 6970M の iMac (OS X 10.8.5) でSVF の対話機能ではドラッグ毎に L-BFGS によるあり，本研究の実装での SVF の実行環境は CPU が制約解消と行列積の計算が実行される．対話操作中もIntel Core i7 (4.0GHz)，メモリ 8GB，PCI Express描画を行うため，描画にかかる時間も勘定する必要がx16 Gen3，グラフィックスは NVIDIA GeForce GTXある．よって対話操作中のおよその FPS は L-BFGS

770 の HP ENVY-700-560jp (Windows 10 Home)の制約解消にかかる計算時間と行列積の計算時間のである．高見らの実装についての性能評価のデータは和を実行時間 t1[s] とする．この t1 に１フレームの論文 [12] のデータを一部引用している．

描画時間 t2[s] を足したものを対話操作中における１評価のための性能比較に５つのネットワークを使用フレームの実行時間として考える．対話操作中の他した．ネットワークの名前について，USPol は米国の計算は無視できるものとして考え，1/(t1 + t2) がの政治ブログ [1]，4Univ は Twitter における四大学連合のフォロー関係 †8 ，Math は Wikipedia の数学

FPS’ であると概算する．

に関する記事の参照関係 †9 ，Internet は BGP の構†8 https://twitter.com†9 https://ja.wikipedia.org/wiki/Category:数学†10 http://www-personal.umich.edu/ mejn/netdata/as22july06.zip†11 https://www.cs.cmu.edu/ ./enron/表3

高見らの実装と本研究の実装との対話操作の性能比較

6 まとめと今後の課題
高見らの実装本研究の実装描画手法と計算手法の工夫により，対話的可視化シ

データ

t1[ms]

t2[ms]FPS’

t1[ms]

FPS’

ステムである SVF のスケールアップを達成した．高

USPol

11757

1.5160

見らの実装と比べ少なくとも 10 倍の大きさのネット

4Univ

12835

1.8760

ワークについて対話的に可視化を行うことが出来る

Math

52633

2.34

60

ようになった．

Internet

193

67

3.8

5.64

58

世の中の社会ネットワークのスケールに至ることが

Enron

379

133

1.9

7.9750

今後の課題であるが，現状の SVF は性能の課題とアルゴリズムの課題がある．性能の課題は描画で辺のL-BFGS は高見らの実装では libLBFGS†12 ，本研

情報を GPU に配置して描画フレームの通信量をなく究の実装では scipy のライブラリを用いて計算していす，行列積を高度な計算ライブラリによって計算する

る．この計算については本研究で工夫した点はなく，などによってある程度は解消できる見込みである．ア

どちらの実装でもおよそ 1ms で計算が終了するため，ルゴリズムの課題は大規模な行列の固有値計算が厳

この実行時間は無視する．よって t1 は行列積の計算しい課題となっている．数十万規模の距離行列の固有として求める．

値を求めることは莫大な計算量を要する．SVF の描

高見らの実装において t1 は論文 [12] で評価されて画アルゴリズムにおける計算を近似的なアプローチおり，t2 は表２から求まる．これにより FPS’ を計算に代替するなどが考えられるが，現状で見通しは立っし，高見らの実装における対話操作中の性能とする．ていない．

本研究の実装では，SVF の対話操作を１分間行った

また，大規模なネットワークを可視化した際に生じ平均の FPS を計測して FPS’ とし，行列積計算の性る埋め込みの視覚的な煩雑さについても対処が必要

能比較のために本研究の実装における t1 を個別に計である．

測した．これらをまとめたものが表３である．
高見らの実装では 4Univ と Math における行列積

謝辞
研究を支えてくださった皆様に深く感謝いたします．の計算時間 t1 が小さいにもかかわらず描画の遅さによって FPS’ が低くなっていることがわかる．本研究

参 考 文 献では描画性能が改善されているので，対話操作中も快[ 1 ] Adamic, L. A. and Glance, N.: The political blogosphere and the 2004 US election: divided theyblog, Proceedings of the 3rd international workshop
on Link discovery, ACM, 2005, pp. 36–43.
[ 2 ] Gansner, E. R., Hu, Y., and North, S.: A
maxent-stress model for graph layout, Visualization and Computer Graphics, IEEE Transactions
on, Vol. 19, No. 6(2013), pp. 927–940.
[ 3 ] Harel, D. and Koren, Y.: Graph drawing
by high-dimensional embedding, Graph Drawing,
Vol. 2528, 2002, pp. 207–219.
[ 4 ] Hosobe, H.: A high-dimensional approach tointeractive graph visualization, Proceedings of the2004 ACM symposium on Applied computing,ACM, 2004, pp. 1253–1257.
[ 5 ] Lee, B., Plaisant, C., Parr, C. S., Fekete, J.-D.,
and Henry Riche, N.: Task Taxonomy for Graph
Visualization, ACM, April 2006, pp. 1–5.
[ 6 ] Liu, D. C. and Nocedal, J.: On the limited
memory BFGS method for large scale optimization,

適な FPS’ を保っていた．
また高見らの実装では Internet と Enron における行列積の計算時間 t1 と描画時間 t2 の両方が負担となり，FPS’ を大きく下げていることがわかる．本研
究では行列積を並列に計算することで負荷を軽減しており，t1 は高速に実行されている．描画性能の改善と合わさって，対話操作中では高見らの実装と比べ20 倍程度の FPS’ を達成できた．

†12 http://www.chokkan.org/software/liblbfgs/

Mathematical Programming, Vol. 45, No. 1(1989),
pp. 503–528.
[ 7 ] Ma, K.-L. and Muelder, C. W.:
Largescale graph visualization and analytics, Computer,Vol. 46, No. 7(2013), pp. 39–46.
[ 8 ] Muelder, C. and Ma, K.-L.: Rapid graph layout using space filling curves, IEEE Transactions
on Visualization and Computer Graphics, Vol. 14,No. 6(2008).
[ 9 ] Noack, A.: Energy Models for Graph Clustering., LNCS 2912, Springer, (2004), pp. 425–436.
[10] Panagiotidis, A., Reina, G., Burch, M.,
Pfannkuch, T., and Ertl, T.: Consistently GPUAccelerated Graph Visualization, Proceedings of the
8th International Symposium on Visual Informa-tion Communication and Interaction, VINCI ’15,
New York, NY, USA, ACM, 2015, pp. 35–41.
[11] Torgerson, W. S.: Multidimensional scaling ofsimilarity, Psychometrika, Vol. 30, No. 4(1965),
pp. 379–393.
[12] Wakita, K., Takami, M., and Hosobe, H.: Interactive high-dimensional visualization of socialgraphs, 2015 IEEE Pacific Visualization Symposium (PacificVis), IEEE, 2015, pp. 303–310.
[13] Young, F. W.: Multidimensional scaling, Encyclopedia of Statisical Sciences, Vol. 5, Wiley, 1985,
pp. 649–658.
[14] Young, G. and Householder, A. S.: Discussionof a set of points in terms of their mutual distances,
Psychometrika, Vol. 3, No. 1(1938), pp. 19–22.