k-木のスケールフリー性に関する研究

概要

論文の詳細を見る
近年,WWWやインターネットなどの非一様な構造を持つ多くの社会ネットワークを説明できるモデルとしてスケールフリーグラフが注目を集めている.本研究では,スケールフリーな k -木を生成する単純なランダムモデルを提案する.k -木とは,固定された任意の正整数パラメータ k に対する一般化された木であり,グラフマイナーの分野では基本的な概念である.本稿で提案するモデルは非常に自然で単純な規則から生成される.最初に大きさ k + 1 の極大クリークを一様ランダムに選び,次にそのクリークの中の k 個の頂点を一様ランダムに選び,そしてこれら k 個の頂点に隣接するように新しい頂点を追加するだけである.つまり本モデルでは,新しい頂点を 1 個追加するときに一様ランダムな選択を 2 回行なうだけでよい.このとき結果として得られる k -木において,頂点の次数分布は漸近的にベキ乗則に従い,クラスタ係数は大きく,そしてグラフの直径は小さい.ランダムな選択が単純なので,こうした性質の解析も容易である.また得られた k -木の直径は実験的結果により o (log n)であることが確認できた.ただしここで n は頂点数であり,o (1) 項は k の関数である.
一般社団法人情報処理学会の論文
2009-05-04