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