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

    Если на вас ссылается кто-то авторитетный, это поднимает ваш статус больше, чем ссылки («голоса») от многих малоавторитетных источников — такова была первоначальная идея ранжирования сайтов Гуглом. Она нашла свое очевидное продолжение в 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 любым сайтам, включая те что не имеют ссылок на другие сайты. В другом месте написано, что узлы без исходящих связей следует заменить узлами, которые имеют исходящие связи сразу ко всем другим узлам сети. Но не очень понятно, почему следует сделать именно так и как это влияет на результаты ранжирования.

    Комментарии 10

      +2
      Не понятен посыл топика.
      Есть формула расчёта PR, есть куча неквантифицируемых данных. Алгоритм работает со значительным усреднением, вы хотите идеала? :) Среди графа в 100млрд связей? :)

      «С учетом сказанного, данная проблематика относится, по-видимому, к развивающейся ныне области Dynamic network analysis. » Вы уж простите, но подобная фраза из разряда — «для того, чтобы было». Анализ взаимосвязей знания и совокупностей знаний — давняя проблема человека, сейчас он применяет численных, переборные методы, но они, к сожалению (или к счастью) не показывают даже приблизительной картины.
        –2
        seo-шнигэ такие сеошнигэ, всегда ищут смысл там, где его очень мало.
          0
          Я просто нахожу задачу интересной, направление перспективным, а готового решения не вижу. Есть готовая формула для PageRank, но топик и посвящен проблематичности её прямого применения. И кстати я не сеошнег ни разу )
            0
            А готового решения нет, все алгоритмы подсчёта популярности наталкиваются на человеческий фактор. Что и показывает опыт применения PageRank от Брина и Пейджа (спам, линкфермы, продажа ссылок).
              0
              Ну не сразу же наталкиваются. Сеошники появились позже на фоне популярности поисковых сервисов. Вот и здесь то же; я предвижу популярность ранжирования людей не меньшую, чем ранжирование сайтов, и да, на этой волне тоже появятся свои оптимизаторы. Но это проблема завтрашнего дня. Сегодняшняя проблема — как PeopleRank посчитать. Хотя бы для начала в идеальных условиях отсутствия сеошников.
                0
                Нет, seo-шники были всегда, кто-то и в 19 веке ссылался на учёного типа Петрика и говорил — знаешь что он там «лабает»? Это мир перевернёт, ну и.т.д.
        0
        Есть модифицированные алгоритмы взвешенного PageRank'а. Согласование весов, конечно, тоже задача. Кстати, по пункту 3 — обратнопропорциональная раздача ранков еще не означает их взвешенности, это просто свойство алгоритма, как мне кажется.

        Есть еще другие метрики для графов: центральность, коэффициент кластеризации. Для орграфов тут вообще еще есть над чем думать. Можно намутить много всего :)
          0
          По пункту 3 вы наверное правы. Просто хотел сказать, что в гугломатрице записано больше информации, чем в просто в adjacency matrix, и она сродни информации о весах.

          Насчет других метрик тоже согласен, но с их применением вроде нет проблем. Бери как говорится да считай. Единственная проблема, что объем вычислений говорят пропорционален кубу от количества узлов сети )) Но думается совсем всех считать необязательно. Как говорил один гуглер, большое значение имеет только топ. Конечный рейтинг людей думаю должен быть суммой разных центральностей. И прочих факторов, если конечно эти дополнительные факторы не будут уже учтены в разнородности сети.
          0
          Там одинаковое количество информации: из adjacency можно получить гугломатрицу проведя итерации pagerank'а.

          Чтобы получить топ иногда надо просчитать весь граф :)
            0
            Грубыми сравнительно дешевыми методами считаем всех, а потом более точными и затратными считаем все более и более топовых.

            Про adjacency не соображу сразу что за итерации, может можно одно из другого получить. Но суть сказанного это вроде не меняет?

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое