Dissemin is shutting down on January 1st, 2025

Published in

Proceedings of the 2nd ACM SIGMOD Workshop on Databases and Social Networks - DBSocial '12

DOI: 10.1145/2304536.2304541

Links

Tools

Export citation

Search in Google Scholar

Querying subgraph sets with G-tries

Journal article published in 2012 by Pedro Ribeiro ORCID, Fernando Silva ORCID
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

In this paper we present an universal methodology for finding all the occurrences of a given set of subgraphs in one single larger graph. Past approaches would either enumerate all possible subgraphs of a certain size or query a single subgraph. We use g-tries, a data structure specialized in dealing with subgraph sets. G-Tries store the topological information on a tree that exposes common substructure. Using a specialized canonical form and symmetry breaking conditions, a single non-redundant search of the entire set of subgraphs is possible. We give results of applying g-tries querying to different social networks, showing that we can efficiently find the occurrences of a set containing subgraphs of multiple sizes, outperforming previous methods.