「モデリングとシミュレーション実験」 2015 年度期末レポート課題 締切:2016/2/10 期末レポートについて 1 期末レポート課題は、以下の通りです。期日までに、理工学部 7 号館 2 階のレ ポートボックスへ提出すること。 • 電子的に作成し、A4 用紙に印刷して提出すること。 • 正しい日本語で作成すること。 • 他人のレポートを写したと判断した場合には、不合格とする。 • 書籍や Web ページ等を参考としている場合には、必ず出典を明示すること。 • 単に課題に答えるだけでなく、課題の説明、考え方、開発したプログラム (java 及び gnuplot) も含めて、レポートとして筋道のあるものとすること。 2 ランダムネットワークにおけるジャイアントコンポー ネント 2.1 Erdös-Rényi ランダムネットワーク 総頂点数を N とし、L 個の頂点の組をでたらめに選んで辺で結ぶことでできる ネットワークを Erdös-Rényi ランダムネットワークと呼ぶ。頂点数 N の完全ネッ トワークの辺の総数との比を p とすると L=p N (N − 1) 2 と表される。 1 (2.1) 2.2 ジャイアントコンポーネント 講義で説明したように、p が小さいときには、ネットワークには小さなばらばら −1 の連結成分しか存在しない。しかし、p = (N − 1) を超えると、ネットワークに 急に大きな連結成分が発生する。このことを調べることにする。理論的解析では p > (N − 1)−1 で大きな連結成分が発生する。このことを、実際に p を変えながら Erdös-Ré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 ジャイアントコンポーネントの発生 講義では、Erdös-Rényi ネットワークにおいて、辺が存在する確率 p を変化させ −1 ることで、p = (N − 1) において急激に大きな連結成分が発生することを説明し た。このことを実際に確かめよう。そのため、クラス ER を用いて実際に p を変え る、つまり辺の総数を変えながら Erdös-Rényi ネットワークを生成する。そのネッ トワークを対象として、連結成分を調べ、そのうちの最大のもののサイズの変化 を調べる。 課題 3 頂点数 N = 1000 の Erdös-Rényi ネットワークを考える。0 < p ≤ −1 2 (N − 1) の範囲で、p を (N − 1)−1 /100 ずつ変化させ、Erdös-Rényi ネットワー クを構成し、その時の最大の連結成分の大きさの変化を調べ、図示しなさい。 5
© Copyright 2024 ExpyDoc