Skip to main content
8 of 14
edited 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,    0.85, 1.40}, 
         {1.46, 0.36, 0.96, 0.15, 0.97}, 
         {0.24, 1.2,  1.4,  0.96, 0.46}, 
         {1.1,  1.3,  0.03, 0.81, 0.53}, 
         {1.3,  1.5,  1.3,  0.51, 0.42}
       };

matT2 = {
         {0.44, 1,    0.77, 1.2,  0.61}, 
         {0.58, 0.57, 0.65, 0.19, 1}, 
         {1.4,  0.14, 1.2,  1.4,  0.96}, 
         {1.4,  0.95, 0.74, 0.56, 0.47}, 
         {0.98, 0.45, 1.3,  0.34, 0.25}
       };

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]. This yields:

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. This generates 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, we calculate a row-stochastic transition matrix as:

enter image description here

transMatrix = {
         {2/6,  3/6,  1/6}, 
         {3/10, 5/10, 2/10},
         {2/9,  4/9,  3/9}
               };
MatrixPower[transMatrix, 100]

produces the following limiting distribution:

enter image description here

The 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