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

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

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

Реальное применение RGG — моделирование одноранговых сетей . Кроме того, они используются для выполнения тестов графовых алгоритмов.

Определение

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

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

$d(x,y)=||x-y||_{2}={\sqrt {\sum _{i=1}^{d}(x_{i}-y_{i})^{2}}}$.

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

Алгоритмы

Наивный алгоритм

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

Псевдокод

V := generateSamples(n)  // Generates n samples in the unit cube.
for each p ∈ V do
    for each q ∈ V\{p} do
        if distance(p, q) ≤ r then
            addConnection(p, q) // Add the edge (p, q) to the edge data structure.
        end if
    end for
end for

Поскольку этот алгоритм не масштабируем (каждая вершина нуждается в информации о каждой другой вершине), Холтгреве и др. и Функе и др. представили новые алгоритмы для решения этой проблемы.

Распределенные алгоритмы

Холтгреве и др.

Этот алгоритм, предложенный Холтгреве и др., был первым алгоритмом распределенного генератора RGG для измерения 2. Он разбивает единичный квадрат на ячейки одинакового размера со стороной не менее $r$. Для заданного числа $P=p^{2}$процессоров, каждому процессору назначается ${\textstyle {k \over p}\times {k \over p}}$клетки, где ${\textstyle k=\left\lfloor {1/r}\right\rfloor .}$Для простоты, ${\textstyle P}$ предполагается, что это квадратное число, но его можно обобщить на любое количество процессоров. Затем каждый процессор генерирует ${\textstyle {\frac {n}{P}}}$вершины, которые затем распределяются между их владельцами. Затем вершины сортируются по номеру ячейки, в которую они попадают, например с помощью Quicksort . Затем каждый процессор отправляет соседним процессорам информацию о вершинах в граничных ячейках, так что каждый процессор может вычислить ребра в своем разделе независимо от других блоков. Ожидаемое время работы составляет ${\textstyle O({\frac {n}{P}}\log {\frac {n}{P}})}$. Верхняя граница стоимости связи этого алгоритма определяется выражением $T_{all-to-all}(n/P,P)+T_{all-to-all}(1,P)+T_{point-to-point}(n/(k\cdot {P})+2)$, где $T_{all-to-all}(l,c)$обозначает время для связи «все-всем» с сообщениями длиной l бит c партнерам по связи. $T_{point-to-point}(l)$— время, необходимое для двухточечной связи для сообщения длиной l бит.

Поскольку этот алгоритм не свободен от связи, Funke et al. предложенный масштабируемый распределенный генератор RGG для более высоких измерений, который работает без какой-либо связи между процессорами.

Функе и др.

Подход, используемый в этом алгоритме аналогичен подходу в Холтгреве: разбейте единичный куб на куски одинакового размера с длиной стороны не менее r . То есть в d =2 это будут квадраты, в d =3 это кубы. Поскольку там может поместиться только самое большее ${\textstyle {\left\lfloor {1/r}\right\rfloor }}$ кусков на измерение, количество кусков ограничено ${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d}}$. Как и раньше, каждому процессору назначается ${\textstyle {\left\lfloor {1/r}\right\rfloor }^{d} \over P}$куски, для которых он генерирует вершины. Чтобы добиться процесса без обмена данными, каждый процессор затем генерирует одни и те же вершины в соседних фрагментах, используя псевдорандомизацию начальных хеш-функций . Таким образом, каждый процессор вычисляет одни и те же вершины и нет необходимости обмениваться информацией о вершинах.

Что касается измерения 3, Funke et al. показало, что ожидаемое время работы равно ${\textstyle O({\frac {m+n}{P}}+\log {P})}$, без каких-либо затрат на связь между процессорами.

Свойства

и

Вероятность того, что одна вершина изолирована в RGG, равна ${\textstyle (1-\pi r^{2})^{n-1}}$. Позволять ${\textstyle X}$ — случайная величина, подсчитывающая количество изолированных вершин. Тогда ожидаемое значение ${\textstyle X}$ является ${\textstyle E(X)=n(1-\pi r^{2})^{n-1}=ne^{-\pi r^{2}n}-O(r^{4}n)}$. Термин ${\textstyle \mu =ne^{-\pi r^{2}n}}$предоставляет информацию о подключении RGG. Для ${\textstyle \mu \longrightarrow 0}$РГГ асимптотически почти наверняка связна. Для $\mu \longrightarrow \infty$РГГ асимптотически почти наверняка несвязна. И для ${\textstyle \mu =\Theta (1)}$, RGG имеет гигантский компонент, охватывающий более ${\textstyle {\frac {n}{2}}}$вершины и $X$ распределено по Пуассону с параметром $\mu$. Отсюда следует, что если ${\textstyle \mu =\Theta (1)}$, вероятность того, что RGG подключен, равна ${\textstyle P[X=0]\sim e^{-\mu }}$и вероятность того, что RGG не подключен, равна ${\textstyle P[X>0]\sim 1-e^{-\mu }}$.

Для любого ${\textstyle l_{p}}$-Норм( ${\textstyle 1\leq p\leq \infty }$) и для любого числа измерений $d>2$RGG обладает резким порогом связности на уровне ${\textstyle r\sim \left({\ln(n) \over \alpha _{p,d}n}\right)^{1 \over d}}$с постоянным $\alpha _{p,d}$. В частном случае двумерного пространства и евклидовой нормы ( $d=2$ и $p=2$) это дает ${\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}$.

Гамильтоновость

Показано, что в двумерном случае порог ${\textstyle r\sim {\sqrt {\ln(n) \over \pi n}}}$также предоставляет информацию о существовании гамильтонова цикла ( Гамильтонов путь ). Для любого $\epsilon >0$, если ${\textstyle r\sim {\sqrt {\ln(n) \over (\pi +\epsilon )n}}}$, то в РГГ асимптотически почти наверняка отсутствует гамильтонов цикл, и если ${\textstyle r\sim {\sqrt {\ln(n) \over (\pi -\epsilon )n}}}$для любого ${\textstyle \epsilon >0}$, то РГГ асимптотически почти наверняка имеет гамильтонов цикл.

Коэффициент кластеризации

Коэффициент кластеризации РГГ зависит только от размерности d основного пространства [0,1) ^д . Коэффициент кластеризации

${\textstyle C_{d}=1-H_{d}(1)}$даже для $d$ и ${\textstyle C_{d}={3 \over 2}-H_{d}({1 \over 2})}$для странных $d$ где

$$H_{d}(x)={1 \over {\sqrt {\pi }}}\sum _{i=x}^{d \over 2}{\Gamma (i) \over \Gamma (i+{1 \over 2})}\left({3 \over 4}\right)^{i+{1 \over 2}}$$

Для больших $d$, это упрощается до $C_{d}\sim 3{\sqrt {2 \over \pi d}}\left({3 \over 4}\right)^{d+1 \over 2}$.

геометрические

В 1988 году Ваксман обобщил стандартную РГГ, введя вероятностную функцию связи в отличие от детерминированной, предложенной Гилбертом. Пример, представленный Ваксманом, представлял собой растянутую экспоненту, в которой два узла $i$ и $j$ соединить с вероятностью, заданной выражением ${\textstyle H_{ij}=\beta e^{-{r_{ij} \over r_{0}}}}$где $r_{ij}$ это евклидово разделение и $\beta$, $r_{0}$параметры, определяемые системой. Этот тип РГГ с функцией вероятностной связи часто называют мягким случайным геометрическим графом, который теперь имеет два источника случайности; расположение узлов (вершин) и образование связей (ребер). Эта функция связи получила дальнейшее обобщение в литературе. ${\textstyle H_{ij}=\beta e^{-\left({r_{ij} \over r_{0}}\right)^{\eta }}}$который часто используется для исследования беспроводных сетей без помех. Параметр $\eta$ показывает, как сигнал затухает с расстоянием, когда $\eta =2$ свободное пространство, $\eta >2$ моделирует более загроможденную среду, например город (= 6 моделей городов, таких как Нью-Йорк), в то время как $\eta <2$ моделирует высокоотражающую среду. Мы замечаем, что для $\eta =1$ является моделью Ваксмана, тогда как $\eta \to \infty$ и ${\textstyle \beta =1}$ у нас стандартный RGG. Интуитивно этот тип функций соединения моделирует, как вероятность установления соединения уменьшается с расстоянием.

Обзор некоторых результатов для Soft RGG

В пределе высокой плотности для сети с экспоненциальной функцией связи количество изолированных узлов распределено по Пуассону, и результирующая сеть содержит только уникальный гигантский компонент и изолированные узлы. Поэтому, гарантируя отсутствие изолированных узлов, в плотном режиме сеть остается полностью связной; аналогично результатам, показанным на для дисковой модели. Часто свойства этих сетей, такие как центральность по посредничеству, и подключение изучаются в пределе как плотность $\to \infty$ это часто означает, что пограничные эффекты становятся незначительными. Однако в реальной жизни, где сети ограничены, хотя и могут быть чрезвычайно плотными, пограничные эффекты будут влиять на полную связность; фактически показали, что на полную связность с экспоненциальной функцией соединения сильно влияют граничные эффекты, поскольку узлы вблизи угла/грани домена с меньшей вероятностью соединятся по сравнению с узлами в объеме. В результате полная связность может быть выражена как сумма вкладов объема и границ геометрии. Более общий анализ функций соединения в беспроводных сетях показал, что вероятность полной связности можно хорошо аппроксимировать, выраженную несколькими моментами функции соединения и геометрией областей.