Кому нужна математика? Понятная книга о том, как устроен цифровой мир (Литвак, Райгородский) - страница 32

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

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


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


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

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

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

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

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

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

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

Результат Эрдеша – Реньи

В связи с устойчивостью интернета нас интересует вопрос о