Largest connected component in duplication-divergence growing graphs with symmetric coupled divergence

技術要約：対称結合ダイバージェンスを伴う複製・分岐成長グラフにおける最大連結成分

問題提起
本研究は、複製・分岐（duplication-divergence）モデルによって生成される逐次成長ネットワークの構造的進化、特に最大連結成分（LCC）の出現と遷移に焦点を当てて調査を行うものである。本研究は、対称結合ダイバージェンス（ダイバージェンスの非対称率 $\sigma = 1/2$ の場合）という特定のケースを扱っている。解決すべき中心的な課題は、非相互作用頂点（次数 $k=0$ の孤立ノード）がトポロジー的転移を形成する上で果たす役割である。本論文では、頂点の複製に関する2つの選択メカニズムを区別している。

1. $d=1$: 相互作用している頂点（少なくとも1つのエッジを持つ頂点）の間でのみ複製が行われる。
2. $d=0$: 非相互作用頂点を含むすべての頂点の間で一様に複製が行われる。
   目的は、LCCに関連する相転移を特徴付け、臨界ダイバージェンス率 $\delta_c$ を特定し、この転移とオイラーエントロピーの特異点軌跡 $\delta_{c,\xi}$ との関係を分析することである。

手法
著者らは、シミュレーションされた成長グラフを用いた解析的導出と有限サイズスケーリング（FSS）解析を組み合わせて用いている。

• モデルの動力学: 2つの連結頂点からなる初期グラフから開始し、頂点を複製し、そのエッジを確率的に分岐させることでネットワークを成長させる。ダイバージェンス確率は $\delta$ であり、対称結合は、元の頂点またはコピー頂点のいずれかからエッジが失われる確率が等しいことを意味する。
• 解析的近似: 相互作用する頂点の期待数 $N(\delta, t)$ およびエッジ数 $E(\delta, t)$ を導出する。大きな $t$ に対して、$N(\delta, t)$ は $2(1-\delta)t$ と近似される。エッジ数は先行研究 [19] から導かれたガンマ関数分布に従う。
• トポロジー指標: 本研究では、オイラー標数（$n \ge 3$ の $n$-クリークを持たないグラフの場合 $\chi = t - E(\delta, t)$）およびその自然対数であるオイラーエントロピー（$\ln|t - E(\delta, t)|$）を用いて、トポロジー的特異点を検出する。
• 有限サイズスケーリング (FSS): 以下の変数に対してFSS仮説を適用し、臨界指数および臨界点 $\delta_c$ を決定する。
  • 頂点がLCCに属する確率 $P(\delta, t)$。
  • この確率の感受率 $\chi(\delta, t)$。
  • 重み付き平均成分サイズ $\langle s \rangle$。
  • 非相互作用頂点（$s=1$）を除外した修正感受率 $\chi'(\delta, t)$。
• 時間変換: $d=0$ モデルにおいて、$d=0$ の成長動力学を $d=1$ の枠組みにマッピングするための時間変換 $t'(\delta, t)$ が導入され、オイラーエントロピーの特異性に関する統一的な解析が可能となる。

主な結果

1. 臨界ダイバージェンス率:

   • $d=0$ モデルでは、オイラーエントロピーの特異点が $\delta_{c,\xi} \approx 0.442$ で見出された。
   • $d=1$ モデルでは、オイラーエントロピーの特異点は $\delta_{c,\xi} \approx 1 - e^{-1} \approx 0.632$ で発生する。
   • LCCの転移に関する臨界点 $\delta_c$ は、オイラーエントロピーの特異点よりもわずかに先行することが判明した。$d=1$ モデルの場合、$\delta_c = 0.6 \pm 0.002$ である。$d=0$ モデルについては、孤立頂点を除外した成分サイズを分析した際に、修正された臨界点 $\delta_c' = 0.425 \pm 0.001$ が特定された。

2. スケーリングと臨界指数:

   • 転移は、$P(\delta, t)$ および $\chi(\delta, t)$ のスケーリング崩壊（scaling collapse）によって特徴付けられる。
   • $d=1$ モデルにおける推定指数は、$\zeta = -0.033 \pm 0.059$ および $\nu = 9.634 \pm 0.069$ である。関係式 $\psi/\nu = 1 + 2\zeta/\nu$ が成立し、$\psi/\nu \approx 1$ を与える。
   • 推定された $\zeta$ は極めて小さく（$10^{-2}$ のオーダー）、これは転移が爆発的（explosive）ではなく（その場合は $\zeta=0$ となる）、連続的であることを示唆している。
   • $d=0$ モデル（$s=1$ を除外）では、スケーリング崩壊により $\nu' = 6.185 \pm 0.002$ および $\varsigma = 6.827 \pm 0.002$ が得られた。

3. 非相互作用頂点の役割:

   • 非相互作用頂点の存在（$d=0$）は、$d=1$ の場合と比較して成長パターンと臨界ダイバージェンス率の位置を著しく変化させる。
   • 時間変換 $t'(\delta, t)$ は、$d=0$ のオイラーエントロピー曲線を、$頂点選択の根本的な違いにもかかわらず、$d=1$のケースと同様の$1 - e^{-1}$ 付近に特異点軌跡を示すようにマッピングすることに成功した。

意義と主張
本論文は、対称結合ダイバージェンスを伴う複製・分岐ネットワークにおける構造変化についての深い理解を提供することを主張している。主な貢献は以下の通りである。

• 相転移の特定: 対称結合ダイバージェンスモデルにおける最大連結成分の相転移を特定し、孤立頂点が複製プロセスに含まれる場合と含まれない場合の違いを明確にした。
• トポロジー的特異性との相関: LCCの転移がオイラー標数がゼロになる点（オイラーエントロピーの特異点）の近傍で発生することを示し、成長グラフにおける連結性の転移を検出するためのトポロジー不変量の有用性を強化した。
• 頂点選択の影響: 非相互作用頂点の包含（$d=0$）が、相互作用頂点に限定されたモデル（$d=1$）と比較して、臨界ダイバージェンス率を大きくシフトさせる重要な要因であることを強調した。
• 転移の性質: 推定された指数は、転移が連続的であることを示唆しており（$\zeta \approx 0$ かつ $\psi/\nu \approx 1$）、ジャミング転移やボンドパーコレーションとの妥当な類似性を描いているが、著者らは決定的な分類については慎重な姿勢を保っている。

これらの知見は、これらの特定の成長グラフモデルにおけるボンドパーコレーションに関して、特に頂点の選択メカニズムがネットワークのグローバルな連結性にどのように影響するかについて示唆を与えている。