ネットワークの情報が容易に取得できるようになった近年，大規模ネットワークの描画手法の開発への要求は高まっている．従来手法ではネットワークにおける要素の数を減らすことで対応することが多かったが，この手法では曖昧な情報のみしか読み取ることができない．

また，読み手により適切なグラフの規模は異なるということに対応することができない．

本研究では，２つの新しい描画手法を用いて２部グラフを対象とした大規模ネットワークの可読性向上を狙う．可読性向上には，「見易さ」と「読取りやすさ」の向上が不可欠である．

見易さを向上させる手法として「縮退描画手法」を開発した．クラスタリングによりノード間の類似度を求めておき，閾値を超えた類似度のノード集合を

1

つのクラスタとして描画する可視化手法である．閾値は読み手がスライダにより変更でき，ネットワーク図の拡縮を自由に行うことが可能である．

読取りやすさを向上させる手法として「等類似度線描画手法」を開発した．縮退描画手法同様クラスタリングの情報を用い，閾値を超えた類似度のノード集合を閉曲線で囲み描画する可視化手法である．ノード間の類似度の高さを等高線のように表示することで関連性を直接可視化することにより，より理解しやすくさせるのが狙いである．

縮退描画手法と等類似度線描画手法の有効性の検証と評価をするため被験者実験を行った．

結果として，両手法ともグラフの可読性を向上させることに成功しており，特にグラフからの情報の読取りやすさが向上することが確認された．

本描画手法は，読み手が求める適切な情報を表示することで，大規模ネットワークの可読性向上を達成している．従来手法では困難であった，大規模ネットワークの全体的な俯瞰と特定の注視要素の関係情報が一度に読取ることが可能になった．

(3)

図目次

1.1

ネットワークの例

. . . . 2

1.2

グラフを図で表す例

. . . . 2

2.1 . . . . 8

2.2

スプリングモデルのイメージ

. . . . 8

2.3

スプリングモデルによるレイアウト

. . . . 9

2.4 . . . . 10

3.1

クラスタリング手法の分類

. . . . 16

3.2

デンドログラム

. . . . 16

3.3

最短距離クラスタリング

. . . . 17

3.4

クラスタリングの過程

. . . . 19

3.5

クラスタリング順による変化

. . . . 21

3.6 ClusteredAnchorViz

の概観

. . . . 22

3.7

システム構成

. . . . 23

4.1

スライダ変更時の走査

. . . . 26

4.2

デンドログラム切断時の表示するノードとクラスタ

. . . . 27

4.3

アプリケーション初期画面

. . . . 28

4.4

クラスタの展開の様子

. . . . 29

5.1

等類似度描画手法を用いた表現

. . . . 31

5.2

アノテーションで囲み線を用いる例

. . . . 32

5.3

凸包

. . . . 33

5.4

閉曲線を描画する方法

. . . . 34

6.1

実験に用いたグラフをアンカーマップにより描画

. . . . 36

6.2

実験に用いたグラフを縮退描画手法で描画した様子

. . . . 38

6.3

実験に用いたグラフを等類似度線で描画した様子

. . . . 39

7.1

購入時間帯

–

商品の関係のアンカーマップによる描画

. . . . 41

7.2

提案手法による購入時間帯

–

商品の関係の描画

. . . . 42

7.3

購入者

—

商品のアンカーマップによる描画

. . . . 44

(7)

7.4

等類似度線描画手法（

t = 100%

）による購入者

–

. . . . 44

7.5

縮退描画手法による購入者

–

. . . . 45

7.6

２ホップ

. . . . 46

7.7

アンカーマップによる論文共著者情報の可視化

. . . . 47

7.8

等類似度線描画手法（

t = 0%

）による論文共著者情報の可視化

. . . . 47

7.9

縮退描画手法による論文共著者情報の可視化

. . . . 48

8.1

本研究の位置付け

. . . . 54

(8)

第 1 _{章序論}

1.1

ネットワーク

ネットワークはこの世界の至る所に満ちあふれている．言葉こそインターネットの普及により身近になったばかりという感覚を受けるが，人間関係，鉄道路線，電話回路網など人間の生活には切り離せない場所に偏在している（図

1.1

¹）．

近年

Web2.0

という言葉が叫ばれるようになり，一般のユーザが他のユーザに影響を与える

ようなシステムが増えてきている．ソーシャル・ネットワーキング・サービス（

SNS

）はその典型であり，リアルな世界以外のヴァーチャルな友人関係が世界の様々な場所で構築され，

その人間関係のネットワークは拡大の一途を辿っている．

人間関係のネットワークの研究において，しばしば「スモールワールド」もしくは「六次の隔たり（

6–degree

）」という単語が現れる．これは，スタンレー・ミルグラムが

1967

年に行ったスモールワールド実験

[1]

に依るもので，友人関係のネットワークから２人を任意に抽出した場合，最高でも６人の人間の仲介で接続されるという仮説である．

ソーシャル・ネットワーキング・サービス

mixi

の例を示すと，

2005

年の湯田ら，森ら，安田らによる分析結果によると，友人関係のネットワークはマイミク（友人）の平均数が

10.4

，

6

ホップで

96%

をカバーでき，スモールワールドの特徴を備えっていることがわかっている

[2]

．

このようなネットワークの場合，分析には友達同士の関係だけではなく，彼らが所属するコミュニティを読み解くことで，理解が深まるというと言うことが知られている

[3]

．人と所属の関係は２部グラフ（２部ネットワーク）という形式で表現され，社会的なネットワークの特徴を捉える上で重要な役割を担う表現であると考えられている

[4]

．

1.2

ネットワークの可視化

普段のネットワークを意識して生活している人々はそれほど多くはない．なぜなら，ネットワークは目に見えない抽象的なオブジェクトであるためである．

ネットワークは物（オブジェクト）とそのつながりにより構成される構造体の内，フロー

（流れ）が発生するものを指す．この構造体はグラフとして数学的に表現することが可能である．言い換えると，何らかの意味を持ったグラフがネットワークである．

数学的表現のグラフは，人間が直感的に要素間のつながりを認知するには困難な表現手法である．そこで，我々は日常的グラフを認識する方法として用いているのが，「図」というイ

(9)

(a)鉄道路線図 (b) LAN回線図

図

1.1:

ネットワークの例

図

1.2:

グラフを図で表す例

ンタフェースである．図

1.2

にグラフの数学的表記から図への変換例を示す．このように，抽象的な「データ」を，直接見ることが出来る表現へ変換することを，可視化（

Visualization

）と言う．

可視化の用途は，構造の認識や他人との意思疎通，データマイニング，問題発見などがあり，様々な分野で研究が盛んに行われている．

1.3

可視化の目的

人間は外界の情報を視覚，聴覚，触覚，味覚，嗅覚の五感を使い知覚している．この中でも視覚は全情報の

80

％もの情報を得ていると言われており

[5]

，視覚情報をわかりやすくすることがいかに理解につながるかが想像できる．

本研究で扱う情報可視化（

Information Visualization

）は科学的なデータを視覚化する科学的可視化（

Scientific Visualization

）の流れを汲むものである

[6]

．情報可視化の目的は知識の取得と発見である．多量のデータをコンピュータにより可視化により支援し，人間だけでは得

(10)

られない情報と知識の取得，発見を促進する．すなわち，グラフをコンピュータで処理をして結果を見せることではなく，人がそれを情報として利用するための仕組みが目的の技術である．

そのため，結果を読み手に提示させるだけの一方向作用だけではなく，読み手が入力した操作を反映させるインタラクションシステムの環境が適していると言われている

[7]

．

1.4

可視化方法の重要性

ネットワークの可視化における表現手法には様々有るが，図は大きく分けて４つに分類することが出来る．

•

^座標系

:

折れ線グラフ，棒グラフなど

•

^行列系

:

表など

•

^領域系

:

ベン図など

•

^{網図（連結）系}

:

ネットワーク図，フローチャートなど

これらの表現手法の内，座標系や行列系は従来から研究が進んでおり，比較的表現方法がはっきりしている．それに対し領域系，網図系，およびその複合系は，ネットワーク構造の視覚的記法として重要で有るにもかかわらず，描画方法があまり発達していない．

領域系や網図系の図は日常的に利用され，それにより理解が容易になることは経験的に認識されている．ただし，その図の認識のしやすさ，されやすさは，図の書き方に強く依存する．図の美しさによりその図の価値が決定され，理解の支援にも混乱を引き起こす原因にも成り得るのである

[8]

．そのため，構造がわかりやすい等の美しい図を描くことは，可視化にとって最も重要な点の一つであり既存研究の大きな課題となっている．

1.5

ネットワークの肥大化と可視化への影響

情報技術の発展により，身の回りにあるネットワークが肥大化の一途を辿っていることは衆知の事実である．

先に述べた

mixi

は，

2005

年時点でノード数

36

万個，エッジ数

190

万リンクであった．

2008

年

1

月現在では既に

1000

万ノードを超えており，顕著な規模増加が起きている．また，

mixi

の友人関係は擬集性の高いネットワークであることが判明している．つまり，これを

2

次元平面上に可視化した場合，狭い空間にノードがひしめき合い，エッジの交差が多数存在する塊が随所に現れるような表現で描画されることが予想される．

ノード数とエッジ数の増加は，読み手によるネットワークの認識を難しくさせる

[9]

．その理由の一つに可視化結果の可読性の低下がある．表示するデバイスの解像度を上げることできめ細かい描画を行い，すべてのノードとエッジを表示することは可能であるが，人間の理

(11)

解度の向上には繋がりにくい．人間の空間認識能力がはある一定以上上がらないためである．

つまり，読み手がネットワークを認識・理解するのに適当な大きさの領域に，簡潔に描画することが重要となる．

グラフ描画において可読性の問題は重要なトピックスの一つであり，可読性の向上に関する研究は盛んに行われている．

1.6

目的

本研究では，２部グラフで構成される大規模ネットワークの可視化における可読性を向上させることを目的とする．２部グラフという特殊な構造を持ったネットワークを，その特徴を利用した可視化を行うことで読み手の理解を高める．従来の手法は読みることが難しかった構造を読み手に把握し易くし，新たな知識の取得を支援する．

1.7

_{本研究の貢献}

従来手法では注目されていなかったグラフの意味を読み取り易くするという観点を取り入れ，大規模２部グラフの可読性を向上させる手法を開発した．この手法を用いることで，グラフ描画のエキスパートだけではなく普段グラフを読まない人にも，効率よく知識を得られるような描画が可能となる．

(12)

第 2 章ネットワーク描画と可読性

本章では，ネットワークの可視化およびその可読性についての考察を行う．まず，ネットワークの構造であるグラフの説明を行い，本研究で扱う２部グラフについて構造と描画手法の説明を行う．最後に，グラフを可視化したときの可読性とは何かについてを考察する．

2.1

_グラフ

グラフとは，ノード（節点・頂点）の集合とノード間を接続するエッジ（辺・リンク）の集合により構成される数学的なデータ表現である．ノード集合を

V

，エッジ集合を

E

としたとき以下の式

2.1

として表記される．

G = (V, E)

E ⊆ V × V (2.1)

グラフはネットワークの特性により分類することが可能である．エッジには有向エッジと無向エッジの２種類が有り，それを有するグラフのことはそれぞれ有向グラフと無向グラフと呼ばれる．一般に木構造と言われる構造も，閉路を持たず単連結である無向グラフのことを指す．グラフは抽象化された概念の１つの有力な表現形式であるので，様々な分野で基礎的なモデルとして広く利用されている

[8]

．

様々なグラフ構造のうち，本研究では２部グラフとして表現されるネットワークに焦点をあてる．

2.2

_{２部グラフ}

ノードの集合を二つの排他的な集合

V

₁と

V

₂ に分割することができ，エッジの集合

E

が

V

1

× V

2の部分集合であるようなグラフを２部グラフという．数学的には以下の式として表現される（式

(2.2)

）．

G = (V

₁

∪ V

₂

, E) V

1

∩ V

2

= ϕ E ⊆ V

1

× V

2

(2.2)

２部グラフをもつ構造のネットワーク（二部ネットワーク）は実世界の様々な場面で現れている．一般的に所属関係のネットワークは必ず２部グラフの構造を持っている．これは，ソーシャルネットワークにおける「コミュニティ」と「メンバー」の関係であったり，芸能界に

(13)

おける「出演作品」と「出演者」の関係，購買ネットワークにおける「顧客」と「購買商品」

の関係などが例に挙げられる．

amazon.com

で買い物をする際に，「この商品をチェックした人はこんな商品もチェックしています」という項目があるが，これも「商品」と「購入者」の２部グラフの関係が形成されているものであり，日常的に利用される二部ネットワークの一例である．

研究分野でも２部グラフは注目されている．特に社会ネットワークにおいてその注目度は高い．ソーシャルネットワークに関しては友人関係だけを見るのではなく，彼らの属するコミュニティの関係も読み解くことで，理解が深まるのではないかという仮説があることは先に述べた通りであり，それに関しての研究も多数行われている

[10]

．ウェブログについてもブロガーとコミュニティの２部ネットワークを解析することで，ネットワークが発展するとの報告がある

[4]

．論文の共著者関係のネットワークにおいても，その著者を結ぶ論文の存在との関係を見ることで，ネットワークの特徴の新たな発見を期待できる

[11, 12, 13]

．

2.3

２部グラフは様々な形式で記述することが可能である．グラフは基本的に数学的な構造体であるが，先に述べた通り人間にとって数式表現のまま構造をとらえるのは難しい．そのため，人間に読みやすい形に視覚化を行う．本節では２部グラフの可視化表現のうち代表的な表現形式を述べる．商品と購買者から成る購買関係の２部グラフを例に用い，実際に図で表しながら説明を行う．

2.3.1

数学的形式

数学的表記はグラフ構造の表現形式としては基本である．２部グラフにおいてもそれは変わらず，グラフのすべての情報を表現出来るため，情報が欠落してはいけない伝達をする時やグラフを定義する時に用いられる．

G =(V

1

∪ V

2

, E)

V

1

={

石垣

,

岩波

,

斉藤

,

坂崎

,

鈴水

,

中里

}

V

₂

= {

^珈琲

,

紅茶

,

麦茶

,

烏龍茶

,

ビール

,

コーラ

,

栄養ドリンク

} E = { (

石垣

,

珈琲

), (

石垣

,

ビール

), (

石垣

,

コーラ

), (

岩波

,

紅茶

),

(

斉藤

,

珈琲

), (

斉藤

,

紅茶

), (

斉藤

,

烏龍茶

), (

斉藤

,

栄養ドリンク

), (

坂崎

,

紅茶

), (

坂崎

,

麦茶

), (

坂崎

,

コーラ

), (

鈴水

,

紅茶

), (

鈴水

,

烏龍茶

), (

中里

,

珈琲

), (

中里

,

紅茶

), (

中里

,

麦茶

),

(

中里

,

烏龍茶

), (

中里

,

コーラ

), (

中里

,

栄養ドリンク

) }

(14)

上記がグラフを数学的形式で表現した例である．この手法は無論グラフを読み解く際にはあまり向かない．

2.3.2

行列形式

グラフ構造は行列形式で記述することが可能である．エッジは２つの集合間にのみ存在するという２部グラフの特性から通常のグラフよりも簡潔に表現されるため，よく用いられる手法である．それぞれのノード集合を行と列に分解して表記する図

2.1(a)

の例では行に購入者，列に商品を対応させ，購入者が購入した商品の欄に数値を入れることで表現している．

行列表現の特徴としては，一つのノードを注目したときの，エッジの量がわかりやすいことから他のノードの関係を認識するのに良好であることがあげられる．

また，行列表現では情報を落とさない表現が可能であることも特徴の一つである．例えば，

購買情報においては「購入者がどれだけその商品を買ったか」といった情報が存在する．グラフ表現において，この情報はエッジの「重み（

weight)

」として表現される．行列表現においてはこのエッジの重みを数値として明確に表現することが出来るため，正確な詳しい情報を知り得たいような状況では，特に有効な手法である．

但し，視覚的な工夫がなされている訳ではないため，購入者同士の関係構造などの把握にはあまり適さない．また，描画領域の空間効率は他の手法と比較してあまり良くないため，大規模なグラフを表現するときには広い描画領域が必要となる．

2.3.3

網図形式

ネットワークの可視化にはよく網図形（連結系）の表現が用いられる．そのうち，２部グラフの表記に特化した形式では２層形式がある．二層形式はノードの２つの集合をそれぞれ１列で表現する形式である．ノードを点や丸，長方形などで表し，ノード間を直線や曲線で接続することでエッジを表し，グラフの関係を表現する．

図

2.1(b)

は，左側に購入者を，右側に購入商品を配置した二層形式の図である．一列に集

合が整列されているおり，それぞれの集合に属するノードが理解しやすいことが特徴であるため，２部グラフの概要を説明する際に用いられることが多い．他の特徴としては，それぞれの集合に属するノードの数の把握がしやすいこと，エッジ数の多いノードが把握しやすいなどが挙げられる．

この手法の場合エッジの交差の問題の解決が難しく，完全２部グラフに近くなるほどどのノードとどのノードが接続しているかがわかりにくくなってしまう．また，エッジの重みを表現することが難しいため，グラフの解析を目的する時の可視化手法としてはあまり適さない．

2.4

スプリングモデル

グラフの可視化に用いられる網図系の代表的な描画法の１つとして，スプリングモデル（ばね埋込モデル，

Spring Embedded Model

）

[14]

がある．エッジを自然長をもつバネと仮定し，

(15)

(a)行列形式 (b)２層形式

図

2.1:

(a)エッジをばねに見立てる (b)斥力発生

図

2.2:

スプリングモデルのイメージ

エッジにより接続されないノード同士は斥力により反発力を発生させる（図

2.2

）．バネと斥力によりノードを配置し，安定状態を計算することで最終的にノードのレイアウトを求める手法である．

ノードのレイアウトに関しては以下の流れで行う．

1.

初期配置を決定する（ランダム配置など）

2.

各々のノードに働く力の合計を求める

3.

求めた力に従い，ノードのレイアウトを変更する

4. 2

に戻る．

スプリングモデルは２部グラフ専用の表現形式ではないが，二層形式と異なり重みのある

(16)

図

2.3:

スプリングモデルによるレイアウト

エッジを表現することが可能であるため，ノードの関係をより良く知ることが出来る．そのため，グラフの自動描画の基本レイアウトとして多くの研究で用いられている．

図

2.3

は，スプリングモデルを適応した例である．長方形で表示したノードが購買者を，円で表示したノードが商品を表しており，エッジは直線の接続で表現されている．エッジに埋め込まれたばねの力で接続情報が似ているノードが近くにレイアウトされ，ノード同士の関連性が認知しやすくなっている．

2.5 [15]

は，スプリングモデルを発展させて２部グラフに特化させた描画手法である．２部グラフの２種類のノードの集合のうち一方のノード集合の位置に制約を課した描画スタイルと定義される．

前節のスプリングモデルでは全体的な構造は把握しやすいが，２つの集合（例では購買者と商品）が混在しているため，ネットワークの構造がわかりやすいとはいえない．二層形式ではノード集合同士は分割されているので把握はしやすいが，それぞれのノード集合内部同士の関連性の把握は難しい．

ネットワーク構造を効率よく把握するには観点の導入が有効であり，それによりネットワークの構造的特徴を認知するのが容易となる．アンカーマップは，片方のノード集合を固定し座標軸のような効果を与え，観点導入の役割を果たしている．２種類のノードは位置に制約を課す方をアンカーと呼び，もう片方をフリーノードと呼ぶ．アンカーとフリーノードは交換可能で，どちらをアンカーにするかは自由に変更することが出来る．アンカーは円周上に等間隔配置（正多角形の頂点に配置）され，フリーノードはアンカーとの関係を表現する適

(17)

図

2.4:

切な位置にスプリングモデルでレイアウトされる．エッジはアンカーとフリーノードを直線で接続する形式で表現される．

アンカーの配置（順番）はいくつかの美的基準を満たすように行われる．

•

エッジの総線長を最も短くする

•

エッジの交差数を最も少なくする

•

同じフリーノードに接続するアンカーを近くに配置する

図

2.4

は，購入者をアンカー，商品をフリーノードとしてアンカーマップで描画した図である．「紅茶はグラフの中心に配置されているため多くの購買者に買われている」といった，スリングモデルからは発見が難しい情報を素早く認知することが出来る．

現在，数多の２部グラフの表現手法の内，アンカーマップは２部グラフを最も効率的に表現できる手法の一つと考えられる．

2.6

ネットワーク図における可読性

ネットワークを可視化した図は，良い描画をすることは重要であることは第

1

章で述べた．

その描画の善し悪しはグラフの可読性に影響する．

(18)

先に述べたアンカーマップにおいても，アンカーの配置順により可読性の向上を狙っている

[16]

．しかし，ノードの数が増大していくと既存手法のみで対応することは難しい．出力する画面というものは大きさが限られており，画面を埋め尽くすほどのノードを描画しなければならないときには，ノードのレイアウトを変更しても読み手は見易いと感じないと予想できる．また，必要以上に大きい画面や異常なまでに高精細な解像度で出力したところで，これもまたグラフの意味を掴むのは用意ではないだろう．

では，可読性とは如何なるものなのか．

従来のグラフレイアウト手法において可読性を高めるための指標として設定されているのが美的基準（

Aesthetic Criteria

）である．人間の認知特性に関係する様々な基準が定義されている．

•

ノードの重なりが少ない

•

エッジの重なりが少ない

•

隣接関係を持つノードが近くに配置される

•

エッジの交差数が少ない

•

^{エッジの総線長が短い}

•

^{描画領域が小さい}

•

エッジの屈折点が少ない

•

ノードが一様に分布されている

•

構造の階層性を表現する

•

構造の対称性を表現する

これらを満たすレイアウトを生成することが望ましいと考えられている．むろんこれらは排他的な性質を持つわけではなく，競合的な性質を持つ組み合わせや，逆に相乗効果をもたらす組み合わせも存在する．

私は可読性にはいくつかの側面があり，その中でも以下の二つが重要であると考えた．

•

^{空間構造的な可読性}

•

意味的な可読性

「空間構造的な可読性」は，可視化したグラフの「見易さ」のことを指す．見易さとは，人間が視覚的に見易いと感じることの指標であり，見た目に「すっきりしている」という抽象的な感覚のことをここでは定義する．具体的にグラフ描画においては「構成要素（ノード・エッジ）が少ない」であったり，「エッジがあまり交差していない」，「ノードが大きい」などのことで，空間構造的な可読性が向上すると考える．既存手法のアンカーマップにおいてのアン

(19)

表

2.1:

可読性向上手法とその効果

（情報を保ったままの手法）（情報を削減する手法）

レイアウト変更などクラスタリングなど

可読性（全体）

⃝ ⃝

構造的な可読性

⃝ ⃝ ◦

意味的な可読性

⃝ △ ↔ ⃝

カーのレイアウトの美的基準に「エッジの交差数を最小にする」というものがあるが，これはこの可読性を直接的に向上させるものである．

この指標はグラフの自動描画の既存手法で，可読性において一番重要視されてきた点であると考える．なぜなら，「見易い」「見難い」はグラフのみならず，広範囲の分野で人間の感覚に直接効果を及ぼすものであるからである．全く同じ意味を持つ２つの対象があり，見易いものと見づらいものがあれば，見易いものが良いことは自明の理であり可視化の目的の１つはまさにそれである．

大規模グラフの空間構造的な可読性においての先行研究のアプローチとしては，高精細描画とクラスタリングが主なものとしてあげられる．高精細描画は解像度の高い出力を行い，広大な出力空間を有効に用いてノードを配置することで可読性を向上させようという試みである．解像度を高くするため，グラフの規模が増大すれば一つ一つの要素は拡大しなければ目視できなくなる可能性もある手法である．クラスタリングとは集合分類手法のひとつで，

3.2

にて詳しく述べる．類似した情報を持つノードを１つのノードとして表示する手法をとることで，ノードとエッジの数を減少させてグラフを「すっきり」と描画する．空間構造的な可読性を向上させるに当たっては，単純であるが極めて効果的な方法であると考えられる．

「意味的な可読性」は，可視化したグラフの「読み取り易さ」のことを指す．読み取り易さとは，読み手がどの程度グラフの意味を掴みやすいと感じるかということである．こちらは，「見易さ」と違い直接視覚に訴えてくることはない．しかし，人間が可視化したグラフを見る目的はグラフの内容を知ることである．すなわち，内容を取りやすい可視化結果は可読性の高い可視化結果であると言い換えることも可能である．

先に述べたクラスタリングによるノードの数を減らす手法では，描画したグラフの構造とクラスタリング前の元のグラフの構造とが異なってしまう．すなわち，可読性を確保するため情報量を犠牲にしているのである．そのため，グラフの構造を正しく理解することが難しくなる危険性がある．

先行研究において，意味的な可読性はあまり重要視されていない．無論，この可読性を向上させる手法もあるが，多くが空間構造的な可読性を向上した結果の間接作用であり，直接的に効果を及ぼす既存手法は少ない．グラフの自動描画の可読性においては，見易さは一番重要なファクターだと考えられる．しかし，意味がとれないように見易くしても本末転倒である．

いかなる表現にも共通することだが，「読み手」により解釈が変化するという点も重要で

(20)

ある．いかに作り手が一番わかりやすい表現を作成したところで，全世界の人間が一番わかりやすいとは考えない．人間はそれぞれが異なった感覚を持ち認識能力も各々異なるためである．画面上に配置されているノードの数がどの程度で適切であると感じるかは人によって異なる．加えて，その時の目的により欲しい描画は異なる

[17]

．すなわち，可読性の向上を考える際には「読み手」が読みやすい可視化を考える必要性は常に付きまとう．

私は，「空間構造的な可読性」「意味的な可読性」という２つの可読性の向上が大規模グラフの可読性向上のキーであると考えた．加えて「読み手」各々に最適な出力結果が得られるような表現手法を取り入れることで，更なる可読性の向上が期待できる．次章よりその手法について説明を述べる．

(21)

第 3 章可読性を向上させるためのアプローチ

本章では大規模なネットワークの可読性を向上させる手法を述べる．第

2.6

節で述べた２つの可読性，「空間構造的な可読性」「意味的な可読性」を向上させることを目的とし，そのアプローチとして，グラフの構造をコンピュータで解釈し，その情報が読み手によって効果的に反映させることが可能な表現手法で対応する．

3.1

概要

私は大規模な２部グラフの可読性を向上させる描画手法として，「縮退描画手法」と「等類似度描画手法」を考案した．

可読性向上のためには，第

2.6

節で述べた「空間構造的な可読性」と「意味的な可読性」の向上が必要であると考える．加えて，読み手の意図に対応した描画状態，つまり読み手の操作に対応して構造を変更・描画に反映させる手法が可読性向上に繋がると考える．

本描画手法を開発するにあたってのコンセプトは以下の二つである．

•

コンピュータで構造を解析し，それを可視化結果に反映させること

•

読み手の操作に対応して可視化結果を変更するインタラクションシステムであることまず，グラフの構造を捉えるためにクラスタリングを用いた．描画にはアンカーマップの拡張表現を用い，読み手に最適な描画状態を与える手法を加えた．．

本章では，データの解析から描画までの仕組みを述べ，描画手法については次章以降で詳しく述べる．

3.2

クラスタリング

クラスタリングとは、異なる性質のもの同士が混在している集合の中から互いに類似したものを集めてクラスタを形成することで，集合を分類する手法である

[18]

．

一般的にグラフ描画におけるクラスタリングは，論理的に同じ接続構造を持つノードを一つのノードとして描画する手法として扱われることが多い．しかし，この手法はグラフが大規模になると効果が低くなる．グラフ全体に対して同じ接続構造をもつノードの割合は減少すると考えられるためである．無論，対象とするグラフに依り効果に違いはあるが，すべてのグラフに対応することはできないことがわかる．

(22)

上記の手法を拡張し，階層型クラスタリングを用いて多階層のクラスタ構造を形成する手法がある．この手法ではスケーラビリティが高く，どんな大きいグラフでも小さくすることが出来るが，

•

小さくしたことにより情報が欠落する

•

クラスタの集約・展開方法が洗練されていないといった問題が残されている．

本研究で扱うクラスタリング手法は，ノード間のエッジの接続関係から類似度を計算し，階層構造のクラスタを生成するものである．ただし，クラスタが２部グラフの２種類の集合を跨いで形成されることはないようにして，２部グラフの構造を保持するよう注意する．

3.2.1

クラスタリング手法の選択

クラスタリングの手法は，まず大きく「階層型クラスタリング」と「分割型（区分型）クラスタリング」の二つに分けることが出来る（図

3.1

）．

分割型（区分型）クラスタリングとは，要素全体をいくつかのグループに分割する手法であり，自己組織化マップの生成などに利用される．代表的な手法に

k-means

法などがあり，あらかじめ，分割するクラスタの数が分かっている場合には有効な手法である．

階層型クラスタリングとは階層構造を成すようにグループを生成するものである．入れ子を構成するようにクラスタを生成すると考えても良い．

階層型クラスタリングは「分岐型（分割型）」「凝集型（併合型）」に二分される．分岐型は，

要素集合を１つの大きなクラスタとして考え，クラスタを分割しながら，階層構造を形成していく物である．逆に凝集型は１つの要素を１つのクラスタとする初期状態を与え，最も距離が近い二つのクラスタを逐次的に結合していき，すべての要素が１つのクラスタになるまで階層構造を形成する．両者ともクラスタリングの結果はデンドログラムで表現することが出来る（図

3.2

）．

一般的に階層型クラスタリングは集約型の方が多く用いられ，方法論的にも整理されている

[19]

．集約型の代表的な手法としてはウォード法などがある．

グラフ構造の解析と描画をする上で，スケーラビリティが高いのは階層型クラスタリングである．また，クラスタリングの情報を１つの一貫した軸で扱いたいため，集約型の最短距離法を用いて開発を行った．詳しい特徴については後述の

3.2.4

節で述べる．

3.2.2

ノード間類似度の導出方法

クラスタリングを行う際には，要素同士の関連性を表す何らかの指標が必要となる．一般にその指標は要素間の「距離」や「類似度」，「非類似度」などで定義される．グラフにおいてはノード同士の関連度からクラスタリングを行う．本論文ではこの関連度のことを，ノード間の「類似度」という言葉で定義する．本手法では，ノード間の類似度の指標としてジャッカード係数を採用した．

(23)

図

3.1:

クラスタリング手法の分類

図

3.2:

デンドログラム

(24)

図

3.3:

最短距離クラスタリングジャッカード係数（距離）

ジャッカード係数を用いて定義したノード間類似度

S

は，以下のように求められる．ノード

x

が接続するノードの集合を

A(x)

としたとき２つのノード

x, y ( ∈ V )

の類似度

S(x, y)

は式

(3.1)

で表される．

S(x, y) = | A(x) ∩ A(y) |

| A(x) ∪ A(y) | (3.1)

例として，

A(x) = { α, β, γ }

^，

A(y) = { α, β }

^{としたとき，}

S(x, y)

は以下のように算出される．

S(x, y) = |{ α, β }|

|{ α, β, γ }|

= 2

3 ≈ 0.66

3.2.3

クラスタの構築

最短距離クラスタリングとは，クラスタとクラスタの類似度（距離）を内包する要素でそれぞれ一番小さいものをクラスタの類似度とする考え方である．

図

3.3

の例に従って，最短距離クラスタリングを説明する．小さい青い円はノードを表しており，青い円を大きく囲んだ緑色の閉曲線はクラスタを表す．青い円の距離は類似度に比例しているとする．ここで，

Cluster A

と

Cluster B

の類似度を求めるとしたとき，

Cluster A

に含まれる要素と

Cluster B

に含まれる要素のペアのうち，一番近いペア（類似度が高いペア）

の類似度を，クラスタ間の類似度にする．すなわち，図中の

A

5と

B

2の類似度が，

Cluster A

と

Cluster B

の間の類似度になる．

これを数学的に定義し，構築の方法を以下に述べる．

クラスタ

C

はノードとクラスタの集合であり，以下の式で定義する．

C = { c

₁

, · · · , c

_n

} (n ≥ 2)

c

₁

, · · · , c

_n

∈ V ∪ C

(25)

クラスタにおける類似度

S(C)

を以下のように定義する．

S(C) = max

1≤i<j≤n

S(c

_i

, c

_j

) (c

_i

, c

_j

∈ V ∪ C)

式

(3.1)

に加え，類似度

S(p, q) (p, q ∈ V ∪ C)

を以下のように定義する．

S(p, q) = S(q, p)

可換性

S(p, q) =

 

 



 

 

| A(p) ∩ A(q) |

| A(p) ∪ A(q) | (p, q ∈ V )

∀

max

q^′∈q

S(p, q

^′

) (p ∈ V, q ∈ C)

∀p^′∈

max

p,^∀q^′∈q

S(p

^′

, q

^′

) (p, q ∈ C)

類似度が上記の定義になるようなクラスタを構築する手順を以下に示す．

1. s = max

∀x,^∀y∈V2,x̸=y

S(x, y)

となる

s

を求める．

2. S(x, y) = s

となるノード

x

，

y

が存在する場合，

x ∈ C

x，

y ∈ C

yを満たすクラスタ

C

x，

C

yが存在するかを確認する．

(a) C

_xと

C

_yが両方存在しない場合，

x

と

y

を含み，類似度

S(C) = s

のクラスタ

C

を生成する（図

3.4(a)

）．

(b) C

xが存在し，

C

yが存在しない場合，

C = G(C

x

)

とを満たすクラスタ

C

を求める

（図

3.4(b)

）．

i. S(C) = s

の場合，

C

に

y

を加える

ii. S(C) > s

の場合，

y

と

c

を含み，類似度

S(C

^′

) = s

のクラスタ

C

^′を生成する．

(c) C

_yが存在し，

C

_xが存在しない場合，

2b

の

x

と

y

を入れ替えて同様の動作を行う

（図

3.4(c)

）．

(d) C

xと

C

yが両方存在する場合，

C

_x^′

= G(C

x

C

y

)

と

C

_y^′

= G(C

y

)

を求める（図

3.4(d)

）．

i. s = S(C

_x^′

) = S(C

_y^′

)

の場合，

C

_x^′ と

C

_y^′ を結合する

ii. s = S(C

_x^′

)

かつ

s < S(C

_y^′

)

の場合，

C

_x^′ に

C

_y^′ を加える．

iii. s = S(C

_y^′

)

かつ

s < S(C

_x^′

)

の場合，

C

_y^′ に

C

_x^′ を加える．

iv.

それ以外の場合は，

C

_y^′ と

C

_x^′ を含み，類似度

S(C) = s

のクラスタ

C

を生成する．

3. s

であるノードの組み合わせが残っていれば，

2

に戻る

4. s > 0

の場合，

s

より小さい類似度の値中次に大きいものを

s

として，

2

に戻る

(26)

(a) (b)

(c) (d)

図

3.4:

クラスタリングの過程

G(C)

は

C

の最上位の親クラスタで，以下の式で定義する．

When C

^′

⊇ C

^′

⊇ C G(C) = C

^′

satisfied S(C

^′

) = min

∀c^′∈C^′

S(c

^′

)

以上を行うことにより，２つのノードの組み合わせの結果から全ノードのクラスタを木構造で構築していくことが出来る．エッジについては，それぞれの接続ノードを包含するクラスタにも同様に接続する．

(27)

v

₁

v

₂

v

₃

v

₄

v

1

- 0.9 0.8 0.72

v

₂

- 0.9 0.81

v

₃

- 0.9

v

₄

-

表

3.1:

類似度表

3.2.4

本手法の特徴

このクラスタリングの特徴として，通常の階層型クラスタリングよりも計算速度が速いことが挙げられる

[20]

．通常の階層型クラスタリング手法は，

1.

すべてのノードの組み合わせの内最も高い類似度の要素を１組探索し，クラスタとして結合させる

2.

残りのノードの集合と生成されたクラスタの類似度を再計算

を繰り返し，階層構造を形成していく．それと比較し，本手法は類似度の計算は１回で良いので，類似度計算自体のオーダは

O(n

²

)

にとどめることが出来る．加えて，類似度の情報が絶対値で与えられることも特徴である．通常のクラスタリングは，類似度が高い要素ごとにクラスタリングを行うため，後にクラスタリングした要素の類似度がその前にクラスタリングした要素の類似度よりも高いか低いかは不明である．後に述べる描画手法ではこの類似度の絶対性が有効に働く．

もう一つの特徴は，ノードの並び順（クラスタの結合順序）によりクラスタリング結果が変わらない一貫性である

[19]

．例として，

4

つのノード

v

1

, · · · , v

4 の接続ノードの集合

A(v

1

), · · · , A(v

4

)

を

A(v

₁

) = { 2, 3, 4, · · · , 10 } A(v

₂

) = { 1, 2, 3, · · · , 10 } A(v

3

) = { 1, 2, 3, · · · , 9 } A(v

₄

) = { 0, 1, 2, · · · , 9 }

として，類似度を計算した結果を表

3.1

に示す．

ここで，類似度が

0.9

のものが

3

つあるが，結合する順番はノードの並び順に依る．すなわち，

v

₁

-v

₂，

v

₂

-v

₃，

v

₃

-v

₄のどれを始めにクラスタとするかである．それぞれを最初にクラスタリングを行い，全ノードをクラスタリングした場合の結果をデンドログラムとして表したのが，図

3.2.4

である．

v

1

-v

2と

v

2

-v

3は論理的に同じ構造であるが，

v

3

-v

4は他二つとは異なる構造になる．

本論文のクラスタリング手法でこれらノード集合のクラスタリングを行うと，どの順番で行っても，

v

₁〜

v

₄は類似度

0.9

のクラスタで結合され，結果の一貫性が保たれる．通常のク

(28)

(a)v1–v2 (b)v2–v3 (c)v3–v4

図

3.5:

クラスタリング順による変化

ラスタリングよりも高い類似度で結合されるクラスタが多くはなるが，可読性は変わらないと考える．また，後から形成されたクラスタが，以前に形成したクラスタよりも類似度が高い状態になる「反転現象」とよばれる歪みも発生しない．順序依存性と反転現象の影響を受けない階層型クラスタリング手法は，最短距離法のみである．

3.3

描画システム

本研究ではクラスタリングを行ったデータを可視化するツールとして，「

GTBC–GraphML Translater for Bipartite Clustering–

」と「

ClusterdAnchorViz

」の開発を行った

[21]

．

GTBC

はグラフのクラスタリングツールであり，２部グラフのデータにクラスタリングを付加する．

GTBC

は

Java

^TM

6.0 (Java

^TM

Platform, Standard Edition 6 Development Kit

²

)

を用いて製作した．

GraphML

³ 形式で記述された２部グラフの

XML

データファイルを入力として，クラスタリングのデータを付加した

NestedGraph

の

GraphML

形式の

XML

を出力する．

GraphML

とはグラフを

XML

で記述する形式の内の一つであり，多くの可視化研究において

も用いられている

[22]

．

ClusterdAnchorViz

は，クラスタ情報を効率的に可視化する描画機能を備えた２部グラフ描

画ツールである（図

3.6

）．グラフの描画レイアウトには，アンカーマップ

[16]

のレイアウトを用いている．

ClusteredAnchorViz

も

Java

^TM

6.0

を開発言語とし，

Applet

として作成している．

クラスタリングの情報を用いてのネットワーク描画スタイルは，従来手法ではノードとエッジをまとめて表示する手法が一般的である．加えて，そのインタラクションには該当ノードのクリックにより集約と展開を行う手法が多い．これらの手法では，大規模の場合読み手が要求するネットワーク図にたどり着くまでかなりの作業を要する，似た傾向をもつクラスタの発見などが困難であるなどの問題がある．

ClusterdAnchorViz

には「縮退描画手法」と「等類似度線描画手法」という二つの描画機能

が備わっている．縮退描画手法は，クラスタの類似度情報によって複数のノードを１つのノードとして表示させる手法である．等類似度線描画手法は，クラスタに属するノードを閉曲線描画するスタイルである．集約と展開とは異なる描画スタイルで，要素間の関連性の情報を

目 次

クラスタ情報の可視化による 大規模２部グラフの可読性向上手法

佐藤 修治

(

)

2008

3

1

目 次

1

1

1.1

. . . . 1

1.2

. . . . 1

1.3

. . . . 2

1.4

. . . . 3

1.5

. . . . 3

1.6

. . . . 4

1.7

. . . . 4

2

5 2.1

. . . . 5

2.2

. . . . 5

2.3

. . . . 6

2.3.1

. . . . 6

2.3.2

. . . . 7

2.3.3

. . . . 7

2.4

. . . . 7

2.5

. . . . 9

2.6

. . . . 10

3

14 3.1

. . . . 14

3.2

. . . . 14

3.2.1

. . . . 15

3.2.2

. . . . 15

3.2.3

. . . . 17

3.2.4

. . . . 20

3.3

. . . . 21

4

24 4.1

. . . . 24

4.2

. . . . 24

4.2.1

. . . . 25

4.2.2

. . . . 26

4.3

. . . . 26

5

30 5.1

. . . . 30

5.2

. . . . 31

5.2.1

. . . . 31

5.2.2

. . . . 32

5.3

目次

クラスタ情報の可視化による大規模２部グラフの可読性向上手法

佐藤修治

目次

図目次