Райгородский А.М. Экстремальные задачи теории графов и интернет

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

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

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

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

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

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

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

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