4

I have a matrix of size (47*47 double) that have only 0's and 1's.

I want to apply the Markov clustering algorithm on this matrix, but this Method needs a transition matrix as the columns must be normalized to sum to one.

Could anyone help me to turn this adjacency matrix into a transition matrix.

I appreciate any help!

here are the adjacency and the transition matrix I have

https://drive.google.com/open?id=0B6u8fZadKIp2bF9neFM5dmNnR0E

https://drive.google.com/open?id=0B6u8fZadKIp2bjdnVUNTWDMyUm8

F.caren
  • 93
  • 1
  • 9

1 Answers1

4

Adjacency matrix and transition matrix give different information. It's easy to come with a simple method to map valid adjacency matrices into valid transition matrices, but you need to make sure that the transition matrix you get fits your problem - that is, if the information that is in the transition matrix but wasn't in the adjacency matrix is true for your problem.

I understand that your problem deals with 47 different states, and that a directed graph can be build showing all possible transitions -that is, if state i can change to state j, an edge will be drawn from node i to node j- and that your adjacency matrix shows which edges are connected.

Therefore, your adjacency matrix shows which states the system can reach from any given one, but it doesn't show which is the probability to get to each one. That information will be encoded in the transition matrix and you need to know it or to make reasonable assumptions.

A simple assumption is that for any given state all possible transition have the same probability. Under this assumption you can compute the transition matrix by dividing every value in the adjacency matrix by the column sum - that is, making every column to sum 1. Anyway, beware that this simple assumption might not fit your problem.

Edit: From https://www.cs.ucsb.edu/~xyan/classes/CS595D-2009winter/MCL_Presentation2.pdf I see that assuming equal probabilities for every edge from the same node is the standard procedure.

Pere
  • 5,875
  • 1
  • 13
  • 29
  • So I have to divide every value that equals 1 in my adjacency matrix by the column sum of all the 1 in that column, is it right? – F.caren May 29 '17 at 07:34
  • the graph i have is undireted and unweighted graph,1 and 0 means the existence of an edge between nodes, if yes then 1 else is 0, those are all informations i have, when i get this adjacecny matrix i have tried MCL but produce NaN as a result in matlab, and then i recognize that MCL need as input a transition matrix and not an adjacency matrix. – F.caren May 29 '17 at 07:45
  • Then you can just normalize columns - that is, divide all values on each column by a constant so that they sum 1. This way you will get a transition matrix without adding more information. – Pere May 29 '17 at 08:20
  • thanks, bro I will do it, but how to get that constant? because I'm doing everything programmatically in Matlab, and thus whch constant could be taken? – F.caren May 29 '17 at 08:32
  • @F.caren Just sum each column and then divide each value by the sum of its column. I don't know the command to do this in Matlab, but it should be easy in any language. – Pere May 29 '17 at 08:37
  • Hi friend, i have done the previous steps in matlab.I recognized that NaN's are coming from the columns that have all 0's and no 1's, then i avoid them by assign a value of 1 on the diagonal of the whole matrix, and then divide each value by the sum of its column.I run again MCL and is worked, but i don't need self loops nodes in my final graph. Any suggestions!!!. – F.caren May 31 '17 at 04:48
  • @F.caren That should be a new question. However, columns (and rows) with all zeros are nodes not connected to any other node. Obviously, those nodes form their own cluster and the most straightforward approach seems just to remove them from the analysis. Alternatively, you can try adding ones to the diagonals of such columns or even the whole matrix, although I'm not sure if those ones can change anything else in the clusters. I'd guess that ones in the all-zero columns wouldn't change anything but in other columns they can affect clusters. – Pere May 31 '17 at 09:55
  • my graph has 3 components, so I just keep the more dense component and delete others. I run the MCL again and still have NaN; plz any suggestions, I get stuck. – F.caren Jun 02 '17 at 06:40
  • @F.caren Without seeing your data - or at least an example which produces the same error - I doubt anybody can help. – Pere Jun 02 '17 at 19:07
  • @ Pere I have shared the matrices, plz could you have a quick check? – F.caren Jun 06 '17 at 02:02