「モデリングとシミュレーション」 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) を超えると、ネットワークの
中に、急に大きな連結成分が発生する。このことを調べることにする。この大き
な連結部分をジャイアントコンポーネントと呼ぶ。
任意の頂点がジャイアントコンポーネントに含まれていない確率を u とする。あ
る頂点 i が、他の頂点 j と隣接していない確率は 1 − p である。頂点 i が、頂点 j
に隣接していて、ジャイアントコンポーネントに含まれないためには、j もジャイ
アントコンポーネントに含まれていない必要がある。その確率は pu となる。頂点
i が、他の N − 1 個の頂点に隣接しない、またはジャイアントコンポーネントに含
まれない頂点と隣接しているときだけ、頂点 i はジャイアントコンポーネントに含
まれない。このことから、
u = (1 − p + pu)N −1
(2.2)
となる。ここで、c = (N − 1) p と置き換えると
(
)N −1
c
u= 1−
(1 − u)
N −1
(2.3)
となる。
課題 1
N ≫ 1 のとき、式 (2.3) が
u = e−c(1−u)
(2.4)
となることを示しなさい。
変数を S = 1 − u と置き換えると、式 (2.4) は
S = 1 − e−cS
(2.5)
となる。この式を数値的に解くことを考える。ただし、0 ≤ S ≤ 1 であることに留
意する。
まず、解がどのような場合に存在するかを考える。S = 0 は、明らかに解であ
る。つまり、S > 0 の解が存在するための条件を考える必要がある。
課題 2 式 (2.5) の左辺、つまり y = x という直線と、右辺、つまり y = 1 − e−cx
という曲線の x = 0 以外の交点の有無が分かることが重要である。そこで、c の異
なるいくつかの曲線を描き、c = 1 を境に、x = 0 以外の交点が発生することを示
しなさい。また、そのようになる理由を式 (2.5) を分析することから説明しなさい。
2
2.3
数値計算
c > 1 のとき、式 (2.5) には S > 0 である解があることが分かった。そこで、次
にその解を数値的に求めることを考える。式 (2.5) の S > 0 である解を S ∗ とする。
このとき、曲線 y = 1 − e−cx は、直線 y = x を左上から右下へ交差する。つまり
S の関数 f (S) = S − 1 + e−cS は、その交点 S ∗ の近傍で増大する。
d
f (S) = 1 − ce−cS > 0
dS
(2.6)
次に、以下の手順を考える。ある初期値 S0 を考える。
S1 = 1 − e−cS0
(2.7)
とする。c > 1 に対して、0 < S0 < S ∗ ならば、
S1 > S 0
(2.8)
S1 < S 0
(2.9)
であり、S ∗ < S1 ならば
となることが、容易にわかる。S1 を式 (2.5) の右辺に代入することで S2 を得、さ
らに S2 を右辺に代入して S3 を得るような過程を繰り返すと、適当な出発点 S0 か
ら S ∗ に近づきそうである。
つぎに、本当に S ∗ に近づくことを確認する。そこで、S ∗ 近傍での振舞を調べる
こととする。
S0 = S ∗ + ∆S
(2.10)
とする。この値を式 (2.5) の右辺に代入して
S1 = 1 − e−cS0 = S ∗ + e−cS
となる。ここで、
∆S1 = e−cS
∗
(
∗
(
1 − e−c∆S
1 − e−c∆S
)
)
(2.11)
(2.12)
と置く。
課題 3
式 (2.11) を導出しなさい。
|c∆S| ≪ 1 と仮定すると、
∆S1 = e−cS
∗
(
(
c∆S + O (c∆S)2
))
(2.13)
となる。c > 1 及び S ∗ > 0 の場合、S ∗ の近傍で
∗
ce−cS < 1
3
(2.14)
であることから、|∆S1 | < |∆S|、つまり解 S ∗ との差が小さくなることが分かる。
課題 4
式 (2.13) を導出しなさい。
以上から、適当な S0 > 0 から出発して、
Si+1 = 1 − e−cSi
(2.15)
lim Si = S ∗
(2.16)
と反復することで
i→∞
となることが分かる。
課題 5 c を変化させながら S ∗ を数値的に求めなさい。そのためのプログラムを
示すとともに、結果を作図しなさい。
4

Download Report