固有楕円ポテンシャルを利用した ラベル付きグラフ可視化の座標計算

情報処理学会論文誌
数理モデル化と応用
Vol. 1
No. 1
88–101 (Sep. 2008)
固有楕円ポテンシャルを利用した
ラベル付きグラフ可視化の座標計算
松 林
藤 村
達
史†1
滋†2
山 田
藤 村
武
士†1
考†2
本研究では，ラベル付きグラフ可視化のための，ラベルどうしが重ならない効率的
な可視化座標計算の手法を提案する．従来のラベル付きグラフ可視化の座標計算アル
ゴリズムは Force-directed 法やバネモデルといった，ノードを “点” として扱う座標
計算を行うために，文字列や，異なるサイズのラベルを扱う場合，ラベルどうしが重
なってしまうという問題が生じる．ラベルの重なりを回避する手法はいくつか提案さ
れているが，いずれの手法も可視化計算を行った後に，再び座標計算処理を必要とす
る．これ等の手法では大規模なグラフ可視化では計算量が莫大となり，さらに元の可
視化結果を破壊してしまうという問題が生じる．そこで，各ノードの斥力項として，
ラベルサイズに依存した固有楕円ポテンシャルを与え，さらに，点対称ポテンシャル
と固有楕円ポテンシャルの関数の重ね合わせる手法を提案する．提案法により，メン
タルマップを保ちつつ，かつ，局所的なラベルの重なりを回避できることを示した．
out. The proposed algorithm gives an individually different ellipsoidal potential
to each node depending on its label size as well as a common point-symmetric
potential, and the combination of these two potentials defines the repulsion
force. This enables an efficient graph layout that can avoid local node overlaps
while maintaining the mental map.
1. は じ め に
複雑な関係データをネットワーク（もしくはグラフ）を用いて表現し，さらにこれらを可
視化する手法は様々な研究分野で広く用いられている．ここで関係データとは，重力や分子
間力によって相互作用する星群や分子群のように数学的にシンプルなものや，遺伝子やタン
パク質のように複雑な相互作用を持つもの，またハイパーリンクで互いに参照するインター
ネットの WEB ページ，人間あるいは企業間のソーシャルネットワーク（SN）など，様々
である．
これらの表現としてネットワークを用いる利点として，グラフ理論など数学的手法による
構造解析が可能となることがあげられる．さらに，ネットワークを低次元空間に配置し，可
視化することにより，データの潜在的な構造を浮き彫りにし，それによって大量なデータに
対する直感的理解か可能となるという点も重要である．そこで，これらのグラフ可視化にお
いてはネットワークの特性を利用した，効果的な可視化手法が必要となる．
Labeled Graph Drawing Based on
the Individual Ellipsoidal Potentials
一般的なグラフ可視化においてはネットワークの関連性をもとに，2 次元もしくは 3 次元
のユークリッド空間にノードを「点」として，エッジを点と点をつなぐ「直線」として投影
し描画する．しかしながら，各ノードが固有情報，たとえばノードの名称や画像などを持
Matsubayashi,†1
Yamada,†1
Tatsushi
Takeshi
Shigeru Fujimura†2 and Ko Fujimura†2
ち，これらをノード上に直接文字列あるいは縮小版画像として埋め込みたい場合もある．こ
れらいずれの場合も，ノードは「点」ではなく大きさを持つ「ラベル」として描画する必要
がある．
We present a new graph layout algorithm for a graph with node labels. The
proposed algorithm can generate a graph layout efficiently avoiding overlapping
of node labels. Most of the conventional algorithms such as force-directed and
spring methods compute node positions by treating nodes as “points”, and thus
may cause node overlapping when strings or labels with various sizes are added
to the nodes. Most of the conventional approaches to solve this problem require an initial graph layout creation phase without considering label sizes and
a separate layout adjustment phase for overlap removal as its post processing.
These methods are not suitable for a large-scale graph layout, because their
computational costs are high and they may even destroy the initial graph lay-
88
一般的なラベル付きグラフ可視化の手法では主にまず，Kamada ら1) のバネモデル法（KK
法）や，Fruchterman ら2) の Force-directed 法（FR 法）をもとにしたグラフ可視化アル
ゴリズムを用いてラベルを無視した通常の可視化計算を行い，座標を得る（これは layout
†1 NTT
NTT
†2 NTT
NTT
コミュニケーション科学基礎研究所
Communication Science Laboratories
サイバーソリューション研究所
Cyber Solutions Laboratories
c 2008 Information Processing Society of Japan
89
固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
(a)
(b)
図 1 graphviz を用いて “Dolphin social network”（表 4 参照）の可視化を行った．graphviz にはラベルどうしが重ならないように表示するモードが存在
し，左図は “重なりあり”，右図は “重なりなし” のモードで表示した
Fig. 1 Layout results of the labeled graph data “Dolphins social network” (given in Table 4) with graphviz. The left figure is the result
with “overlap=true” mode, while the right is with “overlap=false” mode.
creation と呼ばれる）．次にこの座標を基点として座標を調整し，ラベルの表示を行う（こ
のである．graphviz にはラベルどうしが重ならないように表示するモードが存在し，左図
れは layout adjustment と呼ばれる）方法が広く用いられている．このような座標計算結
は “重なりあり（overlap=true）”，右図は “重なりなし（overlap=false）” のモードで表示
果をもとにグラフ可視化を行うソフトとして，世界中で最も利用されているソフトである
したものである．“重なりなし” のモードは，KK 法で座標計算を行った後に，与えられた
graphviz 1 や同様によく知られるソフトである pajek 2 では layout creation として前記 2
ノードを基準にボロノイ分割を行い，各ノードをボロノイセルの中心に動かすという計算
手法を用いている．
を，ラベルが重ならなくなるまで繰り返し行う．しかしながらこの手法では，ノードの増加
Misue ら5) によれば，ラベル付きグラフ可視化における layout adjustment は以下の条
件を満足する必要があるとしている．
にともない計算量の増加が莫大となる．また，図 1 で示されるように，ボロノイ分割の繰
返しにより，元の可視化結果の構造が大きく変わってしまう，すなわち，メンタルマップの
• 定められた描画領域からはみ出ないように，コンパクトに配置
保存が困難であるという問題が生じる．
そのほか，layout adjustment としてこれまで Force-Scan 法5) や，近年の研究では，Slide
• ラベルどうしが重ならないように配置
• layout creation で得られた配置のメンタルマップ（相対的方向性，ノード間の近接性，
トポロジ）を保存するように配置
model 法などが提案されている3),4) ．これの手法では，与えられた座標値を基準にラベルど
うしが重ならないようにスライドさせて表示を行う手法で，路線図や地図上に駅名や地名を
図 1 は，graphviz を用いて “Dolphin social network”（表 4 参照）の可視化を行ったも
表示させる場合に有用な手法として提案されている．
しかしながら，これらの，layout creation と layout adjustment に分けて行う従来法は，
比較的小規模なグラフデータには有効であるものの，より大規模なデータにおいては，ノー
1 http://www.graphviz.org/
2 http://vlado.fmf.uni-lj.si/pub/networks/pajek/
情報処理学会論文誌
数理モデル化と応用
Vol. 1
ドが密集した領域が生じたり，また，極端に異なるラベルサイズを持つノードが存在する場
No. 1
88–101 (Sep. 2008)
c 2008 Information Processing Society of Japan
90
固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
合があるため，ラベルどうしの重なりを抑えつつメンタルマップを保存することが困難であ
る．また，座標値を計算した後，再び局所的に座標計算を行う必要があり，データの規模の
増加により計算量が莫大となるため，用途が限定されている．
したがって本稿では，layout creation と layout adjustment を同時に行う可視化手法を
提案する．これら 2 つの layout を同時に行うことにより，layout creation 時に得られたメ
ンタルマップが layout adjustment によって失われるという問題を解決し，さらに，メンタ
ルマップの保存においては，ノード間の近接性の保存のみを考えればよいことになる．
以下本研究では，総ノード数を N ，総エッジ数を E とし，無向かつラベル付きグラフデー
タを対象に，ラベルどうしが重ならない可視化手法を提案する．
2 章では従来研究，3 章では提案手法を詳細に述べ，4 章ではサンプルデータをもとに提
案手法の妥当性の考察を行い，5 章では応用例として “BLOGRANGER TG” について述
べ，6 章で本研究のまとめを行う．
2. 従 来 研 究
従来，グラフ可視化の研究分野では 1980 年代より様々な手法が考案されてきた．最も一
般的な手法は，ノード間の仮想空間上に配置されたグラフ距離や，ノード間の接続関係など
図 2 図 (a) は従来の可視化手法による，各ノードのポテンシャルの模式図．各同心円がポテンシャルの大きさを表
す．図 (b) は図 (a) を基準とした，大きさの異なるラベルの可視化例．図 (c) は図 (a) を基準とした，長い
文字列のラベルの可視化例
Fig. 2 Figure (a) shows a schematic picture of point symmetric potentials. Figures (b) and (c) show
visualization with various size labels and with long string labels, respectively. In both Figures,
each label position is calculated from the potentials shown in Figure (a).
に基づき，系にポテンシャルエネルギーを定義し，エネルギー最小化問題として扱う手法で
ある．エネルギー関数からポテンシャル勾配を求め，加速度方向に座標を逐次的に更新する
となるように座標を更新する．この際，ノード間のバネ定数を kij ，ノードの空間的な座標
ことにより，系の最小エネルギー状態を求める．各ノードはポテンシャルの低い場所に次第
ベクトルを xi とし，グラフの全ノード集合を N，総ノード数（N のサイズ）を N とした
に移動し，結果として系全体のエネルギーが極小となるように更新される．
とき，系の総エネルギーは以下で定義される．
従来のグラフ可視化アルゴリズムでは，ノードを「点」，エッジを「辺」として描画する
ことを前堤として計算が行われるため，ラベルどうしが重なり合ってしまうという問題が
ΨKK =
ある．
たとえばノードのポテンシャルを図 2 (a) とした場合，図 2 (b) のように大きさの異なる
ラベルを表示したり，図 2 (c) のように IP アドレスや人名など，1 方向に長いラベルを表示
させたりする場合にはラベルどうしが重なり，また従来の手法では限界がある．
1
2
kij (|xij | − lij )2
(1)
(i,j)∈N2 ,i=j
ここで xij = xj − xi であり，|xij | は i 番目のノードと j 番目のノードのユークリッド距離
2
である．また，KK 法ではバネ定数を kij = k/lij
とし，k は無次元量の規格化定数である．
KK 法では，Newton-Raphson 法を用いた逐次更新手法により，ポテンシャル勾配の 2
以下，可視化の座標計算手法として広く用いられている 2 つの手法について説明する．
次導関数を求め，勾配の絶対値の大きなものから逐次的に座標更新を行う．計算終了条件は
2.1 Kamada and Kawai Method
系のエネルギー変化率を求め，あらかじめ設定した閾値よりも小さくなり次第計算を終了さ
Kamada ら
1)
は（以下 KK 法と略す）すべてのノード間に仮想的なバネを仮定し，1 ノー
せる．
ドずつ逐次的に座標を更新する手法を提案した．i 番目のノードと j 番目のノードのグラフ
2.2 Fruchterman and Reingold Method
上での最短経路長を，ノード間のバネの自然長（lij ）として与え，全体のエネルギーが極小
Fruchterma ら2) の提案した手法（以下 FR 法と略す）では，連結するノード間（エッジ）
情報処理学会論文誌
数理モデル化と応用
Vol. 1
No. 1
88–101 (Sep. 2008)
c 2008 Information Processing Society of Japan
91
固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
に働く力を引力として与え，さらにノード間に斥力を与え，2 つの力の和を与えることによ
りノードの座標更新を行う．ここで系の総エネルギーは以下のように表される．
ΨFR =
1 k2
|xij |3 −
3k
2
ln |xij |
(2)
(i,j)∈N2 ,i=j
(i,j)∈E
ここで k は無次元量の定数であり，E は接続関係を意味するエッジ全体の集合，E はエッ
ジ総数（E のサイズ）であるとする．右辺第 1 項がエッジとしての引力項を示し，右辺第 2
項が各ノード間の斥力項を示す．
FR 法では，ポテンシャル勾配である加速度の方向に，全ノードの座標を同時更新する．
更新幅については，あらかじめ設定した繰返し演算数に対し，最大更新幅が 0 に収束するよ
うな冷却関数によって動的に調節する．
3. 提 案 手 法
従来のグラフ可視化手法における座標値計算では，ノード間の力学方程式として位相空間
上での座標間距離に比例した関数系を考える．つまり KK 法や FR 法において，i 番目の
ノードと j 番目のノードに関わる加速度はユークリッド距離 |xij | に比例した関数として与
えられ，その加速度の方向ベクトルは xij と平行である．
ここで本研究では，固有楕円ポテンシャルを用いて各ノードに対して異なる形状の斥力を
図 3 図 (a) は固有楕円ポテンシャルを与えた各ノードのポテンシャルの模式図．各同心円がそれぞれのノードのポ
テンシャルの大きさを表す．図 (b) は図 (a) を基準としたラベル配置例．ラベルの大きさは図 2 (b) と同じ．
図 (c) は文字列に固有楕円ポテンシャルを与えた場合の模式図．各同心円がそれぞれのノードのポテンシャル
の大きさを表し，図 (d) は図 (c) を基準としたラベル配置例
Fig. 3 Figure (a) shows a schematic picture of the ellipsoidal potentials of various size labels and
Figure (b) shows its visualization result. Figure (c) shows a schematic picture of the ellipsoidal potentials of long string labels and Figure (d) its result. In the right figures, each label
position is calculated from the corresponding left figures.
与えることによって，個々のラベルの大きさを考慮した最適配置を求める手法を提案する．
以下，2 次元に絞り提案手法を説明する．
とする配置を探すことで，図 3 (b) および図 3 (d) のように重なり合わなくなる．
3.1 固有楕円ポテンシャル
しかしながら，図 3 (d) のようにすべてのノードが文字列の場合，すべてのノードのポテ
提案手法では i 番目のノードに対して x 軸方向，y 軸方向に Ai ，Bi という大きさを持つ
ンシャルが横方向に扁平となり，その結果可視化結果も全体的に扁平となるという問題が生
ラベル付きのグラフに対して，ラベルの大きさに依存した斥力のポテンシャルを用いる．す
じる．したがって，単純に FR 法に固有楕円ポテンシャルを導入するだけでは，可視化結果
なわち，i 番目のノードの作るポテンシャルの斥力成分 Φ0,r
は空間上の座標 (x, y) に対し
i
に影響を及ぼす可能性がある．
そこで本研究では，楕円ポテンシャルを斥力項のみに与え，さらに斥力項のポテンシャル
て以下のような関数で与えることができる，
Φ0,r
i (x, y) = hi (|x̃ij |),
|x̃ij | =
(xj − xi )2 (yj − yi )2
+
A2j
Bj2
(3)
1/2
(4)
ここで xi , yi はそれぞれ i 番目のノードの x 座標と y 座標である．
関数を二重化させることによりこの問題を解決する．詳細を次節に記す．
3.2 ポテンシャル関数の二重化
本研究では，斥力項のポテンシャル関数を二重化する手法を提案する．この手法による効
果は主に 3 点あり，第 1 に，図 3 (d) のように可視化結果が全体的に潰れることを防ぐ効果
たとえば 図 2 (b) および 図 2 (c) において重なり合っているラベルが，図 3 (a) および 図 3 (c)
がある．第 2 に，遠方で点対称ポテンシャルによる斥力を残しつつ，近傍ではラベルサイ
のような固有の楕円ポテンシャルを与えることにより，各ノードが系の総エネルギーを最小
ズに依存した斥力を強くすることができる，という利点がある．つまり，メンタルマップを
情報処理学会論文誌
数理モデル化と応用
Vol. 1
No. 1
88–101 (Sep. 2008)
c 2008 Information Processing Society of Japan
92
固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
保ったままラベルどうしが重ならないという制限をより強くすることができる．第 3 に，遠
方でのラベルサイズに依存した楕円ポテンシャルの影響を弱くすることにより，Tree-code
のような既存の近似手法（FADE: Quigley ら6) ）と組み合わせることが可能となる．
具体的には i 番目のノードの作るポテンシャルの斥力成分を
Φri (x, y) = f (|xij |) + g(|x̃ij |)
(5)
と定義することにより，点対称ポテンシャル成分 f (|xij |) と楕円ポテンシャル成分 g(|x̃ij |)
とに分けて考える．このとき注意すべき点は，|xij | は i，j に対して対称である一方，|x̃ij |
は非対称であり，さらに関数 g(|x̃ij |) が f (|xij |) よりも近傍では強く，遠方では速く減衰す
るように関数を定める必要がある．つまり，
f (|xij |) g(|x̃ij |)
if |xij |, |x̃ij | → 0
f (|xij |) g(|x̃ij |)
if |xij |, |x̃ij | → ∞
(6)
を満たす必要がある．たとえば，FR 法ではポテンシャルが式 (2) で与えられ，斥力項のポ
テンシャル関数は
f (|xij |) = k2 ln |xij |
(7)
となる．したがって，楕円ポテンシャル項を |x̃ij | の巾関数として以下のように与えれば，
g(|x̃ij |) =
kα
qj |x̃ij |−α
α
図 4 図 (a) は式 (8) で表される楕円ポテンシャル成分．図 (b) は式 (7) で表される点対称ポテンシャル成分．図
(c) は図 (a) と図 (b) のポテンシャルの重ね合わせであり，式 (5) に相当する．それぞれ反発係数と関数の巾
は kα = 1，α = 4，qi = 1 とし，ラベルサイズは A = 5，B = 1 とした
Fig. 4 Figure (a) shows a schematic picture of the ellipsoidal potential given as Equation (8) and
Figure (b) shows that of a point symmetric potential given as Equation (7). Figure (c)
corresponds to Equation (5) and shows a superposition of figure (a) and figure (b). Here,
parameters are kα = 1, α = 4, A = 5, B = 1 and qi = 1.
(8)
α > 0，kα > 0，qj > 0 であれば条件式 (6) を満たす．ここで qj はノードの重みであり，
図 4 は二重化されたポテンシャルの例である．図 4 (a) は式 (8) において，kα = 1，α = 4，
反発係数である．提案手法では，ノード間の斥力には力を与える側の次数を重みとして与え
A = 5，B = 1 とした楕円ポテンシャル成分．図 4 (b) は式 (7) の点対称ポテンシャル成分
る．すなわち，Ei を i 番目のノードの持つ総リンク数として，
を表し，図 4 (c) は図 4 (a) と図 4 (b) の重ね合わせであり，二重化されたポテンシャル関数
q i = Ei
(9)
を用いて近傍ではラベルの大きさに比例した斥力，遠方では近似的にユークリッド距離のみ
に依存した斥力を与えることが可能であることが分かる．
とする．
一般的に大規模ネットワークデータは，一部に次数の非常に高いノードが存在し，その
ようなノード付近では多くのノードが密集し，可視化結果が潰れてしまうという問題があ
る．Andreas 7) では各ノードに，ノードの次数に比例した重みを与え，次数の高いノード
どうしの斥力を強めることによりこの問題を回避している．しかしながら Andreas の手法
では，ノード間の斥力にお互いの次数を乗算しているため，KK 法や FR 法などの描画結果
以上をふまえて，提案手法では，ポテンシャル関数 Φi として，FR 法のポテンシャル関
数に，式 (8) で定義される固有楕円ポテンシャル成分を足した，以下の式を用いる．
Φi (x, y) =
2
1 kα
|xij |3 −
k ln |xij |− qj |x̃ij |−α
3k
α
j∈Ei
(10)
j∈N,j=i
とはまったく異なる可視化結果となってしまう．それゆえ提案手法ではノードに与える反発
ここで Ei は，i 番目のノードと直接リンクでつながっているノード全体の集合とし，また，
力は，各ノードの次数を与え，従来手法による可視化結果と大きく変わることなく，かつ次
右辺第 2 項は i 以外の全ノードにわたる和を表す．
数の高いノードが集まる領域においてもラベルが重ならない手法を提案する．
情報処理学会論文誌
数理モデル化と応用
Vol. 1
No. 1
88–101 (Sep. 2008)
c 2008 Information Processing Society of Japan
93
固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
3.3 加 速 度
一般的にポテンシャルと加速度の関係は，ポテンシャル関数を定めれば，勾配関係より以
下のように導出することができる，
ai =
∇Φj .
(11)
j∈N,j=i
FR 法による i 番目のノードに対する加速度 aFR,i は，式 (2)，(11) より
xij
1
aFR,i =
|xij |xij − k2
k
|xij |2
j∈Ei
(12)
j∈N,j=i
として与えられる．また，式 (8) で定義される楕円ポテンシャル成分は，x 成分，y 成分，
それぞれ
ar,x,i = −kα
qj (xj − xi )
j∈N,j=i
ar,y,i = −kα
(13)
A2j |x̃ij |α+2
qj (yj − yi )
j∈N,j=i
(14)
Bj2 |x̃ij |α+2
と表すことができる．
以上より，提案手法では，固有楕円ポテンシャルによる斥力は，x 成分，y 成分それぞれ
表 1 提案手法によるノード配置の更新
Table 1 Updating node positions by the proposed method.
1.
2.
3.
4.
5.
初期配置 xi をランダムに与える
全ノードの加速度 ai を式 (15)，(16) より求める
全ノードの xi (t + 1) を式 (17) より求める
時間を更新する，t = t + 1.
2-4 を，t = TEND を満たすまで繰り返す
表 2 FR 法のアルゴリズム
Table 2 Algorithm for the FR method.
1: for i = 1 to N do
2:
for i = j, j = 1 to N do
3:
dx = x[j] – x[i];
4:
dy = y[j] – x[i];
5:
dx2 = dx*dx;
6:
dy2 = dy*dy;
7:
r2 = dx2+dy2;
8:
r2in = 1.0 / r2;
9:
ax[i] += r2in*dx ;
10:
ay[i] += r2in*dy ;
11:
end for
12: end for
以下の式を用いる，
ax,i =
1
|xij |(xj − xi ) −
k
1
|xij |(yj − yi ) −
k
j∈Ei
ay,i =
j∈N,j=i
j∈Ei
j∈N,j=i
kα q j
k2
+
|xij |2 A2j |x̃ij |α+2
kα q j
k2
+
|xij |2 Bj2 |x̃ij |α+2
ことにより十分な精度で計算を行った．ここで表 1 に更新手法の具体的な手順を示す．
(xj − xi )
(15)
グラフ可視化において単純な計算を行う場合，計算量のオーダは O(E + N 2 ) となる．こ
のときスパースなデータを扱う際には E N 2 となり，特に N が大きなグラフデータを扱
う場合は，計算量の 99% 以上がノード間の斥力項の計算に費やされる．
(yj − yi )
(16)
FR 法ではノード間の斥力項の計算量は式 (12) の第 2 項で与えらる．ここで，アルゴリ
ズムを表 2 に示す．一方，提案手法ではノード間の斥力項は式 (15) および，式 (16) の第 2
なお，本研究においては k = kα = 1 として計算を行った．
項で与えられ，C 言語によるアルゴリズムは表 3 となる．ここで，FR 法との差分を太字で
3.4 座標更新手法と計算量
示した．FR 法のアルゴリズムでは，斥力項の計算量は加乗算 9 回，割算 1 回を行うのに対
座標の更新計算は，FR 法をベースとし，可視化の座標計算手法は以下のように設定する．
xi (t + 1) = xi (t) + η × ai × min (1, 1/|ai |) .
(17)
ここで η は 1 ステップあたりの最大更新幅で，初期配置は乱数で与え，η = 0.001 として
5
10 回の繰返し演算を行った．FR 法では冷却関数を用いて更新幅を 0 に収束させているが，
し，提案手法では加乗算 18 回，割算 2 回を行い，FR 法に比べ 2 倍の計算量を要する．な
お，提案手法では割算回数の軽減のため，あらかじめ 1/A2i および 1/Bi2 を A2in[i] および
B2in[i] として記憶させて計算を行っている．
また，提案手法は並列処理の実装が可能であり，MPI（Message-Passing Interface）や
提案手法ではあらかじめ最大更新幅を十分小さく抑え，さらに繰返し演算の回数を多くする
情報処理学会論文誌
数理モデル化と応用
Vol. 1
No. 1
88–101 (Sep. 2008)
c 2008 Information Processing Society of Japan
94
固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
表 3 提案手法のアルゴリズム
Table 3 Algorithm for the proposed method.
表 4 モデルデータ
Table 4 Model Data.
Data name
Dolphin social network
American college football
Word adjacencies
1: for i = 1 to N do
2:
for i = j, j = 1 to N do
3:
dx = x[j] - x[i];
4:
dy = y[j] - y[i];
5:
dx2 = dx*dx;
6:
dy2 = dy*dy;
7:
r2 = dx2 + dy2;
8:
r2j = dx2*A2in[j] + dy2*B2in[j];
9:
r2in = 1.0 / r2;
10:
r2inj = 1.0 / r2j;
11:
qr4inj = q[j]*r2inj*r2inj;
12:
ax[i] += (r2in+qr4inj*A2in[j])*dx;
13:
ay[i] += (r2in+qr4inj*B2in[j])*dy;
14:
end for
15: end for
N
62
115
112
E
159
616
425
kmax
12
13
49
Ei 5.13
10.71
7.59
GPGPU（General Purpose computation on Graphics Processing Units 1 ）による並列
処理を用いることにより，数万ノードを超える大規模なグラフ可視化が可能であり，提案手
法のような複雑な関数も高速演算可能となる．
図 5 各モデルデータの次数分布
Fig. 5 Distribution of degree k for each model data.
本研究では，3 つのサンプルデータ（表 4 参照）に対して，可視化計算に要した時間は 10
万回の繰返し演算に対し，Intel Core2Quad Q6600（2.4 GHz）を用いて 10 秒以内であっ
た．しかしながら，5 章で用いたグラフデータは N 5, 000 と規模が大きく，さらに高精度
計算を行うため 2 × 107 回の更新計算を，GPU を用いて行った．この計算は上記汎用 CPU
ここでデータ規模の指標として，各データのノード数および，エッジ数，最大次数 kmax ，平
を用いた場合約 800 時間の計算時間を要する．一方，GPU を用いた計算では約 450 倍の高
均次数 Ei を表 4 に示した．また，図 5 はこれらモデルデータの次数分布を表したもので
速化を実現し，約 2 時間で計算が終了した．なお，GPU に関する詳細な報告は別途行う予
ある．
次に，これらのデータにラベルサイズを設定する．サンプルデータとして，i 番目のノー
定である．
ドに対して文字の大きさ Bi をノードの次数に比例し与え，Ai は文字列の長さに対しさら
4. 可 視 化
に文字の大きさで規格化させた値を用いた．ここで i 番目のノードの次数を Ei として，Ai
および Bi を以下のように与えた，
4.1 モデルデータ
2
本研究ではモデルデータとして，Newman のサイト から取得可能な 3 つのグラフデー
タを用いた．これらのデータは各ノードのラベル名，各ノード間のエッジの連結情報を持つ．
Ai = Bi × 0.5 × strlen(name)
(18)
Bi = 0.8 + 0.2 × Ei
(19)
文字列の長さは C 言語の strlen 関数を用いて文字数をカウントし，半角文字に対して 0.5
を乗算してある．ここで一例として，表 5 に “Dolphin social network” のデータに関する
1 http://www.gpgpu.org
2 http://www-personal.umich.edu/˜mejn/netdata/
情報処理学会論文誌
数理モデル化と応用
Vol. 1
各ノードのラベル名，文字列の長さを考慮したスケール，文字の大きさ，およびノードの次
No. 1
88–101 (Sep. 2008)
c 2008 Information Processing Society of Japan
95
固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
表 5 Dolphin social network data
Table 5 Dolphin social network data.
ID
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
name
Beak
Beescratch
Bumper
CCL
Cross
DN16
DN21
DN63
Double
Feather
Fish
Five
Fork
Gallatin
Grin
Haecksel
Hook
Jet
Jonah
Knit
Kringel
MN105
MN23
MN60
MN83
Mus
Notch
Number1
Oscar
Patchback
PL
Ai
4
12
4.8
2.1
2.5
3.2
4
3.6
6
7.7
3.6
2
2
9.6
6.4
8.8
4
3.9
5.5
3.2
9.1
5
2
2.8
4
2.1
3.5
6.3
4.5
11.7
1.8
Bi
2
2.4
1.6
1.4
1
1.6
2
1.8
2
2.2
1.8
1
1
2.4
3.2
2.2
2
2.6
2.2
1.6
2.6
2
1
1.4
2
1.4
1.4
1.8
1.8
2.6
1.8
Ei
6
8
4
3
1
4
6
5
6
7
5
1
1
8
12
7
6
9
7
4
9
6
1
3
6
3
3
5
5
9
5
ID
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
name
Quasi
Ripplefluke
Scabs
Shmuddel
SMN5
SN100
SN4
SN63
SN89
SN9
SN90
SN96
Stripes
Thumper
Topless
TR120
TR77
TR82
TR88
TR99
Trigger
TSN103
TSN83
Upbang
Vau
Wave
Web
Whitetip
Zap
Zig
Zipfel
Ai
2.5
7.7
7
7.2
2
5.5
4.5
4.8
2.4
3.6
3.6
4
7.7
5.6
10.5
3
4
2
2.4
4.4
9.8
4.8
3
6.6
1.8
2.4
3.9
4
2.7
1.5
4.2
Bi
1
1.4
2.8
1.8
1
2.2
3
2.4
1.2
2.4
1.8
2
2.2
1.6
3
1.2
2
1
1.2
2.2
2.8
1.6
1.2
2.2
1.2
1.2
2.6
1
1.8
1
1.4
Ei
1
3
10
5
1
7
11
8
2
8
5
6
7
4
11
2
6
1
2
7
10
4
2
7
2
2
9
1
5
1
3
図 6 スケーリングによる重なりの回避手法
Fig. 6 The scaling method to avoid overlapping of each label.
は，図 6 に示すように，得られた i 番目のノードの座標 (xi , yi ) および j 番目のノードの座
標 (xj , yj ) を用いて
sij = min
Ai + Aj Bi + Bj
,
2|xj − xi | 2|yj − yi |
(20)
と与えることができる．
全体の最小スケーリング S は，以下のように，すべての i，j の組合せに対しての sij の
最大値となる．
S = max sij
(21)
i,j,i=j
可視化計算により得られた座標値全体を S 倍することにより，任意のラベルどうしが重
ならないよう配置することが可能となる．
以下本研究では，全体の座標値をスケーリングし描画を行った可視化結果を用いて議論を
進める．
数をそれぞれ name，Ai ，Bi ，Ei として示した．以下，これら 3 つのデータを用いて，ラ
ベルサイズの異なるグラフ可視化手法に関する議論を行う．
4.3 可視化結果
“Dolphin social network” のデータはニュージーランドに生息する 62 頭のイルカに対し
4.2 スケーリング
て，性別，年齢から各々のイルカを関連づけたものである．図 7 は FR 法による可視化結
ラベル付きグラフ可視化において，ラベルの重なりを確実に回避する手法として全体のス
果であり，ノードが密集した領域の影響により，描画領域全体が広がり相対的にここのラ
ベルが小さくなっていることが分かる．一方 図 8 は提案手法において，α = 2 とした可視
ケーリングを変える手法がある．
任意の i 番目のラベルと j 番目のラベルに対し，重なりを回避する最小スケーリング sij
情報処理学会論文誌
数理モデル化と応用
Vol. 1
No. 1
88–101 (Sep. 2008)
化結果であり，FR 法と比べ個々のラベルも十分な大きさが保たれている．提案手法では，
c 2008 Information Processing Society of Japan
96
固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
図 8 提案手法による “Dolphin social network” の可視化結果．ただし，固有楕円ポテンシャルは α = 2 とした
Fig. 8 Layout result of the “Dolphin social network” with the proposed method, where α = 2.
ノードが密集した領域においても，各ノードにラベルサイズに比例した形状のポテンシャル
を与えたことにより，お互いのラベルを回避するように効率良く配置される．同様に図 9，
図 7 FR 法による “Dolphin social network” の可視化結果
Fig. 7 Layout result of the “Dolphin social network” with the FR method.
図 10 は，それぞれ提案手法に対して固有楕円ポテンシャルを α = 4，α = 6 として与えた
可視化結果である．
情報処理学会論文誌
数理モデル化と応用
Vol. 1
No. 1
88–101 (Sep. 2008)
c 2008 Information Processing Society of Japan
97
固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
図 9 提案手法による “Dolphin social network” の可視化結果．ただし α = 4 として，固有楕円ポテンシャルを
与えた
Fig. 9 Layout result of the “Dolphin social network” with the proposed method, where α = 4.
“American college football” はアメリカの大学のアメリカンフットボールチームの対戦
図 10 提案手法による “Dolphin social network” の可視化結果．ただし α = 6 として，固有楕円ポテンシャル
を与えた
Fig. 10 Layout result of the “Dolphin social network” with the proposed method, where α = 6.
履歴をネットワークとして表現したものであり，データの特性上，図 5 よりも分かるよう
に，個々のノードの次数分布のばらつきが小さいデータである．また，個々のラベルは長い
文字列で構成されているため，FR 法による可視化結果では図 11 のように，ノードが横並
びに隣接した際にラベルの重なりを回避するためにスケーリング S が大きくなってしまう．
4.4 ラベルの面積占有率
ラベル付きグラフ可視化においては全体のスケールを変更することによりラベルの重な
りを回避することが可能である．しかしながらスケーリングによる回避は不必要に描画面
その結果相対的に個々のラベルが小さくなってしまう．しかしながら提案手法では図 12 の
積を大きくし，相対的にラベルの大きさが小さくなるという問題が起きる．1 章で述べたよ
ように，長い文字列も重なりを回避するように効率の良い配置が行われる．
うに，ラベル付きグラフ可視化においてはできるかぎり描画面積を小さくする必要がある．
“Word adjacencies” は名詞と形容詞について単語間の接続関係をネットワークとして表
現したものであり，単語「little」「good」「old」「other」が k ≥ 28 と，高い次数を持つ．
図 13 は FR 法による可視化結果であり，中心の大きなラベルどうしの重なりの影響により
全体の描画領域が広がってしまい，図 13 では個々のラベルを認識することができない．一
方図 14 は提案手法において α = 2 とした可視化結果では，中心の大きなラベルも効率良
く配置されており，提案手法が有効であることが分かる．
情報処理学会論文誌
数理モデル化と応用
Vol. 1
No. 1
88–101 (Sep. 2008)
以下本章では FR 法によるスケーリング後の面積と提案手法によるスケーリング後の面積
を求め，提案手法の妥当性の定量的評価を行う．
描画領域の大きさは，式 (21) の最小スケーリングサイズ S を用いて，x 軸方向の大きさ
X と，y 軸方向の大きさ Y は，
X = max Sxi +
i
Ai
2
− min Sxi −
i
Ai
2
(22)
c 2008 Information Processing Society of Japan
98
固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
図 11 FR 法による “American college football” の可視化結果
Fig. 11 Layout result of the “American college football” with the FR method.
Y = max Syi +
i
Bi
2
− min Syi −
i
Bi
2
図 12 提案手法による “American college football” の可視化結果．ただし，固有楕円ポテンシャルは α = 2 と
した
Fig. 12 Layout result of the “American college football” with the proposed method, where α = 2.
(23)
と，表すことができる．このとき描画領域の面積は XY となり，ラベルの面積占有率 L は
L=
提案手法では，α を大きくすることにより，固有楕円ポテンシャルの影響力を強くすること
N
1 Ai Bi
XY
(24)
i
が可能である．表 6 から，α が大きくなるに従い，ラベルの面積占有率 L が大きくなるこ
とが分かる．
ここで，各データに対しての，スケーリング後の描画面積と，ラベルの面積占有率を表 6，
表 8，および表 7 に示す．
情報処理学会論文誌
“Dolphin social network” では，FR 法による可視化結果においてはラベルの総面積が全
体の面積に対して 1% 程度の占有率であるのに対し，提案手法では 10% 以上となる．また
以下のように定義することができる，
数理モデル化と応用
“American college football” では，提案手法では面積占有率が 20% を超えるのに対し，
FR 法では 2% 程度にとどまる．また，“Word adjacencies” でも同様に，提案手法が 14.8%
Vol. 1
No. 1
88–101 (Sep. 2008)
c 2008 Information Processing Society of Japan
99
固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
図 13 FR 法による “Word adjacencies” の可視化結果
Fig. 13 Layout result of the “Word adjacencies” with the FR method.
である一方，FR 法では 0.3% と 1% に満たない．これは “Word adjacencies” のデータは
ラベルの大きさに偏りがあり，特に FR 法では大きなラベルの影響を受けやすいことを示し
図 14 提案手法による “Word adjacencies” の可視化結果．ただし，固有楕円ポテンシャルは α = 2 とした
Fig. 14 Layout result of the “Word adjacencies” with the proposed method, where α = 2.
ている．しかしながら提案手法では，ラベルの大きさに分布がある場合でも効率の良い配置
が行われていることが分かる．
以上より，固有楕円ポテンシャルを用いた提案手法は，ラベルの大きさを考慮した効率の
良い配置が可能であり，ラベル付きグラフ可視化において有効な手段といえる．
5. 応用例—BLOGRANGER TG
BLOGRANGER TG とは，NTT サイバーソリューション研究所と NTT コミュニケー
ション科学基礎研究所が共同で研究を進めているプロジェクト8) であり，2007 年 12 月より
情報処理学会論文誌
数理モデル化と応用
Vol. 1
No. 1
88–101 (Sep. 2008)
c 2008 Information Processing Society of Japan
100
固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
表 6 “Dolphin social network” の可視化結果における描画サイズとラベルの面積占有率
Table 6 Drawing scale and total label region for “Dolphin social network”.
dolphins
FR 法
α=2
α=4
α=6
X
143.8
60.0
87.5
64.4
Y
293.2
96.7
63.5
56.1
XY
42153.3
5803.7
5556.2
3610.5
L
0.0141
0.1025
0.1071
0.1648
表 7 “American college football” の可視化結果における描画サイズとラベルの面積占有率
Table 7 Drawing scale and total label region for “American college football”.
football
FR 法
α=2
X
447.6
151.2
Y
469.3
160.4
XY
210033.7
24265.8
L
0.0233
0.2017
図 15 BLOGRANGER TG によるタグクラウド地図．ただし画像は 2008 年 1 月現在のものである
Fig. 15 Tag cloud map of “BLOGRANGER TG”.
表 8 “Word adjacencies” の可視化結果における描画サイズとラベルの面積占有率
Table 8 Drawing scale and total label region for “Word adjacencies”.
adjnoun
FR 法
α=2
X
747.0
101.3
Y
850.6
129.2
XY
635397.0
13081.6
L
0.0031
0.1484
6. ま と め
本研究では各ノードに固有の楕円ポテンシャルを与えることにより，ラベルどうしの重な
りを回避する座標計算手法を提案した．
goo ラボにおいて公開1 されている大規模タグクラウド・ブログ地図である．このプロジェ
従来手法では，ノードを “点” として扱うためにラベル付きグラフ可視化においては，全
クトでは，従来のタグクラウドのように順番に羅列するのではなく，類似性を持ったタグど
体のスケーリングを大きくするか，もしくは後処理3)–5) を行う必要がある．しかしながら
うしをノード間の類似度を基準に，関連性の高いもの近傍に配置したものであり，可視化計
提案手法では，ラベルサイズに依存した固有楕円ポテンシャルを用いることにより，後処理
算には提案手法を用いている．詳細な手法と評価は別途報告する予定である．
を必要とせず，効率良く配置を行うことが可能であることを示した．
BLOGRANGER TG では，最新の 1,500 万ブログ記事より約 5,000 種類のタグの自動
提案手法では，固有楕円ポテンシャル成分と点対称ポテンシャル成分の 2 成分により，斥
抽出を行い，タグをノード，タグ間の類似度をエッジとして，重み付きの無向グラフを用い
力のポテンシャル関数を二重化することによって，従来手法の可視化結果に対してメンタル
る．提案手法による可視化計算手法を用いて，全体のタグマップ画像を 10000 × 10000 ピク
マップを保ちつつ，局所的にはラベルの重なりを効率良く回避することを可能とした．ま
セルで生成し，Ajax を用いてスクローラブルマップとしてサービス提供を行っている．本
た，斥力項のポテンシャル関数の重ね合わせにより，FADE などの近似手法も実装可能で
サービスではスクローラブルマップ内タグをクリックすることにより，関連する最新のブロ
あり，さらに GPU の利用により，大規模グラフデータに対しても高速に計算を行うことを
グの検索が可能である．図 15 は現在サービス中の地図であり，画像は 2008 年 1 月 9 日現
可能とした．
在のものである．地図はマウスによるスクロールが可能であり，さらに左上に全体の広域図
従来グラフ可視化においては引力，斥力のポテンシャル関数は自然科学的な（たとえば
万有引力のような）普遍的な関数が存在せず，ポテンシャルの関数の設定には自由度が生じ
を表示している．
る．それゆえ当該分野においては，いまだに評価手法が確立されておらず，可視化結果の定
量的評価は重要課題として残る．本研究では面積占有率 L を用いて定量的な評価を行った
1 http://ranger.labs.goo.ne.jp/TG/
情報処理学会論文誌
数理モデル化と応用
Vol. 1
No. 1
88–101 (Sep. 2008)
c 2008 Information Processing Society of Japan
101
固有楕円ポテンシャルを利用したラベル付きグラフ可視化の座標計算
が，FR 法との比較には有効な手段である一方，他の手法との比較においては問題も残る．
山田 武士（正会員）
今後は可視化結果の評価手法に関して重点的に研究を進めてゆく予定である．
昭和 39 年生．昭和 63 年 3 月東京大学理学部数学科卒業．同年 NTT 入
参
考 文
社．平成 8 年より 1 年間英国コベントリー大学客員研究員．主として機械
献
学習，データマイニング，メタヒューリスティクスによる組合せ最適化等
1) Kamada, T. and Kawai, S.: An algorithm for drawing general undirected graphs,
Information Processing Letters, Vol.12, No.31, pp.7–15 (1989).
2) Fruchterman, T.M.J. and Reingold, E.M.: Graph Drawing by Force-directed Placement, Software — Practice and Experience, Vol.11, No.21, pp.1129–1164 (1991).
3) Ebner, D., Klau, G.W. and Weiskircher, R.: Label Number Maximization in the
Slider Model, Proc. Graph Drawing, New York, pp.144–154 (2004).
4) Theophil, S. and Schȯdel, A.: An Efficient Algorithm for ScatterChart Labeling,
Proc. National Conference on AAAI, Boston, Massachusetts, USA (July 2006).
5) Misue, K., Eades, P., Lai, W. and Sugiyama, K: Layout Adjustment and the Mental Map, Journal of Visual Languages and Computing, Vol.6, No.2, pp.183–210
(1995).
6) Quigley, A. and Eades, P.: FADE: Graph Drawing, Clustering, and Visual Abstraction, Proc. Graph Drawing 2000, Lecture Notes in Computer Science, 1984,
pp.183–196 (2001).
7) Andreas, N.: Visual clustering of graphs with nonuniform degrees, Technical Report 02/04, BTU Cottbus, (2004).
8) Fujimura, K., Fujimura, S., Matsubayashi, T., Yamada, T. and Okuda, H.: Topigraphy: Visualization for large-scale Tag Clouds, Proc. World Wide Web, Beijing,
pp.1087–1088 (2008).
の研究に従事．博士（情報学）．電子情報通信学会，ACM，IEEE 各会員．
藤村
滋
日本電信電話株式会社サイバーソリューション研究所所属．平成 17 年
東京大学大学院情報理工学系研究科修士課程修了後，日本電信電話株式会
社に入社．Web マイニング，自然言語処理等の研究開発に従事．人工知
能学会会員．
藤村
考（正会員）
昭和 59 年北海道大学工学部電気工学科卒業．平成元年同大学大学院工
学研究科情報工学専攻博士課程修了．同年日本電信電話（株）に入社．以
来，トランザクション処理記述言語，汎用電子チケットシステム，電子決
済システム，ウェブマイニングの研究開発に従事．現在，NTT サイバー
ソリューション研究所所属．電気通信大学大学院情報システム学研究科客
(平成 19 年 11 月 22 日受付)
員教授．工学博士．電子情報通信学会，日本社会情報学会各会員．
(平成 20 年 1 月 10 日再受付)
(平成 20 年 2 月 14 日採録)
松林 達史
昭和 50 年生．平成 12 年京都大学理学部物理学科卒業．平成 17 年東京
工業大学理工学研究科地球惑星科学専攻博士課程修了．同年日本電信電話
（株）入社．現在，NTT コミュニケーション科学基礎研究所研究員．主と
して可視化の研究開発に従事．理学博士．
情報処理学会論文誌
数理モデル化と応用
Vol. 1
No. 1
88–101 (Sep. 2008)
c 2008 Information Processing Society of Japan