Towards a Faster Network-Centric Subgraph Census

Pedro Paredes and Pedro Ribeiro

2013

Abstract

Determining the frequency of small subgraphs is an important computational task lying at the core of several graph mining methodologies, such as network motifs discovery or graphlet based measurements. In this paper we try to improve a class of algorithms available for this purpose, namely network-centric algorithms, which are based upon the enumeration of all sets of k connected nodes. Past approaches would essentially delay isomorphism tests until they had a finalized set of k nodes. In this paper we show how isomorphism testing can be done during the actual enumeration. We use a customized g-trie, a tree data structure, in order to encapsulate the topological information of the embedded subgraphs, identifying already known node permutations of the same subgraph type. With this we avoid redundancy and the need of an isomorphism test for each subgraph occurrence. We tested our algorithm, which we called FaSE, on a set of different real complex networks, both directed and undirected, showcasing that we indeed achieve significant speedups of at least one order of magnitude against past algorithms, paving the way for a faster network-centric approach.

Keywords

Complex Networks; Graph Mining; Subgraphs; G-Tries; Network Motifs; Graphlets

Reference (text)

Pedro Paredes and Pedro Ribeiro. Towards a Faster Network-Centric Subgraph Census. Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 264-271, IEEE, Niagara Falls, Canada, August, 2013.

Bibtex

@inproceedings{ribeiro-ASONAM2013,
  author = {Pedro Paredes and Pedro Ribeiro},
  title = {Towards a Faster Network-Centric Subgraph Census},
  doi = {10.1145/2492517.2492535},
  booktitle = {IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining},
  pages = {264-271},
  publisher = {IEEE},
  month = {August},
  year = {2013}
}