###### tags: `research`,`network`

# [研究構想] random regular graphが同期すること

## 先行研究: [arXiv:2203.03152](https://arxiv.org/abs/2203.03152)
Strogatzらの論文。ネットワーク上の振動子が同期するかについて議論している。微分方程式は
$$
\frac{d\theta_{i}}{dt}=\sum_{j=1}^{n}a_{ij}\sin(\theta_{j}-\theta_{i})
$$
である。$a_{ij}$はネットワークの隣接行列の$(i,j)$成分である。ネットワークとして特にErdos-Renyiグラフを考える。これは各頂点間に枝を張るかを確率$p$で決めるランダムネットワークである。$p$が大きいほどネットワークが密になるので同期しやすいと考えられるが、このときある閾値があって$p$が頂点数$n$に対してどれほどであれば必ず同期するだろうか？という問いが立つ。[arXiv:1809.11083](https://arxiv.org/abs/1809.11083)では、$p\gg \log (n)/n^{1/3}$であれば$n\to\infty$で高い確率で同期することが示されている。この論文では$p\gg \log^{2}(n)/n$であれば$n\to\infty$で高い確率で同期することを示している。

:::info
[arXiv:1809.11083](https://arxiv.org/abs/1809.11083)では$p\gg \log(n)/n$であれば高い確率で同期するのではないか、とは予想されている。これの証明はまだである。
:::

以下で証明の概略を紹介する。大きく分けると2ステップあって、1つ目はランダムネットワークのスペクトラムノルムと同期の関係に関する十分条件を求めている(section 3,4,5)。その後に、Erdos-Renyiグラフのスペクトラムノルムに関する公式を用いて同期の具体的な評価を求めている(section 6)。

### 同期するための十分条件
この論文の中の定理11は特に大事である。この定理でODEが同期することとネットワークの性質(特にスペクトル)に対する関係(十分条件)を与えている。

Theorem 11
: $\|\Delta_{A}\|/(np)<1/12$かつ$\|\Delta_{L}\|/(np)<1/4$かつ
$$
\frac{\pi/4}{\sin^{-1}[12\|\Delta_{A}\|/(np)]}>\frac{\log(n/6)}{\log[np/(2\|\Delta_{L}\|)-1]}+1
$$
であれば必ず同期する。

ここで、$L=D-A$をラプラシアンとして$\Delta_{A}=A-pJ_{n},\Delta_{L}=L-pJ_{n}+npI_{n}$で定めている。$J_{n}$はすべての要素が$1$の行列である。これらはそれぞれ平均が零行列になるように定数行列でシフトを入れたものである。すなわち、$\Delta_{A}=A-\mathbb{E}[A]$である。$L$も同様である。

:::warning
この定理の証明にはErdos-Renyiグラフに関することは何も使っていないが定理の主張の中に$p$が入ってるのでそれは適宜翻訳が必要のように思う。
:::

### 　集中不等式から
$f(n,p)=2\sqrt{n\log n p(1-p)}+4(\log n)/3$としたとき、
$$
\mathbb{P}[\|\Delta_{A}\|\geq f(n,p)]<2n^{-1},\mathbb{P}[\|\Delta_{L}\|\geq 2f(n,p)]<2n^{-1}
$$
である。これを定理11に代入することで色々な評価ができる。例えば、

- $n=10^6$において、$p>0.256$であれば99.9996%以上の確率で同期する。
- $n=10^7$において、$p>0.0474$であれば99.9996%以上の確率で同期する。

がわかる。

Erdos-Renyiグラフのスペクトルに関するより強い評価が存在して、$f(n,p)=\mathcal{O}(\sqrt{np(1-p)})$の[結果](https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20089)を用いることで、
$$
p\gg \log^{2}(n)/n
$$
であれば同期する、という結果を得ることができる。

上の不等式は行列$A$に対する平均からのずれ$\mathbb{P}[\|A-\mathbb{E}[A]\|\geq f(n,p)]$がどれくらい抑えられるのか、という形になっている。特に、Erdos-Renyiグラフは各枝が独立に張られることから、$\|A-\mathbb{E}[A]\|$を独立な行列の和の形で書ける。独立な確率変数たちを足し合わせたものが平均からどれくらいずれるかを評価するものが集中不等式として広く知られていて、今回の不等式は特に(行列バージョンの)Bernsteinの不等式から得られるものである。

:::info
今回はBernsteinの不等式からErdos-Renyiグラフのスペクトルの評価を得て、それをもとに同期の判定の十分条件を与える、ということを行った。他にもこれまでの研究では$p>2\log(n-1)/n$(この評価はoptimalではなく更に良い評価も存在する)であれば$n\to\infty$で高い確率でErdos-Renyiグラフが連結になることが知られていて、これも集中不等式から得られる結果である。
:::

:::danger
上の話からErdos-Renyiグラフが$p\gg\mathcal{O}(\log(n)/n)$であれば連結になるらしい。一方で$p\gg\mathcal{O}(\log(n)/n)$であれば同期すると信じられている。これは偶然？？？同期するためにはネットワークは少なくとも連結でなければいけないから同期するための$p$のオーダーは連結するための$p$のオーダーより小さくはなりえないが。。。
:::

## random regular graphの場合
今よねだが考えているのはかんたんに言えばErdos-Renyiの話をrandom regular graphに焼き直す、ということである。なので最終的にほしい結果は、
:::success
$n$頂点の$d$-正則グラフ全体の集合を$\mathcal{M}_{n,d}$とおく。$\mathcal{M}_{n,d}$から一様ランダムに行列$A$を選んで、その上の振動子モデルを構成したときに、$d\gg\mathcal{O}(f(n))$であれば$n\to\infty$で高い確率で振動子は必ず同期する。
:::
のようなものであり、このときの$f(n)$を何らかの形で表現したいのである。これは完全に妄想だが、次数の数を考えるとErdos-Renyiグラフは平均的には$d=np$なので$f(n)=\log(n)$とか$f(n)=\log^{2}(n)$あたりで評価できるのかもしれない。

:::warning
random regular graphを考えるモチベーションは密なネットワーク側のcritical connectivityの話から来ている、となんとなく書いておく。ここも深く吟味しているわけではないので。
:::

Strogatzらの論文の手法をそのまま使おうと思うならば、やるべきことは、

1. 定理11をrandom regular graphの場合に改めて書き直す。
2. random regular graphの場合の$\Delta_{A}=A-\mathbb{E}[A]$のスペクトルの評価を行う。

の2つに分かれる。(もちろんStrogatzの手法が最善ではない可能性だってあるのでこれ以外のやり方もあり得るかもしれないけどね。)Erdos-Renyiグラフにおいてはスペクトルの評価に集中不等式を用いていたが、これは隣接行列の各要素が独立に選ばれることを利用していた。しかし、random regular graphにおいては各頂点の次数が固定されているため、隣接行列の各要素を確率変数とした場合にはそれらは独立にはならない。そのため、random regular graphにおける$\Delta_{A}$のスペクトルの評価に集中不等式を使うことができない！！なので、かんたんな焼き直しができるわけではないのが現状である。

### しばらく考えたこと
- まずrandom regular graphの隣接行列の平均はいくらだろうか？？自己ループや重複した枝がないと思うと非対角成分に$1$が立つ確率はどれも等しいように思える。また、$\mathcal{M}_{n,d}$のいずれも各行の和は$d$である。これを考えると、一様ランダムに選んだ$A\in\mathcal{M}_{n,d}$について、
$$
\mathbb{E}[A]=\frac{d}{n-1}(J_{n}-I_{n})
$$
になりそうに思える。
:::danger
このことを確認しようと思って、pythonの`networkx`の`random_regular_graph`を使って隣接行列の平均値がどうなるかを見てみようと思っていくらか計算していたら、何遍やっても生成されたrandom regular graphの$(0,1)$成分が$1$になってしまう。何かがおかしい？？下のコードを動かしたら全部1になるのが確認できると思う。

    import networkx as nx
    for seed in range(100):
        print(nx.to_numpy_array(nx.random_regular_graph(4, 100, seed))[0,1])

:::
- 上の話が正しいとしよう。random regular graphの平均をshiftする前の隣接行列についてのスペクトルの評価$\|A\|$はいくらか知られている。その結果からshiftした$\Delta_{A}$のスペクトルの評価$\|\Delta_{A}\|$につなげることができるか？？$\mathbb{E}[A]$は$J_{n}$と$I_{n}$からなっている。単位行列$I_{n}$は固有値を平行移動させるから問題ないとして、要素がすべて$1$の行列$J_{n}$の摂動で固有値はどのように変わるのだろうか？？なにか明確な計算方法があるのかな。計算してみようと思ったけど何かうまい法則があるのかはわからなかった。ググってみるとmathoverflowで
- https://mathoverflow.net/questions/243836/how-are-eigenvalues-and-eigenvectors-affected-by-adding-the-all-ones-matrix

っていうドンピシャなページがあった。ただ、明確にこうなる、ってのはなかったからすぐにはなにかわかるわけではない。いくらか数値計算をしてみて固有値分布の様子を見てみる必要があるのかもしれない。

- 厳密性は置いておくと、$\|\Delta_{A}\|$は大体$2\sqrt{d-1}$になる。そうすると、$\|\Delta_{A}\|/(np)<1/12$をrandom regular graphに置き換えた$\|\Delta_{A}\|<d/12\Leftrightarrow\sqrt{d-1}<d/6$はだいたい成り立ちそうな気がする。あと、ラプラシアン$L=D-A$について$D=dI_{n}$の定数行列になるから、$\Delta_{A}=-\Delta_{L}$であって$\|\Delta_{A}\|=\|\Delta_{L}\|$になる。ので評価も少しかんたんになるかもしれない。
- 定理11の形でネットワークの同期に関する十分条件を与えているけど、それはそもそもErdos-Renyiグラフの場合に集中不等式が使えて$\|A-\mathbb{E}[A]\|$の評価を与えることができるからな気もする。そう思うと、あまりrandom regular graphに対して$\|A-\mathbb{E}[A]\|$の評価を考えようとするのも良い道筋ではないのかもしれない。その意味では、定理11を別の形で表現するのも一つの手だと思う。Strogatzの論文の流れを注意深く追っていってrandom regular graphがいい感じに評価できる形に読み替えていくことも大事なのかもしれない。