The tale of Tsar Saltan about the potential of the Laplacian

"Three girls under the window were spinning late in the evening."



Well, as spun. Not spun, of course, but like each other. Under the terms of the contest "Miss Sultan" girls had to choose the best among themselves.
')
“Some strange competition,” worried the girls. And it was true. According to the rules of the contest, the participant's like weight depended on how many likes he receives from others. What does this mean - none of the girls did not fully understand.
“How complicated it all is,” the girls grieved and cheered themselves on with the song “If I was a queen.”

Soon "the king entered the luminaries - the sides of the sovereign" (shown in the figure). "During the whole conversation ...", - well, of course, in general.
“We collect likes of tenderness - we form an adjacency matrix,” he said cheerfully.
The beautiful girls with the names Alyona, Varvara and Sophia were embarrassed, but the likes (from the balalaika) were transmitted.

Here is what was there:

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

The king took the huskies, twirled the nuts, tapped the wheels, snorted his nose, smacked his lips, gritted his teeth, drove them into the chambers and announced the results.

Sophia got the greatest weight of likes (7 points), but Alena got the title “Miss Saltan” (15 points).


After the results were announced, the girls rushed to the tsar with a request to tell, where did these strange figures come from?

1. Equation of balance

Our world is based on balance. This means that if in one place something arrived, then in another place as much has gone.

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

The graph has nodes through which the stream flows (well, how it flows - jolts and irregularly). The principle of balance is simple - in the graph node there is a difference between how much has flowed from it and how much has flowed into it. And where does the flow from the node flow? That's right - in other nodes, respectively, the stream flows into the node also from other nodes.

We write this set of words with the formula:



Here denotes the amount of input to the i- th node, - the number of outgoing flow from the node, - change in the remainder in the node.

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

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

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



Cool. But so far it is of little use.

Potential balance

When we said that a stream could flow from node i to node j , we meant that there was some connection between these nodes. Otherwise, the flow simply has nothing to flow. The connectivity of nodes of a graph is usually called the adjacency matrix (connectivity) , its elements are denoted by . As applied to flows, an adjacency matrix is ​​also called a 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 proportionality factor?

The answer will be a bit foggy - the flow from the node is proportional to a certain potential of the node .
The essence of this answer is that the nodes have some potential and this potential directly determines the amount of 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 this really works.

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



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



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. Solving a system of balance equations is a direct task of calculating the potentials (and flows) of a graph.

In equation (1.4) we used the concept of total conductivity of outgoing links from the node — the degree of the node:

Ratings and self-assessments

“Everything is great,” said the girls, yawning. - “But where does the husky come from?”

In voting systems where participants evaluate each other, ratings are taken based on the weight of each participant’s vote. And the weight of the vote, again, depends on how this member is rated by others.

We associate with threads. When the i- th participant with the weight of the voice evaluates the j- th member with a rating (number of likes) he shares his stream with him . There is no need to save the balance here, so each participant shares with the others everything that he received.

Member voice is potential , the likes matrix is ​​an adjacency (connectedness) matrix, and the final score is the total received (it is 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 who will balance the system.

2. Laplacians

When I was young and stupid, I first encountered the equation of balance (1.4), I already knew how to program and knew about cycles. Therefore, I solved it as a programmer using the method of successive 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 led me to “uncover formulas”.

I remember the “wow effect” when I learned that there is another way to calculate the potentials, about which, apparently, our grandfathers Laplace and Kirchhoff knew. The method is based on the properties of matrix Laplacians. There have recently recalled Laplacians in continuous environments. Discrete Laplacians are no less interesting and important.

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





Let us assume that the conductivity outgoing from the node i is given in the ith column of the matrix. Accordingly, in the i- th row of the matrix - the conductivity of the arcs included in the node. Then the sum of the elements of each column of the Laplacian is zero.

Generally speaking, the matrices of this type form a separate class, - Laplacians . The determinant of the Laplacians is always zero, so, for example, for them there is no ordinary inverse matrix. But then there is another (pseudo) inverse, there is also its own identity matrix. You can get the Laplacian not only by the above conversion. For example, the deviation transformation also gives the Laplacian at the output.

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

Kirchhoff matrix belongs to the class of Laplacians.

Potentials of Laplacians

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 crossing out of rows and columns (taking into account the sign). Cofactors play a big role in laplacians.

The potential of the 1st order of the Laplacian is called the determinant of the matrix, obtained by deleting one row and one column from the original Laplacian.

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

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



So these 1st order potentials from the Kirchhoff matrix are the desired solution of equation (1.4).
Amazing. No need for any cycles, initial assignments, the product of matrices, etc. Deleted a row / column, considered the determinant - got the 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 (expensive) to calculate the potential vector through the calculation of the determinants of the Laplacian minors. In such situations, it is better to use matrix inversion. The algorithm is as follows:

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

Ranking objects based on potentials and flows

According to the results of our example, it turned out that Sophia received the greatest weight of the vote, but Alain scored the most points.
This means that the authoritative and the chosen are not the same.

What exactly should serve as a 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 use of a ranking system in relation to the definitions of the outcome of a chess tournament. Is the current system of determining the winner a simple sum of points? In our opinion, it has only one virtue - simplicity. But in the age of smartphones, who cares about simplicity?
It is unfair that the winning of the strong is essentially equal in the “simple system” to winning against the weak.

A modern and correct approach is to consider weighted glasses, that is, to use the calculation of potentials and flows. One more plus - with this system, the sharing of places is practically excluded - no need to think about what to do with equal points.

Just recently , the Candidates Tournament ended in Moscow (congratulations to Sergey Karjakin on his victory!), Following which a large number of participants divided the seats (2-3, 4-7). Using the method of potentials, let's try to figure out who actually took the place.

The tournament results are the adjacency matrix of the graph. In terms of likes, losing a participant is like putting a winner to a like (although it sounds a bit unusual). From the loser to the winner is a flow of weighted points.

And what is the potential in relation to the players?
Potential is the strength of the game shown by the participant (in this tournament). The higher the potential of the participant - 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 one? Yes, it is quite possible, although it happens less often. For example, in the aforementioned tournament of applicants the strength of the participant and the points scored by him coincided - the ranking by potentials and flows turned out to be equivalent.

Drunkard potentials

The last example that we will consider in this article is the calculation of the value of the cards in the popular game "Drunkard".
Thanks for this astgtciv example. Without his article , perhaps it would not be this.

Details on the formulation of the problem are in the above-mentioned article, - the cards beat each other according to the rules of precedence, but at the same time the six beat the ace.
This task is good because the values ​​of the potentials (hmm, and what the flows mean what?) Can be expressed in an explicit form - with simple formulas.

The general view of the adjacency matrix corresponds to the results of card comparisons - who beats whom.
Numbering the cards from the conditional ace to the conditional six, we obtain 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 equal to (n-2)! Because having crossed out the column and the row corresponding to the “six” (these are the extreme rows on the right and below), 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 the ace (1st line and column) with the only difference that it contains an element (n-2) in the multipliers. Therefore, it is immediately obvious that the potential of an ace is always (n-2) times the potential of the six.

Conclusion

How many could try and listened to the girls the tale of Tsar Saltan about the possibilities of the Laplacian, but still overcame their sound sleep.
They dreamed of good fellows with great potential, managing large flows.

It is time for us to wrap up. Use potentials!