Fast Streaming Small Graph Canonization

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2018

Autores

Paredes, P (Autor) Outra; Pedro Ribeiro (Autor) FCUP

Ata de Conferência Internacional

Título: COMPLEX NETWORKS IX

Páginas: 27-40

9th International Conference on Complex Networks (CompleNet)

Northeastern Univ, Boston, MA, MAR 05-08, 2018

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Outras Informações

ID Authenticus: P-00P-RJM

DOI: 10.1007/978-3-319-73198-8_3

Abstract (EN): In this paper, we introduce the streaming graph canonization problem. Its goal is finding a canonical representation of a sequence of graphs in a stream. Our model of a stream fixes the graph's vertices and allows for fully dynamic edge changes, meaning it permits both addition and removal of edges. Our focus is on small graphs, since small graph isomorphism is an important primitive of many subgraph-based metrics, like motif analysis or frequent subgraph mining. We present an efficient data structure to approach this problem, namely a graph isomorphism discrete finite automaton and showcase its efficiency when compared to a non-streaming-aware method that simply recomputes the isomorphism information from scratch in each iteration.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 14