A New Approach to Count Pattern Motifs Using Combinatorial Techniches

Details A New Approach to Count Pattern Motifs Using Combinatorial Techniches A New Approach to Count Pattern Motifs Using Combinatorial Techniches

2012-03-15

arxiv.org/abs/1203.3415v1

Computer Science

Computational Complexity

Scientific paper

We proposed two new exact algorithms to detect network motifs of size 3 and 4. Considering that motifs need to count the isomorphic patterns in the original graph $G(V,E)$ and in a set of randomized graphs, the following complexities concern about count isomorphic patterns in a single graph. Let $m=|E|$ and let $a(G)$ be the arboricity of $G$. Assume $|E|\geq|V|$. We describe a $O(a(G)m)$ time complexity algorithm to count isomorphic patterns of size 3. The complexity is a $O({m\sqrt{m}})$ in the worst graph. The second algorithm is a $O(m^2)$ complexity algorithm to count isomorphic patterns of size 4. The final result was expressive faster when compared with other implemented algorithms.

Affiliated with

Also associated with

No associations

Rating

A New Approach to Count Pattern Motifs Using Combinatorial Techniches does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A New Approach to Count Pattern Motifs Using Combinatorial Techniches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A New Approach to Count Pattern Motifs Using Combinatorial Techniches will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-31475