# Markov Cluster Algorithm transition matrix

I am reading the notes on Markov Cluster Algorithm by Kathy Macropol (http://www.cs.ucsb.edu/~xyan/classes/CS595D-2009winter/MCL_Presentation2.pdf)

On slide 14/46 the author talks about inflation and on slide 12/46 the author provides an example for mcl. I am not sure how the author got the results shown in the matrix on the right.

The author mentions this is squaring and normalizing, I understand this but I guess I am having issues getting started. Any assistance on helping me understand how this matrix was derived is much appreciated.

C = matrix(
c( 0, .25, .33, .33, 0, 0, 0,
.33, 0, .33, .33, .33, 0, 0,
.33, .25, 0, .33, 0, 0, 0,
.33, .25, .33, 0, 0, 0, 0,
0, .25,   0, 0, 0, .5, .5,
0,   0,   0, 0, .33, 0, .5,
0, 0, 0, 0, .33, .5, 0),
nrow=7,
ncol=7)

C = t(C)
C

c1s = (sum(C[,1])^2)
C11 = C[,1]^2
C1N = C11/c1s

c2s = (sum(C[,2])^2)
C22 = C[,2]^2
C2N = C22/c2s

c3s = (sum(C[,3])^2)
C33 = C[,3]^2
C3N = C33/c3s

c4s = (sum(C[,4])^2)
C44 = C[,4]^2
C4N = C44/c4s

c5s = (sum(C[,5])^2)
C55 = C[,5]^2
C5N = C55/c5s

c6s = (sum(C[,6])^2)
C66 = C[,6]^2
C6N = C66/c6s

c7s = (sum(C[,7])^2)
C77 = C[,7]^2
C7N = C77/c7s

Ct = cbind( C1N,C2N,C3N,C4N,C5N,C6N,C7N )
Ct

CN = Ct%*%Ct
CN

C = CN


The example in slide 12 is similar to the one provided in slide 8.
The resultant matrix to the right is not the result of one step of squaring and normalising, but after some iterations.
You can do multiple steps of matrix squaring and normalising just like in slide 8 to arrive at the final matrix. I wrote a small R script to test the same and it is correct.

a=matrix(0,7,7);
a[1,]=c(0,.25,.33,.33,  0, 0, 0);
a[2,]=c(.33,0,.33,.33,.33,0, 0);
a[3,]=c(.33,.25, 0, .33,  0, 0, 0);
a[4,]=c(.33,.25   ,.33,  0,   0, 0,0);
a[5,]=c(0,.25, 0,   0,   0,.5,.5);
a[6,]=c(0,  0,  0,   0, .33,0,.5);
a[7,]=c(0,  0,  0,   0, .33,.5,0);

normalize<-function(mat){
for(i in 1:7){mat[,i]=mat[,i]/sum(mat[1:7,i])}
return (mat);
}
iterate<-function(mat){
bm=mat;
for(i in 1:10){
bm<-bm%*%bm;
bm<-normalize(bm);
print(paste("Iteration",i));
print(bm);
print ("-----");
}
return (bm);
}
iterate(a);


Observe that it converges just after 4 iteraions.

Thanks

• , thanks Vihari. I am confused. I updated the questions section with the code I wrote earlier. I was squaring the column and dividing by the squared sum of columns, because I thought normalizing should be based on the inflation factor example in slide 15, D <- matrix(c(0, 0.5, 0, 1/6,1/3),byrow=TRUE, nrow=5); (D^2)/sum(D^2); library(MASS);fractions((D^2)/sum(D^2)) – bison2178 Dec 24 '15 at 21:35
• Yeah, you are confused :) Why are you multiplying C and Ct, when you are supposed to square the matrix at every iteration? – Vihari Piratla Dec 25 '15 at 6:02
• you are absolutely right, thanks for pointing that out. + 10 for you my friend. – bison2178 Dec 26 '15 at 16:51