Towards a Faster Network-Centric Subgraph Census

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

Autores

paredes, p (Autor) Outra; ribeiro, p (Autor) FCUP

Ata de Conferência Internacional

Título: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013

Páginas: 270-277

Advances in Social Networks Analysis and Mining 2013, ASONAM '13, Niagara, ON, Canada - August 25 - 29, 2013

Indexação

ISI Web of Knowledge - 5 Citações

Scopus - 24 Citações

Outras Informações

ID Authenticus: P-009-3YT

DOI: 10.1145/2492517.2492535

Abstract (EN): Determining the frequency of small subgraphs is an important computational task lying at the core of several graph mining methodologies, such as network motifs discovery or graphlet based measurements. In this paper we try to improve a class of algorithms available for this purpose, namely network-centric algorithms, which are based upon the enumeration of all sets of k connected nodes. Past approaches would essentially delay isomorphism tests until they had a finalized set of k nodes. In this paper we show how isomorphism testing can be done during the actual enumeration. We use a customized g-trie, a tree data structure, in order to encapsulate the topological information of the embedded subgraphs, identifying already known node permutations of the same subgraph type. With this we avoid redundancy and the need of an isomorphism test for each subgraph occurrence. We tested our algorithm, which we called FaSE, on a set of different real complex networks, both directed and undirected, showcasing that we indeed achieve significant speedups of at least one order of magnitude against past algorithms, paving the way for a faster network-centric approach.

Idioma: Inglês

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

Nº de páginas: 8