[МУЗЫКА] Здравствуйте. Меня зовут Владимир Подольский, и на этой неделе мы обсудим с вами случайные блуждания и их приложения. И давайте начнем с обсуждения такой задачи. Пусть у нас есть какой-то граф, который мы взяли из практики. То есть из каких-то приложений мы взяли граф. И мы хотим ответить на такой вопрос: какие ребра правильно было бы добавить к этому графу? И в принципе, эта задача звучит странно. Это просто граф. Как понять, какие ребра туда нужно добавить, каких ребер там не хватает, как вообще это формализовать, что это вообще за задача? И неясно, как отвечать на такой вопрос. Но при этом такие задачи реально возникают на практике. У нас на практике может быть граф, в который нам может хотеться предложить добавить каких-то ребер. И конкретная обстановка тут, конечно, зависит от контекста. Так что давайте разберем некоторые примеры. Давайте разберем пример соцсетей. Пусть у нас дан граф соцсети: у нас вершины — это пользователи, и мы соединяем их ребрами, если они друзья. И мы хотим предложить пользователю добавить друзей. Мы хотим предложить пользователю людей, которые у него еще не в друзьях, но которых он, может быть, захотел бы добавить. И мы хотели бы предложить тех при этом, кого он, скорее всего, знает. Будет странно предлагать ему случайных людей, с которыми он не знаком. Хотелось бы предложить ему тех, кого он, скорее всего, знает. И по сути мы хотим угадать, каких ребер не хватает в нашем графе соцсети. Мы хотим угадать, каких людей пользователь не добавил, но которых стоит ему предложить добавить, которые на самом деле являются его друзьями. Хорошо, давайте другой пример рассмотрим. В нашем онлайн-магазине есть разные товары. И у нас есть информация о том, какие товары часто покупают вместе. И мы хотели бы понять, что еще можно предложить пользователям, которые купили какой-то товар. И какой у нас тут граф? Мы возьмем товары в качестве наших вершин и соединим ребрами те, которые часто покупают вместе. И тогда мы хотели бы угадать, каких ребер не хватает в графе. Что бы еще следовало предложить пользователю, который купил один товар, какие товары еще стоило бы соединить, тоже, опять же, наша задача. Давайте еще один пример рассмотрим. Пусть у нас есть видеосервис, и там пользователи просматривают разные видео. И у нас есть вся информация о том, кто из пользователей что посмотрел. И мы хотели бы рекомендовать пользователям новые видео для просмотра. И граф тут такой: мы соединяем ребрами пользователя с теми видео, которые он посмотрел, и соотвественно хотим угадать, каких ребер не хватает в графе, какие ребра стоило провести, какие видео стоит порекомендовать пользователю, которые ему, скорее всего, понравятся. Хорошо, вот у нас есть такая задача, как же собственно ее решать? И давайте рассмотрим пример соцсети, пусть у нас какая-то такая несложная картинка. И кого бы нам стоило предложить в друзья пользователю A? Вот на этой картинке. И тут может быть такая идея. Если у нас есть два человека, которые еще не друзья, но у которых много общих знакомых, то они, скорее всего, тоже знакомы. И можно попробовать предлагать пользователю тех друзей, которые у него еще не в друзьях, но с которыми у него много общих друзей. И например, пользователю A из этих соображений можно было бы предложить пользователя E, потому что у него целых три общих друга. На этой картинке тут вообще не так много людей, скорее всего, они знакомы, может быть, стоит предложить E. И в целом можно пользоваться таким подходом. И оказывается, что уже этот подход неплохо работает на практике. То есть если мы будем так делать, то мы довольно часто будем предлагать действительно людей, которые знакомы друг с другом. Но мы обсудим и другие подходы. Но давайте сначала поймем зачем: зачем обсуждать другие подходы, если у нас уже есть неплохо работающий один подход. Во-первых, такой подход неплохо работает в соцсетях, когда нам нужно предложить общих друзей. Но в других ситуациях, в других графах, в других наших примерах это может плохо работать. И в целом оказывается, что в разреженных графах, в которых мало ребер по сравнению с количеством вершин, такой подход работает плохо, потому что в разреженных графах соседей у вершин не очень много и информация об общих соседях становится не очень содержательной. И на самом деле даже в соцсетях будет странно, если пользователь будет заходить каждый день в соцсеть и видеть одни и те же предложения. Он их уже просмотрел вчера, зачем ему сегодня снова показывать те же самые варианты? Поэтому на самом деле даже для случая соцсетей лучше иметь разные методы, чтобы мы могли в разные дни делать пользователю разные предложения, чтобы ему продолжало это быть интересно. И наконец, конечно, этот метод работает неплохо, но, может быть, можно этот метод улучшить. И это, в принципе, может быть важным, то есть хорошо бы, чтобы сервисы нашей соцсети работали лучше. И оказывается, чтобы эффективные и продвинутые методы чаще всего получаются какой-то хитрой и сложной комбинацией простых методов. А поэтому, в принципе, полезно знать несколько простых методов, чтобы понимать, какие они есть и что с чем комбинировать, как они работают. И для таких целей тоже полезно знать несколько разных простых методов. Хорошо, но прежде чем переходить к их обсуждению, давайте обсудим такой вопрос. Вот у нас есть простой метод: просто смотреть на число общих соседей у двух вершин. У нас будут еще разные методы, основанные на случайных блужданиях, но замечательно, и возможно, что все это работает неплохо, но как это проверять? То есть как это вообще тестировать, как проверять, хорошо работает метод или плохо, какой метод лучше, какой хуже? И здесь есть стандартный подход, и он такой: мы можем взять реальный граф, какой-нибудь граф соцсети, какой-нибудь граф из практики. И мы можем сделать следующее: мы можем взять какую-то вершину и удалить у нее несколько случайно выбранных ребер. То есть мы просто берем какого-то пользователя соцсети, например, и удаляем нескольких его друзей. И после этого мы можем запустить наши методы на получившемся графе в этой вершине и посмотреть, что наши методы предложат. И тут что хорошо? Хорошо, что мы знаем, какие на самом деле ребра следовало бы провести — ровно те, которые мы удалили. То есть, в принципе, наш метод, если он идеально сработает, он должен предложить просто ровно те же ребра. Конечно, не всегда это возможно, не всегда можно прямо угадать, что мы там удалили. Но тем не менее можно посмотреть, насколько близкий результат покажут наши методы. И так можно их сравнивать, можно оценивать их качество и все такое. [МУЗЫКА]
