Condensed Graphs: A Generic Framework for Accelerating Subgraph Census Computation

Miguel Martins and Pedro Ribeiro

2020

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 frequency; Subgraph census; Condensed graph

Reference (text)

Miguel Martins and Pedro Ribeiro. Condensed Graphs: A Generic Framework for Accelerating Subgraph Census Computation. Proceedings of the 11th Conference on Complex Networks (CompleNet), pp. 3-15, Springer, Exeter, UK, March, 2020.

Bibtex

@inproceedings{ribeiro-COMPLENET2020,
  author = {Miguel Martins and Pedro Ribeiro},
  title = {Condensed Graphs: A Generic Framework for Accelerating Subgraph Census Computation},
  doi = {10.1007/978-3-030-40943-2_1},
  booktitle = {11th Conference on Complex Networks},
  pages = {3-15},
  publisher = {Springer},
  month = {March},
  year = {2020}
}