![image](https://habrastorage.org/files/fc0/b5f/0be/fc0b5f0be95a47e1872561f28ae1056f.jpg)
Ну как пряли. Не пряли, конечно, а лайкали друг
«Какой-то странный конкурс», — беспокоились девицы. И это было правдой. По правилам конкурса вес лайка участника зависел от того, сколько лайков он получает от других. Что это значит, — никто из девиц до конца не понимал.
«Как все сложно», — тосковали девушки и подбадривали себя песней «Кабы я была царицей».
Вскоре «в светлицу вошел царь — стороны той государь» (показан на рисунке). «Во все время разговора...», — ну понятно в общем.
«Собираем лайки нежности — формируем матрицу смежности», — бодро срифмовал он.
Девицы-красавицы с именами Алена, Варвара и Софья засмущались, но лайки (из балалайки) передали.
Вот что там было:
- Алена получила 1 лайк от Софьи и 2 лайка от Варвары.
- Варвара получила по лайку от Алены и Софьи.
- А Софья получила 2 лайка от Алены и 1 от Варвары.
Царь взял лайки, покрутил гайки, постучал по колесам, пошмыгал носом, причмокнул губами, поскрипел зубами, сгонял в палаты и объявил результаты.
Наибольший вес лайков (7 баллов) получила Софья, но титул «мисс Салтан» достался Алене (15 баллов).
вектор потенциалов равен (5, 4, 7), а вектор потоков — (15, 12, 14).
После объявления результатов девицы
1. Уравнение баланса
В основе нашего мира лежит баланс. Это означает, что если в одном месте что-то прибыло, то в другом месте столько же убыло.
Физики демонстрируют данный баланс уравнением непрерывности для сплошных и непрерывных сред. Но в современном мире рулят
У графа есть узлы, через которые течет поток (ну как течет — толчками и нерегулярно). Принцип баланса прост — в узле графа остается разница между тем, сколько из него вытекло и сколько в него втекло. А куда течет поток из узла? Правильно — в другие узлы, соответственно втекает поток в узел тоже из других узлов.
Запишем это множество слов формулой:
Здесь
Да, остатки в наших кошельках подчиняются данному уравнению баланса. И весь бухгалтерский учет на нем основан, — даже названия специальные придумали: исходящий поток — кредит, входящий — дебет.
Неизвестно, кто и почему ввел принцип баланса в естественные (физические) системы, но в основу искусственных систем (учет, рейтинги, кармы и пр.) лучше закладывать принцип баланса. Если мир выжил на балансе, то и у такой системы есть шанс.
В многих ситуациях (в частности с нашим конкурсом оценок) учет остатка в узле не нужен. То есть он всегда нулевой — сколько втекло — столько и вытекло. Игра с
Круто. Но пока малополезно.
Баланс потенциалов
Когда мы говорили о том, что поток может течь из узла i в узел j, мы подразумевали, что есть некая связь между данными узлами. Иначе потоку просто не по чему течь. Связность узлов графа обычно называют матрицей смежности (связности), ее элементы обозначают через
Есть связь — есть поток, нет связи — нет потока. Логично предположить, что чем сильнее связь — тем больше поток.
Итак, поток между узлами пропорционален величине связи узлов. Но чему равен коэффициент пропорциональности?
Ответ будет немного туманный — поток из узла пропорционален некоему потенциалу узла.
Суть данного ответа в том, что узлы обладают неким потенциалом
Связь потока с потенциалами и проводимостью выражается простой формулой:
Подставляя (1.3) в уравнение баланса (1.2) получаем систему уравнений для расчета потенциалов узлов:
В данном уравнении известными являются проводимости, а неизвестными — потенциалы.
Количество уравнений в системе равно количеству узлов графа. Решение системы балансовых уравнений является прямой задачей расчета потенциалов (и потоков) графа.
В уравнении (1.4) мы использовали понятие общей проводимости исходящих из узла связей — степень узла:
Рейтинги и самооценки
«Все это здорово,» — сказали девушки, зевая. — «Но причем тут лайки?»
В системах голосования, при которых участники оценивают друг друга, оценки берутся с учетом веса голоса каждого участника. А вес голоса опять же зависит от того, как данного участника оценили другие.
Связываем с потоками. Когда i-й участник с весом голоса
Вес голоса участника — это потенциал
Для ранжирования участников (определения лучших) нам надо решить уравнение баланса (1.4), то есть определить веса участников, которые сбалансируют систему.
2. Лапласианы
Когда я
Помню «вау-эффект», когда я узнал о том, что есть и другой способ расчета потенциалов, о котором, видимо, знали еще
Для того, чтобы определить матрицу лапласиана по заданной матрице смежности, используем веденное выше понятие степени узлов. Степени узлов расположим по диагонали лапласиана, а остальные элементы возьмем из матрицы смежности с обратным знаком. Получившуюся матрицу называют также матрицей Кирхгофа:
Примем, что проводимость исходящих из узла i дуг задается в i-м столбце матрицы. Соответственно в i-й строке матрицы – проводимость входящих в узел дуг. Тогда сумма элементов каждого столбца лапласиана равна нулю.
Вообще говоря, матрицы данного вида образуют отдельный класс, — лапласианы. Определитель лапласианов всегда равен нулю, поэтому, например, для них не существует обычной обратной матрицы. Но зато есть другая (псевдо)обратная, есть и своя единичная матрица. Получить лапласиан можно не только приведенным выше преобразованием. Например, преобразование девиации тоже дает лапласиан на выходе.
Лапласианы могут быть симметричными — в них потенциалы всех узлов равны между собой — для нашей задачи они пока неинтересны.
Матрица Кирхгофа относится к классу лапласианов.
Потенциалы лапласианов
В линейной алгебре есть понятие дополнительного минора (кофактора) матрицы — это определитель матрицы, полученной из исходной вычеркиванием строк и столбцов (с учетом знака). Кофакторы играют большую роль в лапласианах.
Потенциалом 1-го порядка лапласиана называется определитель матрицы, полученный вычеркиванием из исходного лапласиана одной строки и одного столбца.
Поскольку мы приняли, что в наших лапласианах сумма каждого столбца нулевая, то значение потенциала определяется только вычеркнутой колонкой, — строка может быть любой. Удобно вычеркивать ту же строку, что и колонка, — тогда не надо думать о знаке определителя.
Итак, если обозначить через
Так вот эти потенциалы 1-го порядка от матрицы Кирхгофа и являются искомым решением уравнения (1.4).
Удивительно. Не нужны никакие циклы, начальные присваивания, произведение матриц и пр. Удалил строку/колонку, посчитал определитель — получил ответ.
- Потенциал узла представляет собой сумму произведений (кортежей) проводимостей ребер графа по всем возможным путям в данный узел, исключая контуры (циклы).
- Количество множителей в произведении на 1 меньше размерности (количества узлов) графа.
- Потенциал узла не зависит от проводимостей исходящих из него дуг.
- Каждый кортеж (путь) в выражении для потенциала узла состоит из дуг, которые исходят из всех узлов, кроме данного. В одном кортеже нет двух дуг, исходящих из одного узла, но могут быть дуги, входящие в один узел.
- В каждом кортеже (пути) обязательно присутствует дуга, входящая в узел (замкнутость).
- В выражении для потенциала отсутствуют кортежи, содержащие циклы (контуры).
- Количество кортежей в выражении для потенциала определяется известной формулой Кэли
, и быстро растет с ростом узлов графа. Для 4-х узлов имеем 4^2 = 16 слагаемых, для пяти — 5^3 = 125 и т. д.
- В симметричном графе потенциалы всех узлов равны – следствие того, что структура выражения для потенциалов всех узлов одна и та же (разница лишь в направлении).
![](https://habrastorage.org/files/d5b/096/73f/d5b09673fbb748b2a3d5f29713dc3bdc.png)
Для определения потока через узел достаточно умножить потенциал узла на его степень:
Мы получили, что хотели.
Это вес голоса каждого участника. Теперь считаем потоки и определяем, кто сколько голосов набрал:
Алена набрала больше всех голосов.
Как считать потенциалы больших графов
Если граф большой (много узлов), то считать вектор потенциалоф через вычисление определителей миноров лапласиана неудобно (затратно). В таких ситуациях лучше использовать обращение матрицы. Алгоритм следующий:
- В матрице лапласиана заменяем первую строку на вектор (1, 0, 0, ...).
- Считаем обратную матрицу от полученной и находим ее детерминант.
- Делим значения первой колонки полученной обратной матрицы на ее детерминант. Это и есть искомый вектор потенциалов. В первой строке — потенциал первого узла, во второй — второй и т. д.
- Если абсолютное значение потенциала неважно, то считать и делить на детерминант необязательно.
Ранжирование объектов на основе потенциалов и потоков
По итогам нашего примера получилось так, что наибольший вес голоса получила Софья, но больше всего баллов набрала Алена.
Это означает, что авторитетные и избранные — это не одно и тоже.
Что именно должно служить основанием для ранжирования, — потенциалы или потоки,- требует отдельного рассмотрения в каждой задаче, поскольку определяется прикладным аспектом.
Результаты турниров
Рассмотрим применение системы ранжирования применительно к определениям итогов шахматного турнира. Справедлива ли нынешняя система определения победителя простой суммой очков? На наш взгляд, она имеет лишь одно достоинство — простота. Но в век смартфонов кого волнует простота?
Несправедливо то, что выигрыш сильного по сути приравнивается в «простой системе» выигрышу у слабого.
Современный и правильный подход — считать взвешенные очки, то есть использовать расчет потенциалов и потоков. Еще один плюс — при данной системе практически исключена дележка мест — не надо думать о том, что делать при равенстве очков.
Как раз недавно в Москве закончился турнир претендентов (поздравляем Сергея Карякина с победой!), по итогам которого большое количество участников поделило места (2-3, 4-7). Используя метод потенциалов, попробуем разобраться, кто же какое место занял на самом деле.
Результаты турнира — это матрица смежности графа. В терминах лайков проигрыш участника — это проставление лайка победителю (хотя и звучит немного непривычно). От проигравшего к победителю идет поток взвешенных очков.
А что такое потенциал применительно к игрокам?
Потенциал — это показанная участником сила игры (в данном турнире). Чем выше потенциал участника — тем большую ценность имеют очки, полученные от него другими.
Возможно ли, чтобы менее сильный игрок набрал большее количество очков, чем более сильный? Да, такое вполне возможно, хоть и бывает не так часто. Например, на упомянутом турнире претендентов сила участника и набранные им очки совпали — ранжирование по потенциалам и потокам оказались эквивалентными.
Сергей Карякин | Хикару Накамура | Аниш Гири | Виши Ананд | Веселин Топалов | Левон Аронян | Фабиано Каруана | Петр Свидлер | |
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. Без его статьи, возможно, не было бы и этой.
Подробности о постановке задачи есть в упомянутой статье, — карты бьют друг друга по правилам старшинства, но при этом шестерка бьет туза.
Данная задача хороша тем, что значения потенциалов (хм, а потоки тут что означают?) могут быть выражены в явном виде — несложными формулами.
Общий вид матрицы смежности соответствует результатам карточных сравнений — кто кого бьет.
Нумеруя карты от условного туза к условной шестерке, получаем следующий вид матрицы смежности:
Ключевая особенность — в левом нижнем (и/или правом верхнем) углу — «шестерка бьет туза».
Тогда матрица Кирхгофа будет иметь вид:
Теперь наглядно видно, почему потенциал «шестерки» равен (n-2)! Потому что вычеркнув колонку и строку, соответствующие «шестерке» (это крайние ряды справа и снизу), мы получаем треугольную матрицу, определитель которой считается простым умножением элементов главной диагонали.
То же самое справедливо и для туза (1-я строка и колонка) с той лишь разницей, что у него в составе множителей два раза встречается элемент (n-2). Поэтому сразу видно, что потенциал туза всегда в (n-2) раза больше потенциала шестерки.
Интересно, что сумма потенциалов всех карт (кроме шестерки и туза) равна потенциалу туза:
Заключение
Сколько могли старались и слушали девицы сказ царя Салтана про возможности лапласиана, да все равно сморил их крепкий сон.
Снились им добры-молодцы с большим потенциалом, управляющие крупными потоками.
Пришла и нам пора закругляться. Используйте потенциалы!
Комментарии (30)
Dreamastiy
01.04.2016 19:09+1Потенциалы — это аналог взвешенного PageRank без телепортации?
dmagin
01.04.2016 21:28+2PageRank это частный случай использования потенциалов для ранжирования. Принцип тот же.
danzalux
01.04.2016 21:26А возможно применить потенциалы для оценки статей и комментов на хабре, например?
dmagin
01.04.2016 21:35+1В статье описан принцип самооценки объектов. То есть скорее можно говорить о его использовании для оценки участниками хабра друг друга. С другой стороны, полученный таким образом вес может быть применим к оценке статей.
pkalinin
01.04.2016 22:12А кто мешал решить систему методом Гаусса и не мучаться со всякими лапласианами?
dmagin
01.04.2016 22:30Гаусс, конечно, крутой, но даже он не смог придумать метод, который решал бы все системы. Обычный Гаусс тут неприменим, но, возможно, вы имеете ввиду какой-то другой неизвестный мне метод.
pkalinin
02.04.2016 05:34+2А уточните, почему? Неужели ваши матрицы настолько плохо определены? Все остальные системы Гаусс вполне решает, и вряд ли система уравнений 3x3 из небольших случайных целых чисел настолько плохо определена.
Конечно, у нее определитель ноль, но с коих пор это было помехой Гауссу? Это просто обозначает, что ваши потенциалы определены с точностью до произвольного множителя (а чего еще вы хотели от однородной системы?), но тогда просто полагаете последний (или какой надо будет) потенциал равным единице, например, и вполне себе находите остальные потенциалы.
Вот я сейчас проделал это для вашей системы 3x3, приведенной в начале поста (добавив на диагональ что надо), и вполне получил потенциалы 5/7, 4/7, 1 — что и следовало ожидать.dmagin
02.04.2016 10:34Да, я был неточен насчет Гаусса. В статье приведен способ определения потенциалов через обращение матрицы. Перед этим матрицу надо немного модифицировать, примерно так же, как вы и указали. Ну а обращать матрицы можно и Гауссом, конечно.
Но то, что мы таким образом делаем, — это и есть "мучение с лапласианами" ) — с Гауссом или без — не особо принципиально.professor_k
07.04.2016 16:56Задаем начальный вектор потенциалов, умножаем его на матрицу смежности, делим на степени узлов, получаем новый вектор потенциалов и т. д.
А вот-это называется методом Гаусса-Ньютона :)
TuMoXEP
02.04.2016 02:18+3Спасибо за статью. Офигеть, как круто. А если добавить еще участника, все надо будет заново полностью пересчитать? Или есть вариант побыстрее?
dmagin
02.04.2016 11:03Хороший вопрос насчет нового участника. Навскидку не скажу, надо смотреть.
Но знаю, что при изменении элемента матрицы смежности пересчитывать все по новой необязательно. Производная потенциала 1-го порядка (по Cij) определяется потенциалом 2-го порядка. В статью не стал включать, чтоб не раздувать.
Mingun
02.04.2016 09:19+1Но ведь при таком способе расчёта важен порядок проставления лайков участниками. Поскольку с каждым прилетевшим в твою сторону лайком увеличивается твой вес и, соответственно, твой вклад в вес остальных участников.
dmagin
02.04.2016 11:18+2Если я правильно понял ваше замечание, то вы говорите о системе, при которой учитываются остатки в узле. То есть используется уравнение (1.1), а не (1.2). Что-то подобное учету текущего рейтинга спортсменов (шахматистов, например). (Можно назвать такие системы открытыми). Там да, порядок (историчность) лайков имеет значение.
xskif
02.04.2016 10:58+2Потрясающая статья. Ещё раз убедился что пора вспоминать чему учился в университете, а то вот так сидишь, учишь 3-й яп или новый framework, а матрицы уже забыл. Недавно ужаснулся, когда осознал что забыл как решать СЛАУ и квадратные уравнения...
alekseyefremov
02.04.2016 11:19Статья очень интересная! Скажите, а какие методы оценки можно использовать для систем с двумя, тремя параметрами?
В качестве примера можно привести «лайки» и «репосты».dmagin
02.04.2016 11:25Хм, я не знаю, честно говоря,- надо думать. И еще насчет учета дислайков надо бы определиться.
TuMoXEP
02.04.2016 12:01+1Наверное, проще всего будет установить какое-нибудь соответствие между параметрами, 1 репост = 1,5 лайка например.
cyber-security
02.04.2016 18:58+3По причине некоторых запретов в правилах Хабра я не могу воспользоваться всеми словами русского языка, чтобы сказать, насколько хорошая статья получилась, и насколько правильное дело вы делаете; поэтому просто знайте, что статья получилась очень хорошая, и дело вы делаете очень правильное.
rotozeev
03.04.2016 05:11Очень интересно! Напоминает математическое рассмотрение рефлексии у Лефевра из серии "я знаю, что ты знаешь, что я знаю, что ты знаешь...." => "ты поставил мне лайк, поэтому мой лайк тебе будет более ценным для тебя, но тогда и твой изначальный лайк мне стал ценнее, увеличив в свою очередь ценность ответного лайка...".
Интересен сам подход, внедрение понятия потоков по узлам. Уравнение 1.4, как тут заметили в комментариях, действительно простая однородная система линейных уравнений, которая элементарно решается с точностью до общего множителя, и поэтому я не сильно понял зачем лапласианы тут, как и упоминание о сходимости и итерациях. Хотя этот програмистский метод сходимостей и итераций, возможно, базируется на подсознательном воплощении в программе рассуждений из первого абзаца данного комментария.dmagin
03.04.2016 10:49) Думаю, что источником недоумения насчет "метода итераций" является фраза "когда я впервые столкнулся с уравнением...". На самом деле я столкнулся не с уравнением, конечно же, а с конкретной прикладной задачей,- как и автор упоминаемой статьи о ценности карт (читали?). А про уравнение и прочее это я уже потом выяснил.
И еще соглашусь, пожалуй, что в приведенных примерах можно было бы обойтись и без понятия "потенциал лапласиана" (просто вектор решения уравнения баланса). Но если мы копнем чуть глубже, то столкнемся с потенциалами 2-го и более высоких порядков. Там уравнение баланса уже особой роли не играет.
RomanPyr
03.04.2016 18:55исходящий поток — кредит, входящий — дебет
Для точности стоит отметить, что как раз наоборот:
Входящий поток — кредит, исходящий — дебет, остаток — сальдо.
Кредит является источником средств, а дебет — куда они были потрачены.
Уставный капитал, целевое финансирование учитывается на пассивных счетах (счетах с кредитовым сальдо).
Пассивная часть баланса говорит откуда средства пришли, активная — куда ушли.dmagin
03.04.2016 21:21Вы точно не путаете остатки с оборотами? Про пассивы и активы вы правильно пишите, но дебетовые обороты счета (того же, например, 51-го), — это, извиняюсь, все-таки приход.
RomanPyr
03.04.2016 22:22Как думаете, почему всё-таки в учёте используются дебет/кредит, а не приход/расход? Хотя попытки были и не раз (например Ф.В. Езерским)
Наверное, потому что это не одно и то же :)
Например, оприходование излишков:
Дебет "Товары" Кредит "Прибылей и убытков"
заменилось бы на:
Приход "Товары" Расход "Прибыли и убытки"
хотя прибыль-то как раз появилась :)
Дебет/Кредит в зависимости от типа счёта (активный/пассивный) могут как уменьшать, так и увеличивать сальдо.
51 — активный счёт. А 80, 84 и остальные? ;)))
Как и любая абстракция — эта протекла.dmagin
03.04.2016 22:47Соглашусь с замечанием в том плане, что для пассивных счетов (типа капитала), входящий поток действительно уменьшает капитал (кредитовый остаток). Но при этом остается дебетовым.
В статье, кстати, все примеры — активные счета.
mmatrosov
10.04.2016 14:21Статья про потоки, потенциалы, схемы, графы — без единого рисунка графа. Хм. Автор явно высокого мнения о способностях аудитории к абстрактному мышлению :)
Yeah
Я тупой… :(
mafia8
Более корректно: Я не понял это… :(
PavelMSTU
Это ж математика! Вооружаемся листком бумаги и карандашиком.
Прочитали абзац — пописали формулки — перешли к следующему абзацу.
Conso
Я вот тоже понял только общую идею. С формулами беда. Может есть какой-то дополнительный материал?