Кому нужна математика? Понятная книга о том, как устроен цифровой мир

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

Фазовый переход

На самом деле теорема Эрдеша – Реньи несколько точнее и еще удивительнее, чем мы описали в предыдущем разделе. Эта теорема выявила интересное явление, которое физики называют фазовым переходом. Фазовый переход – это резкий скачок от одного состояния системы к совершенно другому[10].

Самый знаменитый фазовый переход – изменение состояния воды в зависимости от температуры. При 0° Цельсия вода превращается в лед, а при 100° – в пар. 0° и 100° – критические значения, при которых состояние резко меняется.

Нечто похожее происходит и с вероятностью связности сети, если изменять вероятность недоступности каналов. Оказывается, надежность сети меняется не постепенно, а очень резко. Если вероятность помехи меньше критического значения, то с подавляющей вероятностью связность сохраняется. Но стоит хотя бы немного пересечь критическую черту – и сеть почти наверняка распадется.

На рис. 4.7 показан пример сети из 100 компьютеров. Согласно результатам Эрдеша – Реньи, критическая вероятность помех в такой сети равна 95,4 %. Слева вероятность помехи 95 %, то есть меньше критического значения. Как видите, связность сети сохранилась. Мы неоднократно повторили эксперимент, но получить несвязную сеть нам так и не удалось. На рисунке справа вероятность помехи 96 %. И что же? Одна точка оторвалась от сети, связность потеряна. Опять же как мы ни старались повторить эксперимент, связной сети мы не получили ни разу. Результат впечатляет тем, насколько тонкой оказывается грань между связностью и несвязностью!

Рис. 4.7. Сеть из 100 компьютеров в виде графа. Слева: вероятность недоступности канала 95 %; связность сохраняется. Справа: вероятность недоступности канала 96 %; связность нарушена

Если вероятность помех в точности равна критической, то произойдет примерно то же самое, что и с водой и снегом при нуле градусов: может получиться и так и эдак. В нашем случае вероятность сохранения связности приблизительно составит 36,79 %.

Критическая вероятность недоступности канала для сети размера п вычисляется по формуле

Для примера мы приводим несколько значений в табл. 4.3.

Таблица 4.3. Результат Эрдеша – Реньи: критическая вероятность помех. Если вероятность помех меньше критической, связность сети сохраняется, а если больше – разрушается

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

Как доказывается результат Эрдеша – Реньи

Глубокие математические доказательства часто строятся на очень простых интуитивных идеях. Результат Эрдеша – Реньи – блестящий пример данной закономерности[11].

Математики заметили, что наиболее вероятный способ разрушить связность сети – отрезать один узел от всех каналов связи. Группу узлов отрезать гораздо труднее, потому что число каналов, которые связывают ее и остальную часть сети, относительно большое. Маловероятно, что все эти каналы недоступны. Тогда изначально сложный вопрос:

С какой вероятностью разрушится связность сети?

сводится к гораздо более простому вопросу:

С какой вероятностью хотя бы один из узлов потеряет все свои каналы связи?

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

Например, если у нас 100 узлов и вероятность помехи 0,96, то каждый узел может оказаться оторванным от всех 99 других узлов с вероятностью

(0,96)⁹⁹ (×100 %)

Это очень специфическое выражение: число, близкое к единице, возведенное в большую степень. Такие выражения хорошо известны в математике и относятся к так называемым замечательным пределам, из которых, по сути дела, и следует результат.

Что мы знаем и чего не знаем о надежности интернета