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



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

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

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

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

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

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

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


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

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

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

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

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

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



Здесь обозначает количество входящего потока в i-й узел, — количество исходящего из узла потока, — изменение остатка в узле.

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

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

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



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

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

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

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

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

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



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



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

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

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

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

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

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

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

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

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

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

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

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





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

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

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

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

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

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

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

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

Итак, если обозначить через дополнительный минор матрицы, то определение потенциала лапласиана можно записать как



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




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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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



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

Заключение

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

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