Zufälliger geometrischer Graph

Ein zufälliger geometrischer Graph ist ein ungerichteter geometrischer Graph mit Knoten gleichverteilt auf dem zugrundeliegenden Raum ${\displaystyle [0,1)^{d}}$. Zwei Knoten sind genau dann verbunden, wenn ihre Distanz geringer ist als ein zuvor spezifizierter Parameter ${\displaystyle r\in (0,1)}$.

Zufällige geometrische Graphen ähneln menschlichen sozialen Netzwerken in vielerlei Hinsicht. Sie zeigen häufig Gemeinschaftsstrukturen, d. h. es bilden sich dicht verknüpfte Gruppen von Knoten. Andere Generatoren für zufällige Graphen, wie zum Beispiel das Erdős-Rényi-Modell oder Barabási-Albert-Modell (BA-Modell), generieren keine solche Strukturen. Außerdem sind Knoten mit einem hohen Knotengrad besonders wahrscheinlich verbunden mit anderen Knoten mit einem hohen Knotengrad.

Eine Anwendung der zufälligen geometrischen Graphen besteht in der Modellierung von Ad-hoc-Netzwerken. Außerdem können sie benutzt werden, um Benchmarks für (externe) Graphalgorithmen zu erstellen.