SNAP, small-world network analysis and partitioning: An open-source parallel graph framework for the exploration of large-scale networks

David A. Bader, Kamesh Madduri

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

93 Scopus citations

Abstract

We present SNAP (Small-world Network Analysis and Partitioning), an open-source graph framework for exploratory study and partitioning of large-scale networks. To illustrate the capability of SNAP, we discuss the design, implementation, and performance of three novel parallel community detection algorithms that optimize modularity, a popular measure for clustering quality in social network analysis. In order to achieve scalable parallel performance, we exploit typical network characteristics of small-world networks, such as the low graph diameter, sparse connectivity, and skewed degree distribution. We conduct an extensive experimental study on real-world graph instances and demonstrate that our parallel schemes, coupled with aggressive algorithm engineering for small-world networks, give significant running time improvements over existing modularity-based clustering heuristics, with little or no loss in clustering quality. For instance, our divisive clustering approach based on approximate edge betweenness centrality is more than two orders of magnitude faster than a competing greedy approach, for a variety of large graph instances on the Sun Fire T2000 multicore system. SNAPalso contains parallel implementations of fundamental graph-theoretic kernels and topological analysis metrics (e.g., breadth-first search, connected components, vertex and edge centrality) that are optimized for small-world networks. The SNAPframework is extensible; the graph kernels are modular, portable across shared memory multicore and symmetric multiprocessor systems, and simplify the design of high-level domain-specific applications.

Original languageEnglish (US)
Title of host publicationIPDPS Miami 2008 - Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium, Program and CD-ROM
DOIs
StatePublished - Sep 10 2008
EventIPDPS 2008 - 22nd IEEE International Parallel and Distributed Processing Symposium - Miami, FL, United States
Duration: Apr 14 2008Apr 18 2008

Publication series

NameIPDPS Miami 2008 - Proceedings of the 22nd IEEE International Parallel and Distributed Processing Symposium, Program and CD-ROM

Other

OtherIPDPS 2008 - 22nd IEEE International Parallel and Distributed Processing Symposium
Country/TerritoryUnited States
CityMiami, FL
Period4/14/084/18/08

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Software
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'SNAP, small-world network analysis and partitioning: An open-source parallel graph framework for the exploration of large-scale networks'. Together they form a unique fingerprint.

Cite this