title: “孤立頂点が消滅するしきい値に関する実験” format: html editor: visual —
直径<=３となる場合
頂点 i と j は、以下の場合に「bad pair」と見なす。
❶それらは直接接続されていない。
❷両方に直接接続されている他の頂点はない。
❸i の隣接頂点を u、j の隣接頂点を r としたとき、u と r も直接接続されていない。
par(family= "HiraKakuProN-W3")
library(igraph)
library(extrafont)## Warning: package 'extrafont' was built under R version 4.3.3font_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=1000 #サンプル数
cs = seq(0.1, 1.5, 0.1)
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="相転移の調査")
確率pの閾値
ランダムグラフG(n, p)の直径が3である確率pのしきい値は、グラフに直径が3を超える「bad pair」が存在する確率が0に近づくようなpの値。
「bad pair」の総数の期待値をE(n, p)とする。 E(n, p) = 0となるpの値を求める。
bad pairである確率:
2つの頂点i, jがbad pairである確率P(i, j)は、以下の3つの条件が同時に満たされる確率。
❶iとjが隣接していない確率: \[(1 - p)\] ❷iとjに共通の隣接頂点がない確率: \[(1 - p²)⁽ⁿ⁻²⁾\]
❸iの隣接頂点とjの隣接頂点の間に辺がない確率:
\[i の隣接頂点の数を k、j の隣接頂点の数を l とすると、u と r の間にエッジがない確率は (1−p)^{k⋅l}\]
\[ したがって、P(i, j) = (1 - p) \cdot (1 - p^2)^{(n - 2)} \cdot (1−p)^{k⋅l}}となる。 \] k, l はそれぞれ i, j の次数であり、ランダムグラフ G(n,p) における頂点の次数は、平均 np の二項分布に従う。
n が十分に大きいとき、二項分布は正規分布で近似できる。したがって、k, l はそれぞれ平均 np の正規分布に従うと近似できる。
k, l の期待値をそれぞれ E[k], E[l] とすると、E[k]=E[l]=np
P(i,j) の期待値 E[P(i,j)] は、k, l をそれぞれ E[k], E[l] で置き換えることで近似的に計算できる。 \[E[P(i,j)] ≈ (1 - p) \cdot (1 - p^2)^{(n - 2)} \cdot (1-p)^{np\cdot np}\\ =E[P(i,j)] ≈ (1 - p) \cdot (1 - p^2)^{(n - 2)} \cdot (1-p)^{n^2p^2}\] グラフに直径が 3 を超える「bad pair」が存在する確率は、E[P(i,j)] をすべての頂点ペア (i,j) について合計したもの
頂点ペアの数は \[{n\choose{2}}= \frac {n(n-1)}{2}\] より、グラフに直径が 3 を超える「bad pair」が存在する確率 P は、 \[P≈\frac {n(n-1)}{2}\cdot(1 - p) \cdot (1 - p^2)^{(n - 2)} \cdot (1-p)^{n^2p^2}\] P が 0 に近づくような p の値を求めるために、P を p で微分し、微分係数が 0 になる p を求める。
しかし、P を p で微分することは困難です。そこで、P の対数をとって近似する。
\[\log P≈\log\frac{n(n-1)}{2}+\log(1-p)+(n-2)\log(1-p^2)+n^2p^2\log(1-p)\] logPをpで微分すると \[\frac{d\log P}{dp}≈ -\frac{1}{1-p}-\frac{2(n-2)p}{1-p^2}+2np^2\log(1-p)-\frac{n^2p^2}{1-p}\] \[\frac{d\log P}{dp}=0となるpは、n が十分に大きいとき、p は 0 に近いと仮定することで近似できる。\] p が 0 に近いとき、 \[\frac{d\log P}{dp}≈−1−2(n−2)p+2np^2\log(1−p)−n^2p^3\]
\[\frac{d\log P}{dp}≈-1-2np+2np^2\log(1-p)-n^2p^3\] \[\frac{d\log P}{dp}=0とすると\] \[-1-2np+2np^2\log(1-p)-n^2p^3=0\\n^2p^3-2np^2\log(1-p)+2np+1=0\] p が 0 に近いと仮定することで、log(1−p)≈−p と近似でき \[n^2p^3+2np^2\cdotp+2np+1=0\\n^2p^3+2np^3+2np+1=0\\(n^2+2n)p^3+2np+1=0\]
この方程式を解くために、カルダノの公式を用いる. (以降生成AIにより計算・省略)
計算の結果 \[p≈-\sqrt[3]{\frac{4}{n(n+2)}}\] n が十分に大きいとき、n+2≈n と近似でき \[p≈-\sqrt[3]{\frac{4}{n^2}}\] p は確率なので、正の値をとる必要があるため、グラフに直径が 3 を超える「bad pair」が存在する確率が 0 に近づくような p の値は、 \[p≈\sqrt[3]{\frac{4}{n^2}}\] n=100の時
\[p≈\sqrt[3]{\frac{4}{100^2}}= \sqrt[3]{\frac{4}{10000}} = \sqrt[3]{0.0004} ≈0.0736\] n が 100 よりも大きい場合は、p の値はさらに小さくなる。
したがって、n が十分に大きい場合、p≈0.00 となる。
結果
・cが0.1から1.5の範囲では、縦軸の値（直径が3以上の割合）が急激に増加
・閾値は約0.0736
・頂点数n が増加すると、閾値は左にシフトする