Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions (WWW'15)

概要

• たくさんの密グラフの包括的・階層的表現
  • 沢山の密部分グラフが欲しい
  • 密度や大きさの分布が欲しい
  • 構造的関係（入れ子）が知りたい
• いかした図を出力する
  • グラフを「核の森」で表す (Nucleus Decomposition)

定義 k-(r,s)-nucleus

• パラメータ k, r, s がある (r < s)
• 別のグラフを考える
  • 頂点はサイズ r のクリーク
  • サイズ s のクリークを hyperedge だと思う
• このグラフの k-core を取る

関係

• r = s-1 なら k-clique community
• k-(1,2)-nucleus は k-core
• k-(2,3)-nucleus は k-truss に近いけど違う

性質

• (r, s)-核は層族 (laminar family)
  • K_r の集合で考えるからである．
  • K_r を共有しない．K_r-1 なら共有するかも（OK）．
• それぞれの k についての核を森で表現

結果

• いかした図