DROPS

Document

DOI: 10.4230/OASIcs.ICCSW.2018.1

Speeding Up BigClam Implementation on SNAP

Authors: C. H. Bryan Liu and Benjamin Paul Chamberlain

Published in: OASIcs, Volume 66, 2018 Imperial College Computing Student Workshop (ICCSW 2018)

Abstract

We perform a detailed analysis of the C++ implementation of the Cluster Affiliation Model for Big Networks (BigClam) on the Stanford Network Analysis Project (SNAP). BigClam is a popular graph mining algorithm that is capable of finding overlapping communities in networks containing millions of nodes. Our analysis shows a key stage of the algorithm - determining if a node belongs to a community - dominates the runtime of the implementation, yet the computation is not parallelized. We show that by parallelizing computations across multiple threads using OpenMP we can speed up the algorithm by 5.3 times when solving large networks for communities, while preserving the integrity of the program and the result.

Cite as

C. H. Bryan Liu and Benjamin Paul Chamberlain. Speeding Up BigClam Implementation on SNAP. In 2018 Imperial College Computing Student Workshop (ICCSW 2018). Open Access Series in Informatics (OASIcs), Volume 66, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:OASIcs.ICCSW.2018.1,
  author =	{Liu, C. H. Bryan and Chamberlain, Benjamin Paul},
  title =	{{Speeding Up BigClam Implementation on SNAP}},
  booktitle =	{2018 Imperial College Computing Student Workshop (ICCSW 2018)},
  pages =	{1:1--1:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-097-2},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{66},
  editor =	{Pirovano, Edoardo and Graversen, Eva},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2018.1},
  URN =		{urn:nbn:de:0030-drops-101829},
  doi =		{10.4230/OASIcs.ICCSW.2018.1},
  annote =	{Keywords: BigClam, Community Detection, Parallelization, Networks}
}

Search Results

Documents authored by Chamberlain, Benjamin Paul

Speeding Up BigClam Implementation on SNAP

Abstract

Cite as

Thanks for your feedback!

Could not send message