  Computing subgraph frequencies is a fundamental task that lies at the core of
several network analysis methodologies, such as network motifs and
graphlet-based metrics, which have been widely used to categorize and compare
networks from multiple domains. Counting subgraphs is however computationally
very expensive and there has been a large body of work on efficient algorithms
and strategies to make subgraph counting feasible for larger subgraphs and
networks.
  This survey aims precisely to provide a comprehensive overview of the
existing methods for subgraph counting. Our main contribution is a general and
structured review of existing algorithms, classifying them on a set of key
characteristics, highlighting their main similarities and differences. We
identify and describe the main conceptual approaches, giving insight on their
advantages and limitations, and provide pointers to existing implementations.
We initially focus on exact sequential algorithms, but we also do a thorough
survey on approximate methodologies (with a trade-off between accuracy and
execution time) and parallel strategies (that need to deal with an unbalanced
search space).

Data Structures and Algorithms