2025-11-21T11:49:15.652907

Entropy of Random Geometric Graphs in High and Low Dimensions

Baker, Dettmann

We use a multivariate central limit theorem (CLT) to study the distribution of random geometric graphs (RGGs) on the cube and torus in the high-dimensional limit with general node distributions. We find that the distribution of RGGs on the torus converges to the Erd\H os-RÃ©nyi (ER) ensemble when the nodes are uniformly distributed, but that the distribution for RGGs with non-uniformly distributed nodes on the torus, and for RGGs with any distribution of nodes with kurtosis greater than 1 on the cube is different. In these cases, the distribution has a lower maximum entropy than the ER ensemble, but is still symmetric. Soft RGGs in either geometry converge to the ER ensemble. An Edgeworth correction to the CLT is then developed to derive the $\mathcal{O}\left(d^{-\frac{1}{2}}\right)$ sub-leading term of the Shannon entropy of RGGs in dimension for both geometries. We also provide numerical approximations of maximum entropy in low-dimensional hard and soft RGGs, and calculate exactly the entropy of hard RGGs with 3 nodes in the one-dimensional cube and torus.

academic

高次元および低次元におけるランダム幾何グラフのエントロピー

基本情報

論文ID: 2503.11418
タイトル: Entropy of Random Geometric Graphs in High and Low Dimensions
著者: Oliver Baker、Carl P. Dettmann（ブリストル大学）
分類: math.PR（確率論）
発表日: 2025年8月26日（arXiv プレプリント）
論文リンク: https://arxiv.org/abs/2503.11418v3

要旨

本論文は、多変量中心極限定理（CLT）を用いて、立方体およびトーラス上のランダム幾何グラフ（RGG）の高次元極限分布を研究している。研究結果として、ノードが均一分布する場合、トーラス上のRGGはErdős-Rényi（ER）集合に収束するが、トーラス上の非均一分布ノードを持つRGG、および立方体上の尖度が1より大きい任意のノード分布を持つRGGは、ER集合とは異なる分布を示す。これらの場合、分布の最大エントロピーはER集合より低いが、対称性は保持される。ソフトRGGは両方の幾何構造で ER集合に収束する。本論文はさらにCLTのEdgeworth補正を展開し、両幾何構造におけるRGGのシャノンエントロピーの次元に関する $\mathcal{O}(d^{-1/2})$ の主導項を導出している。

研究背景と動機

問題背景

ネットワーク複雑性の理解の必要性: 現代のデータサイエンスにおいて、コンピュータビジョンから大規模言語モデルまで、高次元データセットが関わっている。例えば、MNISTデータセットは784個の特徴を持ち、GPT-3の埋め込み空間は12288次元である。高次元空間におけるネットワーク構築の幾何学的特性を理解することは極めて重要である。
グラフエントロピー理論の発展: 1955年のRashevskiによるグラフエントロピー概念の導入以来、ランダムネットワークの不確実性または複雑性を決定することは重要な研究分野となっており、シャノンエントロピー、フォン・ノイマンエントロピー、ギブスエントロピーなど複数の定義が含まれている。
ランダム幾何グラフの限界: RGGモデルは浸透、連結性、中心性測度などの側面で十分に研究されているが、集合範囲の性質（シャノンエントロピーなど）の研究は限定的であり、特に高次元の場合はそうである。

研究動機

理論的空白: 現在のところ、ノード位置に条件付けされない限り、無制約集合のエントロピーを解析的に最大化することはできない。
高次元挙動: RGGが高次元極限でER図に収束するかどうか、およびエントロピーのスケーリング挙動を理解する必要がある。
実用的応用: 高次元データにおける近傍グラフアルゴリズムに理論的基礎を提供する。

核心的貢献

初の解析計算: 1次元立方体およびトーラス上の3ノード硬RGG集合のエントロピーを解析的に計算した。
数値シミュレーション方法: 低次元ソフトRGGの最大エントロピーの数値近似方法を開発した。
収束性理論: トーラス $T^d$ 上の非均一分布ノードを持つ硬RGGがER極限から逸脱することを証明した。
普遍性結果: 立方体 $[0,1]^d$ における尖度が1より大きい任意のi.i.d.ノード分布を持つ硬RGGが決してER極限に収束しないことを証明した。
次元スケーリング: Edgeworth補正を用いて、両幾何構造におけるRGGエントロピーの次元スケーリング則を導出した。

方法の詳細

タスク定義

ランダム幾何グラフ集合のシャノンエントロピーを研究する。ここで：

入力: 幾何領域（立方体またはトーラス）、ノード分布、接続半径
出力: グラフ集合のエントロピーおよび高次元極限における挙動
制約: 固定ノード数n、次元d→∞のとき接続半径r₀はdに依存

核心的数学フレームワーク

1. ランダム幾何グラフの定義

硬RGG: $\rho(X_i, X_j) \leq r_0$ のときのみ辺 $(i,j)$ が存在 ソフトRGG: 辺 $(i,j)$ が確率 $p(\rho(X_i, X_j)/r_0)$ で存在

2. 距離測度

立方体: ユークリッド距離 $\|x\|$
トーラス: $\rho_T(x,y) = \sqrt{\sum_{i=1}^d \min(|x_i - y_i|, 1-|x_i - y_i|)^2}$

3. 中心極限定理フレームワーク

標準化距離を定義： $q_{ij} = \frac{1}{\sqrt{d}}\sum_{k=1}^d q_{ij}^k$ ここで $q_{ij}^k = |X_i^k - X_j^k|^2 - \mu_c$

技術的革新点

1. 多変量CLTの応用

高次元距離問題を多変量ガウス分布に変換し、共分散行列 $\Sigma$ の構造が収束挙動を決定：

トーラス均一分布: $\Sigma_T$ が対角行列 → ER収束
立方体任意分布: $\Sigma_c$ が非対角 → ER非収束

2. 尖度判別基準

隣接距離が無相関であるための必要十分条件が、座標分布の尖度が1に等しいことであることを証明した。これはパラメータが1/2のベルヌーイ分布のときのみ成立する。

3. Edgeworth展開

3次補正を展開： $f(q) \approx N(0,\Sigma)(q)\left[1 + \frac{1}{6\sqrt{d}}\sum_{|\alpha|=3} E[q^\alpha]H_\alpha(q)\right]$

実験設定

低次元精密計算

次元: d=1、n=3
幾何: 1次元立方体0,1およびトーラスT¹
方法: 各グラフ確率 $p_k$ の解析積分計算

数値シミュレーション

パラメータ範囲: d∈{1,2,3}、n=3
サンプル数: L=10⁸個のグラフ
接続関数: Rayleigh減衰 $p(r/r_0) = \exp(-(r/r_0)^η)$ 、η∈{1,2,3,4,5,6}および硬接続

高次元理論分析

ノード分布: 均一分布、切断ガウス分布
収束判別: 共分散行列構造分析を通じて

実験結果

主要結果

1. 精密エントロピー計算（d=1、n=3）

トーラスT¹:

最適接続半径: $\hat{r_0} = 1/4$
最大平均接続確率: $\bar{p}_{max} = 1/2$

立方体0,1:

最適接続半径: $\hat{r_0} = 0.283$
最大平均接続確率: $\bar{p}_{max} = 0.486 \neq 1/2$

2. 低次元数値結果

表3は異なる幾何および接続関数の最大エントロピーを示す：

幾何	η=1	η=2	η=3	η=4	η=5	η=6	硬接続
0,1	2.994	2.945	2.888	2.849	2.826	2.812	2.771
T¹	2.998	2.982	2.929	2.893	2.870	2.854	2.812

観察:

ソフトRGGは最大エントロピー3.0に近い
エントロピーはηの増加に伴い減少
トーラスのエントロピーは一般に立方体より高い

3. 高次元収束挙動

定理の要約:

幾何	接続関数	G(n,p)に収束?	エントロピー挙動
$T^d$ - 均一ノード	硬	✓	= H(G(n,p))
$T^d$ - 非均一ノード	硬	✗	< H(G(n,p))
$T^d$	ソフト	✓	= H(G(n,p))
$[0,1]^d$	硬	✗	< H(G(n,p))
$[0,1]^d$	ソフト	✓	= H(G(n,p))