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

Assuming its an undirected graph, the answer lies in networkx library of python. if you just need to count triangles, use:

import networkx as nx
tri=nx.triangles(g)

But if you need to know the edge list with triangle (triadic) relationship, use

all_cliques= nx.enumerate_all_cliques(g)

This will give you all cliques (k=1,2,3...max degree - 1)

So, to filter just triangles i.e k=3,

triad_cliques=[x for x in all_cliques if len(x)==3 ]

The triad_cliques will give a edge list with only triangles.

Answer 2

I am working on the same problem of counting number of triangles on undirected graph and wisty's solution works really well in my case. I have modified it a bit so only undirected triangles are counted.

    #### function for counting undirected cycles
    def generate_triangles(nodes):
        visited_ids = set() # mark visited node
        for node_a_id in nodes:
            temp_visited = set() # to get undirected triangles
            for node_b_id in nodes[node_a_id]:
                if node_b_id == node_a_id:
                    raise ValueError # to prevent self-loops, if your graph allows self-loops then you don't need this condition
                if node_b_id in visited_ids:
                    continue
                for node_c_id in nodes[node_b_id]:
                    if node_c_id in visited_ids:
                        continue    
                    if node_c_id in temp_visited:
                        continue
                    if node_a_id in nodes[node_c_id]:
                        yield(node_a_id, node_b_id, node_c_id)
                    else:
                        continue
                temp_visited.add(node_b_id)
            visited_ids.add(node_a_id)

Of course, you need to use a dictionary for example

    #### Test cycles ####

    nodes = {}

    nodes[0] = [1, 2, 3]
    nodes[1] = [0, 2]
    nodes[2] = [0, 1, 3]
    nodes[3] = [1]

    cycles = list(generate_triangles(nodes))
    print cycles

Using the code of Wisty, the triangles found will be [(0, 1, 2), (0, 2, 1), (0, 3, 1), (1, 2, 3)]

which counted the triangle (0, 1, 2) and (0, 2, 1) as two different triangles. With the code I modified, these are counted as only one triangle.

I used this with a relatively small dictionary of under 100 keys and each key has on average 50 values.