Finding cycle of 3 nodes ( or triangles) in a graph?

Question

I am working with complex networks. I want to find group of nodes which forms a cycle of 3 nodes (or triangles) in a given graph. As my graph contains about million edges, using a simple iterative solution (multiple "for" loop) is not very efficient. I am using python for my programming, if these is some inbuilt modules for handling these problems, please let me know. If someone knows any algorithm which can be used for finding triangles in graphs, kindly reply back.

Answer 1

A triangle can be considered as a length 3 path from A back to A, AB-BC-CA

If you take the incidence matrix to the third power, the elements in the main diagonal are the number of length three paths from point #i back to itself.

So first take A^3 and look only at i where the diagonal element of A^3 is non-zero.

If we had an even number like 4 or a larger number for the path length, we might have to worry about re-tracings (AB-BA) but that is not a problem with triangles.

The triangle can be considered as a length 2 path AB-BC and then a return CA

Look at the incidence matrix to the second power A^2 to find the number of length 2 paths from and i to j, i not equal j. Then look at the basic incidence matrix A to find if there is a path from j backto i. If you have a directed graph, check position ji, but in an undirected graph that is the same as i,j.

Flow chart:

Input incidence matrix A and save. Calculate A^2 and A^3 and save.

For all i = 1 to n

In A^3 is A^#_i,i = 0?

Yes --- i is in no triangles, omit

No -- continue check

For all j not equal i from 1 to n, is A^2_i,j = 0?

[Note: this could be reduced in an undirected graph by checking only j > i since j < i was checked in previous lines by reversing i,j; also avoids duplication]

Yes -- no triangles involving i and j [in increasing order undirected] , omit

No -- continue check

For all j not equal i, is A_j,i = 0?

Yes -- No triangles involving i and j, omit

No -- The pair i,j is contained in at least one triangle [with i,j increasing]. Save this pair

For all pairs (i,j) found, check the list for "triangle completion" pairs (j.k), (i,k) [undirected]

List all triangles found.

***************************************************************

This is a rough draft just summarizing the logic, but working by weeding out like this should be quite efficient.