Просторова мережа (іноді також геометричний граф) — це граф, у якому вершини або ребра є просторовими елементами, пов'язаними з геометричними об'єктами, тобто вузли розташовані в просторі, оснащеному певною метрикоюM. Barthelemy, "Morphogenesis of Spatial Networks", Springer (2018). Найпростішою математичною реалізацією просторової мережі є решітка або випадковий геометричний граф (див. малюнок праворуч), де вузли рівномірно розподілені випадковим чином по двовимірній площині; пара вузлів з'єднана, якщо евклідова відстань менша за заданий радіус околиці.

Транспортні та мобільні мережі, Інтернет, мережі мобільного зв'язку, енергетичні мережі, соціальні та контактні мережі, а також біологічні нейронні мережі — все це приклади, де базовий простір є релевантним, і де сама топологія графа не містить усієї інформації. Характеристика та розуміння структури, стійкості та еволюції просторових мереж має вирішальне значення для багатьох різних галузей, від урбанізму до епідеміології.

Приклади Міську просторову мережу можна побудувати, абстрагуючи перехрестя як вузли, а вулиці як сполучні ланки, що називається транспортною мережею.

Можна уявити «космічну карту» як негатив стандартної карти, де відкритий простір вирізаний з фонових будівель або стінHillier B, Hanson J, 1984, The social logic of space (Cambridge University Press, Cambridge, UK)..

Характеристика просторових мереж Наступні аспекти є деякими характеристиками для дослідження просторової мережіM. Barthelemy, "Morphogenesis of Spatial Networks", Springer (2018):

Планарні мережі

У багатьох застосуваннях, таких як залізничні мережі, автомобільні дороги та інші транспортні системи, мережа вважається планарною. Планарні мережі становлять важливу категорію просторових мереж, однак не всі просторові мережі є планарними. Наприклад, пасажирські мережі авіакомпаній є непланарним типом просторових мереж, оскільки багато великих аеропортів світу з’єднані між собою прямими авіарейсами.

Те, як вона вбудована в простір

Існують приклади мереж, які, на перший погляд, не є «безпосередньо» вбудованими у простір. Соціальні мережі, наприклад, пов’язують людей через відносини дружби. Проте у цьому випадку просторовий чинник проявляється в тому, що ймовірність виникнення зв’язку між двома людьми зазвичай зменшується зі збільшенням відстані між ними.

Теселяція Вороного

Просторову мережу можна представити діаграмою Вороного, яка є способом поділу простору на певну кількість областей. Подвійний графік для діаграми Вороного відповідає тріангуляції Делоне для того ж набору точок. Теселяції Вороного цікаві для просторових мереж тим, що вони забезпечують природну модель представлення, з якою можна порівняти мережу реального світу.

Змішування простору та топології

Дослідження топології вузлів і ребер – це ще один спосіб характеристики мереж. Часто розглядається розподіл степеня вузлів, а щодо структури ребер корисно знайти мінімальне охоплююче дерево або узагальнення – дерево Штейнера та граф відносних околів.

Ймовірнісні та просторові мережі У «реальному» світі багато аспектів мереж не є детермінованими — випадковість відіграє важливу роль. Наприклад, виникнення нових зв’язків, що відображають дружні стосунки в соціальних мережах, певною мірою має випадковий характер. Моделювання просторових мереж із урахуванням стохастичних процесів є послідовним підходом. У багатьох випадках для апроксимації наборів даних просторових мереж використовують просторовий процес Пуассона. Інші стохастичні аспекти, що становлять інтерес:

Процес лінії Пуассона Стохастична геометрія: графік Ердеша–Реньї Теорія перколяції

Підхід з теорії просторового синтаксису Інше визначення просторової мережі походить із теорії просторового синтаксису. Однією з основних проблем є визначення просторового елемента у складних просторах, що включають великі відкриті ділянки або велику кількість взаємопов’язаних шляхів. Засновники просторового синтаксису Білл Хілльєр і Жульєн Хансон використовують осьові лінії та опуклі простори як просторові елементи. Умовно осьова лінія визначається як «найдовша лінія огляду та доступу» через відкритий простір, а опуклий простір — як «максимальний опуклий багатокутник», який можна побудувати у відкритому просторі. Кожен із цих елементів визначається геометрією локальних меж у різних ділянках просторової карти. Розкладання просторової карти на повний набір пересічних осьових ліній або перекривних опуклих просторів відповідно створює осьову карту або карту опуклих просторів. Існують алгоритмічні методи визначення таких карт, що дозволяє перетворювати просторову карту довільної форми на мережу, придатну для аналізу за допомогою математичного апарату теорії графів, у чітко визначений спосіб. Осьові карти використовуються для аналізу міських мереж, де система зазвичай складається з лінійних сегментів, тоді як опуклі карти частіше використовуються для аналізу планів забудови, де просторові схеми часто більш опукло виражені, проте в будь-якій ситуації можна використовувати як опуклі, так і осьові карти.

Наразі у спільноті розробників просторового синтаксису спостерігається тенденція до кращої інтеграції з геоінформаційними системами (ГІС), і значна частина програмного забезпечення, яке вони створюють, взаємодіє з комерційно доступними ГІС-системами.

Історія Хоча мережі та графи вже давно були предметом багатьох досліджень у математиці, фізиці, математичній соціології, інформатиці, просторові мережі також інтенсивно вивчалися протягом 1970-х років у кількісній географії. Об'єктами досліджень у географії є, серед іншого, місця розташування, діяльність та потоки людей, а також мережі, що розвиваються в часі та просторіP. Haggett and R.J. Chorley. Network analysis in geography. Edward Arnold, London, 1969.. Більшість важливих проблем, таких як розташування вузлів мережі, еволюція транспортних мереж та їх взаємодія з населенням та щільністю активності, розглядаються в цих ранніх дослідженнях. З іншого боку, багато важливих моментів залишаються незрозумілими, частково тому, що на той час бракувало наборів даних великих мереж та потужніших комп'ютерів. Останнім часом просторові мережі стали предметом досліджень у статистиці, щоб пов'язати ймовірності та стохастичні процеси з мережами в реальному світі.

Див. також

Складні мережі Планарні графи Теорія протікання Випадковий граф Топологічна теорія графів Світ тісний (граф) Молекулярний граф Взаємозалежні мережі

Посилання

Джерела