Discovering topological motifs using a compact notation

Abstract

Discovering topological motifs or common topologies in one or more graphs is an important as well as 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 larger network studies. The explosion in the size of 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 graphs and present a simple three-step approach to solving this problem completely and exactly (without resorting to heuristics). We handle the natural combinatorial explosion due to isomorphisms inherent in the problem (which could result in output size being exponential in the input size) by the use of "compact location lists." In other words, instead of enumerating k elements out of n, we use the (kn) form in an implicit manner (k immediate neighbors of a vertex out of n possible immediate neighbors). 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. © Mary Ann Liebert, Inc.