読者です 読者をやめる 読者になる 読者になる

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 についての核を森で表現

結果

  • いかした図