Комплексная сеть - Complex network

«Сложные сети» перенаправляются сюда. Для компании см. Комплексные сети.
Сетевая наука
Internet_map_1024.jpg
Типы сетей
Графики
Функции
Типы
Модели
Топология
Динамика
  • Списки
  • Категории
  • Категория: Теория сетей
  • Категория: Теория графов

В контексте теория сети, а сложная сеть это график (сеть) с нетривиальным топологический функции - функции, которых нет в простых сетях, таких как решетки или же случайные графы но часто встречаются в сетях, представляющих реальные системы. Изучение сложных сетей - молодая и активная область научных исследований.[1][2][3] (с 2000 г.) во многом вдохновленные эмпирическими выводами реальных сетей, таких как компьютерная сеть, биологические сети, технологические сети, сети мозга, климатические сети и социальные сети.

Определение

Наиболее Социальное, биологический, и технологические сети демонстрируют существенные нетривиальные топологические особенности с паттернами связи между их элементами, которые не являются ни чисто регулярными, ни чисто случайными. К таким особенностям можно отнести тяжелый хвост в распределение степеней, высота коэффициент кластеризации, ассортативность или дизассортативность между вершинами, структура сообщества, и иерархическая структура. В случае направленных сетей эти функции также включают взаимность, профиль значимости триады и другие особенности. Напротив, многие математические модели сетей, которые изучались в прошлом, такие как решетки и случайные графы, не показывайте эти функции. Самые сложные структуры могут быть реализованы сетями со средним числом взаимодействий.[4] Это соответствует тому, что максимальная информативность (энтропия ) получается для средних вероятностей.

Два хорошо известных и хорошо изученных класса сложных сетей: безмасштабные сети[5] и сети малого мира,[6][7] чье открытие и определение являются каноническими тематическими исследованиями в данной области. Оба характеризуются определенными структурными особенностями -сила закона распределение степеней для первого и короткого пути и высокого кластеризация для последнего. Однако, поскольку изучение сложных сетей продолжает расти в важности и популярности, многие другие аспекты сетевых структур также привлекают внимание.

В последнее время изучение сложных сетей было расширено до сетей сетей.[8] Если эти сети взаимозависимый, они становятся значительно более уязвимыми, чем отдельные сети для случайных отказов и целевых атак, и демонстрируют каскадные отказы и перколяционные переходы первого порядка.[9][10]

Кроме того, было изучено коллективное поведение сети при отказе и восстановлении узлов.[11] Было обнаружено, что такая сеть может иметь спонтанные отказы и самопроизвольные восстановления.

Эта область продолжает развиваться быстрыми темпами и объединила исследователей из многих областей, включая математика, физика, электроэнергетические системы,[12] биология,[13] климат,[14] Информатика, социология, эпидемиология,[15] и другие.[16] Идеи и инструменты сетевой науки и инженерии были применены для анализа метаболических и генетических регуляторных сетей; изучение стабильности и устойчивости экосистемы;[17] клиническая наука;[18] моделирование и проектирование масштабируемых сетей связи, таких как создание и визуализация сложных беспроводных сетей;[19] разработка стратегий вакцинации для борьбы с болезнями; [20][21]и широкий круг других практических вопросов. Исследования сетей регулярно публикуются в наиболее заметных научных журналах и получают активное финансирование во многих странах. Сетевая теория недавно оказалась полезной для выявления узких мест в городском движении.[22] Наука о сетях является темой многих конференций в самых разных областях и является предметом многочисленных книг как для неспециалистов, так и для экспертов.

Безмасштабные сети

Основная статья: Безмасштабные сети
Рис. 1: Пример сложной безмасштабной сети.

Сеть называется безмасштабируемой[5][23] если его распределение по степени, то есть вероятность того, что узел, выбранный равномерно случайным образом, имеет определенное количество связей (степень), следует математической функции, называемой сила закона. Из степенного закона следует, что распределение степеней этих сетей не имеет характерного масштаба. Напротив, сети с одним четко определенным масштабом чем-то похожи на решетку тем, что каждый узел имеет (примерно) одинаковую степень. Примеры сетей с единой шкалой включают Случайный граф Эрдеша – Реньи (ER), случайные регулярные графы, правильные решетки, и гиперкубы. Некоторые модели растущих сетей, которые производят масштабно-инвариантные распределения степеней, являются Модель Барабаши – Альберта и фитнес-модель. В сети с безмасштабным распределением степеней некоторые вершины имеют степень, на несколько порядков превышающую среднюю - эти вершины часто называют «концентраторами», хотя этот язык вводит в заблуждение, поскольку по определению не существует внутреннего порога. выше которого узел можно рассматривать как концентратор. Если бы был такой порог, сеть не была бы безмасштабируемой.

Интерес к безмасштабным сетям возник в конце 1990-х годов с сообщений об открытиях степенного распределения степеней в реальных сетях, таких как Всемирная паутина, сеть Автономные системы (AS), некоторые сети Интернет-маршрутизаторов, сети взаимодействия с белками, сети электронной почты и т. Д. Большинство из этих заявленных «степенных законов» терпят неудачу при тщательном статистическом тестировании, но более общая идея распределений степеней с тяжелыми хвостами, которые многие этих сетей действительно проявляют (до того, как возникнут эффекты конечного размера) - сильно отличаются от того, что можно было бы ожидать, если бы ребра существовали независимо и случайным образом (т. е. если бы они следовали распределение Пуассона ). Есть много разных способов построить сеть со степенным распределением степеней. В Йольский процесс является каноническим порождающим процессом для степенных законов и известен с 1925 года. Однако он известен под многими другими названиями из-за его частого переосмысления, например, принцип Гибрата от Герберт А. Саймон, то Эффект Мэтью, совокупное преимущество и, преференциальная привязанность к Барабаши и Альберта для степенного распределения степеней. Недавно, Гиперболические геометрические графики были предложены как еще один способ построения безмасштабных сетей.

Некоторые сети со степенным распределением степеней (и некоторые другие типы структур) могут быть очень устойчивы к случайному удалению вершин, то есть подавляющее большинство вершин остаются соединенными вместе в гигантском компоненте.[24] Такие сети также могут быть весьма чувствительны к целевым атакам, направленным на быстрое разрушение сети. Когда граф является равномерно случайным, за исключением распределения степеней, эти критические вершины имеют наивысшую степень и, таким образом, участвуют в распространении болезней (естественных и искусственных) в социальных и коммуникационных сетях, а также в распространении причуд. (оба моделируются просачивание или же ветвящийся процесс ). В то время как случайные графы (ER) имеют среднее расстояние порядка log N[6] между узлами, где N - количество узлов, граф без масштабирования может иметь расстояние log log N. Такие графы называются сетями сверхмалого мира.[25]

Сети малого мира

Основная статья: Сеть малого мира

Сеть называется сетью малого мира[6] по аналогии с феномен маленького мира (широко известный как шесть ступеней расставания ). Гипотеза маленького мира, которую впервые описал венгерский писатель Фриджес Каринти в 1929 г. и испытано экспериментально Стэнли Милгрэм (1967), заключается в том, что два произвольных человека связаны только шестью степенями разделения, то есть диаметр соответствующего графа социальных связей не намного больше шести. В 1998 г. Дункан Дж. Уоттс и Стивен Строгац опубликовал первую модель сети малого мира, которая с помощью одного параметра плавно интерполирует между случайным графом и решеткой.[6] Их модель продемонстрировала, что при добавлении лишь небольшого количества дальних связей обычный граф, диаметр которого пропорционален размеру сети, может быть преобразован в «маленький мир», в котором среднее количество ребра между любыми двумя вершинами очень малы (математически они должны расти как логарифм размера сети), в то время как коэффициент кластеризации остается большим. Известно, что множество абстрактных графов демонстрируют свойство маленького мира, например случайные графы и безмасштабные сети. Кроме того, сети реального мира, такие как Всемирная паутина и метаболическая сеть также демонстрируют это свойство.

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

Пространственные сети

Многие реальные сети встроены в космос. Примеры включают транспортные и другие инфраструктурные сети, нейронные сети мозга. Было разработано несколько моделей пространственных сетей.[26][27]

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

Рис. 2: Иллюстрация модели. Гетерогенная пространственная модульная модель представляет собой структуру сети внутри городов и между городами. Внутри города легко добраться из одного места в другое (зеленые ссылки), например, сеть Эрдеша – Реньи, имеющая случайную подобную структуру, при перемещении из одного города в другой обычно возможно между соседними городами, имеющими пространственную структуру (синие ссылки).

Модель пространственно модульных сетей была разработана Гроссом и др.[28] Модель описывает, например, инфраструктуры в стране, где сообщества (модули) представляют собой города со многими связями, расположенные в двухмерном пространстве. Связи между сообществами (городами) меньше и обычно с ближайшими соседями (см. Рис. 2).

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

Книги

  • Б. С. Манодж, Абхишек Чакраборти и Рахул Сингх, Сложные сети: перспективы создания сетей и обработки сигналов, Пирсон, Нью-Йорк, США, февраль 2018 г. ISBN  978-0134786995
  • С.Н. Дороговцев, Ю.Ф.Ф. Мендес, Эволюция сетей: от биологических сетей к Интернету и WWW, Oxford University Press, 2003 г., ISBN  0-19-851590-1
  • Дункан Дж. Уоттс, Шесть степеней: наука соединенного века, W. W. Norton & Company, 2003 г., ISBN  0-393-04142-5
  • Дункан Дж. Уоттс, Маленькие миры: динамика сетей между порядком и случайностью, Princeton University Press, 2003 г., ISBN  0-691-11704-7
  • Альберт-Ласло Барабаши, Связано: как все связано со всем остальным, 2004, ISBN  0-452-28439-2
  • Ален Барра, Марк Бартелеми, Алессандро Веспиньяни, Динамические процессы в сложных сетях, Cambridge University Press, 2008 г., ISBN  978-0-521-87950-7
  • Стефан Борнхольдт (редактор) и Хайнц Георг Шустер (редактор), Справочник по графам и сетям: от генома к Интернету, 2003, ISBN  3-527-40336-1
  • Гвидо Кальдарелли, Безмасштабные сети, Oxford University Press, 2007 г., ISBN  978-0-19-921151-7
  • Гвидо Кальдарелли, Микеле Катандзаро, Сети: очень краткое введение Oxford University Press, 2012 г., ISBN  978-0-19-958807-7
  • Э. Эстрада, "Структура сложных сетей: теория и приложения", Oxford University Press, 2011, ISBN  978-0-199-59175-6
  • Реувен Коэн и Шломо Хэвлин, Сложные сети: структура, надежность и функции, Cambridge University Press, 2010 г., ISBN  978-0-521-84156-6
  • Марк Ньюман, Сети: введение, Oxford University Press, 2010 г., ISBN  978-0-19-920665-0
  • Марк Ньюман, Альберт-Ласло Барабаши и Дункан Дж. Уоттс, Структура и динамика сетей, Princeton University Press, Принстон, 2006 г., ISBN  978-0-691-11357-9
  • Р. Пастор-Саторрас и А. Веспиньяни, Эволюция и структура Интернета: подход статистической физики, Cambridge University Press, 2004 г., ISBN  0-521-82698-5
  • Т. Льюис, Network Science, Wiley 2009,
  • Нилой Гангули (редактор), Андреас Дойч (редактор) и Анимеш Мукерджи (редактор), Применение динамики сложных сетей в биологии, информатике и социальных науках, 2009, ISBN  978-0-8176-4750-6
  • Вито Латора, Винченцо Никосия, Джованни Руссо, Сложные сети: принципы, методы и приложения, Издательство Кембриджского университета, 2017 г. ISBN  978-1107103184

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

  1. ^ Р. Альберт, А.-Л. Барабаши (2002). «Статистическая механика сложных сетей». Обзоры современной физики. 74 (1): 47–49. arXiv:cond-mat / 0106096. Bibcode:2002РвМП ... 74 ... 47А. Дои:10.1103 / RevModPhys.74.47. S2CID  60545.
  2. ^ Марк Ньюман (2010). «Сети: Введение». Oxford University Press. ISBN  978-0-19-920665-0.
  3. ^ Реувен Коэн и Шломо Хэвлин (2010). «Сложные сети: структура, надежность и функции». Издательство Кембриджского университета. ISBN  978-0-521-84156-6.
  4. ^ Т. Вильгельм, Дж. Ким (2008). «Что такое сложный граф?». Physica A. 387 (11): 2637–2652. Bibcode:2008PhyA..387.2637K. Дои:10.1016 / j.physa.2008.01.015.
  5. ^ а б А. Барабаши, Э. Бонабо (2003). «Безмасштабные сети». Scientific American. 288 (5): 50–59. Дои:10.1038 / scientificamerican0503-60. PMID  12701331.
  6. ^ а б c d С. Х. Строгац, Д. Дж. Уоттс (1998). «Коллективная динамика сетей« маленького мира »». Природа. 393 (6684): 440–442. Bibcode:1998 Натур.393..440Вт. Дои:10.1038/30918. PMID  9623998. S2CID  4429113.
  7. ^ ОН. Стэнли, Л.А.Н. Амарал, А. Скала, М. Бартелеми (2000). «Классы сетей малого мира». PNAS. 97 (21): 11149–52. arXiv:cond-mat / 0001458. Bibcode:2000PNAS ... 9711149A. Дои:10.1073 / pnas.200327197. ЧВК  17168. PMID  11005838.
  8. ^ Булдырев, Сергей В .; Паршани, Рони; Пол, Джеральд; Стэнли, Х. Юджин; Хавлин, Шломо (2010). «Катастрофический каскад отказов во взаимозависимых сетях». Природа. 464 (7291): 1025–1028. arXiv:0907.1182. Bibcode:2010Натура.464.1025Б. Дои:10.1038 / природа08932. ISSN  0028-0836. PMID  20393559. S2CID  1836955.
  9. ^ Паршани, Рони; Булдырев, Сергей В .; Хавлин, Шломо (2010). «Взаимозависимые сети: уменьшение силы связи приводит к переходу от перколяционного перехода первого ко второму порядку». Письма с физическими проверками. 105 (4): 048701. arXiv:1004.3989. Bibcode:2010PhRvL.105d8701P. Дои:10.1103 / PhysRevLett.105.048701. ISSN  0031-9007. PMID  20867893. S2CID  17558390.
  10. ^ Дж. Гао, С.В. Булдырев, Е. Стэнли, С. Хэвлин (2012). «Сети, образованные из взаимозависимых сетей». Природа Физика. 8 (1): 40–48. Bibcode:2012НатФ ... 8 ... 40Г. Дои:10.1038 / nphys2180.CS1 maint: использует параметр авторов (связь)
  11. ^ Майдандзич, Антонио; Подобник, Борис; Булдырев, Сергей В .; Kenett, Dror Y .; Хавлин, Шломо; Юджин Стэнли, Х. (2013). «Самопроизвольное восстановление в динамических сетях». Природа Физика. 10 (1): 34–38. Bibcode:2014НатФ..10 ... 34М. Дои:10.1038 / nphys2819. ISSN  1745-2473.
  12. ^ Салех, Махмуд; Эса, Юсеф; Мохамед, Ахмед (29 мая 2018 г.). «Приложения комплексного сетевого анализа в электроэнергетических системах». Энергии. 11 (6): 1381. Дои:10.3390 / en11061381.
  13. ^ A. Bashan, R.P. Bartsch, J.W. Kantelhardt, S. Havlin, P.C. Иванов (2012). «Сетевая физиология раскрывает взаимосвязь между сетевой топологией и физиологической функцией». Nature Communications. 3: 72. arXiv:1203.0242. Bibcode:2012НатКо ... 3..702B. Дои:10.1038 / ncomms1705. ЧВК  3518900. PMID  22426223.CS1 maint: несколько имен: список авторов (связь)
  14. ^ Дж. Фан, Дж. Мэн, X. Чен, Ю. Ашкенази, С. Хэвлин (2017). «Сетевые подходы к климатологии». Science China: физика, механика и астрономия. 60 (1): 10531. Bibcode:2017SCPMA..60a0531F. Дои:10.1007 / s11433-016-0362-2.CS1 maint: несколько имен: список авторов (связь)
  15. ^ Лукас Д Вальдес, Лидия Браунштейн, Шломо Хавлин (2020). «Распространение эпидемии по модульным сетям: страх объявить пандемию». Физический обзор E. 101 (3): 032309. arXiv:1909.09695. Bibcode:2020PhRvE.101c2309V. Дои:10.1103 / PhysRevE.101.032309. PMID  32289896. S2CID  202719412.CS1 maint: несколько имен: список авторов (связь)
  16. ^ А.Э. Моттер, Р. Альберт (2012). «Сети в движении». Физика сегодня. 65 (4): 43–48. arXiv:1206.2369. Bibcode:2012ФТ .... 65д..43М. Дои:10.1063 / pt.3.1518. S2CID  12823922. Архивировано из оригинал на 2012-09-06.
  17. ^ Джонсон С., Домингес-Гарсиа В., Донетти Л., Муньос М.А. (2014). «Трофическая согласованность определяет стабильность пищевой сети». Proc Natl Acad Sci USA. 111 (50): 17923–17928. arXiv:1404.7728. Bibcode:2014PNAS..11117923J. Дои:10.1073 / pnas.1409077111. ЧВК  4273378. PMID  25468963.CS1 maint: несколько имен: список авторов (связь)
  18. ^ С.Г. Хофманн, Дж. Э. Куртисс (2018). «Комплексный сетевой подход к клинической науке». Европейский журнал клинических исследований. 48 (8): e12986. Дои:10.1111 / eci.12986. PMID  29931701.
  19. ^ Мухамед Абдулла (22 сентября 2012 г.). Об основах стохастического пространственного моделирования и анализа беспроводных сетей и его влиянии на потери в каналах. Кандидат наук. Диссертация на кафедре электротехники и вычислительной техники, Университет Конкордия, Монреаль, Квебек, Канада, сентябрь 2012 г. (кандидат наук). Университет Конкордия. стр. (Глава 4 разрабатывает алгоритмы построения и визуализации сложных сетей).
  20. ^ Р. Коэн, С. Хэвлин, Д. Бен-Авраам (2003). «Эффективные стратегии иммунизации для компьютерных сетей и населения». Phys. Rev. Lett. 91 (24): 247901. arXiv:cond-mat / 0207387. Bibcode:2003PhRvL..91x7901C. Дои:10.1103 / PhysRevLett.91.247901. PMID  14683159. S2CID  919625.CS1 maint: использует параметр авторов (связь)
  21. ^ Чен, Y; Пол, G; Havlin, S; Liljeros, F; Стэнли, H.E (2008). «Поиск лучшей стратегии иммунизации». Phys. Rev. Lett. 101 (5): 058701. Bibcode:2008PhRvL.101e8701C. Дои:10.1103 / PhysRevLett.101.058701. PMID  18764435.
  22. ^ Ли, Дацин; Фу, Боуэн; Ван, Юньпэн; Лу, Гуанцюань; Березин, Йехиель; Стэнли, Х. Юджин; Хавлин, Шломо (2015). «Перколяционный переход в динамической сети трафика с развивающимися критическими узкими местами». Труды Национальной академии наук. 112 (3): 669–672. Bibcode:2015ПНАС..112..669Л. Дои:10.1073 / pnas.1419185112. ISSN  0027-8424. ЧВК  4311803. PMID  25552558.
  23. ^ Р. Альберт, А.-Л. Барабаши (2002). «Статистическая механика сложных сетей». Обзоры современной физики. 74 (1): 47–97. arXiv:cond-mat / 0106096. Bibcode:2002РвМП ... 74 ... 47А. Дои:10.1103 / RevModPhys.74.47. ISBN  978-3-540-40372-2. S2CID  60545.
  24. ^ Коэн, Реувен; Эрез, Керен; бен-Авраам, Даниил; Хавлин, Шломо (2000). «Устойчивость Интернета к случайным сбоям». Письма с физическими проверками. 85 (21): 4626–4628. arXiv:cond-mat / 0007048. Bibcode:2000ПхРвЛ..85.4626С. Дои:10.1103 / PhysRevLett.85.4626. ISSN  0031-9007. PMID  11082612. S2CID  15372152.
  25. ^ Р. Коэн, С. Хэвлин (2003). «Безмасштабные сети - сверхмалые». Phys. Rev. Lett. 90 (5): 058701. arXiv:cond-mat / 0205476. Bibcode:2003PhRvL..90e8701C. Дои:10.1103 / Physrevlett.90.058701. PMID  12633404. S2CID  10508339.
  26. ^ Ваксман Б. М. (1988). «Маршрутизация многоточечных соединений». IEEE J. Sel. Коммунальные районы. 6 (9): 1617–1622. Дои:10.1109/49.12889.CS1 maint: использует параметр авторов (связь)
  27. ^ Данцигер, Майкл М .; Шехтман, Луи М .; Березин, Йехиель; Хавлин, Шломо (2016). «Влияние пространственности на мультиплексные сети». EPL. 115 (3): 36002. arXiv:1505.01688. Bibcode:2016EL .... 11536002D. Дои:10.1209/0295-5075/115/36002.CS1 maint: использует параметр авторов (связь)
  28. ^ Бная Гросс, Дана Вакнин, Сергей Булдырев, Шломо Хавлин (2020). «Два перехода в пространственных модульных сетях». Новый журнал физики. 22 (5): 053002. arXiv:2001.11435. Bibcode:2020NJPh ... 22e3002G. Дои:10.1088 / 1367-2630 / ab8263. S2CID  210966323.CS1 maint: несколько имен: список авторов (связь)