Реальные сети и «тяжелые хвосты»

В конце 90-х годов ХХ века изучением реальных сетевых структур занялись физики.
Возросшие вычислительные мощности современных компьютеров и доступ к хранящимся в информационных системах «экспериментальным данным» позволил анализировать такие структуры, как:

• сети дорог и транспортных маршрутов;
• сети телефонных звонков между людьми;
• сети, образованные взаимодействием серверов в Интернет и гипертекстовыми ссылками на сайты в World Wide Web;
• сети совместной работы актеров в снятых фильмах;
• сети научного соавторства и сети цитирования научных работ;
• сложные системы в медицине и биологии – сети, формирующиеся взаимодействующими нейронами мозга, сети химических реакций;
• семантические сети, образуемые взаимосвязанными терминами и понятиями и т.п.

Первые же исследования реальных сетей различных типов принесли целую серию неожиданных и драматических результатов, показавших, что любимые ранее математиками случайные графы и модели на их основе имеют весьма слабое отношение к реальным сетям. Одним из первых результатов исследований стала идентификация ряда объединяющих принципов и статистических свойств, общих для большинства рассмотренных реальных сетей. Оказалось, в частности, что в реальных сетях распределение количества узлов по степеням существенно отличается от Пуассоновского распределения, ожидаемого для случайного графа и, во многих случаях, описывается степенным законом с показателем экспоненты (гамма) от 2 до 3 (Рис. 8). На графике в двойном логарифмическом масштабе степенному закону распределения соответствует прямая линия.

Рис. 8. Примерное распределение степени узлов в реальной сложной сети

В сети, характеризующейся таким распределением «среднее» и «наиболее вероятное» – далеко не одно и тоже! Подавляющее большинство узлов такой сети имеют сравнительно малое количество связей, и, наоборот, основная масса связей приходится на относительно небольшое количество узлов с очень высокой степенью.  Если показатель «гамма» в законе распределения не меняется при изменении степени узла на протяжении нескольких порядков, то говорят, что эта сеть – безмасштабная (scale-free network). В такой сети нет какого-то типичного «характерного масштаба», а небольшое случайно выбранное подмножество сети ведет себя как вся сеть в целом.

Распределение, описываемое степенной функцией – частный случай большого семейства так называемых распределений с «тяжелыми хвостами», а те, в свою очередь – причина известных законов Ципфа, распределения Парето в экономике, закона Гутенберга-Рихтера в сейсмологии и многих других…

Помимо таких замечательных статистических свойств, для топологии многих реальных сетей характерны ассортативность (корреляции в свойствах соседних узлов), свойства «малого мира» (сети имеют сравнительно небольшой диаметр, определяемый как средняя длина кратчайших путей между узлами), содержат большое количество коротких петель и направленных маршрутов обхода (motifs), наличие кластеров (сильно-связанных компонент) и т.п. и т.д. Нетривиальность статистических и топологических свойств реальных сетей – второй фактор, оправдывающий введение нового термина: «Complex Networks».