Rand-FaSE: fast approximate subgraph census

• Type: Article in International Scientific Journal
• Date: 2015

Authors

Paredes, P (Author) Other; Pedro Ribeiro (Author) FCUP

Journal

Title: Social Network Analysis and Mining

Vol. 5

Pages: 17:1-18

ISSN: 1869-5450

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 12 Citations

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 18