Modèles probabilistes de graphes dans lesquels les sommets sont placés dans un espace géométrique (souvent aléatoirement) et les arêtes sont formées selon la proximité géométrique ou une règle de probabilité dépendant de la distance, faisant le lien entre géométrie continue et théorie des graphes aléatoires.

Principe

Imbriquer les sommets dans un espace métrique et connecter les paires en fonction d'une distance seuil ou d'un noyau de probabilité de connexion; étudier les propriétés du graphe (connectivité, tailles des composantes, nombres de cliques, percolation) en fonction de la géométrie sous-jacente, du processus ponctuel et du régime d'échelle.

Démonstration

Dans le modèle de Gilbert (disque unité) sur le plan, n points échantillonnés uniformément dans un carré sont reliés lorsque leur distance euclidienne est inférieure à un rayon r; lorsque n croît et que r est adapté, on observe des transitions de phase en connectivité et l'émergence d'une grande composante.

Mauvaise application

Considérer les graphes géométriques aléatoires comme des graphes d'Erdős–Rényi sans tenir compte des corrélations spatiales ou supposer l'indépendance des arêtes conduit à des seuils incorrects et à des conclusions erronées sur l'amasement et les longueurs de chemins.

Conséquence

Les graphes géométriques aléatoires modélisent des réseaux spatiaux (sans-fil, capteurs, écologiques) avec localité réaliste, fournissent des lois asymptotiques pour la connectivité et les propriétés spectrales, et informent des algorithmes exploitant la géométrie pour routage et regroupement.

Inversion

Inverser en ignorant la géométrie et en utilisant des graphes aléatoires purement combinatoires; cela simplifie l'analyse mais omet les contraintes spatiales, les effets de localité et les phénomènes induits par la géométrie comme des seuils de percolation dépendant de la dimension.

Limite

Le cadre dépend de l'espace métrique ambiant, du processus ponctuel (Poisson, binomial) et de la règle de connexion; de nombreux résultats supposent indépendance, stationnarité ou homogénéité qui échouent dans des environnements hétérogènes ou contraints.

Tension sémantique

La tension réside entre les modèles géométriques/à arêtes dépendantes et les graphes aléatoires classiques à arêtes indépendantes: la géométrie induit des dépendances et la localité qui entrent en conflit avec les approximations de champ moyen courantes en théorie combinatoire.

Synthèse

Les graphes géométriques aléatoires intègrent géométrie stochastique et théorie des graphes en plaçant des nœuds dans l'espace et en formant des arêtes par règles de proximité, capturant la dépendance spatiale et permettant l'analyse de la connectivité, des limites d'échelle et des applications aux systèmes en réseau.