Rand-FaSE: Fast Approximate Subgraph Census Pedro Paredes and Pedro Ribeiro 2015

Abstract

Abstract 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. 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.

Keywords

Complex Networks; Graph Mining; Subgraphs; G-Tries; Network Motifs; Graphlets

Digital Object Identifier (DOI)

doi 10.1007/s13278-015-0256-2

Publication in PDF format

pdf Download PDF

Software

software FaSE

Journal/Conference/Book

Social Network Analysis and Mining

Reference (text)

Pedro Paredes and Pedro Ribeiro. Rand-FaSE: Fast Approximate Subgraph Census. In Social Network Analysis and Mining, Vol. 5(1), pp. 1-18, Springer, 2015.

Bibtex

@article{ribeiro-SNAM2015,
  author = {Pedro Paredes and Pedro Ribeiro},
  title = {Rand-FaSE: Fast Approximate Subgraph Census},
  doi = {10.1007/s13278-015-0256-2},
  journal = {Social Network Analysis and Mining},
  volume = {5},
  issue = {1},
  pages = {1-18},
  publisher = {Springer},
  year = {2015}
}