3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It is hard to figure out your question, but you need to explain how the values at each vertex change over time. You may find the topic of graph laplacians interesting to read about if you have not already. $\endgroup$ – Anthony D'Arienzo Dec 31 '19 at 2:53
  • 1
    $\begingroup$ Maybe Markov chains would be of interest too. $\endgroup$ – Hans Lundmark Dec 31 '19 at 7:44
  • $\begingroup$ Okay , today i will try to clarify this example $\endgroup$ – Patrik Bašo Dec 31 '19 at 8:22
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.