Talk
?
1 like?801 views
JWEIN 2016 network analysis session talk MDS expanded to handle directed graphs, which results in visualizing schematically well-known bow-tie structure of a directed-graph.
Talk
- 1. 多次元尺度法の拡張による有向グラフの可視化 藤田 裕二 Yuji Fujita 株式会社 ターンストーンリサーチ yuji@turnstone.jp 相馬 亘 Wataru Souma 日本大学理工学部 souma.wataru@nihon-u.ac.jp 藤原 義久 Yoshi Fujiwara 兵庫県立大学大学院シミュレーション研究科 yoshi.fujiwara@gmail.com
- 2. 関係性は一般に非対称 ● 経済取引 ● 引用 , リンク ● 化学反応 ● 人間関係 有向グラフの描画 : 辺を磁化して磁場をかける
- 3. グラフ描画の評価 ● 同一性 ● 判別性 クリアするために ,MDS で初期配置を計算し , 凝集し た頂点をクーロン力とフックバネで適度に散開させる 手法を採用してきた MDS を有向グラフに対応させられないか ?
- 4. MDS は相互距離行列が出発点 距離関数は対称的なので , リンクの非対称性情報は 埋め込めないように見えるが ...
- 5. Direction-aware MDS (DMDS) ● 頂点 A,B 間に , 無向最短距離に一致する有向パス がある場合は , パス長をそのまま頂点間距離に ● そのような有向パスが存在しない場合は無向最短 距離を 2 で割った値を頂点間距離にする ● 相互距離行列を従来の MDS 同様にスペクトル分解
- 6. ● AD 間の距離は無向距離 2 に一致する有向パスが あるので ,2 オレンジ色 ● BC 間は , 無向距離 2 に一致する有向パスが無い ( そもそも有向パスで到達不能 ) なので ,DMDS 距 離は , 無向距離 2 を 2 で割って 1 緑色
- 8. ネットワークデータ紹介 ● GNU Emacs-version "24.5.1" ELISP 関数シンボ ルの定義 / 被定義関係 ● ノード数 8689, リンク数 40127 ● 例 : 階乗の定義
- 10. Bow Tie Structure ● 相互に有向パスで到達可能な SCC ● SCC から出てゆくパスで到達可能な OUT ● SCC に入るパスで到達可能な IN
- 12. ● MDS で有向グラフを表現できる ● 概念的存在だった Bow Tie 構造を可視化