VoG: Summarizing and Understanding Large Graphs

VoG: Summarizing and Understanding Large Graphs

  • Danai Koutra, U Kang, Jilles Vreeken, Christos Faloutsos
  • SDM 2014

概要

  • ソーシャルネットワークがもらえる
  • グラフの構造に対してなにか言いたい
  • いろんな語彙をもってしてグラフを簡潔に表現したい
    • 但し,グラフ圧縮が目的では無くてあくまでグラフの理解が目的(らしい)
  1. 問題定式化
  2. 効率的手法
  3. 実験

提案手法

  • MDLを評価関数として使う
  • Mが構造の集合,GがグラフでL(G, M)
    • 位置とかそういう情報も記述長がある
  • 語彙: Ω={完全・近似クリーク,完全・近似二部グラフ,スター,チェイン}
  • L(G,M) = L(M)+L(E)
    • E=M^A
    • L(M)はサイズほげのクリークが位置ふがにある,とかそういう情報の記述長
    • Mで表しきれなかったAの残り部分
  • モデルのエンコード
    • 沢山式がある
    • 基本的には全パターンの対数bitで表現できるのでそういう議論をしている
  • VoGの概要
    1. 既存のコミュニティ検出アルゴリズムで部分グラフ生成
    2. 個々の部分グラフをΩで表そうとする
    • 問題が超難しいので適当に色々考えてやってみているっぽい?

実験

  • 色々やっている

まとめ

  • イメージとしては,グラフの隣接行列に(クリークとかスターとかの)XORスタンプを押して簡単にしたいとかな感じ
  • もっとΩをちゃんとやりたい
    • フレキシブルに対応できるのは確かだが与えるんじゃなくて自分で抽出して欲しい
    • とか思ったが激ムズっぽいとRelated WorkのQ&Aコーナーで書いてたわ…
  • これは高速化とかじゃないので,ちゃんとどういう知見が得られるか書かんといかんのだなあ.
  • Referenceをいくつか持っておこう

SDM グラフ要約

2014-09-11 04:13:01 (Thu)

タグ:

SDM グラフ要約
最終更新:2014年09月11日 04:13