The tale of King Saltan about the potential of Laplacian

“The three girls under the window spun late in the evening.”



Well, how they spun. Not spun, of course, but laykali one to another. According to the terms of the Miss Saltan contest, the girls had to choose the best among themselves.

“Some kind of strange contest,” the girls were worried. And that was true. According to the rules of the contest, the weight of a participant’s likes depended on how many likes he receives from others. What does this mean - none of the girls to the end did not understand.
“How complicated it is,” the girls yearned and encouraged themselves with the song “If I were the Queen”.

Soon "the king entered the chamber - the side of that sovereign" (shown in the figure). “Throughout the conversation ...”, well, understandably in general.
“We collect huskies of tenderness - we form an adjacency matrix,” he said briskly.
The beautiful girls with the names of Alena, Barbara and Sophia were embarrassed, but the huskies (from the balalaika) were transmitted.

Here is what was there:

• Alena received 1 like from Sophia and 2 like from Barbara.
• Barbara received a like from Alena and Sophia.
• And Sophia received 2 likes from Alena and 1 from Barbara.

The king took huskies, twisted nuts, tapped the wheels, poked his nose, smacked his lips, gritted his teeth, drove him into the wards and announced the results.

Sophia got the largest weight of likes (7 points), but Alena (15 points) got the title "Miss Saltan".


After the results were announced, the girls rushed and asked the tsar to tell them, - where did these strange numbers come from?

1. The balance equation

At the heart of our world is balance. This means that if in one place something arrived, then in another place the same amount went away.

Physicists demonstrate this balance by the equation of continuity for continuous and continuous media. But in the modern world, tank wedges are driven by discrete systems - graphs.

The graph has nodes through which the stream flows (well, how it flows - with shocks and irregularly). The balance principle is simple - in the graph node there remains a difference between how much has flowed out of it and how much has flowed into it. And where does the stream flow from the node? Correctly - to other nodes; accordingly, a stream flows into the node from other nodes as well.

We write this set of words with the formula:



Here denotes the amount of incoming flow to the i- th node,- the amount of flow originating from the node; - the change in the remainder in the node.

Yes, the balances in our wallets obey this balance equation. And all accounting is based on it, - they even came up with special names: outgoing flow - credit, incoming flow - debit.

It is not known who and why introduced the principle of balance into natural (physical) systems, but it is better to lay the principle of balance at the basis of artificial systems (accounting, ratings, karma, etc.). If the world has survived on balance, then such a system has a chance.

In many situations (in particular, with our assessment competition), accounting for the remainder in the node is not necessary. That is, it is always zero - how much has flowed in - so much has flowed out. A zero cost game with a zero balance. For such systems, the equation is simplified:



Cool. But so far it is of little use.

Potential balance

When we talked about the fact that a stream can flow from node i to node j , we implied that there is some kind of connection between these nodes. Otherwise, the stream simply has no reason to flow. The connectivity of graph nodes is usually called the adjacency matrix , its elements are denoted by . For flows, the adjacency matrix is ​​also called the conductivity matrix . Its elements reflect the bandwidth of the edges of the graph.

There is a connection - there is a flow, there is no connection - there is no flow. It is logical to assume that the stronger the connection, the greater the flow.
So, the flow between nodes is proportional to the magnitude of the connection nodes. But what is the coefficient of proportionality?

The answer will be a bit foggy - the flow from the node is proportional to some potential of the node .
The essence of this answer is that the nodes have a certain potential and this potential directly determines the magnitude of the outgoing flow. If, for example, we have two nodes, the conductivity between which is the same in both directions ( ), then the total flow between the nodes will be determined by the potential difference of these nodes. The existence of electrical networks proves that it really works.

The connection of the flow with the potentials and conductivity is expressed by a simple formula:



Substituting (1.3) into the balance equation (1.2) we obtain a system of equations for calculating the node potentials:



In this equation, the conductivities are known, and the potentials are unknown.
The number of equations in the system is equal to the number of nodes in the graph. The solution of the system of balance equations is the direct task of calculating the potentials (and flows) of the graph.

In equation (1.4), we used the concept of the general conductivity of bonds originating from a node — the degree of a node:

Ratings and self-esteem

“All this is great,” the girls said, yawning. - “But where does the like?”

In voting systems, in which participants rate each other, ratings are taken based on the weight of each participant’s vote. And the weight of the voice again depends on how others rated this participant.

We connect with streams. When the i- th participant with the weight of the vote evaluates the j- th participant with an estimate (the number of likes), then he shares his flow with him . There is no need to save leftovers, so each participant shares with the rest everything that he received.

The weight of the participant’s voice is the potential , the like matrix is ​​the adjacency (connectivity) matrix, and the final rating is the total received (aka given) stream .

To rank the participants (determine the best), we need to solve the balance equation (1.4), that is, determine the weights of the participants that balance the system.

2. Laplacians

When I was young and stupid for the first time I came across the balance equation (1.4), I already knew how to program and knew about cycles. Therefore, I solved it as a programmer - by the method of sequential iterations. We set the initial vector of potentials, multiply it by the adjacency matrix, divide by the degrees of the nodes, obtain a new vector of potentials, etc. As a rule, the process converges. And I remembered about youth, having read an article about the values ​​of a drunkard , which in general prompted me to "uncover formulas."

I remember the “wow effect” when I found out that there is another way of calculating potentials, which, apparently, our grandfathers Laplace and Kirchhoff also knew about . The method is based on the properties of Laplacian matrices. They have recently recalledLaplacians in continuous media. Discrete Laplacians are no less interesting and important.

In order to determine the Laplacian matrix by a given adjacency matrix, we use the notion of degree of nodes presented above. We place the degrees of the nodes along the diagonal of the Laplacian, and take the remaining elements from the adjacency matrix with the opposite sign. The resulting matrix is ​​also called the Kirchhoff matrix :





We assume that the conductivity of arcs emanating from node i is specified in the ith column of the matrix. Accordingly, in the i- th row of the matrix is ​​the conductivity of the arcs entering the node. Then the sum of the elements of each column of the Laplacian is zero.

Generally speaking, matrices of this form form a separate class, the Laplacians . The determinant of Laplacians is always equal to zero, therefore, for example, for them there is no ordinary inverse matrix. But there is another (pseudo) inverse, there is also its own identity matrix. Laplacian can be obtained not only by the above transformation. For example, the deviation transformation also gives the Laplacian at the exit.

Laplacians can be symmetrical - in them the potentials of all nodes are equal to each other - for our problem they are not interesting yet.

The Kirchhoff matrix belongs to the class of Laplacians.

Laplacian potentials

In linear algebra there is the concept of an additional minor (cofactor) of a matrix - this is the determinant of a matrix obtained from the original by deleting rows and columns (taking into account the sign). Cofactors play a large role in Laplacians.

The first-order potential of a Laplacian is the determinant of a matrix obtained by deleting one row and one column from the original Laplacian.

Since we accepted that in our Laplacians the sum of each column is zero, the value of the potential is determined only by the crossed out column - the row can be any. It is convenient to cross out the same line as the column - then you do not need to think about the sign of the determinant.

So, if we denote by the additional minor of the matrix, then the definition of the potential of the Laplacian can be written as



So these first-order potentials of the Kirchhoff matrix are the desired solution to equation (1.4).
Amazing No cycles, initial assignments, product of matrices, etc. are needed. I deleted a row / column, counted the determinant - received an answer.




To determine the flow through the node, it is enough to multiply the potential of the node by its degree:



We got what we wanted.

How to count the potentials of large graphs

If the graph is large (many nodes), then it is inconvenient (costly) to consider the potential potential vector by calculating the determinants of the Laplacian minors. In such situations, it is better to use matrix inversion. The algorithm is as follows:

• In the Laplacian matrix, we replace the first row with the vector (1, 0, 0, ...).
• We consider the inverse of the matrix obtained and find its determinant.
• Divide the values ​​of the first column of the obtained inverse matrix by its determinant. This is the desired vector of potentials. In the first line - the potential of the first node, in the second - the second, etc.
• If the absolute value of the potential is unimportant, then it is not necessary to count and divide by the determinant.

Ranking of objects based on potentials and flows

According to the results of our example, it turned out that Sophia got the most weight, but Alena scored the most points.
This means that the authoritative and the elect are not the same thing.

What exactly should serve as the basis for ranking, potentials or flows, requires a separate consideration in each task, since it is determined by the applied aspect.

Tournament Results

Consider the application of the ranking system in relation to determining the outcome of a chess tournament. Is the current system for determining the winner just a simple point? In our opinion, it has only one advantage - simplicity. But in the age of smartphones, who cares about simplicity?
It is unfair that the gain of the strong is essentially equal in the “simple system” to the gain of the weak.

A modern and correct approach is to count weighted points, that is, use the calculation of potentials and flows. Another plus - with this system, the division of places is practically excluded - no need to think about what to do when the points are equal.

Just recently in Moscow the tournament of applicants has ended(we congratulate Sergey Karjakin on the victory!), as a result of which a large number of participants divided the places (2-3, 4-7). Using the potential method, let’s try to figure out who actually took what place.

Tournament results are the graph adjacency matrix. In terms of likes, losing a member is like putting a winner on (although it sounds a bit unusual). From the loser to the winner there is a stream of weighted points.

And what is the potential for players?
Potential is the strength of the game shown by the participant (in this tournament). The higher the participant’s potential, the more valuable are the points received from him by others.
Is it possible for a less strong player to score more points than a stronger player? Yes, this is quite possible, although it does not happen so often. For example, at the aforementioned tournament of applicants, the strength of the participant and the points scored by him coincided - the ranking by potentials and flows was equivalent.

Potentials of a drunkard

The last example that we will consider in this article is the calculation of the value of cards in the folk game “Drunkard”.
Thanks for this astgtciv example . Without his article , perhaps this would not have happened.

Details on the statement of the problem are in the mentioned article - the cards beat each other according to the rules of seniority, but at the same time the six beats the ace.
This problem is good in that the values ​​of the potentials (hmm, what do the fluxes mean here?) Can be expressed explicitly - with simple formulas.

The general view of the adjacency matrix corresponds to the results of card comparisons - who beat whom.
Numbering cards from a conditional ace to a conditional six, we get the following form of the adjacency matrix:



The key feature - in the lower left (and / or upper right) corner - "six beats an ace."
Then the Kirchhoff matrix will look like:



Now you can clearly see why the potential of the “six” is (n-2)! Because having crossed out the column and row corresponding to the “six” (these are the extreme rows on the right and bottom), we get a triangular matrix, the determinant of which is considered to be a simple multiplication of the elements of the main diagonal.
The same is true for an ace (1st row and column) with the only difference being that he has the element (n-2) twice in his multipliers. Therefore, it is immediately clear that the ace potential is always (n-2) times greater than the potential of the six.

Conclusion

As much as the girls tried and listened to the tale of Tsar Saltan about the possibilities of the Laplacian, but still their good sleep ruined them.
He dreamed of good fellows with great potential, managing large flows.

It’s time for us to come round. Use potentials!