Skip to main content
13 of 14
added 2 characters in body
Tugrul Temel
  • 6.4k
  • 3
  • 14
  • 33

How to convert a weighted, directed graph into a discrete Markov transition matrix

Suppose that I have matrix matT1 at time t and matT2 at time t+1:

matT1 = {
         {0.98, 0.95, 1.00, 0.85, 1.40}, 
         {1.46, 0.36, 0.96, 0.15, 0.97}, 
         {0.24, 1.20, 1.40, 0.96, 0.46}, 
         {1.10, 1.30, 0.03, 0.81, 0.53}, 
         {1.30, 1.50, 1.30, 0.51, 0.42}
       };

matT2 = {
         {0.44, 1.00, 0.77, 1.20, 0.61}, 
         {0.58, 0.57, 0.65, 0.19, 1.00}, 
         {1.40, 0.14, 1.20, 1.40, 0.96}, 
         {1.40, 0.95, 0.74, 0.56, 0.47}, 
         {0.98, 0.45, 1.30, 0.34, 0.25}
       };

Note that these matrices represent two different weighted directed graphs with 5 vertices. Elements of these two matrices are assigned to one of the three states s1=[0, 0.5], s2=(0.5, 1], and s3=(1, 1.5].

r1T1=BoolEval[0<= matT1<=0.5]/.{1->s1};
r2T1=BoolEval[0.5<matT1<= 1]/.{1-> s2};
r3T1=BoolEval[1<matT1<=1.5]/.{1 -> s3};
matT1S = r1T1 + r2T1 + r3T1 // MatrixForm

r1T2=BoolEval[0<=matT2<=0.5]/.{1 -> s1};
r2T2=BoolEval[0.5<matT2<=1]/.{1 -> s2};
r3T2=BoolEval[1<matT2<=1.5]/.{1 -> s3};
matT2S = r1T2 + r2T2 + r3T2 // MatrixForm

respectively yield:

matT1S = {
          {s2, s2, s2, s2, s3},
          {s3, s1, s2, s1, s2},
          {s1, s3, s3, s2, s1},
          {s3, s3, s1, s2, s2},
          {s3, s3, s3, s2, s1}
         };
matT2S = {
          {s1, s2, s2, s3, s2},
          {s2, s2, s2, s1, s2},
          {s3, s1, s3, s3, s2},
          {s3, s2, s2, s2, s1},
          {s2, s1, s3, s1, s1}
         };

We then derive a map of transition from matT1S to matT2Sby manually comparing the states in both matrices.

Clear[n, states, map];
n = Length[matT2S];
states = {s1, s2, s3};
map = {};

Do[
   If[matT1S[[i, j]] == states[[1]] &&  
      matT2S[[i, j]] == states[[2]], 
      AppendTo[map, {i, j}]
     ], {i, n}, {j, n}
  ]  (* states[[i]] index should be changed for each transition type. This code generates the number of transition (3) from `s1` to `s2` only.*)
 
Length[map]   (* gives 3 *)

For each pair of states, I run the above code to obtain the following map:

enter image description here

Rows are associated with time t and columns with t+1. This map illustrates that, out of 6 links in state s1 at time t, 2 remain in s1 at t+1, and 3 move to s2 at t+1 and 1 moves to s3 at t+1. Other numbers in the map should be read likewise. Using this map,

traMap ={{2,3,1},{3,5,2},{2,4,3}};
transMatrix=
  DiagonalMatrix[1/Total[traMap,
  {2}]].traMap

A row-stochastic transition matrix as:

transMatrix = {
               {2/6,  3/6,  1/6}, 
               {3/10, 5/10, 2/10},
               {2/9,  4/9,  3/9}
             };

which is:

enter image description here

and

MatrixPower[transMatrix, 100] 

produces the following limiting distribution:

enter image description here

This limiting distribution translates the current vector (6, 10, 9) to (0.29, 0.49, 0.22)*(6, 10, 9) = (7,25, 12.25, 5.5). This means that states s1 and s2 host more links while state s3 looses its members.

My question: Although I found out the change shown as (7,25, 12.25, 5.5), I do not know which linkages are in each state in the final period t+100. I know that 7.25 will be in state s1 after 100 repetition of transition but which linkages are they? Basically, I like to know the specific linkages associated with (7.25, 12.25, 5.5).

Would it be possible to write a function transMatrix[matrixT_,matrixT1_]:=... to produce: a transition matrix (row stochastic matrix), a final distribution of the linkages across three states, and subsets of the linkages across each state?

Tugrul Temel
  • 6.4k
  • 3
  • 14
  • 33