Rand-FaSE: fast approximate subgraph census

• Tipo: Artigo em Revista Científica Internacional
• Data: 2015

Autores

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

Revista

Título: Social Network Analysis and Mining

Vol. 5

Páginas: 17:1-18

ISSN: 1869-5450

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 12 Citações

Outras Informações

ID Authenticus: P-00G-6HF

DOI: 10.1007/s13278-015-0256-2

Abstract (EN): Determining the frequency of small subgraphs is an important graph mining primitive. One major class of algorithms for this task is based upon the enumeration of all sets of k connected nodes. These are known as network-centric algorithms. FAst Subgraph Enumeration (FaSE) is a exact algorithm for subgraph counting that contrasted with its past approaches by performing the isomorphism tests while doing the enumeration, encapsulating the topological information in a g-trie and thus largely reducing the number of required isomorphism tests. Our goal with this paper is to expand this approach by providing an approximate algorithm, which we called Rand-FaSE. It uses an unbiased sampling estimator for the number of subgraphs of each type, allowing an user to trade some accuracy for even faster execution times. We tested our algorithm on a set of representative complex networks, comparing it with the exact alternative, FaSE. We also do an extensive analysis by studying its accuracy and speed gains against previous sampling approaches. With all of this, we believe FaSE and Rand-FaSE pave the way for faster network-centric census algorithms.

Idioma: Inglês

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

Nº de páginas: 18