Случайные графы

Математическая теория, которая, в частности, позволяет ответить на вопрос об устойчивости больших сетей, возникла на рубеже 50–60-х годов XX века. Ее авторами стали два замечательных венгерских математика Пол Эрдеш и Альфред Реньи{9}{10}.

Эрдеш – настоящий классик современной комбинаторики, теории чисел, теории вероятностей. Он написал более полутора тысяч статей, решил множество проблем и еще больше поставил задач, которые определили пути развития науки на долгие годы. Реньи – выдающийся венгерский специалист по теории вероятностей. Его именем назван математический институт в Будапеште, подобно тому как математический институт в Москве носит имя Владимира Андреевича Стеклова.

Пол Эрдеш

Пол Эрдеш (1913–1996) очень необычная фигура в математике. Он написал около 1500 статей с 509 соавторами.

Практически вся его собственность умещалась в один чемодан. Деньги его совсем не интересовали. Он жил в дороге, ездил с одной конференции на другую или останавливался у коллег. Рассказывают, что он появлялся на пороге и говорил: «Мой мозг открыт». Затем он работал с хозяевами несколько дней, получал результаты для нескольких статей и ехал дальше, в следующий дом и к другим задачам.

Его соавтор Фэн Чжун написала в своих воспоминаниях: «Все 83 года своей жизни он был абсолютно верен себе. Его не соблазняли посты и деньги. Большинство из нас окружили себя множеством земных благ и обязательств. Каждая встреча с ним напоминала мне, что это все-таки возможно, вот так идти за своей мечтой, не обращая никакого внимания на мелочи жизни. Именно по этому качеству дяди Пола я скучаю больше всего».

В математике, как в искусстве или моде, есть индивидуальные стили и вкусы. Соавторы Эрдеша рассказывают, что ему удавалось найти задачи, подходящие именно для них. Так хорошо он понимал своих соавторов и столько разных задач у него было в запасе! Результаты Эрдеша – разнообразные и в огромном количестве – сильно повлияли на современную науку.

Среди математиков есть понятие число Эрдеша. Это количество соавторов, которые отделяют математика от Эрдеша. У соавторов Эрдеша число Эрдеша равно 1. У их соавторов, которые с Эрдешем не работали, число Эрдеша – 2. И так далее. Самое распространенное значение – 5, и очень редко у кого из математиков число Эрдеша равно 8 или больше.

У одного из нас число Эрдеша 3, а у другого 2. Мы оба работаем со случайными графами и вносим свой посильный вклад в решение пока нерешенных проблем.

Теория, основы которой заложили Эрдеш и Реньи, называется теорией случайных графов. А математическая модель, рассмотренная в их первых работах, носит имя случайный граф Эрдеша – Реньи. Конечно, эти графы не имеют ничего общего с князьями и баронами. Слово «граф» в данном случае имеет то же происхождение, что и слово «график», хорошо известное со школы. Граф – это просто рисунок.

Например, нашу мини-сеть из предыдущего раздела очень легко представить в виде графа. Мы это сделали на рис. 4.4 слева. Сеть изображена в виде трех узлов (компьютеров), которые соединены линиями (каналами связи). В математике узлы называются вершинами графа, а линии между ними – ребрами. Чтобы не затруднять восприятие абстрактными терминами, мы в основном будем пользоваться более интуитивными терминами «узлы» и «линии»[9].

Рис. 4.4. Слева: мини-сеть в виде графа. Узлы – это компьютеры, а линии – каналы связи. Справа: социальная сеть из главы 7 в виде графа. Узлы – это люди, а линии – «дружба» в социальной сети

В главе 7 мы вернемся к графам, когда будем обсуждать социальную сеть. В этом случае узлы – это люди, а линии между ними – «дружба» в социальной сети. Мы изобразили пример графа из главы 7 на рис. 4.4 справа.

Естественно, узлов у графа может быть и тысяча, и миллион, и миллиард…

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

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

Случайный граф – естественная модель во многих ситуациях. Например, дружба в социальных сетях возникает непредсказуемым образом. В телекоммуникациях или электрических сетях на линиях связи могут случаться сбои. Если попытаться смоделировать нейронную сеть мозга, то взаимодействия нейронов можно выявить только с определенной вероятностью.

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

Что же говорит теория случайных графов об устойчивости сети?