Премия Просветитель

Zimin Foundation

«Математическая составляющая»

Книга «Математическая составляющая» рассказывает, как и следует из названия, о математической составляющей как привычных нам вещей так и достижений цивилизации. У каждой главы-рассказа свой автор. Среди них — без преувеличения — великие математики современности. Представляем небольшой фрагмент, который называется «Математика интернета» Андрея Райгородского.

***

Странное название, скажет читатель, проводящий часть жизни в интернете. Ведь возникновение сайтов, их наполнение контентом, установление связей между ними (ссылки)—всё это происходит стихийно, никем явным образом не управляется. Но как и другие сложные системы, состоящие из большого числа «свободных» элементов, интернет становится средой, в целом имеющей устойчивые свойства, не зависящие от беспорядка в мелочах, и поддающиеся исследованию математическими методами.

Будем представлять интернет в виде графа. Граф — это множество точек (вершин графа), соединённых конечным числом дуг (рёбер графа). Вершинами будем считать интернет-сайты, а рёбрами—гиперссылки, идущие с одних сайтов на другие. Рёбра этого графа—ориентированные (в ссылках важно кто на кого ссылается), некоторые из них — кратные (несколько ссылок с одного сайта на другой), есть и петли (ссылки между страницами одного и того же сайта).

Построенный веб-граф — настоящий монстр с миллиардами вершин и рёбер. Этот граф постоянно меняется: добавляются и исчезают сайты, пропадают и появляются ссылки. Но при всех изменениях, некоторые свойства интернета остаются неизменными на протяжении всей истории его исследования. Вот несколько примеров таких «устойчивых» свойств.

Веб-граф разрежен. В нём лишь в несколько раз больше рёбер, чем вершин. Казалось бы, странное дело — возможны любые ссыл- ки, а рёбер всё равно мало. Несмотря на разреженность, интернет-мир очень тесен. А именно, от любого сайта до любого другого можно по ссылкам перейти за 5–6 "кликов«(знаменитый закон «шести рукопожатий»). В веб-графе высока вероятность того, что «соседи» данной вершины (сайты, связанные ссылками с данным) сами связаны ребром: «мои знакомые знакомы между собой».

Важная характеристика вершины графа — её степень, т.е. число входящих и выходящих рёбер. Оказывается, что степени вершин «правильно», т.е. по определённому закону, распределены: доля вершин данной степени d пропорциональна величине 1/dγ, где γ ≈ 2,3. В этой формуле есть понятное ядро — доля вершин большой степени d (сайтов с большим количеством ссылок) мала. Но есть и удивительная деталь — постоянная γ не зависит от числа вершин веб-графа, т.е. не меняется в процессе развития интернета. Этот степенной закон является универсальным для сложных сетей — от биологических до межбанковских, разве что для разных сетей величина γ немного разная.

Интернет как целое устойчив к случайным атакам на сайты. А именно, если уничтожение сайтов происходит независимо и с одинаковой вероятностью, то веб-граф с вероятностью, близкой к 1, сохраняет «гигантскую» связную компоненту. Эта компонента сохраняется даже при прицельной атаке на хабы—вершины наибольших степеней — пока доля атакованных хабов не превысит некоторое критическое значение.

Для изучения интернета необходимо уметь строить модель «случайного графа», которая с высокой вероятностью обладает ожидаемыми свойствами реального интернета. При этом для практических нужд, да и для чисто математических целей, крайне важно, чтобы модель не была слишком сложной. Эта трудная и привлекательная задача полностью не решена. Построение хорошей математической модели интернета сразу же даёт качественно новые инструменты для улучшения информационного поиска, выявления спама, прогнозирования распространения информации в социальных сетях и в интернете в целом.

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

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



Ранее в этом блоге

Нашли опечатку? Выделите фрагмент и нажмите Ctrl+Enter.