Efficient Network Motif Finder

Question

[Simon Cockell]

I'm currently trying to find over-represented network motifs in a (relatively) large graph. I've experimented with a few tools, but found them all to be unworkably slow (one tool is still running, 2 weeks later).

Could I ask for your recommendations for a (fast) algorithm to solve this problem?

(PS, I'm currently looking for 6 node motifs in a network of ~120,000 nodes & ~600,000 edges)

EDIT - thanks for the answers so far, I'm trying out FANMOD, but it's 27 hours in and still hasn't got past 1% of the input graph, let alone onto analysing random graphs. Not sure there's a ready made solution to this problem.

[Istvan Albert]

I think in a graph that large the most you can do is compile node/edge statistics (degree distributions, clustering coefficients etc). Most graph algorithms are probably unfeasible.

[Neilfws]

What tools have you tried?

[Simon Cockell]

Good point - currently running - Kavosh (2 weeks and counting) and mfinder (a week and still going).

[Marcin Cieslik]

Is your graph node and/or edge labeled? Having a hypothesis helps i.e. if you have some idea on how a netowork motif looks (and what its edge/node properties are) you can implement a function that looks for it.

[Istvan Albert]

Those interested in network motifs should also read the paper here written by colleagues here at Penn State. It makes a strong point that the seminal papers on network motifs (thus possibly the software for it as long as it reproduces the results) are fundamentally incorrect.

[Marcin Cieslik]

Algorithms in the spirit of PageRank do not need to analyze the network as a whole to return meaningful statistics about any node

[haider.waseem]

FANMOD had been excellent for my 4 node motifs. Author Sebestian is very helping and responds real quick.

Answer 1

[Neilfws]

I have not tried it but FANMOD claims to be "much faster than any other available motif detection tool, especially for larger motifs of size > 4". There's an accompanying publication in Bioinformatics.

My usual favourite, igraph, only handles motif size 3 or 4 for some reason and I imagine would be quite slow anyway.

Answer 2

[Jussi]

We have successfully used SQL (Oracle) to find the motifs from table containing over 10 million edges. The scalability was very good, the largest pathway was about 500 000 edges and we could easily search for 6 node motifs. We even tried finding 20 node motifs, but then it took days to get the result.

Unfortunately, I do not have the source code, but the implementation is straightforward: 2 node motif is simple select from the edge table. Extra nodes in the motif are implemented using self joins where join condition is based on nodes connecting the edges.

[Khader Shameer]

That's an interesting approach. How much time it took to get the 6 node motifs from the tables of 10 million edges ?

[Jussi]

It varies a lot since some motifs or sub-motifs are more common than the others. If the motif does not exist, then the response time was less than a second. I do not remember how long did take to retrieve common motifs and unfortunately the whole database is not available anymore for testing...

[Jussi]

That database is not available any more, but I tested similar configuration on my laptop. I created a table for edge data and populated with 600000 random edges of 120 000 nodes. The total size of the table is not relevant, the size of the pathway is more important. So, the result: finding instances of one 6 node motif takes about 0.5 seconds.

Answer 3

[Istvan Albert]

Those interested in network motifs should also read the paper titled On the origin of distribution patterns of motifs in biological networks written by colleagues here at Penn State. It makes a strong case that the seminal papers on network motifs (thus possibly the software for it as long as it reproduces the results) are fundamentally incorrect

[Khader Shameer]

Very interesting paper. Thanks for pointing this.

Answer 4

[Lars Juhl Jensen]

I have previously used FANMOD with some success. It is in my experience much faster than the alternatives.