Is There Interest In K-Node Network Motifs For Large K?
Entering edit mode
9.9 years ago

A motif in a network is a connected subgraph that occurs significantly more frequently as an induced subgraph than would be expected in a similar random network.

From what I've read in various papers, it seems that the vast majority of interest in network motifs is focussed on k-node motifs for k=3,4,5 (and infrequently k=6). The only papers I've seen talking about motifs of size k=7,8,... are papers that introduce motif detection algorithms, touting the additional functionality of these programs.

Now I'm working on a program with a group in China which can achieve respectable speedups vs. Kavosh for k<=6 (but no functionality for k>=7). I'm planning on making the following claim in our paper:

...the majority of real-world attention has, so far, been on k-node motifs where k is quite small (3<=k<=6).

In fact, this is why we have focused our attention on the k<=6 cases. From what I've encountered so far, this is accurate. However, I would like to gauge the communities response to this claim, just in case I have somehow encountered a misleading sample of papers.

Question: Is the above claim accurate?

PS. I recognise that there are certain k-node subgraphs in networks that are considered important, but are not motifs (in that they do not appear with abnormal frequency).

EDIT: Well, perhaps it's difficult to answer the above question in the affirmative (if it were true, and it seems to be). So here is are two, more focussed questions.

Question: Is anyone currently working with k-node network motifs (where k>=7)?

Question: Are there any research papers that involve k-node network motifs (where k>=7)?

I'm aiming for applications with the above questions, rather than implementation.

network motif graphs network • 2.3k views
Entering edit mode
9.8 years ago
Qdjm 1.9k

I haven't come across papers that search for k>=7 for network motifs.

My guess is that these algorithms would not be widely used because many of the biological networks that people analyze contain false positive (FP) and false negative (FN) interactions. Even with relatively small FP and FN rates, with such a large k, there are very likely to be one or more errors in the measured subgraph.

Entering edit mode

Thanks for that -- I think I can safely make the above claim. Also, your second paragraph raises quite an important point. Hmm...

Entering edit mode
9.6 years ago

Biological (ecological) networks involving foodwebs might look quite different.

That aside, I work with protein/gene networks built around differential responses to environmental stimuli based on genetic differences. These networks have k < 6.

Time is often not portrayed in gene/protein networks, such that a network of B and C connected to A might really be A-B in early and A-C in late response/differentiation/etc. Such could be the source of some FP and FNs rightly mentioned by qdjm, even when many are of a technical nature.

Entering edit mode
9.5 years ago

My experience is similar to yours.


Login before adding your answer.

Traffic: 1669 users visited in the last hour
Help About
Access RSS

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.

Powered by the version 2.3.6