A Parallel Algorithm for Counting Subgraphs in Complex Networks

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

Authors

Pedro Ribeiro (Author) FCUP; Fernando Silva (Author) FCUP; Luis Lopes (Author) FCUP

Conference proceedings International

Title: Communications in Computer and Information Science

Pages: 380-393

3rd International Joint Conference on Biomedical Engineering Systems and Technologies

Valencia, SPAIN, JAN 20-23, 2010

Indexing

ISI Web of Knowledge - 3 Citations

Scopus - 5 Citations

Scientific classification

FOS: Engineering and technology > Environmental biotechnology

Other information

Authenticus ID: P-002-Y3R

DOI: 10.1007/978-3-642-18472-7_30

Abstract (EN): Many natural and artificial structures can be represented as complex networks. Computing the frequency of all subgraphs of a certain size can give a very comprehensive structural characterization of these networks. This is known as the subgraph census problem, and it is also important as an intermediate step in the computation of other features of the network, such as network motifs. The subgraph census problem is computationally hard and most associated algorithms for it are sequential. Here we present several increasingly efficient parallel strategies for, culminating in a scalable and adaptive parallel algorithm. We applied our strategies to a representative set of biological networks and achieved almost linear speedups up to 128 processors, paving the way for making it possible to compute the census for bigger networks and larger subgraph sizes.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14