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

«Сложные сети» перенаправляется сюда. Информацию о компании см. в разделе «Комплексные сети» .

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

Определение

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

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

Эта область продолжает развиваться быстрыми темпами и объединила исследователей из многих областей, включая математику , физику , электроэнергетические системы, биология , климат , информатика , социология , эпидемиология и другие. Идеи и инструменты сетевой науки и инженерии были применены к анализу метаболических и генетических регуляторных сетей; изучение стабильности и устойчивости экосистем; клиническая наука; моделирование и проектирование масштабируемых сетей связи, например создание и визуализация сложных беспроводных сетей; и широкий спектр других практических вопросов. Сетевая наука является темой многих конференций в самых разных областях и является предметом многочисленных книг как для непрофессионалов, так и для экспертов.

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

Основная статья: Безмасштабные сети

Пример сложной безмасштабной сети.

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

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

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

маленького

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

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

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

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

Основная статья: Пространственная сеть

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

См. также

• Структура сообщества
• Сложная адаптивная система
• Сложные системы
• Двухфазная эволюция
• Динамический сетевой анализ
• Взаимозависимые сети
• Многомерная сеть
• Теория сетей
• Сетевая наука
• Теория перколяции
• Случайный график
• Теория гелеобразования на случайных графах
• Безмасштабные сети
• Маленькие мировые сети
• Пространственная сеть
• Трофическая когерентность

Книги

• Б.С. Манодж, Абхишек Чакраборти и Рахул Сингх, Комплексные сети: взгляд на сети и обработку сигналов , Пирсон, Нью-Йорк, США, февраль 2018 г. ISBN   978-0-13-478699-5
• С. Н. Дороговцев и Дж. Ф. Мендес, Эволюция сетей: от биологических сетей к Интернету и WWW , Oxford University Press, 2003, ISBN   0-19-851590-1
• Дункан Дж. Уоттс, Шесть степеней: наука эпохи взаимосвязи , WW 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
• Марк Ньюман, Сети: введение , 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
• Т. Льюис, Сетевые науки, Wiley, 2009 г.,
• Нилой Гангули (редактор), Андреас Дойч (редактор) и Анимеш Мукерджи (редактор), « Динамика и приложения сложных сетей в биологии, информатике и социальных науках» , 2009 г., ISBN   978-0-8176-4750-6
• Вито Латора, Винченцо Никосия, Джованни Руссо, Сложные сети: принципы, методы и приложения , Cambridge University Press, 2017, ISBN   978-1-107-10318-4

Ссылки

• DJ Уоттс и С.Х. Строгац (1998). «Коллективная динамика сетей «маленького мира». Природа . 393 (6684): 440–442. Бибкод : 1998Natur.393..440W . дои : 10.1038/30918 . ПМИД   9623998 . S2CID   4429113 .
• С.Х. Строгац (2001). «Изучение сложных сетей» . Природа . 410 (6825): 268–276. Бибкод : 2001Natur.410..268S . дои : 10.1038/35065725 . ПМИД   11258382 .
• Р. Альберт и А.-Л. Барабаши (2002). «Статистическая механика сложных сетей». Обзоры современной физики . 74 (1): 47–97. arXiv : cond-mat/0106096 . Бибкод : 2002РвМП...74...47А . дои : 10.1103/RevModPhys.74.47 . S2CID   60545 .
• С. Н. Дороговцев и Ж. Ф. Мендес (2002). «Эволюция сетей». Адв. Физ . 51 (4): 1079–1187. arXiv : cond-mat/0106144 . Бибкод : 2002AdPhy..51.1079D . дои : 10.1080/00018730110112519 . S2CID   429546 .
• МЭДж Ньюман, Структура и функции сложных сетей , SIAM Review 45, 167-256 (2003).
• С. Н. Дороговцев, А. В. Гольцев и Ж. Ф. Мендес, Критические явления в сложных сетях , Rev. Mod. Физ. 80, 1275, (2008)
• Дж. Калдарелли, Р. Маркетти, Л. Пьетронеро, Фрактальные свойства Интернета, Europhysical Letters 52, 386 (2000). https://arxiv.org/abs/cond-mat/0009178 . DOI: 10.1209/epl/i2000-00450-8
• А.Е. Моттер (2004). «Каскадное управление и защита в сложных сетях». Физ. Преподобный Летт . 93 (9): 098701. arXiv : cond-mat/0401074 . Бибкод : 2004PhRvL..93i8701M . doi : 10.1103/PhysRevLett.93.098701 . ПМИД   15447153 . S2CID   4856492 .
• Дж. Ленерт, Управление шаблонами синхронизации в сложных сетях, весна 2016 г.
• Долев, Шломи; Эловичи, Юваль; Пузис, Рами (2010), «Центральность маршрутизации между связями», J. ACM , 57 (4): 25:1–25:27, doi : 10.1145/1734213.1734219 , S2CID   15662473