Cтр. 10

Математика интернета
Поделиться…

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

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

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

Веб–граф разрежен. В нём лишь в несколько раз больше рёбер, чем вершин. Казалось бы, странное дело — возможны любые ссылки, а рёбер всё равно мало.

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

В веб–графе высока вероятность того, что «соседи» данной вершины (сайты, связанные ссылками с данным) сами связаны ребром: «мои знакомые знакомы между собой».

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

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

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

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

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

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

Изучение подобных систем — один из центральных разделов прикладной математики и неиссякаемый источник новых задач для всей математики.

Литература

  • Райгородский А. М. Математические модели интернета // Журнал «Квант». 2012. № 4. Стр. 12—16.
  • Райгородский А. М. Модели интернета. — М.: Интеллект, 2013.
  • Оре О. Графы и их применение. — М.: Мир, 1965.