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

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

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

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

В гиперболический закон косинусов позволяет измерить расстояние ${\displaystyle d_{ij}}$ между двумя точками ${\displaystyle i}$ и ${\displaystyle j}$,^[2]

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

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

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

Функция распада подключения

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

Создание гиперболических геометрических графов

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

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

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

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

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

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

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

${\displaystyle V=\{\},E=\{\}}$за ${\displaystyle i\gets 0}$ к ${\displaystyle N-1}$ делать    ${\displaystyle \theta \gets U[0,2\pi ]}$    ${\displaystyle r\gets {\frac {1}{\alpha }}{\text{acosh}}(1+(\cosh \alpha R-1)U[0,1])}$    ${\displaystyle V=V\cup \{(r,\theta )\}}$для каждой пары  ${\displaystyle (u,v)\in V\times V,u\neq v}$ делать    если ${\displaystyle U[0,1]\leq \gamma (d_{uv})}$ тогда        ${\displaystyle E=E\cup \{(u,v)\}}$возвращаться ${\displaystyle V,E}$

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

Субквадратичная генерация

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

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

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

Результаты

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

Приложения

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

Рекомендации

1. Бартелеми, Марк (2011). «Пространственные сети». Отчеты по физике. 499 (1–3): 1–101. arXiv:1010.0302. Bibcode:2011ФР ... 499 .... 1Б. Дои:10.1016 / j.physrep.2010.11.002.
2. Криуков Дмитрий; Пападопулос, Фрагкискос; Кицак, Максим; Вахдат, Амин; Богуна, Мариан (2010). «Гиперболическая геометрия сложных сетей». Физический обзор E. 82 (3): 036106. arXiv:1006.5169. Bibcode:2010PhRvE..82c6106K. Дои:10.1103 / PhysRevE.82.036106. PMID  21230138.
3. Barnett, L .; Ди Паоло, Э .; Буллок, С. (2007). «Пространственно вложенные случайные сети». Физический обзор E. 76 (5): 056115. Bibcode:2007PhRvE..76e6115B. Дои:10.1103 / PhysRevE.76.056115.
4. Криуков Дмитрий; Орсини, Кьяра; Альдекоа, Родриго (17 марта 2015 г.). «Генератор гиперболических графов». Компьютерная физика Коммуникации. 196: 492–496. arXiv:1503.05180. Bibcode:2015CoPhC.196..492A. Дои:10.1016 / j.cpc.2015.05.028.
5. фон Лооз, Мориц; Мейерхенке, Хеннинг; Пруткин, Роман (2015). Эльбассиони, Халед; Макино, Кадзухиса (ред.). «Генерация случайных гиперболических графов в субквадратичном времени». Алгоритмы и вычисления. Конспект лекций по информатике. Springer Berlin Heidelberg. 9472: 467–478. Дои:10.1007/978-3-662-48971-0_40. ISBN  9783662489710.
6. Мейерхенке, Хеннинг; Лауэ, Сорен; Оздайи, Мустафа; фон Лооз, Мориц (30.06.2016). «Более быстрое создание массивных сложных сетей с гиперболической геометрией на практике». arXiv:1606.09481v1. Bibcode:2016arXiv160609481V.
7. Пенсчук, Мануэль (2017). «Создание практических случайных гиперболических графов в почти линейное время и с сублинейной памятью». Schloss Dagstuhl - Leibniz-Zentrum für Informatik GMBH, Вадерн / Саарбрюккен, Германия. Leibniz International Proceedings in Informatics (LIPIcs). 75: 26:1–26:21. Дои:10.4230 / lipics.sea.2017.26. ISBN  9783959770361.
8. Пападопулос, Фрагкискос; Кицак, Максим; Серрано, М. Анхелес; Богуна, Мариан; Криуков, Дмитрий (12 сентября 2012 г.). «Популярность против сходства в растущих сетях». Природа. 489 (7417): 537–540. arXiv:1106.0286. Bibcode:2012Натура.489..537P. Дои:10.1038 / природа11459. PMID  22972194.