直径>=３となる場合
par(family= "HiraKakuProN-W3")
library(igraph)
library(extrafont)
font_import()
Importing fonts may take a few minutes, depending on the number of fonts and the speed of the system.
Continue? [y/n]
n=100 #頂点数
N=400 #サンプル数
cs = seq(1, 2, 0.01)
ratio=c()
for (c in cs){
count=0
for (i in 1:N){
p=c*sqrt(log(n)/n)
g=sample_gnp(n,p)
if(diameter(g)>=3){
count=count+1
}
}
ratio=c(ratio,count/N)
}
barplot(ratio,names.arg=cs)
plot(cs, ratio, type="l", col="blue", xlab="c (密度パラメータ)", ylab="直径 >= 3 の割合", main="相転移の調査")
異なる頂点数 (n) の影響を調べる
par(family= "HiraKakuProN-W3")
library(igraph)
library(extrafont)
N = 400 # サンプル数
cs = seq(1, 2, 0.01) # 密度パラメータ
n_values = c(50, 100, 200) # 異なる頂点数
# 実験
results = list()
for (n in n_values) {
ratio = c()
for (c in cs) {
count = 0
for (i in 1:N) {
p = c * sqrt(log(n) / n)
g = sample_gnp(n, p)
if (diameter(g) >= 3) {
count = count + 1
}
}
ratio = c(ratio, count / N)
}
results[[as.character(n)]] = ratio
}
# プロット
plot(cs, results[[1]], type = "l", col = "red", lwd = 2,
xlab = "c (密度パラメータ)", ylab = "直径 >= 3 の割合",
main = "異なる頂点数での相転移")
for (i in 2:length(n_values)) {
lines(cs, results[[i]], col = i + 1, lwd = 2)
}
legend("topright", legend = paste("n =", n_values), col = 2:(length(n_values) + 1), lwd = 2)
❶相転移現象があるか？
相転移現象とは、ある物理量がパラメータ（この場合は cに対応）を徐々に変化させたときに、突然変化することを指す。
ランダムグラフにおいては、c（またはp）が特定の閾値を超えたときに、直径が急激に減少する現象として現れる。
（c の刻み幅を小さくして変化をより精密に観察する）
❷n(頂点数)の変化によって閾値がどう変化するか？
❸閾値が√2より小さい場合、bad pairの個数の期待値はどうなるか？
授業の内容より、
頂点i,jがbad pairである確率:
\[
(1−p) \cdot (1−p^2)^{n−2}
\]
bad pairの個数の期待値: \[
\binom{n}{2} \cdot (1-p) \cdot (1-p^2)^{n-2}
\] \[閾値 p=c \cdot \sqrt(\frac{(\log n)}{n})の場合\]
\[1-p ≈ e^{-p}\]
期待値E(bad pairの個数):
\[
\left(\frac{n(n-1)}{2}\right)⋅e^{-p}⋅e^{(-p^2)⋅(n-2)}
\] 閾値p = √2の時:
\[
\left(\frac {n(n-1)}{2} \right) \cdot {e}^{-√2} \cdot {e}^{(-2)\cdot(n-2)}
\]
\[
E=\left(\frac {n(n-1)}{2} \right)⋅e^{(-2)\cdot(n-2)-√2}
\]
・n = 100(頂点数)の時
\[
E=(\left(\frac{100\cdot99}{2}\right)\cdot e^{-196-√2} ≈ 9.09 × 10^{-83}
\]
←期待値はほぼゼロ
・N = 400(サンプル数)
\[
(\frac{400 \cdot 399}{2})⋅e^{-796-√2} ≈ 0
\]
←期待値はゼロとみなせる
結果
・c が1.0から約1.3の範囲では、縦軸の値（直径が3以上の割合）が急激に減少
・閾値 c は 約1.2前後
←閾値が√2より小さい
←bad pairが非常に稀
・n=50(赤線),𝑛=100(緑線),n=200(青線)と n を増やすにつれて、閾値が右方向（より大きなc）にシフトする
<-頂点数n が増加すると、より高い密度が必要になり、直径が3以上の状態が崩れることを示している
・bad pair の個数は閾値が√2より小さいとき急激に減少する
・閾値が√2を超えるとbad pair がほとんど観測されなくなる
