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.