Component Evolution in General Random Intersection Graphs

Milan Bradonjic, Aric Hagberg, Nicolas W. Hengartner, Allon G. Percus
http://arxiv.org/abs/1005.5475

Random Intersection Graphというものがあるようで，それの連結成分の進化に関する論文．Random Intersection Graph (RIG) とは次のように定められるランダム・グラフである．頂点数はn．各頂点にm個の属性の中のいくつかが割り当てられる．割当は頂点iと属性jに対して確率p(i,j)が与えられていて，頂点iに属性jが割り当てられる確率がp(i,j)．それを頂点と属性の2個組すべてに対して決めていく．そして，2頂点が辺で結ばれるということを，その頂点が共通の属性をs個以上持っていること，とする．これでランダムにグラフが生成できる．いろいろな分野で出てくる現象のモデルになっているようなので，今後要注目かもしれない．