Теория графов и интернет

С точки зрения моего сегодняшнего доклада, интернет — это графы. Давайте представлять себе вершины этого графа как сайты в интернете, а ребра этого графа, направленные, — как гиперссылки между этими сайтами. То есть если есть один сайт, который ссылается на другой, мы рисуем направленное ребро. Если таких ссылок несколько, скажем, есть несколько страниц, которые ссылаются на другие страницы, то мы рисуем, соответственно, несколько ребер. Ребра могут быть направлены в разные стороны, и могут возникать даже петли. Ведь понятно, что внутри каждого сайта могут быть страницы, которые тоже друг друга цитируют. Получается такой хитрый граф, который мы будем называть веб-графом.

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

Очень полезно считать количество вхождений данной конкретной фиксированной структуры в наш граф. Сколько там треугольников? Сколько там циклов заданной длины, деревьев, еще чего-то? Это очень полезно его характеризует. То есть можно посмотреть, сколько в реальности в графе должно быть треугольников, потом посчитать, сколько их в модели.

В рубрике «Лекции» мы будем выбирать для вас самые интересные лекции авторов ПостНауки, прочитанные ими на различных площадках, и публиковать в привычном формате. Так мы со временем соберем лучшие выступления ученых в одном месте. Чтобы посоветовать нам лекции, пишите postnauka@postnauka.ru.