finding cycle of 3 nodes ( or triangles) in a graph

Question

hi all, i am working with complex networks. I want to find group of nodes which forms cycle of 3 nodes ( or triangles) in a given graph. As my graph contains about million edges, so the use simple iterative (multiple "for" loop) is not very efficient.

If someone knows any algorithm which can be used for finding triangles in graphs, kindly reply back.

thanks a lot

zapa

( I am using python for my programming, if these is some inbuilt modules for handling these problems , please let me know)

Answer 1

Even though it isn't efficient, you may want to implement a solution, so use the loops. Write a test so you can get an idea as to how long it takes.

Then, as you try new approaches you can do two things: 1) Make certain that the answer remains the same. 2) See what the improvement is.

Having a faster algorithm that misses something is probably going to be worse than having a slower one.

Once you have the slow test, you can see if you can do this in parallel and see what the performance increase is.

Then, you can see if you can mark all nodes that have less than 3 vertices.

Ideally, you may want to shrink it down to just 100 or so first, so you can draw it, and see what is happening graphically.

Sometimes your brain will see a pattern that isn't as obvious when looking at algorithms.

Answer 2

That's an interesting problem. Given that you are using python you should post this question on the scipy (or numpy) discussion forums.

Answer 3

Do you need to find 'all' of the 'triangles', or just 'some'/'any'? Or perhaps you just need to test whether a particular node is part of a triangle?

The test is simple - given a node A, are there any two connected nodes B & C that are also directly connected.

If you need to find all of the triangles - specifically, all groups of 3 nodes in which each node is joined to the other two - then you need to check every possible group in a very long running 'for each' loop.

The only optimisation is ensuring that you don't check the same 'group' twice, e.g. if you have already tested that B & C aren't in a group with A, then don't check whether A & C are in a group with B.

Answer 4

I don't want to sound harsh, but have you tried Google it? First link is a pretty quick algorithm to do that: http://www.mail-archive.com/[email protected]/msg05642.html

And then there is this article on ACM (which you may have access to): http://portal.acm.org/citation.cfm?id=244866 (and if you don't have access, I am sure if you kindly ask the lady who wrote it, you will get a copy)

Also, I can imagine a triangle enumeration method based on clique-decomposition, but I don't know if it was described somewhere.

Answer 5

A million edges is quite small. Unless you are doing it thousands of times, just use a naive implementation.

I'll assume that you have a dictionary of node_ids, which point to a sequence of their neighbors, and that the graph is directed.

For example:

nodes = {}
nodes[0] = 1,2
nodes[1] = tuple() # empty tuple
nodes[2] = 1

My solution:

def generate_triangles(nodes):
    """Generate triangles. Weed out duplicates."""
    visited_ids = set() # remember the nodes that we have tested already
    for node_a_id in nodes:
        for node_b_id in nodes[node_a_id]:
            if nod_b_id == node_a_id:
                raise ValueError # nodes shouldn't point to themselves
            if node_b_id in visited_ids:
                continue # we should have already found b->a->??->b
            for node_c_id in nodes[node_b_id]:
                if node_c_id in visited_ids:
                    continue # we should have already found c->a->b->c
                if node_a_id in nodes[node_c_id]:
                    yield(node_a_id, node_b_id, node_c_id)
        visited_ids.add(node_a_id) # don't search a - we already have all those cycles

Checking performance:

from random import randint
n = 1000000
node_list = range(n)
nodes = {}
for node_id in node_list:
    node = tuple()
    for i in range(randint(0,10)): # add up to 10 neighbors
        try:
            neighbor_id = node_list[node_id+randint(-5,5)] # pick a nearby node
        except:
            continue 
        if not neighbor_id in node:
            node = node + (neighbor_id,)
    nodes[node_id] = node

cycles = list(generate_triangles(nodes))
print len(cycles)

When I tried it, it took longer to build the random graph than to count the cycles.

You might want to test it though ;) I won't guarantee that it's correct.

You could also look into networkx, which is the big python graph library.