Towards a Faster Network-Centric Subgraph Census

• Type: Article in International Conference Proceedings Book
• Date: 2013

Authors

paredes, p (Author) Other; ribeiro, p (Author) FCUP

Conference proceedings International

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

Pages: 270-277

Advances in Social Networks Analysis and Mining 2013, ASONAM '13, Niagara, ON, Canada - August 25 - 29, 2013

Indexing

ISI Web of Knowledge - 5 Citations

Scopus - 24 Citations

Other information

Authenticus ID: P-009-3YT

DOI: 10.1145/2492517.2492535

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 8