Please use this identifier to cite or link to this item:
|Type:||Artigo de evento|
|Title:||Accelerated Motif Detection Using Combinatorial Techniques|
Da Conceicao A.F.
|Abstract:||Network motif algorithms have been a topic of research mainly after the 2002-seminal paper from Milo et al, that provided motifs as a way to uncover the basic building blocks of most networks. This article proposes new algorithms to exactly count isomorphic pattern motifs of size 3 and 4 in directed graphs. The algorithms are accelerated by combinatorial techniques. Let G(V,E) be a directed graph with m = |E|. We describe an O(m√m) time complexity algorithm to count isomorphic patterns of size 3. To counting isomorphic patterns of size 4, we propose an O(m2) algorithm. The new algorithms were implemented and compared with Fanmod motif detection tool. The experiments show that our algorithms are expressively faster than Fanmod. We also let our tool to detect motifs, the acc-MOTIF, available in the Internet. © 2012 IEEE.|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.