Connecting Nearest Neighborモデルとは,スケールフリー性,クラスタ性,スモールワールド性を満たすソーシャルネットワーク的なグラフを生成するアルゴリズムの一つです.何かしらのシミュレーションなどに使えるのではないかと思います. アルゴリズムは以下を繰り返すだけとなります. 1-pの確率で新たなvertexを作成.ランダムに既存のvertexを一つ選ぶ.新たなvertexと選ばれた既存のvertexを結びつける. pの確率で,ランダムに選んだpotential edge一つを本物のedgeへと変換する. ちなみに,potential edgeとは次のような,潜在的なedgeです. 例えば,以下のようなグラフがあった場合のpotential edgeは,1と3を結ぶedgeとなります. 2 / \ 1 3また,以下のようなグラフであった場合は,1-5,1-3,5-3,2