Vizster

複雑系

SNSのさきがけでFriendsterというものがあります。ご存じですか？もともとの発想は、出会い系SNSのようです。mixiにも似ているのですが、4ホップ先のユーザまでしかプロフィールが公開されない点で制限が強く、そのことが各ユーザにより多くの情報を得る目的で友人を積極的に増やさせる動機付けを与えているようです。今日、紹介する論文はFriendsterの友人関係をグラフ状に可視化するためのVizsterというツールです。mixiをグラフ状に可視化するツールとしてmixiGraphという類似のツールがありますが、直接操作の機能、可視化機能、コミュニティ構造の表示機能などの面でVizsterの方がさらに洗練されているようです。

問題点 提案 評価
友人・友人関係の発見 グラフの可視化、検索機能、属性表示 ???
コミュニティ構造の発見 Newman法＋スライダー ???
巨大なグラフの自然な取り扱い 直接操作 500人のパーティ、内輪での実験
処理性能 Barnes-Hutのアルゴリズムで高速化 5万ノードまで対応

3節にFriendsterの解説が書いてあります。Friendsterの特徴とそれが発展した経緯が説明されていて面白いです。

関連ページ

グラフの可視化

ゴール
  1. 友人たちが構成する社会ネットワークを俯瞰できるようにする。
  2. 顔写真を見せることで個人の識別と個性を容易に把握できるようにする。
  3. プロフィールの記述を表示することで個々の人物の性格を知る助けをする。*1
  4. 自己中心的なネットワークの描画。各ユーザを中心に据え、Vizsterとのインタラクションを経て、徐々に周辺の詳細を表示する方式。*2

システムの設計

友人・友人関係の発見

個々のユーザに対応する頂点をダブルクリックすることで、そのユーザの友人たちをまとめて表示・非表示する。バネモデルの計算を動かし続けることで、グラフはユーザからの操作に応じて刻々と表示を変化させる。

頂点の上でポインタを静止すると、その頂点からのグラフ論的な距離に応じて、他の頂点の色の明度と色相を減衰させる。これにより頂点を中心とした構造を見せる。細かいことだが、表示が激しく変化しないような工夫をしている。*3

"Linkage view"はクリックにより選択した頂点と中心の頂点を結ぶ経路を表示する。

グラフを観察するために画面の表示位置を移動(panning)したり、拡縮(zooming)できる。グラフの背景を左ドラッグすれば表示位置を移動し、右ドラッグすれば拡縮する。

特定のいくつかの頂点の情報を見せるために、頂点を選んで拡大表示する機能(長クリック)を提供している。

ユーザのプロフィールに関して検索するための検索窓を提供している。また、検索の直接操作インタフェイスとして、個別のプロフィールの単語をクリックすることで、その単語についての検索を開始できる。同様にプロフィールの単語をダブルクリックすることで、その単語を含む句(フレーズ)の検索ができる。

全ユーザについて、特定の属性に関する情報をまとめて把握するために、「X線モード」を提供している。このモードでは、通常表示の顔写真に替えて、選択されているプロフィール属性をグラフの頂点として表示する。

コミュニティ構造の発見

Newmanのコミュニティ構造発見アルゴリズムを実装し、得られたコミュニティをベン図のように表示する機能を提供している。さらにコミュニティスライダーによって、コミュニティの粒度を調整できるようにしている。*4

巨大なグラフの自然な取り扱い

Friendsterの友人関係を、ユーザを頂点、友人関係を枝とする無向グラフによって表現し、それを互いに反発する頂点がバネで相互に接続されたバネモデルを用いて表示している。*5モデルの解法としてはBarnes-HutのN体問題の数値解法を応用している。

隣接する友人たちの表示・非表示によってグラフの形状は大きく変化し、それとともに描画されたグラフも大きく変化する。*6

実装

VizsterはJavaとprefuseという可視化ツールキットを用いて実装されている。

キーワード検索にはLucene検索エンジンを用いている。

リンク関係と属性情報は自前のクローラでダウンロードし、MySQLサーバに保存した。

Vizsterのソースはprefuseの一部として公開されている。

評価

  • 500人が集るパーティイベントにVizster端末を設置し、参加者が自由に利用できるようにし、彼らの行動を分析した。
  • 研究室の仲間6名に最初は使い方を説明せずに、次に使い方を教えて使わせて、各自に気づいた点を報告してもらった。

考察

個人向けに彼らが自分の周辺の様子を把握するためのツールとして提案されている。ニーズがよく分析され、それに応じてシステムをよく設計してあるようだ。可視化においても、色、インタラクションの容易性、情報提示の方法、直接操作について洗練されているように思う。

われわれが目指しているものは1,000万頂点の規模を対象とし、その全体像を俯瞰的に把握するためのシステムであるため、興味の範囲や利用可能な技術がかなり異なるが、いずれわれわれが実装中のマクロな視点から設計されたシステムとここで提案されたミクロな視点から設計したシステムを継ぎ目なく統合する必要がでてくるだろう。

参考文献

社会ネットワークの可視化システム

  • Ghoniem, Fekete, and Castagliola, "A comparison of the readability of graphs using node-link and matrix-based representations," InfoViz 2004, pp. 551-558.*7
  • Adamic, Buyukkokten, and Adar, "A social network caught in the Web," First Monday, 8(6), 2003.
  • Fischer and Dourish, "Social and temporal structures in everyday collaboration," CHI 2004.
  • Newman, "Co-authorship networks and patterns of scientific collaboration," Proc. National Academic Sciences, 101, pp. 5200-5205, 2004.

ネットワーク可視化システム(研究指向)

  • Shneiderman, "The eyes have it: A task by data type taxonomy for information


ネットワーク可視化システム(ユーザ指向)

  • Harrison and Dourish, "Re-place-ing space: The roles of place and space in collaborative systems," in CSCW 1996, pp. 67-76.
  • Nardi and others, "ContactMap: Integrating communication and information through visualizing personal social networks," CACM, Apr. 2002.

*1:プロフィールの修正機能も提供する。Friendsterは18才未満への利用を禁止しているため、17才以下のユーザは年齢を逆に(17なら71、16なら61と)記載してFriendsterを騙しつつ、互いの年齢を公開していた。プロフィールの修正機能は、このような表記を自動的に本来の年齢の表記に改める機能。

*2:Shneidermanの情報可視化の大原則「まず全体の外観を表示し、必要に応じて部分を拡大表示せよ」には反している。基本的に興味の範囲が自己の近傍にあるアプリケーションだから、このような設計になったのだろう。

*3:Moving the mouse off the node causes the highlighting to disappear, but with a half-second hysteresis applied to prevent annoying visual "bouncing" as consecutive nodes are visited by the mouse pointer.

*4:やはり、コミュニティ解析はΔQ<0についてもやった方がよいのかもしれない。

*5:バネモデルを用いた描画システムにはVisual Thesaurus, TouchGraphなどがある

*6:これはユーザにとって負担とならないのか？

*7:この分野のサーベイが載っているらしい。