2025-11-16T21:22:11.887650

Rare event probabilities in Random Geometric Graphs

Deka, Luo, Wu

In this paper, we study rare events in spherical and Gaussian random geometric graphs in high dimensions. In these models, the vertices correspond to points sampled uniformly at random on the $d$ dimensional unit sphere or correspond to $d$ dimensional standard Gaussian vectors, and edges are added between two vertices if the inner-product between their corresponding points are greater than a threshold $t_p$, chosen such that the probability of having an edge is equal to $p$. We focus on two problems: (a) the probability that the RGG is a complete graph, and (b) the probability of observing an atypically large number of edges. We obtain asymptotically exponential decay rates depending on $n$ and $d$ of the probabilities of these rare events through a combination of geometric and probabilistic arguments.

academic

Wahrscheinlichkeiten seltener Ereignisse in zufälligen geometrischen Graphen

Grundinformationen

Paper-ID: 2510.09196
Titel: Rare event probabilities in Random Geometric Graphs
Autoren: Prabhanka Deka (Beijing International Center for Mathematical Research, Peking-Universität), Fangzhou Luo (School of Mathematical Sciences, Peking-Universität), Baichuan Wu (School of Mathematical Sciences, Peking-Universität)
Klassifikation: math.PR (Wahrscheinlichkeitstheorie)
Veröffentlichungsdatum: 10. Oktober 2025 (arXiv-Preprint)
Paper-Link: https://arxiv.org/abs/2510.09196

Zusammenfassung

Dieses Paper untersucht seltene Ereignisse in hochdimensionalen Sphären und Gaußschen zufälligen geometrischen Graphen. In diesen Modellen entsprechen Knoten gleichmäßig zufällig gewählten Punkten auf der $d$ -dimensionalen Einheitssphäre oder $d$ -dimensionalen Standard-Gaußvektoren. Eine Kante wird zwischen zwei Knoten eingefügt, wenn das innere Produkt der entsprechenden Punkte einen Schwellenwert $t_p$ übersteigt, wobei $t_p$ so gewählt wird, dass die Wahrscheinlichkeit für das Vorhandensein einer Kante gleich $p$ ist. Das Paper konzentriert sich auf zwei Probleme: (a) die Wahrscheinlichkeit, dass der zufällige geometrische Graph ein vollständiger Graph ist, und (b) die Wahrscheinlichkeit, eine ungewöhnlich große Anzahl von Kanten zu beobachten. Durch eine Kombination geometrischer und wahrscheinlichkeitstheoretischer Argumente werden asymptotische Exponentialabfallraten dieser Wahrscheinlichkeiten seltener Ereignisse ermittelt, die von der Anzahl der Knoten $n$ und der Dimension $d$ abhängen.

Forschungshintergrund und Motivation

Problemdefinition

Die Kernprobleme dieser Forschung sind die Analyse zweier Klassen seltener Ereignisse in hochdimensionalen zufälligen geometrischen Graphen:

Vollständige-Graph-Wahrscheinlichkeit: Die Wahrscheinlichkeit, dass der zufällige geometrische Graph ein vollständiger Graph wird (Kanten zwischen allen Knotenpaaren existieren)
Große Abweichungen der Kantenzahl: Die Wahrscheinlichkeit, eine ungewöhnlich große Anzahl von Kanten zu beobachten

Forschungsbedeutung

Theoretische Bedeutung: Zufällige geometrische Graphen sind grundlegende Werkzeuge zur Modellierung komplexer Systeme und werden in Informatik, Biologie, Soziologie und Physik weit verbreitet angewendet
Praktische Anwendungen:
- Anomalieerkennung und Hypothesentests
- Analyse von Clique-Strukturen in hochdimensionalen Daten
- Robustheitsanalyse geometrischer Netzwerkmodelle
- Innenproduktsbasierte Ähnlichkeitsmessungen in neuronalen Netzen und Kernmethoden

Einschränkungen bestehender Forschung

Frühere Arbeiten fixierten typischerweise die Dimension $d$ und ließen die Knotenzahl $n$ gegen Unendlich gehen
Systematische Analyse hochdimensionaler dichter zufälliger geometrischer Graphen fehlte
Die komplexen Abhängigkeitsbeziehungen zwischen Kanten erschweren die Analyse erheblich

Kernbeiträge

Etablierung eines vollständigen theoretischen Rahmens: Bereitstellung einer einheitlichen Analysemethode für seltene Ereignisse in sphärischen und Gaußschen zufälligen geometrischen Graphen
Ermittlung präziser Abfallraten: Bereitstellung von Ober- und Untergrenzen für die Wahrscheinlichkeit vollständiger Graphen und großer Abweichungen der Kantenzahl unter verschiedenen $n$ - und $d$ -Beziehungen
Entwicklung innovativer technischer Werkzeuge:
- Anwendung sphärischer symmetrischer Umordnungstechniken
- Kopplungsmethoden zwischen zwei Modellen
- Organische Kombination geometrischer und wahrscheinlichkeitstheoretischer Argumente
Offenlegung von Dimensionseffekten: Entdeckung, dass sich zufällige geometrische Graphen im hochdimensionalen Fall dem Erdős-Rényi-Modell ähneln, während sie im niedrigdimensionalen Fall unterschiedliche Eigenschaften aufweisen

Methodische Details

Modelldefinition

Sphärischer zufälliger geometrischer Graph (SRGG)

Knoten: $(X_1, \ldots, X_n)$ unabhängig und identisch verteilt gleichmäßig auf der $d$ -dimensionalen Einheitssphäre $S^{d-1}$
Kanten: Eine Kante existiert zwischen Knoten $i$ und $j$ , wenn $\langle X_i, X_j \rangle \geq t_p$
Schwellenwert: $t_p$ wird so gewählt, dass $P(\langle X_1, X_2 \rangle \geq t_p) = p$

Gaußscher zufälliger geometrischer Graph (GRGG)

Knoten: $(\tilde{X}_1, \ldots, \tilde{X}_n)$ unabhängig und identisch verteilt nach der $d$ -dimensionalen Standardnormalverteilung
Kanten: Eine Kante existiert zwischen Knoten $i$ und $j$ , wenn $\langle \tilde{X}_i, \tilde{X}_j \rangle \geq \tilde{t}_p$
Schwellenwert: $\tilde{t}_p$ wird so gewählt, dass $P(\langle \tilde{X}_1, \tilde{X}_2 \rangle \geq \tilde{t}_p) = p$

Kernmethodische Techniken

1. Kopplungstechnik

Durch die Beobachtung, dass $\tilde{X}/\|\tilde{X}\|$ gleichmäßig auf der Sphäre verteilt ist, wird eine Kopplungsbeziehung zwischen den beiden Modellen etabliert:

Lemma 3.2: Für festes $p < 1/2$ und kleines $\delta > 0$ existieren Konstanten $c_\delta, \Delta_\delta$ , so dass: $P_{n,d}(\tilde{E}(n,d,p)) \leq \exp(-c_\delta dn) + 2^n P_{n,d}(E((1-\delta)n, d, q))$

2. Symmetrische Umordnungstechnik

Nutzung symmetrischer Umordnung auf der Sphäre zur Behandlung komplexer geometrischer Nebenbedingungen:

Theorem 3.4: Für Funktionen $f_1, \ldots, f_n$ auf der Sphäre und steigende Funktionen $K_{i,j}$ gilt: $I[f_1, \ldots, f_n] \leq I[f_1^*, \ldots, f_n^*]$ wobei $f^*$ die symmetrische Umordnung von $f$ bezeichnet.

3. Asymptotisches Verhalten des Schwellenwerts

Lemma 3.1: Für festes $p \in (0,1)$ gilt bei $d \to \infty$ :

$\tilde{t}_p = (\Phi^{-1}(p) + o(1))\sqrt{d}$
$t_p = (\Phi^{-1}(p) + o(1))/\sqrt{d}$

Hauptbeweisstrategien

Beweis der Untergrenzen

Erdős-Rényi-Typ-Untergrenzen: Beweis von $P(E) \geq p^{\binom{n}{2}}$ durch geometrische Argumente
Bias-Argumente: Im Gaußmodell wird eine kleine Verzerrung auf die erste Koordinate aller Vektoren angewendet
Dimensionsabhängige Grenzen: Wenn $\log n < \varepsilon d$ , dann $P(\tilde{E}) \geq \exp(-Cn\sqrt{d \log n})$

Beweis der Obergrenzen

Bayessche Argumente: Nutzung der Eigenschaften der Statistik $S = \sum_{i \neq j} \langle \tilde{X}_i, \tilde{X}_j \rangle$
Sphärische-Kappe-Prozessanalyse: Umwandlung komplexer konvexer Mengenprozesse in Sphärische-Kappe-Prozesse durch symmetrische Umordnung
Momentenerzeugungsfunktionsmethode: Verwendung der exponentiellen Markov-Ungleichung für Kantenabweichungsprobleme

Experimentelle Ergebnisse

Hauptergebnisse zur Wahrscheinlichkeit vollständiger Graphen

Nach Theorem 2.1 und Theorem 2.2 haben die Wahrscheinlichkeiten vollständiger Graphen in verschiedenen Dimensionsbereichen unterschiedliche Abfallraten:

Dimensionsbereich	Untergrenze	Obergrenze
$d \gtrsim n^2$	$-Cn^2$	$-cn^2$
$n^2/\log n \lesssim d \lesssim n^2$	$-Cn\sqrt{d}$	$-cn^2$
$n^{4/3+o(1)} \lesssim d \lesssim n^2/\log n$	$-Cn\sqrt{d}$	$-cn\sqrt{d \log n}$
$\log n \lesssim d \lesssim n^{4/3+o(1)}$	$-Cn\sqrt{d \log n}$	$-cn\sqrt{d \log n}$
$d \lesssim \log n$	$-Cnd$	$-cnd$

Hauptergebnisse zu großen Abweichungen der Kantenzahl

Theorem 2.3 und Theorem 2.4 geben präzise Grenzen für große Abweichungen der Kantenzahl:

Für das Ereignis $I_\varepsilon := \{|E(G)| \geq (1+\varepsilon)\binom{n}{2}p\}$ gilt: $\exp(-c\min(n^2, n\sqrt{d})) \leq P(I_\varepsilon) \leq \exp(-C\min(n^2, n\sqrt{d}))$

Wichtigste Erkenntnisse

Dimensionsschwelleneffekt: Wenn $d \gtrsim \sqrt{n}$ , ist die Abfallrate $\exp(-\Omega(n^2))$ , ähnlich wie beim Erdős-Rényi-Modell
Erhaltung geometrischer Effekte: Wenn $d \lesssim \sqrt{n}$ , ist die Abfallrate $\exp(-\Omega(n\sqrt{d}))$ , was die Auswirkungen der geometrischen Struktur widerspiegelt
Übereinstimmende Ober- und Untergrenzen: In den Bereichen $d \geq n^2$ und $d \leq n^{4/3+o(1)}$ wurden übereinstimmende Ober- und Untergrenzen erreicht

Technische Innovationen

1. Innovative Anwendung der Kopplungstechnik

Durch die Sphärenprojektionen $\tilde{X}/\|\tilde{X}\|$ wird eine Verbindung zwischen den beiden Modellen hergestellt, was wiederholte Analysen komplexer Natur vermeidet.

2. Innovative Anwendung geometrischer Werkzeuge in der Wahrscheinlichkeitstheorie

Innovative Anwendung der symmetrischen Umordnung, eines geometrischen Analysewerkzeugs, auf wahrscheinlichkeitstheoretische Probleme, besonders bei der Behandlung komplexer Kantenabhängigkeitsbeziehungen.

3. Mehrskalenanalysegerüst

Etablierung eines einheitlichen Analysegerüsts für verschiedene $(n,d)$ -Beziehungen, das Übergangsverhaltens vom niedrig- zum hochdimensionalen Fall offenlegt.

Einschränkungen und zukünftige Richtungen

Einschränkungen

Technische Einschränkungen: Im mittleren Bereich $n^{4/3} \lesssim d \lesssim n^2$ existiert eine Lücke zwischen Ober- und Untergrenzen
Modelleinschränkungen: Hauptsächlich wird der Fall $p \leq 1/2$ betrachtet; die Analyse für $p > 1/2$ ist relativ begrenzt
Methodische Einschränkungen: Informationsverlust während des symmetrischen Umordnungsprozesses führt zu nicht ausreichend engen Grenzen in einigen Fällen

Zukünftige Forschungsrichtungen

Verbesserung theoretischer Grenzen: Schließung der Lücke zwischen Ober- und Untergrenzen im mittleren Bereich
Modellerweiterung: Betrachtung allgemeinerer $p$ -Werte und anderer geometrischer Metriken
Algorithmische Anwendungen: Anwendung theoretischer Ergebnisse auf praktische Netzwerkanalyse und Machine-Learning-Probleme
Dynamische Modelle: Untersuchung seltener Ereignisse in zeitvarianten zufälligen geometrischen Graphen

Tiefgreifende Bewertung

Stärken

Theoretische Tiefe: Etablierung eines vollständigen mathematischen Theorierahmens, der tiefe Ergebnisse aus Geometrie, Wahrscheinlichkeitstheorie und Analysis kombiniert
Technische Innovation: Die Anwendung der symmetrischen Umordnungstechnik in der Theorie zufälliger Graphen ist bahnbrechend
Vollständigkeit der Ergebnisse: Präzise Ober- und Untergrenzen in mehreren Dimensionsbereichen zeigen die Komplexität des Problems
Allgemeingültigkeit der Methoden: Die entwickelten Techniken können auf andere Probleme geometrischer zufälliger Graphen verallgemeinert werden

Mängel

Unvollständigkeit: Die Nichtübereinstimmung von Ober- und Untergrenzen im mittleren Bereich beeinträchtigt die Vollständigkeit der Ergebnisse
Praktische Einschränkungen: Hauptsächlich theoretische Ergebnisse ohne numerische Verifikation und praktische Anwendungsdemonstration
Technische Komplexität: Die Beweistechniken sind relativ komplex, was die Verallgemeinerbarkeit der Ergebnisse möglicherweise einschränkt

Akademischer Einfluss

Theoretischer Beitrag: Bereitstellung einer wichtigen theoretischen Grundlage für die Theorie hochdimensionaler zufälliger geometrischer Graphen
Methodologischer Beitrag: Die Anwendung der symmetrischen Umordnungstechnik bietet neue Analysewerkzeuge für verwandte Probleme
Inspirationswert: Die Offenlegung der Schlüsselrolle der Dimension in zufälligen geometrischen Graphen bietet Richtung für nachfolgende Forschung

Anwendbare Szenarien

Theoretische Forschung: Theorie zufälliger Graphen, geometrische Wahrscheinlichkeitstheorie, hochdimensionale Phänomene
Anwendungsfelder: Netzwerkwissenschaft, Kernmethoden im Machine Learning, hochdimensionale Statistik
Algorithmisches Design: Algorithmusanalyse und -optimierung basierend auf geometrischen Graphen

Fazit

Dieses Paper erzielt wichtige theoretische Durchbrüche in der Analyse seltener Ereignisse in zufälligen geometrischen Graphen. Durch innovative Kombination von symmetrischen Umordnungstechniken und wahrscheinlichkeitstheoretischen Methoden wird eine systematische Analyse für die Probleme der Wahrscheinlichkeit vollständiger Graphen und großer Abweichungen der Kantenzahl in hochdimensionalen sphärischen und Gaußschen zufälligen geometrischen Graphen bereitgestellt. Obwohl in einigen technischen Details noch Verbesserungsspielraum besteht, legt der etablierte theoretische Rahmen und die gewonnenen tiefgreifenden Ergebnisse eine solide Grundlage für die Entwicklung dieses Forschungsbereichs und besitzen wichtigen akademischen Wert und Inspirationsbedeutung.