Which part of math is describing this transfer graph?

60 Views Asked by At

Imagine we having directional weighted graph. Every graph vertex also is having a number which we can call value. Every graph edge $AX$ is showing to us, what portion of the value of Vertex $A$ is transferred to (the value of) Vertex $X$.

I tried to program it in Python and in the cyclic graph of length 4 and weights

AB = 0.1
BC = 0.2
CD = 0.3
DA = 0.4 

And every graph vertex with a starting value of 25. I found at the end of iteration

vA = 48 
vB = 24
vC = 16
vD = 12

What is this end point mathematically? What subfield of mathematics deals with this? I know that this problem has to do something with calculus.

1

There are 1 best solutions below

0
On BEST ANSWER

What you found is an eigenvector for the largest eigenvalue of the weight matrix of your graph (accounting for self-connections). This matrix is: $$ A :=\begin{pmatrix} 0.9 & 0 & 0 & 0.4 \\ 0.1 & 0.8 & 0 & 0 \\ 0 & 0.2 & 0.7 & 0 \\ 0 & 0 & 0.3 & 0.6 \end{pmatrix}. $$ The values on the diagonal account for the fact that each node retains the portion of value that is not transferred. Using this matrix, you can describe one transfer step as follows: $$v_{t+1} = A·v_t,$$ where $v_{t}$ is the vector of your values at time $t$ and $·$ indicates matrix–vector multiplication.

Applying this matrix–vector multiplication repeatedly for almost all¹ initial condition will result in convergence to an eigenvector of the largest eigenvalue. Using the knowledge that “value” in your sense is preserved, you can find out which one exactly it will be.

Your problem is closely related to the concept of eigenvector centrality.


¹ absolutely all in case of a connected graph non-negative initial conditions, see here.