Гиперболический геометрический граф

Гиперболический геометрический граф (HGG) или гиперболическая геометрическая сеть (HGN) — это особый тип пространственной сети , в которой (1) скрытые координаты узлов разбросаны в соответствии с функцией плотности вероятности в гиперболическое пространство постоянной между двумя узлами присутствует , отрицательной кривизны и (2) ребро если они близки по функции метрики (обычно это либо ступенчатая функция Хевисайда, приводящая к детерминированным соединениям между вершинами, расположенными ближе определенного порогового расстояния, либо убывающая функция гиперболического расстояния, дающая вероятность соединения). HGG обобщает случайный геометрический граф (RGG), пространство вложения которого является евклидовым.

Математическая формулировка

Математически HGG — это граф. $G(V,E)$ вершин с множеством V ( мощность $N=|V|$) и множество ребер E, построенное путем рассмотрения узлов как точек, помещенных в двумерное гиперболическое пространство. $\mathbb {H} _{\zeta }^{2}$ постоянной отрицательной гауссовой кривизны , $-\zeta ^{2}$ и радиус среза $R$, то есть радиус диска Пуанкаре , который можно визуализировать с помощью модели гиперболоида . Каждая точка $i$ имеет гиперболические полярные координаты $(r_{i},\theta _{i})$ с $0\leq r_{i}\leq R$ и $0\leq \theta _{i}<2\pi$.

Гиперболический закон косинусов позволяет измерить расстояние $d_{ij}$ между двумя точками $i$ и $j$,

$\cosh(\zeta d_{ij})=\cosh(\zeta r_{i})\cosh(\zeta r_{j})$$-\sinh(\zeta r_{i})\sinh(\zeta r_{j})\cos {\bigg (}\underbrace {\pi \!-\!{\bigg |}\pi -|\theta _{i}\!-\!\theta _{j}|{\bigg |}} _{\Delta }{\bigg )}.$

Угол $\Delta$ это (наименьший) угол между двумя векторы положения .

В простейшем случае ребро $(i,j)$ устанавливается тогда и только тогда, когда два узла находятся в пределах определенного радиуса окрестности .  $r$, $d_{ij}\leq r$, это соответствует порогу влияния.

Функция затухания связности

В общем случае связь будет установлена ​​с вероятностью, зависящей от расстояния $d_{ij}$. Функция затухания связности $\gamma (s):\mathbb {R} ^{+}\to [0,1]$ представляет вероятность назначения ребра паре узлов на расстоянии $s$. В этой структуре простой случай жесткого кода окрестности, такой как в случайных геометрических графах, называется функцией затухания усечения .

Генерация гиперболических геометрических графов

Криуков и др. описать, как генерировать гиперболические геометрические графы с равномерно случайным распределением узлов (а также обобщенные версии) на диске радиуса $R$ в $\mathbb {H} _{\zeta }^{2}$. Эти графики дают степенное распределение степеней узла. Угловая координата $\theta$ каждой точки/узла выбирается равномерно случайным образом из $[0,2\pi ]$, а функция плотности для радиальной координаты r выбирается согласно распределению вероятностей $\rho$:

$\rho (r)=\alpha {\frac {\sinh(\alpha r)}{\cosh(\alpha R)-1}}$

Параметр роста $\alpha >0$ контролирует распределение: Для $\alpha =\zeta$, распределение равномерно по $\mathbb {H} _{\zeta }^{2}$, для меньших значений узлы распределяются ближе к центру диска, а для больших значений - ближе к границе. В этой модели ребра между узлами $u$ и $v$ существовать тогда и только тогда, когда $d_{uv}<R$ или с вероятностью $\gamma (d_{uv})$ если используется более общая функция затухания связности. Средняя степень контролируется радиусом $R$ гиперболического диска. Можно показать, что для $\alpha /\zeta >1/2$ степени узла подчиняются степенному закону распределения с показателем степени $\gamma =1+2\alpha /\zeta$.

На изображении изображены случайно сгенерированные графики для разных значений $\alpha$ и $R$ в $\mathbb {H} _{1}^{2}$. Можно увидеть, как $\alpha$ влияет на распределение узлов и $R$ о связности графа. Для визуализации графика используется собственное представление, в котором переменные расстояния имеют истинные гиперболические значения, поэтому ребра представляют собой прямые линии.

Случайные гиперболические геометрические графы с N = 100 узлами каждый для разных значений альфа и R.

Генератор квадратичной сложности

Источник:

Наивный алгоритм генерации гиперболических геометрических графов распределяет узлы на гиперболическом диске, выбирая угловые и радиальные координаты каждой точки, выбираемые случайным образом. Затем для каждой пары узлов вставляется ребро с вероятностью значения функции затухания связности соответствующего расстояния. Псевдокод выглядит следующим образом:

$V=\{\},E=\{\}$
for $i\gets 0$ to $N-1$ do
    $\theta \gets U[0,2\pi ]$
    $r\gets {\frac {1}{\alpha }}{\text{acosh}}(1+(\cosh \alpha R-1)U[0,1])$
    $V=V\cup \{(r,\theta )\}$
for every pair  $(u,v)\in V\times V,u\neq v$ do
    if $U[0,1]\leq \gamma (d_{uv})$ then
        $E=E\cup \{(u,v)\}$
return $V,E$

$N$ количество узлов, которые нужно сгенерировать, распределение радиальной координаты по функции плотности вероятности $\rho$ достигается за счет использования выборки обратного преобразования . $U$обозначает равномерную выборку значения в заданном интервале. Поскольку алгоритм проверяет наличие ребер для всех пар узлов, время выполнения является квадратичным. Для приложений, где $N$ большой, это больше нежизнеспособно, и необходимы алгоритмы с субквадратичным временем выполнения.

Субквадратичное поколение

Чтобы избежать проверки ребер между каждой парой узлов, современные генераторы используют дополнительные структуры данных , которые разбивают граф на полосы. Визуализация этого показывает гиперболический график с границей полос, нарисованной оранжевым цветом. В этом случае разбиение производится по радиальной оси. Точки сохраняются отсортированными по их угловым координатам в соответствующем канале. Для каждой точки $u$, пределы его гиперболического круга радиуса $R$ может быть (пере)оценен и использоваться только для проверки границ для точек, лежащих в полосе, пересекающей круг. Кроме того, сортировку внутри каждой полосы можно использовать для дальнейшего сокращения количества точек для просмотра, рассматривая только точки, угловые координаты которых лежат в определенном диапазоне вокруг угловой координаты $u$ (этот диапазон также вычисляется путем завышения гиперболической окружности вокруг $u$).

Используя это и другие расширения алгоритма, временные сложности ${\mathcal {O}}(n\log \log n+m)$(где $n$ количество узлов и $m$ количество ребер) возможны с высокой вероятностью.

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

Выводы

Для $\zeta =1$ (Гауссова кривизна $K=-1$), ГГГ образуют ансамбль сетей, для которого возможно аналитически выразить распределение степеней в виде замкнутой формы для предельного случая большого числа узлов. Об этом стоит упомянуть, поскольку для многих ансамблей графов это неверно.

Приложения

HGG были предложены в качестве многообещающей модели для социальных сетей , где гиперболичность проявляется в конкуренции между сходством и популярностью человека.