В контексте теории сетей сложная сеть — это граф (сеть) с нетривиальными топологическими характеристиками — характеристиками, которые не встречаются в простых сетях, таких как решетки или случайные графы , но часто встречаются в сетях, представляющих реальные системы. Изучение сложных сетей — это молодая и активная область научных исследований [1] [2] (с 2000 года), вдохновленная в значительной степени эмпирическими открытиями реальных сетей, таких как компьютерные сети , биологические сети , технологические сети, мозговые сети , [3] [4] [5] климатические сети и социальные сети .
Большинство социальных , биологических и технологических сетей демонстрируют существенные нетривиальные топологические особенности с моделями связи между их элементами, которые не являются ни чисто регулярными, ни чисто случайными. Такие особенности включают в себя тяжелый хвост в распределении степеней , высокий коэффициент кластеризации , ассортативность или дисассортативность среди вершин, структуру сообщества и иерархическую структуру . В случае направленных сетей эти особенности также включают взаимность , профиль значимости триады и другие особенности. Напротив, многие из математических моделей сетей, которые изучались в прошлом, такие как решетки и случайные графы , не показывают этих особенностей. Самые сложные структуры могут быть реализованы сетями со средним числом взаимодействий. [6] Это соответствует тому факту, что максимальное информационное содержание ( энтропия ) получается для средних вероятностей.
Два хорошо известных и хорошо изученных класса сложных сетей — это безмасштабные сети [7] и сети малого мира [8] [9] , открытие и определение которых являются каноническими примерами в этой области. Оба они характеризуются определенными структурными особенностями — степенными распределениями степеней для первых и короткими длинами путей и высокой кластеризацией для вторых. Однако, поскольку изучение сложных сетей продолжало расти в важности и популярности, многие другие аспекты сетевых структур также привлекли внимание.
Область продолжает развиваться быстрыми темпами и объединяет исследователей из многих областей, включая математику , физику , электроэнергетические системы, [10] биологию , климат , информатику , социологию , эпидемиологию и другие. [11] Идеи и инструменты из сетевой науки и инженерии были применены к анализу метаболических и генетических регуляторных сетей; изучению стабильности и надежности экосистем; [12] клинической науке; [13] моделированию и проектированию масштабируемых сетей связи, таких как генерация и визуализация сложных беспроводных сетей; [14] и широкому кругу других практических вопросов. Сетевая наука является темой многих конференций в различных областях и предметом многочисленных книг как для неспециалистов, так и для экспертов.
Сеть называется безмасштабной [7] [15], если ее распределение степеней, т. е. вероятность того, что узел, выбранный равномерно случайным образом, имеет определенное количество связей (степень), следует математической функции, называемой степенным законом . Степенной закон подразумевает, что распределение степеней этих сетей не имеет характерного масштаба. Напротив, сети с одним четко определенным масштабом несколько похожи на решетку в том, что каждый узел имеет (примерно) одинаковую степень. Примерами сетей с одним масштабом являются случайный граф Эрдёша–Реньи (ER) , случайные регулярные графы, регулярные решетки и гиперкубы . Некоторые модели растущих сетей, которые производят масштабно-инвариантные распределения степеней, являются моделью Барабаши–Альберта и моделью пригодности . В сети с безмасштабным распределением степеней некоторые вершины имеют степень, которая на порядки больше средней — эти вершины часто называют «хабами», хотя этот язык вводит в заблуждение, поскольку по определению не существует внутреннего порога, выше которого узел можно рассматривать как хаб. Если бы такой порог существовал, сеть не была бы безмасштабной.
Интерес к сетям без масштабирования начался в конце 1990-х годов с сообщениями об открытиях степенных распределений степеней в реальных сетях, таких как Всемирная паутина , сеть автономных систем (AS), некоторые сети интернет-маршрутизаторов, сети взаимодействия белков, сети электронной почты и т. д. Большинство из этих сообщенных «степенных законов» терпят неудачу при проверке строгим статистическим тестированием, но более общая идея распределений степеней с тяжелыми хвостами, которые многие из этих сетей действительно демонстрируют (до возникновения эффектов конечного размера), сильно отличается от того, что можно было бы ожидать, если бы ребра существовали независимо и случайным образом (т. е. если бы они следовали распределению Пуассона ). Существует много разных способов построить сеть со степенным распределением степеней. Процесс Юла является каноническим генеративным процессом для степенных законов и известен с 1925 года. Однако он известен под многими другими названиями из-за его частого переосмысления, например, принцип Жибрата Герберта А. Саймона , эффект Мэтью , кумулятивное преимущество и предпочтительное присоединение Барабаши и Альберта для степенных распределений степеней. Недавно были предложены гиперболические геометрические графы как еще один способ построения сетей без масштаба.
Некоторые сети со степенным распределением степеней (и некоторые другие типы структур) могут быть весьма устойчивы к случайному удалению вершин, т. е. подавляющее большинство вершин остаются соединенными вместе в гигантском компоненте. Такие сети также могут быть весьма чувствительны к целевым атакам, направленным на быстрый разрыв сети. Когда граф равномерно случаен, за исключением распределения степеней, эти критические вершины имеют самую высокую степень и, таким образом, были вовлечены в распространение болезней (естественных и искусственных) в социальных и коммуникационных сетях, а также в распространение модных тенденций (оба из которых моделируются процессом перколяции или ветвления ). В то время как случайные графы (ER) имеют среднее расстояние порядка log N [8] между узлами, где N — количество узлов, масштабируемый свободный граф может иметь расстояние log log N.
Сеть называется сетью малого мира [8] по аналогии с феноменом малого мира (широко известным как шесть степеней разделения ). Гипотеза малого мира, впервые описанная венгерским писателем Фридьешем Каринтием в 1929 году и экспериментально проверенная Стэнли Милгрэмом (1967), заключается в идее о том, что два произвольных человека связаны всего шестью степенями разделения, то есть диаметр соответствующего графа социальных связей не намного больше шести. В 1998 году Дункан Дж. Уоттс и Стивен Строгац опубликовали первую модель сети малого мира, которая посредством одного параметра плавно интерполирует между случайным графом и решеткой. [8] Их модель продемонстрировала, что при добавлении лишь небольшого числа дальних связей обычный граф, в котором диаметр пропорционален размеру сети, может быть преобразован в «маленький мир», в котором среднее число ребер между любыми двумя вершинами очень мало (математически оно должно расти как логарифм размера сети), в то время как коэффициент кластеризации остается большим. Известно, что большое разнообразие абстрактных графов демонстрирует свойство малого мира, например, случайные графы и сети без масштаба. Кроме того, сети реального мира, такие как Всемирная паутина и метаболическая сеть, также демонстрируют это свойство.
В научной литературе по сетям существует некоторая двусмысленность, связанная с термином «маленький мир». Помимо ссылки на размер диаметра сети, он также может относиться к совместному появлению малого диаметра и высокого коэффициента кластеризации . Коэффициент кластеризации — это метрика, которая представляет плотность треугольников в сети. Например, разреженные случайные графы имеют исчезающе малый коэффициент кластеризации, в то время как сети реального мира часто имеют значительно больший коэффициент. Ученые указывают на это различие как на предположение о том, что ребра коррелируют в сетях реального мира. Были разработаны подходы для создания сетевых моделей, которые демонстрируют высокую корреляцию, сохраняя при этом желаемое распределение степеней и свойства малого мира. Эти подходы можно использовать для создания аналитически решаемых игрушечных моделей для исследования этих систем. [16]
Многие реальные сети встроены в пространство. Примерами являются транспортные и другие инфраструктурные сети, мозговые сети. [3] [4] Было разработано несколько моделей пространственных сетей. [17]