Потоки и потенциалы в графах (1)
Для того, чтобы писать в ЖЖ, надо перестать его читать.
Итак, интерес к справедливой системе расчета рейтинга (шахматистов) неожиданно вывел меня на некоторые математические находки, которые стоят того, чтобы их зафиксировать. Абсолютно несвязанные, казалось бы, задачи/проблемы замыкаются на свойствах потоков в сетях (графах).
Изначально мне были интересны проблемы ранжирования однородных объектов - например, ранжирование сайтов по релевантности (PageRanking), ранжирование объектов метаданных, ранжирование участников соц. групп... Например, оказалось, что можно проводить голосование внутри коллектива, при котором каждый участник может оценивать других по любой удобной ему шкале. Система расчета (основанная на балансе потоков графа) сама приведет все оценки к единой базе, определит вес голоса участников и рассчитает конечный результат голосования с учетом оценок и веса голосовавших.
В процессе вникания в тему ранжирования выяснилось, что математическими сходными являются расчеты в марковских цепях, электрических потенциалов и токов, потоков в сетях, ну и далее - везде. Графы - это повсеместно встречающийся объект, поскольку выражает наиболее распространенный вид отношений - дуальных.
Далее абстрагируемся от прикладного уровня и рассмотрим математику расчета потоков в графах.
Определение графа потоков выглядит следующим образом. Дан орграф (набор узлов/вершин и ориентированных связей/ребер между ними), связи которого имеют некий вес (пропускная способность ребра). Отсутствие связи - нулевой вес. Через узлы и ребра графа проходит некий поток F (неважно чего). Требуется рассчитать величину потока во всех ребрах и вершинах при условии, что для каждой вершины выполняется условие баланса потока - сумма входящих потоков равна исходящим.
Обозначим через Fij поток, исходящий из узла j в узел i (мы используем "турнирную индексацию",- она отличается от общепринятой для графов и марковских цепей). Общий поток через узел обозначим как F с одним индексом - Fi.
Тогда уравнение баланса можно записать как
Sum(Fij, j) = Sum(Fij, i) = Fi (1)
Для расчета потоков между узлами вводим потенциалы для каждого узла - Ri. Тогда поток Fij через ребро Wij рассчитывается как
Fij = Rj Wij (2)
Подставляя (2) в (1), получаем систему линейных уравнений (относительно Ri). Решается обычно итерационно. Здесь все просто и особых проблем нет. Поскольку система вырождена, то полученное решение можно нормировать (умножать компоненты Ri на любую константу).
Следует отметить следующее важное свойство потенциалов Ri и потоков Fi. Величина потенциала Ri не зависит от диагональных элементов матрицы смежности Wij (диагональные элементы - это соединение узла с самим собой). Но диагональные элементы вносят вклад в величину потока через узел Fi.
Что же необычного обнаружилось в системе уравнений? Существование способа представления решения в аналитическом виде. Например, для графа из трех узлов (3-мерной матрицы W):
* W12 W13
W21 * W23
W31 W32 *
Выражение для потенциала R1 имеет вид:
R1 = W12 W23 + W12 W13 + W32 W13 (3) (выражения для R2 и R3 получаются из (3) перестановкой индексов (1-2), (1-3)).
На основе данного выражения можно вывести правила получения решений для графов любых размерностей. Желающие могут сделать это самостоятельно. (Продолжение следует...)
Итак, интерес к справедливой системе расчета рейтинга (шахматистов) неожиданно вывел меня на некоторые математические находки, которые стоят того, чтобы их зафиксировать. Абсолютно несвязанные, казалось бы, задачи/проблемы замыкаются на свойствах потоков в сетях (графах).
Изначально мне были интересны проблемы ранжирования однородных объектов - например, ранжирование сайтов по релевантности (PageRanking), ранжирование объектов метаданных, ранжирование участников соц. групп... Например, оказалось, что можно проводить голосование внутри коллектива, при котором каждый участник может оценивать других по любой удобной ему шкале. Система расчета (основанная на балансе потоков графа) сама приведет все оценки к единой базе, определит вес голоса участников и рассчитает конечный результат голосования с учетом оценок и веса голосовавших.
В процессе вникания в тему ранжирования выяснилось, что математическими сходными являются расчеты в марковских цепях, электрических потенциалов и токов, потоков в сетях, ну и далее - везде. Графы - это повсеместно встречающийся объект, поскольку выражает наиболее распространенный вид отношений - дуальных.
Далее абстрагируемся от прикладного уровня и рассмотрим математику расчета потоков в графах.
Определение графа потоков выглядит следующим образом. Дан орграф (набор узлов/вершин и ориентированных связей/ребер между ними), связи которого имеют некий вес (пропускная способность ребра). Отсутствие связи - нулевой вес. Через узлы и ребра графа проходит некий поток F (неважно чего). Требуется рассчитать величину потока во всех ребрах и вершинах при условии, что для каждой вершины выполняется условие баланса потока - сумма входящих потоков равна исходящим.
Обозначим через Fij поток, исходящий из узла j в узел i (мы используем "турнирную индексацию",- она отличается от общепринятой для графов и марковских цепей). Общий поток через узел обозначим как F с одним индексом - Fi.
Тогда уравнение баланса можно записать как
Sum(Fij, j) = Sum(Fij, i) = Fi (1)
Для расчета потоков между узлами вводим потенциалы для каждого узла - Ri. Тогда поток Fij через ребро Wij рассчитывается как
Fij = Rj Wij (2)
Подставляя (2) в (1), получаем систему линейных уравнений (относительно Ri). Решается обычно итерационно. Здесь все просто и особых проблем нет. Поскольку система вырождена, то полученное решение можно нормировать (умножать компоненты Ri на любую константу).
Следует отметить следующее важное свойство потенциалов Ri и потоков Fi. Величина потенциала Ri не зависит от диагональных элементов матрицы смежности Wij (диагональные элементы - это соединение узла с самим собой). Но диагональные элементы вносят вклад в величину потока через узел Fi.
Что же необычного обнаружилось в системе уравнений? Существование способа представления решения в аналитическом виде. Например, для графа из трех узлов (3-мерной матрицы W):
* W12 W13
W21 * W23
W31 W32 *
Выражение для потенциала R1 имеет вид:
R1 = W12 W23 + W12 W13 + W32 W13 (3) (выражения для R2 и R3 получаются из (3) перестановкой индексов (1-2), (1-3)).
На основе данного выражения можно вывести правила получения решений для графов любых размерностей. Желающие могут сделать это самостоятельно. (Продолжение следует...)