Потоки и потенциалы в графах. Ранжирование объектов
Надо придать некую законченность постам, поднявшись с фундаментальных вопросов на прикладной уровень. Как баланс потоков графа связан с методикой ранжирования объектов PageRanking?
В основе алгоритма ранжирования объектов (сайтов) PageRanking лежит расчет вероятностей состояний на основе матрицы переходов марковской цепи. Роль матрицы переходов играет матрица взаимных ссылок объектов (сайтов) друг на друга. При этом ссылки с одного сайта нормируются к 1 - чем больше ссылок с данного сайта,- тем меньше вес каждой ссылки (все как в марковской цепи - суммарная вероятность перехода с данного узла равна 1).
Неудобство использования вероятностного (марковского) подхода при ранжировании объектов - в нормировании веса ссылок перед расчетом. Это приводит к тому, что для расчета вероятностей состояний необходимо при изменении количества ссылок на каком-либо сайте пересчитывать заново все веса ссылок с данного сайта.
Подход через баланс потоков не требует нормировки. Или правильнее сказать иначе (поскольку конечный результат один и тот же),- нормировка учитывается после расчета (а не до).
При расчете по методу баланса потоков мы сначала рассчитываем потенциалы узлов Ri, а затем на основе потенциалов - потоки через данные узлы Fi. Итоговая величина потоков и вероятности соответствующих состояний пропорциональны друг другу.
Интересной особенностью данной методики (баланса потоков) является, например, то, что можно проводить самооценку некой группы участников без навязывания шкалы оценок. Каждый может оценивать остальных по удобной ему шкале - кто-то от 1 до 5 баллов, а кто-то от 1 до 100. Методика сама приведет все шкалы к единому знаменателю.
При расчете ранга участника мы получаем два основных показателя:
* вес (голоса) участника - определяет вес его оценок другим участникам (в терминах графа - это потенциал R),
* ранг участника - сколько голосов получил данный участник (в терминах графа - это поток через узел F).
Вес (оценки) и ранг участника - не одно и то же.
Пример.
Три участника дали следующие оценки друг друга:
A B C
A * 2 1
B 1 * 1
C 2 1 *
Здесь участник A отдал два голоса за участника C и один голос за участника B и т.д.
Вектор веса участников (потенциал R) имеет следующее значение (с точностью до множителя): (5, 4, 7). Здесь вес участника A равен 5. Наибольший вес имеет участник C - 7.
Вектор рангов участников: (15, 12, 14). Видим, что наибольший ранг имеет участник А. Вот такой кажущийся парадокс. Естественно, что расчет по алгоритму PageRanking даст с точностью до множителя тот же ранг участников.
При желании можно системно регулировать вес определенных участников через диагональные элементы матрицы оценок. Как отмечалось ранее, диагональные элементы не влияют на вес (потенциал), но влияют на ранг (поток).
В идеале, по приведенной схеме стоило бы проводить любые выборы и самооценки членов соц. групп - оптимальное сочетание демократии и элитности.
Да, и самое главное. Для метода баланса потоков существует алгоритм быстрого приближенного расчета рангов (приведен в предыдущих постах). Это востребовано там, где количество объектов огромно, а точное значение ранга неважно,- важен лишь сам порядок рангов. Использование подобных приближений в классическом PageRanking мне неизвестно. Вроде бы поисковики периодически выполняют пересчет рангов сайтов,- но не слишком часто именно ввиду большой трудоемкости обсчета.
В основе алгоритма ранжирования объектов (сайтов) PageRanking лежит расчет вероятностей состояний на основе матрицы переходов марковской цепи. Роль матрицы переходов играет матрица взаимных ссылок объектов (сайтов) друг на друга. При этом ссылки с одного сайта нормируются к 1 - чем больше ссылок с данного сайта,- тем меньше вес каждой ссылки (все как в марковской цепи - суммарная вероятность перехода с данного узла равна 1).
Неудобство использования вероятностного (марковского) подхода при ранжировании объектов - в нормировании веса ссылок перед расчетом. Это приводит к тому, что для расчета вероятностей состояний необходимо при изменении количества ссылок на каком-либо сайте пересчитывать заново все веса ссылок с данного сайта.
Подход через баланс потоков не требует нормировки. Или правильнее сказать иначе (поскольку конечный результат один и тот же),- нормировка учитывается после расчета (а не до).
При расчете по методу баланса потоков мы сначала рассчитываем потенциалы узлов Ri, а затем на основе потенциалов - потоки через данные узлы Fi. Итоговая величина потоков и вероятности соответствующих состояний пропорциональны друг другу.
Интересной особенностью данной методики (баланса потоков) является, например, то, что можно проводить самооценку некой группы участников без навязывания шкалы оценок. Каждый может оценивать остальных по удобной ему шкале - кто-то от 1 до 5 баллов, а кто-то от 1 до 100. Методика сама приведет все шкалы к единому знаменателю.
При расчете ранга участника мы получаем два основных показателя:
* вес (голоса) участника - определяет вес его оценок другим участникам (в терминах графа - это потенциал R),
* ранг участника - сколько голосов получил данный участник (в терминах графа - это поток через узел F).
Вес (оценки) и ранг участника - не одно и то же.
Пример.
Три участника дали следующие оценки друг друга:
A B C
A * 2 1
B 1 * 1
C 2 1 *
Здесь участник A отдал два голоса за участника C и один голос за участника B и т.д.
Вектор веса участников (потенциал R) имеет следующее значение (с точностью до множителя): (5, 4, 7). Здесь вес участника A равен 5. Наибольший вес имеет участник C - 7.
Вектор рангов участников: (15, 12, 14). Видим, что наибольший ранг имеет участник А. Вот такой кажущийся парадокс. Естественно, что расчет по алгоритму PageRanking даст с точностью до множителя тот же ранг участников.
При желании можно системно регулировать вес определенных участников через диагональные элементы матрицы оценок. Как отмечалось ранее, диагональные элементы не влияют на вес (потенциал), но влияют на ранг (поток).
В идеале, по приведенной схеме стоило бы проводить любые выборы и самооценки членов соц. групп - оптимальное сочетание демократии и элитности.
Да, и самое главное. Для метода баланса потоков существует алгоритм быстрого приближенного расчета рангов (приведен в предыдущих постах). Это востребовано там, где количество объектов огромно, а точное значение ранга неважно,- важен лишь сам порядок рангов. Использование подобных приближений в классическом PageRanking мне неизвестно. Вроде бы поисковики периодически выполняют пересчет рангов сайтов,- но не слишком часто именно ввиду большой трудоемкости обсчета.