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

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

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

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

• 1 Определение
• 2 Алгоритмы
  • 2.1 Наивный алгоритм
    • 2.1.1 Псевдокод
  • 2.2 Распределенные алгоритмы
    • 2.2.1 Holtgrewe et al.
    • 2.2.2 Funke и др.
• 3 Свойства
  • 3.1 Изолированные вершины и связность
  • 3.2 Гамильтонность
  • 3.3 Коэффициент кластеризации
• 4 Обобщенные случайные геометрические графики
  • 4.1 Обзор некоторых результатов для Soft RGG
• 5 Ссылки

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

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

$d\; (x,\; y)\; =\; |\; |\; х\; -\; у\; |\; |\; 2\; знак\; равно\; \sum \; я\; знак\; равно\; 1\; d\; (xi\; -\; yi)\; 2\; \{\backslash \; displaystyle\; d\; (x,\; y)\; =\; ||\; xy\; ||\; \_\; \{2\}\; =\; \{\backslash \; sqrt\; \{\backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{d\}\; (\; x\_\; \{i\}\; -y\_\; \{i\})\; ^\; \{2\}\}\}\}$.

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

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

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

Псевдокод

V: = generateSamples (n) // Генерирует n выборок в единичном кубе. для каждого p ∈ V doдля каждого q ∈ V \ {p} doifdistance (p, q) ≤ r, затем addConnection (p, q) // Добавьте край (p, q) в структуру данных края. конец, если конец для конец для

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

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

Holtgrewe et al.

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

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

Funke et al.

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

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

Изолированные вершины и связность

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

Для любого $lp\; \{\backslash \; стиль\; текста\; l\_\; \{p\}\}$-Norm ($1\; \le \; p\; \le \; \infty \; \{\backslash \; textstyle\; 1\; \backslash \; leq\; p\; \backslash \; leq\; \backslash \; infty\}$) и для любого количества измерений $d>2\; \{\backslash \; displaystyle\; d>2\}$, RGG обладает резким порогом подключения в $r\; \sim \; (ln\; \; (n)\; \alpha \; p,\; dn)\; 1\; d\; \{\backslash \; textstyle\; r\; \backslash \; sim\; (\{\backslash \; ln\; (n)\; \backslash \; over\; \backslash \; alpha\; \_\; \{p,\; d\}\; n\})\; ^\; \{1\; \backslash \; over\; d\}\}$с минусами tant $\alpha \; p,\; d\; \{\backslash \; displaystyle\; \backslash \; alpha\; \_\; \{p,\; d\}\}$. В частном случае двумерного пространства и евклидовой нормы ($d\; =\; 2\; \{\backslash \; displaystyle\; d\; =\; 2\}$и $p\; =\; 2\; \{\backslash \; displaystyle\; p\; =\; 2\}$) это дает $r\; \sim \; ln\; \; (n)\; \pi \; n\; \{\backslash \; textstyle\; r\; \backslash \; sim\; \{\backslash \; sqrt\; \{\backslash \; ln\; (n)\; \backslash \; over\; \backslash \; pi\; n\}\}\}$.

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

Было показано, что в двумерном случае порог $r\; \sim \; ln\; \; (n)\; \pi \; n\; \{\backslash \; textstyle\; r\; \backslash \; sim\; \{\backslash \; sqrt\; \{\backslash \; ln\; (n)\; \backslash \; over\; \backslash \; pi\; n\}\; \}\}$также предоставляет информацию о существовании гамильтонова цикла (Hamiltonian Path ). Для любого $ϵ>0\; \{\backslash \; displaystyle\; \backslash \; epsilon>0\}$, если $r\; \sim \; ln\; \; (n)\; (\pi \; +\; ϵ)\; n\; \{\backslash \; textstyle\; r\; \backslash \; sim\; \{\backslash \; sqrt\; \{\backslash \; ln\; (n)\; \backslash \; over\; (\; \backslash \; pi\; +\; \backslash \; epsilon)\; n\}\}\}$, то RGG асимптотически почти наверняка не имеет гамильтонова цикла, и если $r\; \sim \; ln\; \; (n)\; (\pi \; -\; ϵ)\; n\; \{\backslash \; textstyle\; r\; \backslash \; sim\; \{\backslash \; sqrt\; \{\backslash \; ln\; (n)\; \backslash \; over\; (\backslash \; pi\; -\; \backslash \; epsilon)\; n\}\}\}$для любого $ϵ>0\; \{\backslash \; textstyle\; \backslash \; epsilon>0\}$, тогда RGtoG имеет asy почти наверняка гамильтонов цикл.

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

Коэффициент кластеризации групп RGG зависит только от измерения dнижележащего пространства [0,1). Коэффициент кластеризации равен

$C\; d\; =\; 1\; -\; H\; d\; (1)\; \{\backslash \; textstyle\; C\_\; \{d\}\; =\; 1-H\_\; \{d\}\; (1)\}$для четного $d\; \{\backslash \; displaystyle\; d\}$и $C\; d\; =\; 3\; 2\; -\; H\; d\; (1\; 2)\; \{\backslash \; textstyle\; C\_\; \{d\}\; =\; \{3\; \backslash \; over\; 2\}\; -H\_\; \{d\}\; (\{1\; \backslash \; over\; 2\})\}$для нечетного $d\; \{\backslash \; displaystyle\; d\}$где

$H\; d\; (x)\; =\; 1\; \pi \; \sum \; i\; =\; xd\; 2\; \Gamma \; (i)\; \Gamma \; (i\; +\; 1\; 2)\; (3\; 4)\; я\; +\; 1\; 2\; \{\backslash \; displaystyle\; H\_\; \{d\}\; (x)\; =\; \{1\; \backslash \; over\; \{\backslash \; sqrt\; \{\backslash \; pi\}\}\}\; \backslash \; sum\; \_\; \{i\; =\; x\}\; ^\; \{d\; \backslash \; over\; 2\}\; \{\backslash \; Gamma\; (i)\; \backslash \; over\; \backslash \; Gamma\; (i\; +\; \{1\; \backslash \; over\; 2\})\}\; (\{3\; \backslash \; over\; 4\})\; ^\; \{i\; +\; \{1\; \backslash \; over\; 2\}\}\}$Для больших $d\; \{\backslash \; displaystyle\; d\}$, это упрощается до $C\; d\; \sim \; 3\; 2\; \pi \; d\; (3\; 4)\; d\; +\; 1\; 2\; \{\backslash \; displaystyle\; C\_\; \{d\}\; \backslash \; sim\; 3\; \{\backslash \; sqrt\; \{2\; \backslash \; over\; \backslash \; pi\; d\}\}\; (\{3\; \backslash \; over\; 4\})\; ^\; \{d\; +\; 1\; \backslash \; over\; 2\}\}$.

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

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

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

1. ^Антониони, Альберто ; Томассини, Марко (28 сентября 2012 г.). «Степенные корреляции в случайных геометрических графах». Physical Review E. 86 : 037101. arXiv : 1207.2573. doi : 10.1103 / PhysRevE.86.037101.
2. ^Нековее, Мазиар (28 июня 2007 г.). «Эпидемии червей в беспроводных ad hoc сетях». Новый журнал физики. 9 (6): 189. arXiv : 0707.2293. Bibcode : 2007NJPh.... 9..189N. doi : 10.1088 / 1367-2630 / 9/6/189.
3. ^Пенроуз, Мэтью. (2003). Случайные геометрические графы. Оксфорд: Издательство Оксфордского университета. ISBN 0198506260. OCLC 51316118.
4. ^фон Луз, Мориц; Страш, Даррен; Шульц, Кристиан; Пенчак, Мануэль; Сандерс, Питер; Мейер, Ульрих; Ламм, Себастьян; Функе, Даниэль (2017-10-20). «Генерация массово распределенных графов без общения». arXiv : 1710.07565v3. Bibcode : 2017arXiv171007565F. Для цитирования журнала требуется | journal =()
5. ^ von Looz, Moritz; Strash, Darren; Schulz, Кристиан; Пенчак, Мануэль; Сандерс, Питер; Мейер, Ульрих; Ламм, Себастьян; Функе, Дэниел (2017-10-20). «Создание массово распределенных графов без общения». arXiv : 1710.07565v3. Bibcode : 2017arXiv171007565F. Для цитирования журнала требуется | journal =()
6. ^Perez, Xavier; Mitsche, Дитер; Диаз, Хосеп (13 февраля 2007 г.). «Динамические случайные геометрические графы». arXiv : cs / 0702074. Bibcode : 2007cs........ 2074D. Цитировать журнал требуется | journal =()
7. ^Perez, X.; Mitsche, D.; Diaz, J. (07.07.2006). «Резкий порог гамильтонности случайных геометрических графов». arXiv : cs / 0607023. Bibcode : 2006cs........ 7023D. Cite journal требует | journal =()
8. ^Christensen, Michael; Dall, Jes пер (2002-03-01). «Случайные геометрические графы». Physical Review E. 66 : 016121. arXiv : cond-mat / 0203026. doi : 10.1103 / PhysRevE.66.016121.
9. ^Ваксман, Б.М. (1988). «Маршрутизация многоточечных соединений». Журнал IEEE по избранным областям коммуникаций. 6 (9): 1617–1622. doi : 10.1109 / 49.12889.
10. ^Mao, G; Андерсон, Б.Д. (2013). «Возможность подключения больших беспроводных сетей в рамках общей модели подключения». IEEE Transactions по теории информации. 59 (3): 1761–1772. doi : 10.1109 / tit.2012.2228894.
11. ^Пенроуз, Мэтью Д. (1997). «Самое длинное ребро случайного минимального остовного дерева». Анналы прикладной теории вероятностей: 340361.
12. ^Giles, Alexander P.; Георгиу, Орестис; Деттманн, Карл П. (2015). «Центральность промежуточности в плотных случайных геометрических сетях». 2015 Международная конференция по коммуникациям IEEE (ICC). С. 6450–6455. arXiv : 1410.8521. Bibcode : 2014arXiv1410.8521K. doi : 10.1109 / ICC.2015.7249352. ISBN 978-1-4673-6432-4.
13. ^Mao, G; Андерсон, Б.Д. (2013). «Возможность подключения больших беспроводных сетей в рамках общей модели подключения». IEEE Transactions по теории информации. 59 (3): 1761–1772. doi : 10.1109 / tit.2012.2228894.
14. ^Кун, Дж; Деттманн, С. П.; Георгиу, О (2012). «Полная связность: углы, края и грани». Журнал статистической физики. 147 (4): 758–778. arXiv : 1201.3123. Bibcode : 2012JSP... 147..758C. doi : 10.1007 / s10955-012-0493-y.
15. ^Dettmann, C.P; Георгиу, О. (2016). «Случайные геометрические графы с общими связными функциями». Physical Review E. 93 (3): 032313. arXiv : 1411.3617. Bibcode : 2016PhRvE..93c2313D. doi : 10.1103 / physreve.93.032313. PMID 27078372.

.