Случайный геометрический граф

В теории графов случайным геометрическим графом ( РГГ ) называется математически простейшая пространственная сеть , а именно неориентированный граф , построенный путем случайного размещения N узлов в некотором метрическом пространстве (согласно заданному распределению вероятностей) и соединения двух узлов связью тогда и только тогда если их расстояние находится в заданном диапазоне, например, меньше определенного радиуса окрестности, r .

Случайные геометрические графы во многих отношениях напоминают реальные человеческие социальные сети. Например, они спонтанно демонстрируют структуру сообщества — кластеры узлов с высокой модульностью . Другие алгоритмы генерации случайных графов, например, сгенерированные с использованием модели Эрдёша-Реньи или модели Барабаси-Альберта (BA) , не создают структуры такого типа. Кроме того, случайные геометрические графы отображают степень ассортативности в соответствии с их пространственным измерением: ^[1] «популярные» узлы (имеющие много связей) особенно вероятно будут связаны с другими популярными узлами.

Реальным применением RGG является моделирование одноранговых сетей . ^[2] Кроме того, они используются для выполнения тестов для (внешних) графовых алгоритмов.

В дальнейшем пусть $G = (V, E)$ обозначает неориентированный граф с набором вершин $V$ и набором ребер $E \subseteq V \times V$ . Размеры набора обозначаются символом $| В | = п$ и $| Е | = м$ . Кроме того, если не указано иное, рассматривается метрическое пространство $[0,1)$ $d$ с евклидовым расстоянием , т. е. для любых точек евклидово расстояние x и y определяется как ${\ Displaystyle х, у \ в [0,1) ^ {д}}$

Случайный геометрический граф (RGG) — это неориентированный геометрический граф с узлами, случайно выбранными из равномерного распределения базового пространства $[0,1)$ $d$ . ^[3] Две вершины $p, q \in V$ связаны тогда и только тогда, когда их расстояние меньше заданного ранее параметра $r \in (0,1)$ без учета петель . Таким образом, параметры $r$ и $n$ полностью характеризуют РГГ.

Наивный подход состоит в том, чтобы вычислить расстояние от каждой вершины до любой другой вершины. Поскольку есть возможные соединения, которые проверяются, временная сложность наивного алгоритма равна . Выборки генерируются с помощью генератора случайных чисел (ГСЧ) на . На практике это можно реализовать с помощью d генераторов случайных чисел на , по одному ГСЧ для каждого измерения. ${\ textstyle {\ гидроразрыва {п (п-1)} {2}}}$ ${\ textstyle \ тета (п ^ {2})}$ ${\ Displaystyle [0,1) ^ {д}}$ ${\ Displaystyle [0,1]}$

Генерация случайного геометрического графа для различных параметров связности r.