Towards a faster network-centric subgraph census

Pedro Paredes, Pedro Ribeiro

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

21 Scopus citations

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 networkcentric algorithms, which are based upon the enumeration of all sets of κ connected nodes. Past approaches would essentially delay isomorphism tests until they had a finalized set of κ 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013
PublisherAssociation for Computing Machinery
Pages264-271
Number of pages8
ISBN (Print)9781450322409
DOIs
StatePublished - 2013
Externally publishedYes
Event2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013 - Niagara Falls, ON, Canada
Duration: Aug 25 2013Aug 28 2013

Publication series

NameProceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013

Other

Other2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2013
Country/TerritoryCanada
CityNiagara Falls, ON
Period8/25/138/28/13

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems

Keywords

  • Complex networks
  • G-tries
  • Graph mining
  • Graphlets
  • Network motifs
  • Subgraphs

Fingerprint

Dive into the research topics of 'Towards a faster network-centric subgraph census'. Together they form a unique fingerprint.

Cite this