Математика интернета

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

Математика интернета // Математическая составляющая

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

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

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

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

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

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

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

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

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

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

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

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

Разворот книги

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

Лите­ра­тура

Райго­род­ский А. М. Матема­ти­че­ские модели интер­нета // Жур­нал «Квант». 2012. № 4. Стр. 12—16.

Райго­род­ский А., Лит­вак Н. Кому нужна матема­тика?: Понят­ная книга о том, как устроен циф­ро­вой мир. — М.: МИФ, 2017.

Оре О. Графы и их при­ме­не­ние. — М.: Мир, 1965.