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 smallworld
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.
SNAP also 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 smallworld
networks. The SNAP framework 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.
