Discovering Topological Motifs Using a Compact Notation

Discovering topological motifs or common topologies in one or more graphs is an important and an interesting problem. It had been classically viewed as the subgraph isomorphism problem. This problem and its various flavors are known to be NP-Complete. However, this does not minimize the importance of solving this problem accurately in application areas such as bioinformatics or even large network studies. The explosion in the output is usually caused by isomorphisms in the motif or graph: we present a method to handle this without sacrificing the correct answers. In this paper, we apply the natural notion of maximality, used extensively in strings, to the graphs and present a simple three-step approach to solving this problem completely and accurately (without resorting to heuristics). We handle the natural combinatorial explosion due to isomorphism inherent in the problem by the use of “compact location lists”. In other words, instead of enumerating k elements out of n, we use the form in an implicit manner, this drastically reduces the size of the output without any loss of information. The algorithm we present is linear in terms of the size of the output encoded as compact lists.

By: Laxmi P. Parida

Published in: RC23566 in 2005


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .