Пространственная сеть - Spatial network

А пространственная сеть (иногда также геометрический график) это график в которой вершины или же края находятся пространственные элементы связана с геометрический объекты, то есть узлы расположены в пространстве, оборудованном определенным метрика.^[1][2] Простейшая математическая реализация - это решетка или случайный геометрический граф, где узлы случайным образом распределены равномерно по двумерной плоскости; пара узлов подключена, если Евклидово расстояние меньше заданного радиуса окрестности. Транспортные и мобильные сети, Интернет, сети мобильной связи, электрические сети, социальные и контактные сети и биологические нейронные сети являются примерами, в которых основное пространство имеет значение, а граф топология сам по себе не содержит всей информации. Описание и понимание структуры, устойчивости и эволюции пространственных сетей имеет решающее значение для многих различных областей, от урбанизма до эпидемиологии.

Примеры

Городская пространственная сеть может быть построена путем абстрагирования перекрестков как узлов и улиц как звеньев, что называется, транспортная сеть. Пекинский трафик был изучен как динамическая сеть, и ее свойства перколяции оказались полезными для выявления систематических узких мест.^[3]

Можно подумать о «космической карте» как о негативном изображении стандартной карты с вырезанным на заднем фоне зданиями или стенами открытым пространством.^[4]

Описание пространственных сетей

Следующие аспекты являются некоторыми характеристиками для изучения пространственной сети:^[1]

• Планарные сети

Во многих приложениях, таких как железнодорожные, автомобильные и другие транспортные сети, предполагается, что сеть планарный. Планарные сети составляют важную группу пространственных сетей, но не все пространственные сети являются планарными. Действительно, пассажирские сети авиакомпаний - неплохой пример: все аэропорты мира связаны прямыми рейсами.

• Как он встроен в пространство

Есть примеры сетей, которые, кажется, не встроены в пространство «напрямую». Социальные сети, например, объединяют людей через дружеские отношения. Но в этом случае пространство вмешивается в тот факт, что вероятность соединения между двумя людьми обычно уменьшается с увеличением расстояния между ними.

• Мозаика Вороного

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

• Смешивание пространства и топологии

Рис. 1. Решетчатая сеть в двух измерениях. Шары - это узлы, а ребра, соединяющие соседние узлы, - это связи.

Рис. 2. Пространственно взаимозависимые решетчатые сети. Две квадратные решетки A и B, где в каждой решетке узел имеет два типа связей: связи связности в одном слое и связи зависимости между слоями. Каждый узел связан (с помощью каналов связи) со своими четырьмя ближайшими соседями в одной и той же решетке, и часть узлов в каждой сети имеет связи зависимости с другой сетью. Если узел выходит из строя в одной сети, его зависимый узел в другой сети также выйдет из строя, даже если он все еще подключен к своей сети через каналы связи.

Само исследование топологии узлов и ребер - еще один способ охарактеризовать сети. Распределение степень узлов часто рассматривается, что касается структуры ребер, полезно найти Минимальное остовное дерево, или обобщение, Дерево Штейнера и граф относительной окрестности.

Рис. 3: Пространственно встроенные мультиплексные сети. Узлы занимают правильные места в двумерной решетке, в то время как связи в каждом слое (синий и зеленый) имеют длины, которые экспоненциально распределены с характеристической длиной ζ = 3 и связаны случайным образом со степенью k = 4.

Решетчатые сети

Решетчатые сети (см. Рис. 1) являются полезными моделями для пространственных встроенных сетей. На этих структурах изучено множество физических явлений. Примеры включают модель Изинга для спонтанного намагничивания,^[5] диффузионные явления, моделируемые как случайные блуждания^[6]и перколяция.^[7] Недавно для моделирования устойчивости взаимозависимых инфраструктур, которые пространственно встроены, была введена и проанализирована модель взаимозависимых решетчатых сетей (см. Рис. 2).^[8].^[9] Модель пространственного мультиплексирования была представлена ​​Danziger et al.^[10] и был дополнительно проанализирован Vaknin et al.^[11] Модель см. На рис. 3. Было показано, что локальные атаки на эти две последние модели (показанные на рис. 2 и 3) выше критического радиуса приведут к каскадным сбоям и коллапсу системы.^[12] Перколяция в однослойной двухслойной структуре (как на рис.3) звеньев характерной длины ${\displaystyle \zeta }$ были обнаружены очень богатое поведение^[13]. В частности, поведение до линейных масштабов ${\displaystyle \zeta ^{3/2}}$ как в многомерных системах (среднее поле) на критическом пороге перколяции. Над ${\displaystyle \zeta ^{3/2}}$ система ведет себя как обычная 2-мерная система.

Пространственные модульные сети

Многие реальные инфраструктурные сети пространственно встроены, и их звенья имеют характеристическую длину, например, трубопроводы, линии электропередач или наземные транспортные линии не однородны, как на рис. 3, а скорее неоднородны. Например, плотность связей внутри городов значительно выше, чем между городами. Гросс и др.^[14] разработали и изучили аналогичную реалистичную неоднородную пространственную модульную модель с использованием теории перколяции, чтобы лучше понять влияние неоднородности на такие сети. Модель предполагает, что внутри города есть много линий, соединяющих разные места, в то время как длинные линии между городами разрежены и обычно напрямую соединяют только несколько ближайших соседних городов в двухмерной плоскости, см. Рис. 4. Было обнаружено, что этот неоднородный Модель испытывает два различных перколяционных перехода: один, когда города разъединяются друг от друга, а второй, когда каждый город распадается. Это контрастирует с однородной моделью, рис. 3, где обнаружен единственный переход.

Вероятность и пространственные сети

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

• В Пуассоновский линейный процесс
• Стохастическая геометрия: Граф Эрдеша – Реньи
• Теория перколяции

Подход из теории космического синтаксиса

Другое определение пространственной сети происходит из теории синтаксис пробела. Общеизвестно, что сложно решить, каким должен быть пространственный элемент в сложных пространствах, включающих большие открытые площадки или множество взаимосвязанных путей. Создатели космического синтаксиса Билл Хиллиер и Жюльен Хэнсон использовали осевые линии и выпуклые пространства как пространственные элементы. Грубо говоря, осевая линия - это «самая длинная линия обзора и доступа» через открытое пространство, а выпуклое пространство - это «максимальный выпуклый многоугольник», который можно нарисовать в открытом пространстве. Каждый из этих элементов определяется геометрией локальной границы в различных областях космической карты. Разложение пространственной карты на полный набор пересекающихся осевых линий или перекрывающихся выпуклых пространств дает осевую карту или перекрывающуюся выпуклую карту соответственно. Существуют алгоритмические определения этих карт, и это позволяет выполнять сопоставление пространственной карты произвольной формы с сетью, поддающейся графической математике, относительно четко определенным образом. Осевые карты используются для анализа городские сети, где система обычно состоит из линейных сегментов, тогда как выпуклые карты чаще используются для анализа планы строительства где пространственные узоры часто более выпукло артикулированы, однако как выпуклые, так и аксиальные карты могут использоваться в любой ситуации.

В настоящее время в сообществе космического синтаксиса наблюдается тенденция к лучшей интеграции с географические информационные системы (ГИС) и большая часть программного обеспечения они обеспечивают взаимосвязь с коммерчески доступными системами ГИС.

История

Хотя сети и графы уже долгое время были предметом многих исследований в математика, физика, математическая социология,Информатика пространственные сети интенсивно изучались в 1970-х годах в количественной географии. Объектами изучения географии являются, помимо прочего, местоположения, виды деятельности и потоки людей, а также сети, развивающиеся во времени и пространстве.^[15] Большинство важных проблем, таких как расположение узлов сети, эволюция транспортных сетей и их взаимодействие с населением и плотностью активности, были рассмотрены в этих ранних исследованиях. С другой стороны, многие важные моменты все еще остаются неясными, отчасти потому, что в то время не хватало наборов данных о больших сетях и более крупных компьютерных возможностях. В последнее время пространственные сети стали предметом исследований в Статистика, чтобы связать вероятности и случайные процессы с сетями в реальном мире.^[16]

Смотрите также

• Гиперболический геометрический граф
• Программное обеспечение для анализа пространственной сети
• Каскадный отказ
• Комплексная сеть
• Планарные графики
• Теория перколяции
• Случайные графики
• Топологическая теория графов
• Химический график
• Взаимозависимые сети

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

1. Бартелеми, М. (2011). «Пространственные сети». Отчеты по физике. 499: 1–101. arXiv:1010.0302. Bibcode:2011ФР ... 499 .... 1Б. Дои:10.1016 / j.physrep.2010.11.002.
2. М. Бартелеми, "Морфогенез пространственных сетей", Springer (2018).
3. Li, D .; Fu, B .; Wang, Y .; Lu, G .; Березин, Ю .; Stanley, H.E .; Хавлин, С. (2015). «Перколяционный переход в динамической сети трафика с развивающимися критическими узкими местами». PNAS. 112: 669. Bibcode:2015ПНАС..112..669Л. Дои:10.1073 / pnas.1419185112. ЧВК  4311803. PMID  25552558.
4. Хиллер Б., Хэнсон Дж., 1984, Социальная логика пространства (Cambridge University Press, Кембридж, Великобритания).
5. Маккой, Барри М .; Ву, Тай Цунь (1968). "Теория двумерной модели Изинга со случайными примесями. I. Термодинамика". Физический обзор. 176 (2): 631–643. Bibcode:1968ПхРв..176..631М. Дои:10.1103 / PhysRev.176.631. ISSN  0031-899X.
6. Масоливер, Жауме; Монтеро, Микель; Вайс, Джордж Х. (2003). «Модель случайного блуждания в непрерывном времени для финансовых распределений». Физический обзор E. 67 (2): 021112. arXiv:cond-mat / 0210513. Bibcode:2003PhRvE..67b1112M. Дои:10.1103 / PhysRevE.67.021112. ISSN  1063-651X. PMID  12636658.
7. Бунде, Армин; Хавлин, Шломо (1996). «Фракталы и неупорядоченные системы». Дои:10.1007/978-3-642-84868-1.
8. Ли, Вэй; Башан, Амир; Булдырев, Сергей В .; Стэнли, Х. Юджин; Хавлин, Шломо (2012). «Каскадные отказы во взаимозависимых решетчатых сетях: критическая роль длины связей зависимости». Письма с физическими проверками. 108 (22): 228702. arXiv:1206.0224. Bibcode:2012PhRvL.108v8702L. Дои:10.1103 / PhysRevLett.108.228702. ISSN  0031-9007. PMID  23003664.
9. Башан, Амир; Березин, Йехиель; Булдырев, Сергей В .; Хавлин, Шломо (2013). «Крайняя уязвимость взаимозависимых пространственно встроенных сетей». Природа Физика. 9 (10): 667–672. arXiv:1206.2062. Bibcode:2013НатФ ... 9..667Б. Дои:10.1038 / nphys2727. ISSN  1745-2473.
10. Данцигер, Майкл М .; Шехтман, Луи М .; Березин, Йехиель; Хавлин, Шломо (2016). «Влияние пространственности на мультиплексные сети». EPL. 115 (3): 36002. arXiv:1505.01688. Bibcode:2016EL .... 11536002D. Дои:10.1209/0295-5075/115/36002. ISSN  0295-5075.
11. Вакнин, Дана; Данцигер, Майкл М; Хавлин, Шломо (2017). «Распространение локализованных атак в пространственных мультиплексных сетях». Новый журнал физики. 19 (7): 073037. arXiv:1704.00267. Bibcode:2017NJPh ... 19g3037V. Дои:10.1088 / 1367-2630 / aa7b09. ISSN  1367-2630.
12. Локализованные атаки на пространственно встроенные сети с зависимостями Y. Березин, А.Башан, М.М. Данцигер, Д. Ли, С. Хэвлин, Научные отчеты 5, 8934 (2015)
13. Иван Бонамасса, Бная ​​Гросс, Майкл М. Данцигер, Шломо Хавлин (2019). «Критическое растяжение режимов среднего поля в пространственных сетях». Phys. Rev. Lett. 123 (8): 088301. arXiv:1704.00268. Дои:10.1103 / PhysRevLett.123.088301.
14. Бная Гросс, Дана Вакнин, Сергей Булдырев, Шломо Хавлин (2020). «Два перехода в пространственных модульных сетях». Новый журнал физики. 22: 053002. Дои:10.1088 / 1367-2630 / ab8263. Текст был скопирован из этого источника, который доступен под Международная лицензия Creative Commons Attribution 4.0.
15. П. Хаггетт и Р.Дж. Чорли. Сетевой анализ в геогео-рафи. Эдвард Арнольд, Лондон, 1969 год.
16. http://www.stat.berkeley.edu/~aldous/206-SNET/index.html

• Бандельт, Ханс-Юрген; Чепой, Виктор (2008). «Метрическая теория графов и геометрия: обзор» (PDF). Contemp. Математика.: появиться. Архивировано из оригинал (PDF) 25 ноября 2006 г.
• Пах, Янош; и другие. (2004). К теории геометрических графов. Современная математика, вып. 342, Американское математическое общество.

• Писанский, Томаж; Рандич, Милан (2000). «Мосты между геометрией и теорией графов». В Горини, К.А. (ред.). Геометрия в действии: статьи по прикладной геометрии. Вашингтон, округ Колумбия: Математическая ассоциация Америки. С. 174–194. Архивировано из оригинал на 2007-09-27.