Please use this identifier to cite or link to this item:
Type: Artigo de evento
Title: Accelerated Motif Detection Using Combinatorial Techniques
Author: Meira L.A.A.
Maximo V.R.
Fazenda A.L.
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.
Rights: fechado
Identifier DOI: 10.1109/SITIS.2012.113
Date Issue: 2012
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
2-s2.0-84874098490.pdf677.27 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.