ЛИТЕРАТУРА ПО ФУНДАМЕНТАЛЬНЫМ И ПРИКЛАДНЫМ НАУКАМ
для школьников, студентов и научных работников

Каталог

Книги

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

Экстремальные задачи теории графов и Интернет

Издательство:Интеллект
Год издания:2012
ISBN:978-5-91559-127-0
Кол-во страниц:104
Переплёт:Мягкий
 330 руб.  В корзину

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

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

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

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

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

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

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

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

Комментарии: (авторизуйтесь, чтобы оставить свой)
В корзине нет товаров
Новости
2018-08-08
УВАЖАЕМЫЕ ПОКУПАТЕЛИ! В СВЯЗИ С РЕМОНТНЫМИ РАБОТАМИ В МАГАЗИНЕ И ПРОВОДИМОЙ ИНВЕНТАРИЗАЦИЕЙ ОТПРАВКА ЗАКАЗОВ БУДЕТ ОСУЩЕСТВЛЯТЬСЯ ПОСЛЕ 22 АВГУСТА! ПРИНОСИМ ИЗВИНЕНИЯ!
2018-07-11
В связи с ремонтом фойе нового корпуса МФТИ с 16-го июля магазин (и пункт самовывоза) работает в фойе Главного корпуса по будням с 9.00 до 19.00, суббота и воскресенье — выходные дни.
2018-04-19
Уважаемые покупатели! 22 апреля 2018 г., в День открытых дверей МФТИ, магазин «Физтех-книга» в Новом корпусе МФТИ работает с 09.00 до 19.00
2018-01-31
15 ноября 2017 года Почта России повысила тарифы на внутренние посылки. Тарифы повысились практически ровно на 15%.