StreamFaSE: An Online Algorithm for Subgraph Counting in Dynamic Networks

Henrique Branquinho, Luciano Grácio and Pedro Ribeiro

2020

Abstract

Counting subgraph occurrences in complex networks is an important analytical task with applicability in a multitude of domains such as sociology, biology and medicine. This task is a fundamental primitive for concepts such as motifs and graphlet degree distributions. However, there is a lack of online algorithms for computing and updating subgraph counts in dynamic networks. Some of these networks exist as a streaming of edge additions and deletions that are registered as they occur in the real world. In this paper we introduce StreamFaSE, an efficient online algorithm for keeping track of exact subgraph counts in dynamic networks, and we explain in detail our approach, showcasing its general applicability in different network scenarios. We tested our method on a set of diverse real directed and undirected network streams, showing that we are always faster than the current existing methods for this task, achieving several orders of magnitude speedup when compared to a state-of-art baseline.

Keywords

Subgraph census; Dynamic networks; Temporal networks; Streaming; Online algorithm; Motifs; Graphlets

Reference (text)

Henrique Branquinho, Luciano Grácio and Pedro Ribeiro. StreamFaSE: An Online Algorithm for Subgraph Counting in Dynamic Networks. Proceedings of the 9th International Conference on Complex Networks and their Applications (CNA), pp. 688-699, Springer, Madrid, Spain, December, 2020.

Bibtex

@inproceedings{ribeiro-CNA2020,
  author = {Henrique Branquinho and  Luciano Grácio and Pedro Ribeiro},
  title = {StreamFaSE: An Online Algorithm for Subgraph Counting in Dynamic Networks},
  doi = {10.1007/978-3-030-65351-4_55},
  booktitle = {9th International Conference on Complex Networks and their Applications},
  pages = {688-699},
  publisher = {Springer},
  month = {December},
  year = {2020}
}