WikiDer > Гиперболический геометрический граф - Википедия

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Компонент Резать Цикл Структура данных Край Петля Район Дорожка Вершина Список смежности / матрица Список заболеваемости / матрица Типы Двудольный Полный Режиссер Гипер Мульти Случайный Взвешенный
Метрики Алгоритмы
Центральность Степень Близость Близость PageRank Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия/СЭР
Списки Категории
Темы Программного обеспечения Сетевые ученые Категория: Теория сетей Категория: Теория графов
v т е

А гиперболический геометрический граф (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_ {я} leq R}$ и ${ Displaystyle 0 Leq theta _ {я} <2 pi}$.

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

${ Displaystyle сп ( зета d_ {ij}) = сп ( зета r_ {я}) сп ( зета 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 (я, 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}$ или с вероятностью ${ displaystyle gamma (d_ {uv})}$ если используется более общая функция спада связности. Средняя степень контролируется радиусом ${ displaystyle R}$ гиперболического диска. Можно показать, что для ${ Displaystyle альфа / zeta> 1/2}$ степени узлов подчиняются степенному распределению с показателем ${ Displaystyle гамма = 1 + 2 альфа / zeta}$.

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

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

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

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

${ Displaystyle V =  {}, E =  {}}$за ${ Displaystyle я  получает 0}$ к ${ displaystyle N-1}$ делать    ${ displaystyle  theta  получает U [0,2  pi]}$    ${ displaystyle r  получает { гидроразрыва {1} { alpha}} { text {acosh}} (1 + ( cosh  alpha R-1) U [0,1])}$    ${ Displaystyle В = В  чашка  {(г,  тета) }}$для каждой пары  ${ Displaystyle (и, v)  в V  раз V, и  neq v}$ делать    если ${ Displaystyle U [0,1]  Leq  gamma (d_ {uv})}$ тогда        ${ Displaystyle Е = Е  чашка  {(и, 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}} (п журнал журнал п + м)}$(куда ${ displaystyle n}$ количество узлов и ${ displaystyle m}$ количество ребер) возможны с большой вероятностью.^[7]

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

Результаты

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

Приложения

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

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