Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

Scalable Motif Detection and Aggregation

Dietrich, J. and McCartin, C.

    Motif search in graphs has become a popular field of research in recent years, mainly motivated by applications in bioinformatics. Existing work has focused on simple motifs: small sets of vertices directly connected by edges. However, there are applications that require a more general concept of motif, where vertices are only indirectly connected by paths. The size of the solution space is a major limiting factor when dealing with this kind of motif. We try to address this challenge through motif instance aggregation. It turns out that effective, parallel algorithms can be found to compute instances of generalised motifs in large graphs. To expedite the process, we have developed GUERY, a tool that can be used to define motifs and find motif instances, in graphs represented using the popular JUNG graph library [10]. GUERY consists of two parts - a simple domain specific language that can be used to define motifs, and a solver. The main strengths of GUERY are 1. support for motif instance aggregation, 2. generation of query result streams, as opposed to (very large) static sets of matching instances, 3. support for effective parallelisation in the evaluation of queries. The examples used for validation originate from problems encountered when analysing the dependency graphs of object-oriented programs for instances of architectural antipatterns.
Cite as: Dietrich, J. and McCartin, C. (2012). Scalable Motif Detection and Aggregation. In Proc. Australasian Database Conference (ADC 2012) Melbourne, Australia. CRPIT, 124. Zhang, R. and Zhang, Y. Eds., ACS. 31-40
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS