G-Tries: a data structure for storing and finding subgraphs

• Type: Article in International Scientific Journal
• Date: 2014

Authors

Pedro Ribeiro (Author) FCUP; Fernando Silva (Author) FCUP

Journal

Title: Data Mining and Knowledge Discovery

Vol. 28

Pages: 337-377

ISSN: 1384-5810

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 38 Citations

Scopus - 54 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

CORDIS: Physical sciences > Computer science

Associated Projects

BESTCASE-RL1-SIBILA - Towards Smart Interacting Blocks that Improve Learned Advice

Other information

Authenticus ID: P-008-QF0

DOI: 10.1007/s10618-013-0303-4

Abstract (EN): The ability to find and count subgraphs of a given network is an important non trivial task with multidisciplinary applicability. Discovering network motifs or computing graphlet signatures are two examples of methodologies that at their core rely precisely on the subgraph counting problem. Here we present the g-trie, a data-structure specifically designed for discovering subgraph frequencies. We produce a tree that encapsulates the structure of the entire graph set, taking advantage of common topologies in the same way a prefix tree takes advantage of common prefixes. This avoids redundancy in the representation of the graphs, thus allowing for both memory and computation time savings. We introduce a specialized canonical labeling designed to highlight common substructures and annotate the g-trie with a set of conditional rules that break symmetries, avoiding repetitions in the computation. We introduce a novel algorithm that takes as input a set of small graphs and is able to efficiently find and count them as induced subgraphs of a larger network. We perform an extensive empirical evaluation of our algorithms, focusing on efficiency and scalability on a set of diversified complex networks. Results show that g-tries are able to clearly outperform previously existing algorithms by at least one order of magnitude.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 41