Nodes that form a loop in adjacency matrix (Matlab)

Question

I have an adjacency matrix with directed edges. Computing A^3, would help me detect if there are any cycles of length 3 (triangle) in the matrix. But, I want to know which nodes form the triangle. How can I achieve this in Matlab?

Thanks

Answer 1

The problem with matrix multiplication is that it adds up all the rows. When you multiply the first row of matrix P by the first column of matrix Q, it does an element-wise multiplication and then generates the sum of the resulting vector, throwing away all of the data about the intermediate nodes. Well, we want that vector, so let's stop it from adding them up.

Say we have our adjacency matrix A:

A =

   0   1   0   0   0
   0   0   1   0   0
   1   0   0   1   0
   0   0   0   0   0
   0   0   0   1   0

and we want to find out if there are any paths (not cycles, yet) from node x to node z passing through node y. Row x tells us what nodes have edges from x to y, and column z tells us what nodes have edges from y to z. If we do an element-wise AND of row x and column z, we should get a vector of all of the nodes y that are connected to both x and z.

For example, if we AND row 1 and column 3 for this adjacency matrix:

A =

   0   1   0   0   0
   x   x   1   x   x
   x   x   0   x   x
   x   x   0   x   x
   x   x   0   x   x 

>> A(1,:) & A(:,3).'   %// remember to transpose the column first...
ans =

   0   1   0   0   0 

We see that they're connected by node 2. Awesome, now we know that for this case we have a path 1->2->3. In general though, there could be multiple paths from 1 to 3, so we're going to use the whole vector.

Now all we have to do is make sure that there's a path from node 3 back to node 1. Well, that's row 3, column 1 in our adjacency matrix. If we AND A(3,1) with our vector, we should the same vector back if there's an edge from 3 to 1 and get zeros back if there isn't (and thus, no cycle).

>> (A(1,:) & A(:,3).') & A(3,1)
ans =

   0   1   0   0   0 

Generalizing this, the vector for each path from x to z is

C(x,:,z) = (A(x,:) & A(:,z).') & A(z,x);

Unfortunately I have been unable to find a way to vectorize this, so a double for loop will have to suffice for now:

for x = 1:size(A,1)
   for z = 1:size(A,2)
      C(x,:,z) = (A(x,:) & A(:,z).') & A(z,x);
   end
end

The resulting matrix will have C(x,y,z) = 1 if there is a cycle from x to y to z (and back), and 0 otherwise. Note that each cycle will be listed 3 times:

C(x,y,z) == C(y,z,x) == C(z,x,y)