M.6 動的なデータ構造

2016/11/1７

M.5では階層構造のあるデータの代表的なビジュアライゼーション手法を扱ったが，最終章ではウェブのようにより複雑な物事の関係性をグラフ構造として捉えて扱う手法が紹介されている．

グラフ構造とは

グラフネットワークとは物事のつながりや関係性を表現するデータ構造のことである．グラフは対象物を表す「ノード」とそれらのつながりを表す「エッジ」で構成される．現実に存在するグラフネットワークは一般に複雑であることからよく「複雑ネットワーク」とも呼ばれる．ツリー構造はグラフ構造の特別な場合とみなすことができる．

グラフ構造のレイアウト

グラフネットワークの可視化においてノードをどのように配置し，ネットワークの性質を見やすくするのかはビジュアライゼーションにおける重要な課題の一つである．

力学モデル

つながっているノード同士はバネのように引き合い，それ以外のノード同士は磁石のように反発するようにネットワークをシミュレートすることで，レイアウトがやがていいバランスに落ち着いてくれるだろう，という発想から提案され，よく使われるようになった．

よくある事例

グラフネットワークで表現できる社会現象や科学現象は数多い．

事例1:インターネットのリンク構造

The Internet Map

http://internet-map.net/

事例2:ソーシャルグラフ

デジタルのソーシャルグラフ

"Modelling dynomical processess in complex socio-tehnical systems" Alessandro Vespignani (NATURE Physics)

http://www.nature.com/nphys/journal/v8/n1/fig_tab/nphys2160_F4.html

リアル

How the NSA Uses Social Network Analysis to Map Terrorists Networks

http://www.digitaltonto.com/2013/how-the-nsa-uses-social-network-analysis-to-map-terrorist-networks/

事例3:科学

タンパク質の相互作用ネットワーク

"Network visualization of chromosome maintenance and duplication machinery in baker's yeast, Saccharomyces cerevisiae." NATURE BIOTECH

http://www.nature.com/nbt/journal/v27/n10/fig_tab/nbt.1567_F1.html

社会ネットワークの有名な話

スモールワールド性

1967年頃，社会心理学者のスタンレー・ミルグラムは「アメリカ内陸部の住人に手紙を渡し，全く面識のない東海岸の受取人へ向けて，知人経由で転送するように依頼し，届くまでに何人の仲介者が必要か」を実際に実験した結果，平均して6人を仲介すれば届くことがわかったという．その後も様々な研究が行われたが，やはり5, 6人を介すれば任意の2点が結ばれるということがわかっている．まさに「世界は意外と小さい」である．このことは次の「スケールフリー性」を考慮すれば，わりと自然な結果であることが直感的に理解できる．

スケールフリー性

現実世界のネットワークは得てして「多数のつながりを持つ少数のハブノード」と「多数の比較的少数のつながりしか持たないノード」で構成され，幅広く観察されている性質である．例えば，twitterでも少数の有名人は圧倒的な数のフォロワーを擁しており，一般人はせいぜい多くても〜数百程度である．インターネットでもgoogleやFacebookといった巨人が膨大なリンクを持つ一方で，圧倒的大多数のウェブサイトはわずかなリンクしか持たない．

クラスター性

現実世界には「自分，友人A，友人B」といった三角形のネットワークがたくさん存在するということがわかっている．

動的なデータ構造まとめ

物事のつながりや関係を表すデータ構造がグラフネットワークである．
グラフネットワークはインターネット，ソーシャルグラフといったものが当てはまる．
レイアウトは力学モデルで決めることが多い．
ノードの大きさや色も活用することで，より多くの情報を可視化できる．
グラフのノード数が多いときは魚眼ビューなど見やすくするための工夫テクニックがある．

M.6 Dynamic Data Structures