Pull to refresh

Проблемы обобщения PageRank

Reading time4 min
Views2.1K
Если на вас ссылается кто-то авторитетный, это поднимает ваш статус больше, чем ссылки («голоса») от многих малоавторитетных источников — такова была первоначальная идея ранжирования сайтов Гуглом. Она нашла свое очевидное продолжение в social network analysis, где формула для PageRank является разновидностью центральностей, т.е. определением того, какой из узлов социального графа является более «центральным» и по какому признаку. Я не специалист в данной тематике; из беглого осмотра по диагонали мне показалось, что social network analysis в интернете применяется в основном для нужд social media marketing, где ранжирование людей не является основной целью. Скорее, цель smm — эффективней продвигать бренды, увеличивать продажи и т. п. Однако ранжирование людей может быть самостоятельной интересной целью. Вот здесь я краткотезисно перечислил эти интересы.

Прямое применение формулы PageRank для ранжирования людей вызывает вопросы; мне не хватает компетенций чтобы на них ответить, надеюсь на отклик знающего сообщества.

1. Классический PageRank сайта имеет вероятностную интерпретацию — это вероятность того, что человек путем беспорядочного кликания по ссылкам попадет на данный сайт. При этом учитывается damping factor, т.е. то обстоятельство, что пользователь не кликает бесконечно. С математической точки зрения damping factor обеспечивает единственность решения задачи ранжирования. Но если речь о ранжировании людей, вероятностная интерпретация теряет смысл. Непонятно тогда, как толковать damping factor. Разве что абстрактно — для регуляризации задачи, как полагает Дмитрий Шепелянский. И какое его значение будет адекватным в этом случае.

2. Другая проблема связана с тем, что считать ссылкой или голосом в отношении людей. Для сайтов есть только один тип голоса — гиперссылка, тогда как для людей в качестве голоса можно рассматривать самые разные вещи. Наиболее очевидное — френд-связи в блогах и соцсетях. Но например наличие комментариев к вашему топику — тоже по сути «голоса» в вашу пользу, т.к. тема привлекла интерес и внимание аудитории. Сюда же отнесем лайки, ретвиты, факты прочтения и прочее. Обобщим: любое проявление внимания к автору или его контенту является голосом. Отсюда возникают еще проблемы.

3. Например голос по карме от случайного читателя нельзя считать равнозначным френд-связи. Или опять же один комментарий не равнозначен регулярному комментированию от одного и того же автора. Поэтому матрица, кодирующая социальный граф (adjacency matrix), должна содержать веса связей. Насколько я понимаю, в случае Google matrix связи по сути и являются взвешенными, т.к. один узел раздает ранки обратно пропорционально количеству исходящих из него связей и получается, что связи во всем графе различаются по своей «силе». Иначе говоря, проблемы со стороны математики здесь вроде бы нет, вопрос лишь в адекватном определении весов (хотя он нетривиальный сам по себе).

4. В классической формуле PageRank, если есть ссылка на сайт, то передаваемое значение ранка не может быть отрицательным. Неотрицательность ранков любого узла позволяет применять теорему Перрона-Фробениуса о существовании решения. Но голос по карме может быть отрицательным, комментарий может быть негативным и т. д. Возможность передачи отрицательных значений ранков между узлами социального графа, по-видимому, требует математического доказательства существования и единственности решения задачи ранжирования в такой постановке.

5. Классический PageRank применяется к сети однородных объектов, т.е. объектов одного типа — «сайт». Но как выше сказано, при ранжировании людей внимание может проявляться как непосредственно к автору (голос по карме, френд-связь, рекомендация на LinkedIn и т. п.), так и косвенно через реакцию на его контент. Последний случай причем распространен в интернете — мы чаще оцениваем людей по их контенту, чем через личное знакомство. А авторы и единицы контента образуют уже сеть разнородных объектов, в которой например высокорейтинговый пост может «голосовать» за его автора. Судя по вот этому посту, в методиках ранжирования Witology это обстоятельство каким-то образом учли. В плане математики рейтинг от агенства PRUFFI отнюдь не столь же продвинут, но акцентируется на другом важном аспекте — при рейтинговании людей вполне имеет смысл учитывать рейтинг организаций, в которых они работают. Если под организациями понимать довольно абстрактную вещь — любые проекты с участием рейтингуемого человека, тоже получим сеть разнородных объектов, в которых объекты разных типов передают друг другу ранки.

6. В реальной сети связи не только имеют разный вес, но этот вес еще зависит от времени. Сегодня люди дружат, а завтра они враждуют.

С учетом сказанного, данная проблематика относится, по-видимому, к развивающейся ныне области Dynamic network analysis.

Не хочется записывать седьмым пунктом, поскольку это лично мое непонимание, но у меня на простенькой тестовой задачке вычисления PageRank в сети из четырех узлов получается, что если узел не имеет исходящих связей, то ранки всех узлов сети в конечном счете обнуляются. В одном месте я нашел, как человек исключил все такие узлы из рассмотрения. Это понять можно, но ведь Гугл присваивает значение PR любым сайтам, включая те что не имеют ссылок на другие сайты. В другом месте написано, что узлы без исходящих связей следует заменить узлами, которые имеют исходящие связи сразу ко всем другим узлам сети. Но не очень понятно, почему следует сделать именно так и как это влияет на результаты ранжирования.
Tags:
Hubs:
Total votes 12: ↑6 and ↓60
Comments10

Articles