A Parallel Algorithm for Counting Subgraphs in Complex Networks

Pedro Ribeiro, Fernando Silva and Luís Lopes

2011

Abstract

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.

Keywords

Complex networks; Graph mining; Parallel algorithms; Subgraph census

Reference (text)

Pedro Ribeiro, Fernando Silva and Luís Lopes. A Parallel Algorithm for Counting Subgraphs in Complex Networks. Proceedings of the 3rd International Joint Conference on Biomedical Engineering Systems and Technologies, Revised Selected Papers (BIOSTEC), pp. 380-393, Springer CCIS Vol. 127, Valencia, Spain, 2011.

Bibtex

@inproceedings{ribeiro-BIOSTEC2010,
  author = {Pedro Ribeiro and  Fernando Silva and Luís Lopes},
  title = {A Parallel Algorithm for Counting Subgraphs in Complex Networks},
  doi = {10.1007/978-3-642-18472-7_30},
  booktitle = {3rd International Joint Conference on Biomedical Engineering Systems and Technologies, Revised Selected Papers},
  pages = {380-393},
  publisher = {Springer},
  year = {2011}
}