Сказ царя Салтана о потенциале лапласиана

«Три девицы под окном пряли поздно вечерком.»

image

Ну как пряли. Не пряли, конечно, а лайкали друг на друга. По условиям конкурса «мисс Салтан» девицы должны были выбрать меж собой лучшую.

«Какой-то странный конкурс», — беспокоились девицы. И это было правдой. По правилам конкурса вес лайка участника зависел от того, сколько лайков он получает от других. Что это значит, — никто из девиц до конца не понимал.
«Как все сложно», — тосковали девушки и подбадривали себя песней «Кабы я была царицей».

Вскоре «в светлицу вошел царь — стороны той государь» (показан на рисунке). «Во все время разговора…», — ну понятно в общем.
«Собираем лайки нежности — формируем матрицу смежности», — бодро срифмовал он.
Девицы-красавицы с именами Алена, Варвара и Софья засмущались, но лайки (из балалайки) передали.

Вот что там было:

  • Алена получила 1 лайк от Софьи и 2 лайка от Варвары.
  • Варвара получила по лайку от Алены и Софьи.
  • А Софья получила 2 лайка от Алены и 1 от Варвары.


Царь взял лайки, покрутил гайки, постучал по колесам, пошмыгал носом, причмокнул губами, поскрипел зубами, сгонял в палаты и объявил результаты.

Наибольший вес лайков (7 баллов) получила Софья, но титул «мисс Салтан» достался Алене (15 баллов).

Подробнее о матрице лайков
Для матрицы
%5Cbegin%7Bmatrix%7D%0A%20%20%20%26%20A%

вектор потенциалов равен (5, 4, 7), а вектор потоков — (15, 12, 14).


После объявления результатов девицы бросились обратились к царю с просьбой рассказать,- откуда взялись эти странные цифры?

1. Уравнение баланса


В основе нашего мира лежит баланс. Это означает, что если в одном месте что-то прибыло, то в другом месте столько же убыло.

Физики демонстрируют данный баланс уравнением непрерывности для сплошных и непрерывных сред. Но в современном мире рулят танковые клинья дискретные системы — графы.

У графа есть узлы, через которые течет поток (ну как течет — толчками и нерегулярно). Принцип баланса прост — в узле графа остается разница между тем, сколько из него вытекло и сколько в него втекло. А куда течет поток из узла? Правильно — в другие узлы, соответственно втекает поток в узел тоже из других узлов.

Запишем это множество слов формулой:

%5Csum%5Climits_%7Bj%7D%20%7BJ_i_j%7D%20

Здесь %5Csum%5Climits_%7Bj%7D%20%7BJ_i_j%7D обозначает количество входящего потока в i-й узел, %5Csum%5Climits_%7Bj%7D%20%7BJ_j_i%7D — количество исходящего из узла потока, %5CDelta%20H_i — изменение остатка в узле.

Да, остатки в наших кошельках подчиняются данному уравнению баланса. И весь бухгалтерский учет на нем основан, — даже названия специальные придумали: исходящий поток — кредит, входящий — дебет.

Неизвестно, кто и почему ввел принцип баланса в естественные (физические) системы, но в основу искусственных систем (учет, рейтинги, кармы и пр.) лучше закладывать принцип баланса. Если мир выжил на балансе, то и у такой системы есть шанс.

В многих ситуациях (в частности с нашим конкурсом оценок) учет остатка в узле не нужен. То есть он всегда нулевой — сколько втекло — столько и вытекло. Игра с нулевой стоимостью нулевым остатком. Для таких систем уравнение упрощается:

%5Csum%5Climits_j%7BJ_i_j%7D%20%3D%20%5C

Круто. Но пока малополезно.

Баланс потенциалов


Когда мы говорили о том, что поток может течь из узла i в узел j, мы подразумевали, что есть некая связь между данными узлами. Иначе потоку просто не по чему течь. Связность узлов графа обычно называют матрицей смежности (связности), ее элементы обозначают через C_i_j. Применительно к потокам матрицу смежности также называют матрицей проводимости. Ее элементы отражают пропускную способность ребер графа.

Есть связь — есть поток, нет связи — нет потока. Логично предположить, что чем сильнее связь — тем больше поток.
Итак, поток между узлами пропорционален величине связи узлов. Но чему равен коэффициент пропорциональности?

Ответ будет немного туманный — поток из узла пропорционален некоему потенциалу узла.
Суть данного ответа в том, что узлы обладают неким потенциалом U_i и данный потенциал непосредственно определяет величину исходящего потока. Если, например, у нас есть два узла, проводимость между которыми одинакова в обоих направлениях (C_i_j%20%3D%20C_j_i), то суммарный поток между узлами будет определяться разностью потенциалов данных узлов. Существование электрических сетей доказывает, что это реально работает.

Связь потока с потенциалами и проводимостью выражается простой формулой:

J_i_j%20%3D%20C_i_j%20U_i%5Cquad(1.3)

Подставляя (1.3) в уравнение баланса (1.2) получаем систему уравнений для расчета потенциалов узлов:

U_i%5Csum%5Climits_j%7BC_i_j%7D%20%3D%20

В данном уравнении известными являются проводимости, а неизвестными — потенциалы.
Количество уравнений в системе равно количеству узлов графа. Решение системы балансовых уравнений является прямой задачей расчета потенциалов (и потоков) графа.

В уравнении (1.4) мы использовали понятие общей проводимости исходящих из узла связей — степень узла:

C_i%20%3D%20%5Csum%5Climit_j%7BC_i_j%7D%

Рейтинги и самооценки


«Все это здорово,» — сказали девушки, зевая. — «Но причем тут лайки?»

В системах голосования, при которых участники оценивают друг друга, оценки берутся с учетом веса голоса каждого участника. А вес голоса опять же зависит от того, как данного участника оценили другие.

Связываем с потоками. Когда i-й участник с весом голоса U_i оценивает j-го участника с оценкой (количеством лайков) C_i_j то он делится с ним своим потоком C_i_jU_i. Копить остатки тут ни к чему, поэтому каждый участник делится с остальными всем, что получил.

Вес голоса участника — это потенциал U_i, матрица лайков — это матрица смежности (связности), а итоговая оценка — суммарный полученный (он же отданный) поток J_i.

Для ранжирования участников (определения лучших) нам надо решить уравнение баланса (1.4), то есть определить веса участников, которые сбалансируют систему.

2. Лапласианы


Когда я был молодым и глупым впервые столкнулся с уравнением баланса (1.4), я уже умел программировать и знал про циклы. Поэтому решал его как программист — методом последовательных итераций. Задаем начальный вектор потенциалов, умножаем его на матрицу смежности, делим на степени узлов, получаем новый вектор потенциалов и т. д. Как правило, процесс сходится. А вспомнил я про молодость, прочитав статью о ценностях пьяницы, которая в общем и побудила меня «расчехлить формулы».

Помню «вау-эффект», когда я узнал о том, что есть и другой способ расчета потенциалов, о котором, видимо, знали еще наши деды Лаплас и Кирхгоф. Способ основывается на свойствах матриц-лапласианов. Тут уже недавно вспоминали лапласианы в непрерывных средах. Дискретные лапласианы не менее интересны и важны.

Для того, чтобы определить матрицу лапласиана по заданной матрице смежности, используем веденное выше понятие степени узлов. Степени узлов расположим по диагонали лапласиана, а остальные элементы возьмем из матрицы смежности с обратным знаком. Получившуюся матрицу называют также матрицей Кирхгофа:

K%20%3D%20L(C)%20%3D%20E(C_i)%20-%20C%0A

Тут можно посмотреть лапласиан от наших лайков
%5Cbegin%7Bmatrix%7D%0A%20%20%26%20A%20%

Примем, что проводимость исходящих из узла i дуг задается в i-м столбце матрицы. Соответственно в i-й строке матрицы — проводимость входящих в узел дуг. Тогда сумма элементов каждого столбца лапласиана равна нулю.

Вообще говоря, матрицы данного вида образуют отдельный класс, — лапласианы. Определитель лапласианов всегда равен нулю, поэтому, например, для них не существует обычной обратной матрицы. Но зато есть другая (псевдо)обратная, есть и своя единичная матрица. Получить лапласиан можно не только приведенным выше преобразованием. Например, преобразование девиации тоже дает лапласиан на выходе.

Лапласианы могут быть симметричными — в них потенциалы всех узлов равны между собой — для нашей задачи они пока неинтересны.

Матрица Кирхгофа относится к классу лапласианов.

Потенциалы лапласианов


В линейной алгебре есть понятие дополнительного минора матрицы — это определитель матрицы, полученной из исходной вычеркиванием строк и столбцов. Дополнительные миноры играют большую роль в лапласианах.

Потенциалом 1-го порядка лапласиана называется определитель матрицы, полученный вычеркиванием из исходного лапласиана одной строки и одного столбца.

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

Итак, если обозначить через A_j%5Ei(M) дополнительный минор матрицы, то определение потенциала лапласиана можно записать как

U_i%20%3D%20A_i%5Ei(K)%5Cquad(2.2)

Так вот эти потенциалы 1-го порядка от матрицы Кирхгофа и являются искомым решением уравнения (1.4).
Удивительно. Не нужны никакие циклы, начальные присваивания, произведение матриц и пр. Удалил строку/колонку, посчитал определитель — получил ответ.

Свойства потенциалов 1-го порядка
  • Потенциал узла представляет собой сумму произведений (кортежей) проводимостей ребер графа по всем возможным путям в данный узел, исключая контуры (циклы).
  • Количество множителей в произведении на 1 меньше размерности (количества узлов) графа.
  • Потенциал узла не зависит от проводимостей исходящих из него дуг.
  • Каждый кортеж (путь) в выражении для потенциала узла состоит из дуг, которые исходят из всех узлов, кроме данного. В одном кортеже нет двух дуг, исходящих из одного узла, но могут быть дуги, входящие в один узел.
  • В каждом кортеже (пути) обязательно присутствует дуга, входящая в узел (замкнутость).
  • В выражении для потенциала отсутствуют кортежи, содержащие циклы (контуры).
  • Количество кортежей в выражении для потенциала определяется известной формулой Кэли N_u%20%3D%20n%5E%7B(n-2)%7D, и быстро растет с ростом узлов графа. Для 4-х узлов имеем 4^2 = 16 слагаемых, для пяти — 5^3 = 125 и т. д.
  • В симметричном графе потенциалы всех узлов равны — следствие того, что структура выражения для потенциалов всех узлов одна и та же (разница лишь в направлении).

Для определения потока через узел достаточно умножить потенциал узла на его степень:

F_i%20%3D%20U_iC_i%20%3D%20A_i%5Ei(K)C_i

Мы получили, что хотели.

Считаем лайки

Как считать потенциалы больших графов


Если граф большой (много узлов), то считать вектор потенциалоф через вычисление определителей миноров лапласиана неудобно (затратно). В таких ситуациях лучше использовать обращение матрицы. Алгоритм следующий:

  • В матрице лапласиана заменяем первую строку на вектор (1, 0, 0, …).
  • Считаем обратную матрицу от полученной и находим ее детерминант.
  • Делим значения первой колонки полученной обратной матрицы на ее детерминант. Это и есть искомый вектор потенциалов. В первой строке — потенциал первого узла, во второй — второй и т. д.
  • Если абсолютное значение потенциала неважно, то считать и делить на детерминант необязательно.

Ранжирование объектов на основе потенциалов и потоков


По итогам нашего примера получилось так, что наибольший вес голоса получила Софья, но больше всего баллов набрала Алена.
Это означает, что авторитетные и избранные — это не одно и тоже.

Что именно должно служить основанием для ранжирования, — потенциалы или потоки,- требует отдельного рассмотрения в каждой задаче, поскольку определяется прикладным аспектом.

Результаты турниров


Рассмотрим применение системы ранжирования применительно к определениям итогов шахматного турнира. Справедлива ли нынешняя система определения победителя простой суммой очков? На наш взгляд, она имеет лишь одно достоинство — простота. Но в век смартфонов кого волнует простота?
Несправедливо то, что выигрыш сильного по сути приравнивается в «простой системе» выигрышу у слабого.

Современный и правильный подход — считать взвешенные очки, то есть использовать расчет потенциалов и потоков. Еще один плюс — при данной системе практически исключена дележка мест — не надо думать о том, что делать при равенстве очков.

Как раз недавно в Москве закончился турнир претендентов (поздравляем Сергея Карякина с победой!), по итогам которого большое количество участников поделило места (2–3, 4–7). Используя метод потенциалов, попробуем разобраться, кто же какое место занял на самом деле.

Результаты турнира — это матрица смежности графа. В терминах лайков проигрыш участника — это проставление лайка победителю (хотя и звучит немного непривычно). От проигравшего к победителю идет поток взвешенных очков.

А что такое потенциал применительно к игрокам?
Потенциал — это показанная участником сила игры (в данном турнире). Чем выше потенциал участника — тем большую ценность имеют очки, полученные от него другими.
Возможно ли, чтобы менее сильный игрок набрал большее количество очков, чем более сильный? Да, такое вполне возможно, хоть и бывает не так часто. Например, на упомянутом турнире претендентов сила участника и набранные им очки совпали — ранжирование по потенциалам и потокам оказались эквивалентными.

Для интересующихся подробностями
Мы нормировали потенциалы и потоки так, чтобы их сумма была равна 100.
Сергей Карякин Хикару Накамура Аниш Гири Виши Ананд Веселин Топалов Левон Аронян Фабиано Каруана Петр Свидлер
U 17,8 11,4 12,5 13,7 6,4 12,0 13,8 12,4
J 14,5 11,8 13,0 13,2 9,0 12,4 13,3 12,8
М 1 7 4 3 8 6 2 5

Каруана все-таки второй, а Гири — 4-й.


Потенциалы пьяницы


Последний пример, который мы рассмотрим в данной статье — это расчет ценности карт в народной игре «Пьяница».
Спасибо за данный пример astgtciv. Без его статьи, возможно, не было бы и этой.

Подробности о постановке задачи есть в упомянутой статье, — карты бьют друг друга по правилам старшинства, но пи этом шестерка бьет туза.
Данная задача хороша тем, что значения потенциалов (хм, а потоки тут что значат?) могут быть выражены в явном виде — несложными формулами.

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

C_n%20%3D%20%5Cbegin%7Bpmatrix%7D%0A%20-

Ключевая особенность — в правом нижнем углу — «шестерка бьет туза».
Тогда матрица Кирхгофа будет иметь вид:

K_n%20%3D%20%5Cbegin%7Bpmatrix%7D%0A%201

Теперь наглядно видно, почему потенциал «шестерки» равен (n-2)! Потому что вычеркнув колонку и столбец шестерки, мы получаем треугольную матрицу, определитель которой считается простым умножением элементов главной диагонали.
То же самое справедливо и для туза с той лишь разницей, что у него в составе множителей два раза встречается элемент (n-2). Поэтому сразу видно, что потенциал туза всегда в (n-2) раза больше потенциала шестерки.

Сводка формул
Выражения для потенциалов от туза до шестерки:
U(1%2Cn)%20%3D%20(n-2)!(n-2)%20%5C%5C%0A

Интересно, что сумма потенциалов всех карт (кроме шестерки и туза) равна потенциалу туза:
%5Csum_k%7BU(k%2Cn)%7D%20%3D%20U(1%2Cn)

Заключение

Сколько могли старались и слушали девицы сказ царя Салтана про возможности лапласиана, да все равно сморил их крепкий сон.
Снились им добры-молодцы с большим потенциалом, управляющие крупными потоками.

Пришла и нам пора закругляться. Используйте потенциалы!

© Habrahabr.ru