「モデリングとシミュレーション実験」 2015年度期末レポート課題 1 期末

「モデリングとシミュレーション実験」
2015 年度期末レポート課題
締切:2016/2/10
期末レポートについて
1
期末レポート課題は、以下の通りです。期日までに、理工学部 7 号館 2 階のレ
ポートボックスへ提出すること。
• 電子的に作成し、A4 用紙に印刷して提出すること。
• 正しい日本語で作成すること。
• 他人のレポートを写したと判断した場合には、不合格とする。
• 書籍や Web ページ等を参考としている場合には、必ず出典を明示すること。
• 単に課題に答えるだけでなく、課題の説明、考え方、開発したプログラム
(java 及び gnuplot) も含めて、レポートとして筋道のあるものとすること。
2
ランダムネットワークにおけるジャイアントコンポー
ネント
2.1
Erdös-Rényi ランダムネットワーク
総頂点数を N とし、L 個の頂点の組をでたらめに選んで辺で結ぶことでできる
ネットワークを Erdös-Rényi ランダムネットワークと呼ぶ。頂点数 N の完全ネッ
トワークの辺の総数との比を p とすると
L=p
N (N − 1)
2
と表される。
1
(2.1)
2.2
ジャイアントコンポーネント
講義で説明したように、p が小さいときには、ネットワークには小さなばらばら
−1
の連結成分しか存在しない。しかし、p = (N − 1) を超えると、ネットワークに
急に大きな連結成分が発生する。このことを調べることにする。理論的解析では
p > (N − 1)−1 で大きな連結成分が発生する。このことを、実際に p を変えながら
Erdös-Rényi ランダムネットワークを構成し、その中の最も大きな連結成分の大き
さが変化する様子を調べて、確かめることにする。
2.3
連結成分を求めるアルゴリズム
ネットワークのなかで、互いにつながった頂点のグループである連結成分を見
つけることを考える。頂点の集合 V に対して、その部分集合を Vi ∈ 2V とする。こ
の部分集合が、以下の手続の最後に連結成分を表すようになる。各頂点 vi ∈ V が
どの部分集合 Vj に属しているかを表す写像を M とする。
M : V → 2V
(2.2)
初めに、各 Vj には、たった一つの頂点 vj が属しているとする。つまり、
M (vi ) = {vi } , ∀i
(2.3)
である。
続いて、全ての頂点 vi に対して、以下の操作を順番に行う。注目している頂点
vi の隣接頂点の集合を Vc とする。注目している頂点 vi 及び vj ∈ Vc に対応した集
合のうち、もっとも大きな集合を Vmax とする。
Vmax =
max M (v)
v∈{vi }∪Vc
その Vmax に対して、以下のように写像と Vmax を更新する。
1. M (vi ) ̸= Vmax ならば、
Vmax ← Vmax ∪ M (vi )
とし、
M (vi ) = Vmax
と変更する。
2. 全ての vj ∈ Vc のうち、M (vj ) ̸= Vmax である場合は
Vmax ← Vmax ∪ M (vj )
とし、
M (vj ) = Vmax
と変更する。
2
(2.4)
つまり、
M (v) = Vmax , ∀v ∈ {vi } ∪ Vc
(2.5)
となるように変更する。
以上を、全頂点に対して行うことで、M は頂点がどの連結成分に属するかを表
す写像となる。
1
2
3
4
8
7
10
0
11
9
12
6
5
図 1: 3 個の連結成分のあるネットワーク
注目頂点
v0
v1
v2
v3
v4
v5
v6
v7
v8
v9
表 1: 図 1 に対して連結成分を求める過程 (途中まで)
写像変更
M (v0 ) = M (v10 ) = {v0 , v10 }
M (v1 ) = M (v2 ) = {v1 , v2 }
M (v1 ) = M (v2 ) = M (v3 ) = {v1 , v2 , v3 }
M (v1 ) = M (v2 ) = M (v3 ) = {v1 , v2 , v3 }
M (v4 ) = M (v5 ) = M (v6 ) = {v4 , v5 , v6 }
M (v4 ) = M (v5 ) = M (v6 ) = {v4 , v5 , v6 }
M (v4 ) = M (v5 ) = M (v6 ) = {v4 , v5 , v6 }
M (v0 ) = M (v7 ) = M (v10 ) = {v0 , v7 , v10 }
M (v0 ) = M (v7 ) = M (v8 ) = M (v10 ) = {v0 , v7 , v8 , v10 }
M (v0 ) = M (v7 ) = M (v8 ) = M (v9 ) = M (v10 ) = M (v12 ) = {v0 , v7 , v8 , v9 , v10 , v12 }
具体的に図 1 に対して連結成分を求める過程を見ることにする。途中経過を表 1
に示す。次第に連結成分の全体像が分かる過程を示している。
3
GiantCluster クラス
実際に、連結成分を求め、さらにそのうちで最も大きな連結成分を求めるクラス
が GiantCluster である。そのコンストラクタを表 2 に、public メソッドを表 3
3
に示す。
表 2: GiantCluster クラスのコンストラクタ
コンストラクタと説明
GiantCluster(BaseNetwork network)
対象となるネットワーク network を与えて初期化する。
表 3: GiantCluster クラスのメソッド
修飾子と型
int
int
void
メソッドと説明
findClusters()
連結成分を発見し、連結成分の総数を返す。
findMaxClusterSize()
最大の連結成分の大きさ (頂点数) を返す。
showNodeSets(String filename)
連結成分をファイル名 filename で指定されたファイルへ出
力する。
クラス GiantCluster の private 変数のうち、nodeMap が 2.3 節において説明し
た写像 M : V → 2V に相当する。また、変数 nodeSets は、連結成分の分析が終
わった後に、写像 M の右辺に残った頂点集合、つまり連結成分のリストを表して
いる。
メソッド findClusters では、各頂点 node について、以下の処理を行っている。
1. その頂点から写像 M によって対応付けられた頂点集合 ownSet を求める。
2. その頂点及び隣接頂点から写像 M によって対応付けられた頂点集合のうち
最大のものをメソッド findMaxSet を使って求め、maxSet とする。
3. ownSet と maxSet が等しくない場合の処理
4. 隣接頂点に対応付けられた頂点集合の処理
最後に、nodeMap から nodeSets を生成する。
課題 1
メソッド findClusters を記述しなさい。
課題 2 クラス GiantCluster の main は、図 2 に対応したネットワークを分析す
る。期待される結果が得られていることを確認しなさい。どのように確認したか
も、記述しなさい。
4
0
1
4
2
3
5
8
9
6
7
図 2: GiantCluster クラスのサンプル
4
ジャイアントコンポーネントの発生
講義では、Erdös-Rényi ネットワークにおいて、辺が存在する確率 p を変化させ
−1
ることで、p = (N − 1) において急激に大きな連結成分が発生することを説明し
た。このことを実際に確かめよう。そのため、クラス ER を用いて実際に p を変え
る、つまり辺の総数を変えながら Erdös-Rényi ネットワークを生成する。そのネッ
トワークを対象として、連結成分を調べ、そのうちの最大のもののサイズの変化
を調べる。
課題 3
頂点数 N = 1000 の Erdös-Rényi ネットワークを考える。0 < p ≤
−1
2 (N − 1) の範囲で、p を (N − 1)−1 /100 ずつ変化させ、Erdös-Rényi ネットワー
クを構成し、その時の最大の連結成分の大きさの変化を調べ、図示しなさい。
5

Download Report