An efficient approach for counting occurring induced subgraphs

Luciano Grácio and Pedro Ribeiro

2019

Abstract

Counting subgraph occurrences is a hard but very important task in complex network analysis, with applications in concepts such as network motifs or graphlet degree distributions. In this paper we present a novel approach for this task that takes advantage of knowing that a large fraction of subgraph types does not appear at all on real world networks. We describe a pattern-growth methodology that is able to iteratively build subgraph patterns that do not contain smaller non-occurring subgraphs, significantly pruning the search space. By using the g-trie data structure, we are able to efficiently only count those subgraphs that we are interested in, reducing the total computation time. The obtained experimental results are very promising allowing us to avoid the computation of up to 99.78\% of all possible subgraph patterns. This showcases the potential of this approach and paves the way for reaching previously unattainable subgraph sizes.

Keywords

Subgraph Counting; Pattern-Growth; Induced Subgraphs; Occurring Subgraphs; Network Motifs

Reference (text)

Luciano Grácio and Pedro Ribeiro. An efficient approach for counting occurring induced subgraphs. Proceedings of the 10th Conference on Complex Networks (CompleNet), pp. 33-49, Springer, Tarragona, Spain, March, 2019.

Bibtex

@inproceedings{ribeiro-COMPLENET2019,
  author = {Luciano Grácio and Pedro Ribeiro},
  title = {An efficient approach for counting occurring induced subgraphs},
  doi = {10.1007/978-3-030-14459-3_3},
  booktitle = {10th Conference on Complex Networks},
  pages = {33-49},
  publisher = {Springer},
  month = {March},
  year = {2019}
}