Гіперболічний геометричний граф (ГГГ) або гіперболічна геометрична мережа (ГГМ) – це спеціальний тип просторової мережі, де:
Латентні координати вузлів розкидані відповідно до функції щільності ймовірності в гіперболічний простір постійної негативної кривини; Ребро між двома вузлами присутнє, якщо вони близькі відповідно до функції метрики. Зазвичай це або ступінчаста функція Гевісайда, що призводить до детермінованих зв'язків між вершинами, ближчими за певну порогову відстань, або спадаюча функція гіперболічної відстані, що дає ймовірність зв'язку.
ГГГ узагальнює випадковий геометричний граф (ВГГ), простір вкладення якого є евклідовим.
Математичне формулювання Математично, ГГГ – це граф з множиною вершин V ( потужність ) та множину ребер E, побудовану шляхом розгляду вузлів як точок, розміщених на двовимірному гіперболічному просторі постійної від'ємної гауссової кривини, і радіус відсікання , тобто радіус диска Пуанкаре, який можна візуалізувати за допомогою моделі гіперболоїда. Кожна точка має гіперболічні полярні координати з і .
Гіперболічний закон косинусів дозволяє вимірювати відстань між двома точками і ,
Кут — (найменший) кут між двома векторами положення.
У найпростішому випадку, ребро встановлюється тоді і тільки тоді, коли два вузли знаходяться в межах певного радіуса околиці , , це відповідає порогу впливу.
Функція розпаду зв'язності Загалом, зв'язок буде встановлено з ймовірністю, яка залежить від відстані Функція розпаду зв'язності представляє ймовірність призначення ребра парі вузлів на відстані .
У цій концепції простий випадок жорстко заданої околиці, як у випадкових геометричних графах, називається функцією розпаду внаслідок усічення.
Генерація гіперболічних геометричних графів Крюков та ін. описують, як генерувати гіперболічні геометричні графи з рівномірно випадковим розподілом вузлів (а також узагальнені версії) на диску радіуса в . Ці графи дають степеневий розподіл для градусів вузла.
Кутова координата кожної точки/вузла вибирається рівномірно випадковим чином з , тоді як функція густини для радіальної координати r вибирається відповідно до розподілу ймовірностей :
Параметр зростання визначає характер розподілу вузлів. При розподіл є рівномірним у ; для менших значень α вузли розташовуються ближче до центра диска, а для більших — ближче до його межі. У цій моделі ребро між вузлами та існує тоді й лише тоді, коли , або з імовірністю , якщо використовується більш загальна функція спаду ймовірності зв’язності. Середній степінь вузлів визначається радіусом R гіперболічного диска. Можна показати, що при розподіл степенів вузлів підпорядковується степеневому закону з показником .
Зображення зображує випадково згенеровані графи для різних значень і в Видно, як впливає на розподіл вузлів і на зв'язність графа. Для візуалізації графа використовується рідне представлення, де змінні відстані мають свої справжні гіперболічні значення, тому ребра є прямими лініями.
Генератор квадратичної складності Джерело:
Наївний алгоритм генерації гіперболічних геометричних графів розміщує вузли на гіперболічному диску, випадковим чином вибираючи кутову та радіальну координати кожного вузла. Після цього для кожної пари вузлів додається ребро з імовірністю, що дорівнює значенню функції спаду зв’язності, обчисленої для відстані між цими вузлами. Псевдокод алгоритму має такий вигляд:
for to do
for every pair do if then
return це кількість вузлів, які необхідно згенерувати. Розподіл радіальної координати відповідно до функції густини ймовірності реалізується за допомогою методу оберненого перетворення. Позначення означає рівномірну вибірку значення із заданого інтервалу. Оскільки алгоритм перевіряє наявність ребра для кожної пари вузлів, його часову складність є квадратичною. Для застосувань, у яких є великим, такий підхід стає непрактичним, тому виникає потреба в алгоритмах із субквадратичною часовою складністю.
Субквадратична генерація Щоб уникнути перевірки ребер між кожною парою вузлів, сучасні генератори використовують додаткові структури даних, які розбивають граф на смуги. Візуалізація цього підходу демонструє гіперболічний граф із межею смуг, позначеною помаранчевим кольором. У цьому випадку розбиття виконується вздовж радіальної осі. Точки зберігаються у відповідних смугах, відсортованими за кутовою координатою. Для кожної точки межі її гіперболічного кола радіуса можна наближено оцінити та використовувати для перевірки наявності ребер лише з тими точками, що розташовані у смугах, які перетинає це коло. Крім того, сортування точок у межах кожної смуги дає змогу додатково зменшити кількість перевірок, розглядаючи лише ті точки, кутові координати яких лежать у певному діапазоні навколо кутової координати точки u.
Межі цього діапазону також визначаються на основі наближеної оцінки гіперболічного кола навколо точки .
Використовуючи це та інші розширення алгоритму, часова складність (де – кількість вузлів, а кількість ребер) можливі з високою ймовірністю.
Результати Для (Гаусовська кривина ), ГГГ утворюють ансамбль мереж, для яких можна аналітично виразити розподіл ступенів у замкнутій формі для граничного випадку великої кількості вузлів. Це варто зазначити, оскільки це невірно для багатьох ансамблів графів.
Застосування ГГГ були запропоновані як перспективна модель для соціальних мереж, де гіперболічність проявляється через конкуренцію між схожістю та популярністю особи.
Посилання