Saltar para:
Logótipo
Você está em: Início > Publicações > Visualização > G-Tries: a data structure for storing and finding subgraphs
Mapa das Instalações
FC6 - Departamento de Ciência de Computadores FC5 - Edifício Central FC4 - Departamento de Biologia FC3 - Departamento de Física e Astronomia e Departamento GAOT FC2 - Departamento de Química e Bioquímica FC1 - Departamento de Matemática

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

Título
G-Tries: a data structure for storing and finding subgraphs
Tipo
Artigo em Revista Científica Internacional
Ano
2014
Autores
Revista
Vol. 28
Páginas: 337-377
ISSN: 1384-5810
Editora: Springer Nature
Classificação Científica
FOS: Ciências exactas e naturais > Ciências da computação e da informação
CORDIS: Ciências Físicas > Ciência de computadores
Outras Informações
ID Authenticus: P-008-QF0
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.
Idioma: Inglês
Tipo (Avaliação Docente): Científica
Contacto: pribeiro@dcc.fc.up.pt; fds@dcc.fc.up.pt
Nº de páginas: 41
Documentos
Não foi encontrado nenhum documento associado à publicação.
Publicações Relacionadas

Dos mesmos autores

Time series analysis via network science: Concepts and algorithms (2021)
Outra Publicação em Revista Científica Internacional
Silva, VF; Maria Eduarda Silva; Pedro Ribeiro; Silva, F
Temporal Network Comparison using Graphlet-orbit Transitions (2017)
Outras Publicações
Aparício, DO; Pedro Ribeiro; Silva, F
GoT-WAVE: Temporal network alignment using graphlet-orbit transitions (2018)
Outras Publicações
Aparício, DO; Pedro Ribeiro; Milenkovic, T; Silva, F
Querying Volatile and Dynamic Networks (2014)
Capítulo ou Parte de Livro
Sarvenaz Choobdar; Pedro Manuel Pinto Ribeiro; Fernando M A Silva

Ver todas (39)

Das mesmas áreas científicas

On Applying Linear Tabling to Logic Programs (2010)
Tese
MIGUEL AREIAS; Ricardo Rocha
APRIORI Algorithm for Label Ranking (2010)
Tese
Cláudio Sá; Carlos Soares; Joaquim Costa
On the average size of pd automata: an analytic combinatorics approach (2010)
Relatório Técnico
Sabine Broda; António Machiavelo; Nelma Moreira; Rogério Reis
On Covering Path Orthogonal Polygons (preliminary version) (2016)
Relatório Técnico
Ana Paula Tomás; Catarina Lobo Ferreira

Ver todas (137)

Da mesma revista

Guest editors introduction: special issue of the ECMLPKDD 2015 journal track (2015)
Outra Publicação em Revista Científica Internacional
Bielza, C; João Gama; Jorge, AM; Zliobaite, I
Guest Editorial: Special Issue on Data Mining for Geosciences (2019)
Outra Publicação em Revista Científica Internacional
Jorge, AM; Lopes, RL; Larrazabal, G; Nikhalat Jahromi, H
Very fast decision rules for classification in data streams (2015)
Artigo em Revista Científica Internacional
Kosina, P; João Gama
Probabilistic change detection and visualization methods for the assessment of temporal stability in biomedical data quality (2015)
Artigo em Revista Científica Internacional
Carlos Saez; Pedro Pereira Rodrigues; João Gama; Montserrat Robles; Juan M Garcia Gomez
Novel features for time series analysis: a complex networks approach (2022)
Artigo em Revista Científica Internacional
Silva, VF; Maria Eduarda Silva; Pedro Ribeiro; Silva, F

Ver todas (14)

Recomendar Página Voltar ao Topo
Copyright 1996-2024 © Faculdade de Ciências da Universidade do Porto  I Termos e Condições  I Acessibilidade  I Índice A-Z  I Livro de Visitas
Última actualização: 2016-03-23 I  Página gerada em: 2024-10-31 às 22:51:37 | Política de Utilização Aceitável | Política de Proteção de Dados Pessoais | Denúncias