Large scale graph representations for subgraph census

Pedro Paredes, Pedro Ribeiro

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A Subgraph Census (determining the frequency of smaller subgraphs in a network) is an important computational task at the heart of several graph mining algorithms. Here we focus on the g-tries, an efficient state-of-the art data structure. Its algorithm makes extensive use of the graph primitive that checks if a certain edge exists. The original implementation used adjacency matrices in order to make this operation as fast as possible, as is the case with most past approaches. This representation is very expensive in memory usage, limiting the applicability. In this paper we study a number of possible approaches that scale linearly with the number of edges. We make an extensive empirical study of these alternatives in order to find an efficient hybrid approach that combines the best representations. We achieve a performance that is less than 50% slower than the adjacency matrix on average (almost 3 times more efficient than a naive binary search implementation), while being memory efficient and tunable for different memory restrictions.

Original languageEnglish (US)
Title of host publicationAdvances in Network Science - 12th International Conference and School, NetSci-X 2016, Proceedings
EditorsUlrik Brandes, Dino Pedreschi, Adam Wierzbicki, Frank Schweitzer
PublisherSpringer Verlag
Number of pages9
ISBN (Print)9783319283609
StatePublished - 2016
Externally publishedYes
Event12th International Conference and School on Advances in Network Science, NetSci-X 2016 - Wroclaw, Poland
Duration: Jan 11 2016Jan 13 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference12th International Conference and School on Advances in Network Science, NetSci-X 2016

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Complex networks
  • G-tries
  • Large scale graphs
  • Motifs


Dive into the research topics of 'Large scale graph representations for subgraph census'. Together they form a unique fingerprint.

Cite this