Аннотация

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

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

Книга рассчитана на всех, кто интересуется современными приложениями математики в области анализа данных. Она будет полезна студентам и аспирантам технических ВУЗов, а также исследователям и разработчикам больших сетей – Интернета, биологических и социальных сетей.

Введение

Настоящая брошюра посвящена изучению различных экстремальных задач теории графов, (хотя бы частичное) решение которых может быть полезно при анализе данных. Она возникла на основе семестрового курса лекций, прочитанных автором в Школе Анализа Данных Яндекса.

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

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

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

Первая (и наименее, впрочем, значительная) трудность состоит в том, что заговорщики, будучи, конечно, отнюдь не глупыми людьми, стараются организовать более сложные схемы взаимного цитирования, нежели та, которую мы привели в качестве примера выше. Дело в том, что при попарном цитировании возникает то, что называется полным подграфом в графе или кликой в нем, а с такими «опухолями» бороться худо-бедно умеют. Гораздо хуже, коль скоро, вместо клики, спамеры организуют нечто значительно более «разреженное»: с одной стороны, стандартные алгоритмы поиска перестают работать; с другой стороны, разреженность ссылок не так уж велика, и спамеры все равно получают приоритет.

Вторая трудность еще тоньше первой. Оказывается, что в исключительно сложных системах зачастую просто по необходимости или же с очень большой вероятностью возникают образования, которые сильно напоминают «разреженные» ссылочные кольца и в то же время таковыми, вообще говоря, не являются. Как сколь-нибудь достоверно различать образования-паразиты от естественных подграфов? Требуется, по-видимому, очень хорошо понять вероятностную природу веб-графа, дабы затем построить сильные (статистические) критерии, позволяющие аккуратно выбирать между кольцами и схожими с ними, но не зловредными объектами.

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

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