< Попер   ЗМІСТ   Наст >

Введение

Сейчас вряд ли можно возразить против того, что родилась новая парадигма, или более казенным языком, новое научное направление -теория сложных сетей. Вспомним историю 30-летней давности. Тогда, каждый, кто прочитал, пролистал или хотя бы просмотрел картинки и подписи к ним в книге Б. Мандельброта "Фрактальная геометрия природы" обнаруживал, что куда не глянь - одни фракталы. И деревья, и кусты, и профили гор и облаков, и знакомая еще со школы траектория броуновской частицы и т.д. и т.п. Термин фрактал стал модным, вошел (иногда и "не по делу") в терминологию статей и книг по самым разным областям науки -физики, химии, биологии, экономики, медицины, ... И это при том, что первые фрактальные объекты изучались уже в XIX веке (кривая Пеано, множество Кантора и др.). Сейчас интерес к фракталам остыл, частота употребления термина фрактал в книгах, падает. Новая область, активно развивающаяся - это так называемые "сложные сети". Теперь, куда не глянешь, видишь сети -социальные сети, сети дружбы, соавторства в научных публикациях, сексуальных отношений, бизнес-связей, публикаций в СМИ, совместного употребления слов в текстах, метаболизмов (обменных процессов), кровеносных сосудов, транспорта, наконец, (см. рис.). Интернет и WWW. Огромное поле деятельности, много результатов, новые разделы в научных журналах и новые журналы.

Бенуа Мандельброт (1924 - 2010)

Мандельброт Б. Фрактальная геометрия природы = The Fractal Geometry of Nature. - М.: Институт компьютерн. исследований, 2002. - С. 656.

"Где вы работаете?" - "Я нуль-физик". Изумленно-восхищенный взгляд. "Слушайте, расскажите, пожалуйста, что такое - нуль-физика? Я никак не могу понять". - "Я тоже". А. и Б. Стругацкие "Далекая Радуга".

При первом знакомстве с книгами и обзорами по теории сложных сетей возникает вопрос. Не просто ли модное название эта теория сложных сетей? Экономическая составляющая модного термина хорошо известна, написал "нанофильтр" и получил мегагрант. Чем отличается сеть, пусть и сложная, от графа? А теория сложных сетей от теории графов - теории, начало которой положил еще Эйлер своей знаменитой задачей о Кенигсбергских мостах.

Динамика употребления словосочетания Complex Networks, полученная с помощью сервиса Google Ngram Viewer (https://books.google.com/ngrams)

Рис. Динамика употребления словосочетания Complex Networks, полученная с помощью сервиса Google Ngram Viewer (https://books.google.com/ngrams)

Формально, любая сеть это граф. И, опять же, формально, теория, которая изучает свойства сложных сетей, должна была бы быть названа теорией графов. Приведем следующий контрпример. Классическая механика изучает, в том числе, движение материальных точек. Идеальный газ - это как раз движущиеся материальные точки. Однако свойства газа изучает другой раздел физики -статистическая механика.

У нее свои методы, термины, приемы. А "обычная" классическая механика с задачей описания газа справиться не может, слишком много частиц даже в небольшом "кусочке" газа. И пришлось Максвеллу, Больцману, Гиббсу и многим другим создать новую науку и ввести новые понятия, например, температуру и энтропию, которые не нужны и не вводятся принципиально в классической механике.

Аналогично и взаимоотношение теорий графов и сложных сетей. Как основой классической статистической физики является классическая механика, так основой теории сложных сетей является теория графов. При этом, теория графов может получать содержательные утверждения как правило для графов (сетей) небольшого размера или специальной структуры. В то время как теория сложных сетей имеет дело с большим количеством, как правило, случайным образом соединенных узлов. В связи с этим, с одной стороны, многие распространенные вопросы теории графов не представляют интереса для теории сложных сетей. Например, такой вопрос - планарен ли данный граф? Для случайного графа с большим числом узлов и связей ответ очевиден (и не представляет интереса) - нет. С другой стороны многие очень важные понятия в теории сложных сетей для графа с небольшим числом узлов и связей либо не представляют интереса, либо их просто трудно содержательно сформулировать. Например, такая важная характеристика в теории сложных сетей как функция распределения по степени узлов может быть подсчитана для любого, в т.ч. и малого количества узлов. Однако в силу своего вероятностного содержания это понятие оказывается полезным только в случае большого числа узлов и связей.

Dorogovtsev S.N., Mendes J.F.F . Evolution of Networks: From Biological Networks to the Internet and WWW. - Oxford, USA: Oxford University Press, 2003. -P. 280.

Mark Newman, Albert-Laszlo Barabasi, Duncan J. Watts. The Structure and Dynamics of Networks: (Princeton Studies in Complexity). -Princeton, USA: Princeton University Press, 2006. - P. 624.

Чем же занимается теория сложных сетей? Перечислим некоторые проблемы и задачи.

Во-первых, исследованием стандартных характеристик графов для сложных сетей разной природы - случайных графов, безмасштабных сетей, сетей малого мира и т.п.

Во-вторых, определением и изучением новых характеристик сложных сетей, таких, например, как средний минимальный путь, посредничество, коэффициент кластеризации.

В-третьих, изучением различных "физических" процессов на сложных сетях - диффузии, эпидемических процессов, различных потоков (информации, электрического тока, и т.д.). В конце концов, знаменитый алгоритм PageRank рассматривает блуждание по связям (гиперссылкам) в сложной сети WWW.

В-четвертых, есть очень важное в прикладном отношении, направление - методы восстановления, защиты и уничтожения сетей. Такой вопрос - сколько узлов (связей) нужно "убить" для того, что бы, например, разрушился "гигантский кластер" или что бы значительно увеличился минимальный средний путь? Т.е., как говорят сисадмины, что бы "сеть легла". Сюда же примыкают и вопросы оптимизации сетей.

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

Методы, которые используются для решения этих и многих других задач можно, условно, разделить на три типа. Методы теории графов, в значительной мере комбинаторные. Численное моделирование, в настоящее время хорошо развито, опробовано и приспособлено для целей исследователя сложных сетей. Например, для языка программирования Python разработан специальный пакет (python-networkx) - инструментарий для создания, манипулирования и изучения сложных сетей, позволяющий найти численно практически все возможные характеристики сложных сетей. Третий тип методов, который позволил установить основные закономерности в сложных сетях - методы теоретической физики. От теории среднего поля до ренорм-группы и диаграммной техники. Недаром значительное число ведущих исследователей сложных сетей физики теоретики.

Python-networkx package in Ubuntu (https:// launchpad. net/ubuntu/ +source/python-networkx)

О чем наша книга и для кого она предназначена? Сразу же надо сказать, что для тех, кто знаком с основными обзорами или книгами по теории сложных сетей наша книга не представляет интереса. Она предназначена, в первую очередь, тем кто только слышал термин "сложная сеть" или встречался с ним в статье по биологии, экономике и т.п. Заинтересовавшемуся читателю довольно сложно сразу же освоить большой обзор, терминологию, методы, основные задачи. Здесь и должна помочь предлагаемая книга. В первой ее части описаны, на простых примерах, основные характеристики и свойства нескольких, наиболее часто встречающихся сетей. Вторая часть книги предназначена тем читателям, которые бы хотели, в качестве примера, посмотреть "как работает" теория сложных сетей. Здесь приведены несколько задач (проблем) выбранных на вкус авторов.

Материал книги является основой двухсеместрового спецкурса "Моделирование сложных сетей", который читается студентам Института прикладного системного анализа (ИПСА) Национального технического университета Украины "КПИ". Выражаем благодарность ректору НТУУ "КПИ", заведующему кафедрой математических методов системного анализа (ММСА) академику М.З. Згуровскому, декану факультета системных исследований ИПСА профессору В.Д. Романенко и доценту кафедры ММСА Ю.А. Тимошенко за идею и поддержку в создании этого спецкурса.

И, наконец, выражаем искреннюю благодарность, нашим коллегам, поддержавшим идею написания данного учебного пособия и имеющим непосредственное отношение ко многим результатам, изложенным здесь: М.И. Женировскому, И.В. Безсуднову, А.Г. Додонову и С.М. Брайчевскому.

 
< Попер   ЗМІСТ   Наст >