PaperlayerView exact revision on arXiv

Source-linked AI summary

SNAP: A General Purpose Network Analysis and Graph Mining Library

Jure Leskovec, Rok Sosic

arXiv:1606.07550v1cs.SIcs.DBphysics.soc-ph

TL;DR

Large-network research needs tools that combine scalability, algorithmic breadth, compact representations, dynamic updates, and usability. The paper presents SNAP as a high-performance single-machine library with flexible containers, generic graph methods, open-source implementations, and a complementary public dataset collection. SNAP’s design balances efficient graph algorithms with low-cost structural modification and compact memory use, while supporting broad graph-analysis functionality.

  • Problem

    Existing large-graph systems do not jointly provide scalability, ease of use, numerous algorithms, dynamic-network support, compact representations, and open-source availability.

  • Method

    SNAP combines flexible graph and network containers with representation-agnostic methods, dynamic graph operations, and a public collection of social and information network datasets.

  • Results

    SNAP provides broad graph-analysis functionality while balancing efficient structural modification, fast algorithm execution, and compact memory use on large graphs.

  • Takeaways & Limitations

    SNAP offers an open-source C++ library and Python module, complemented by public datasets for graph-analytics development and benchmarking.

  • Takeaways & Limitations

    The paper describes SNAP as designed for single large-memory machines and identifies parallel execution and broader graph-construction primitives as ongoing extensions.

Abstract

from arXiv · show

Large networks are becoming a widely used abstraction for studying complex systems in a broad set of disciplines, ranging from social network analysis to molecular biology and neuroscience. Despite an increasing need to analyze and manipulate large networks, only a limited number of tools are available for this task. Here, we describe Stanford Network Analysis Platform (SNAP), a general-purpose, high-performance system that provides easy to use, high-level operations for analysis and manipulation of large networks. We present SNAP functionality, describe its implementational details, and give performance benchmarks. SNAP has been developed for single big-memory machines and it balances the trade-off between maximum performance, compact in-memory graph representation, and the ability to handle dynamic graphs where nodes and edges are being added or removed over time. SNAP can process massive networks with hundreds of millions of nodes and billions of edges. SNAP offers over 140 different graph algorithms that can efficiently manipulate large graphs, calculate structural properties, generate regular and random graphs, and handle attributes and meta-data on nodes and edges. Besides being able to handle large graphs, an additional strength of SNAP is that networks and their attributes are fully dynamic, they can be modified during the computation at low cost. SNAP is provided as an open source library in C++ as well as a module in Python. We also describe the Stanford Large Network Dataset, a set of social and information real-world networks and datasets, which we make publicly available. The collection is a complementary resource to our SNAP software and is widely used for development and benchmarking of graph analytics algorithms.

1. INTRODUCTION

SNAP addresses the need for scalable, usable, dynamic large-network analysis by combining high-level operations with compact in-memory representations on single big-memory machines. It also provides broad functionality, open-source implementations, and a complementary public dataset collection.

  • SNAP targets large-network analysis with reasonable scalability, ease of use, numerous algorithms, and support for dynamic networks.
  • SNAP balances maximum performance, compact in-memory graph representation, and dynamic modification of nodes and edges on single big-memory multicore machines.
  • SNAP supports graph manipulation, structural-property calculation, graph generation, and node and edge attributes through low-cost dynamic operations.
  • SNAP provides eight graph and network types, 20 graph-generation methods, 20 graph-manipulation methods, over 100 graph algorithms, and over 200 functions.
  • SNAP is available as an open-source C++ library and Python module, complemented by a public collection of about 80 social and information network datasets.

2. RELATED NETWORK ANALYSIS SYSTEMS

Existing network-analysis systems trade off algorithmic breadth, scalability, flexibility, dynamic updates, usability, or maintenance cost. SNAP is positioned as a single-machine alternative that balances these competing requirements.

  • NetworkX prioritizes flexibility through hash-table representations, while this flexibility imposes performance overhead.
  • iGraph emphasizes fast static-network execution but is prohibitively slow for incremental node and edge additions or deletions.
  • SNAP uses about three times less memory than iGraph, while iGraph is about three times faster on some algorithms benefiting from indexes and vector access.
  • SNAP was designed for one large-memory machine, avoiding the programming, maintenance, communication, and coordination costs associated with distributed systems.

3. SNAP FOUNDATIONS

SNAP separates graph and network containers from generic methods, allowing applications to select representations for different graph types and performance needs. Unified interfaces and iterators let algorithms operate across containers while supporting manipulation, persistence, and graph generation.

  • SNAP defines graphs as nodes connected by directed or undirected edges, while networks additionally associate attributes with nodes and edges.
  • Graph and network methods are designed to be agnostic to the underlying graph or network representation.
  • SNAP uses graph containers for wiring diagrams and networks for graphs carrying data on nodes and edges.
  • Graph and Network Containers: Container classes support directed, undirected, multigraph, bipartite, and attributed-network forms, with each optimized for particular graph or network types.
  • Graph and Network Containers: A unified container interface lets graph methods traverse any container type, so algorithms can be implemented once and reused across representations.
  • Functionality of Graph Containers: SNAP groups methods into graph generation, graph manipulation, and graph analytics, and emphasizes efficient loading and saving for graphs with billions of edges.
  • Graph and Network Containers: SNAP supports arbitrary node and edge identifiers, preserving identifiers when graph structure is manipulated, such as during subgraph extraction.
  • Graph and Network Containers: SNAP provides primitives for adding and deleting nodes and edges, saving and loading graphs, and traversing nodes and edges with iterators.

4. GRAPH METHODS

SNAP groups graph creation, manipulation, and analytics methods, including scalable approaches for community detection, missing-network prediction, personalized PageRank, and network inference.

  • Graph analytics: SNAP provides efficient implementations of traditional graph algorithms and newer machine-learning-based methods for community detection, network modeling, prediction, and random walks.These methods address both graph structure and incomplete or evolving network information.
  • Graph method organization: SNAP organizes graph methods into creation, manipulation, and analytics, covering regular, random, and real-world network generation.The library also provides manipulation and analytics methods that compute statistics or modify graph structure.
  • Community detection: Community-detection methods model overlapping communities as densely connected at their intersections, an observation often ignored by traditional methods.SNAP includes AGM-based network-wide detection and Circles-based categorization of friends in ego networks using connections and profile information.
  • Network prediction: MAG-based methods predict missing nodes, edges, and node features, or model network evolution over time.The methods target settings where only part of the network or its attributes is observed.
  • Random walks: SNAP implements bidirectional personalized PageRank computation by working backward from a target and then generating forward random walks.In social networks, the task can identify source nodes interested in a given target node.
  • Information diffusion: SNAP’s network-inference algorithms reconstruct networks or dynamic changes from observed information-propagation cascades and scale to large datasets.The static inference algorithm is described as provably near-optimal in practice, while a separate alternative addresses dynamic networks.

5. SNAP IMPLEMENTATION DETAILS

SNAP’s implementation balances flexible graph updates, compact memory use, and high performance through hash-table and vector structures, layered abstractions, and reusable interfaces.

  • Graph representation: Node identifiers are stored in a hash table, while adjacency information is stored in one or two vectors of neighboring node or edge identifiers.This structure distinguishes undirected from directed graphs and supports compact adjacency storage.
  • Graph representation: SNAP chooses a middle ground between all-hash-table and all-vector graph representations to support both performance and flexible graph modification.Graphs use a node hash table with one vector for undirected graphs or separate incoming and outgoing vectors for directed graphs.
  • Graph representation: Sorted adjacency vectors provide fast access, ordered traversal, and neighbor selection for sparse networks with skewed degree distributions.For typical real-world networks, the traversal benefits outweigh the sorting overhead.
  • Memory efficiency: SNAP’s representation uses less overall memory than alternatives when edge storage dominates, helping larger networks fit in available RAM and reducing memory access.Although SNAP may use more memory for nodes, it uses less for edges, and most relevant networks contain more edges than nodes.
  • Operation complexity: Most SNAP graph operations run in O(1), while edge operations depend on node degree and remain efficient because most real-world nodes have low degree.The comparison is against maintaining neighbors in hash tables rather than sorted vectors.
  • Implementation layers: SNAP’s layered design separates scalar classes, composite structures, graph containers, and graph methods so higher levels abstract lower-level complexity.Unified iterators allow one algorithm implementation to operate across graph and network container types.
  • Memory management: Reference counting automatically releases unused complex objects with low performance impact distributed across many operations.This makes memory management transparent to SNAP users.

6. BENCHMARKS

SNAP balances performance, memory efficiency, and graph-structure flexibility on a single machine. Benchmarks show strong memory, I/O, mutation, algorithmic, and parallel performance across large graphs.

  • SNAP occupies an intermediate performance–flexibility position between iGraph and NetworkX.iGraph emphasizes performance but limited dynamic-structure support, whereas NetworkX emphasizes flexibility at lower performance.
  • Memory consumption: 1.3GB lets SNAP store a 10M-node, 100M-edge graph, compared with over 3.3GB for iGraph and nearly 55GB for NetworkX.
  • Memory consumption: 123.5 billion edges fit in 1024GB with SNAP, versus 31.9 billion for iGraph and 2.1 billion for NetworkX.
  • Basic graph operations: SNAP is over 15 times faster than iGraph and 100 times faster than NetworkX for graph loading and saving using binary graph representations.SNAP and iGraph have similar performance with textual formats.
  • Basic graph operations: SNAP is about 10–20% faster than or comparable to iGraph for edge-existence tests and much faster than both systems when deleting nodes.The deletion benchmark removes 10% of nodes and corresponding edges from G(1M, 10M).
  • Graph algorithms: SNAP is equal to iGraph in some graph operations, about three times slower in vector-favorable algorithms, and 4–60 times faster than NetworkX.NetworkX performs best for many random accesses, while vector-based access favors iGraph.
  • Parallel performance: Parallel SNAP on one machine can offer comparable performance to specialized algorithms and distributed systems for network analysis.On Twitter2010, PageRank required 6s per iteration on one machine with 40 cores, versus 3.6s on PowerGraph using 64 machines and 512 cores.
  • Parallel performance: A single multi-core, big-memory machine provides an attractive platform for analyzing a large majority of networks.SNAP used about 13GB of RAM for the Twitter2010 graph.

7. STANFORD LARGE NETWORK DATASET COLLECTION

The Stanford Large Network Dataset Collection provides publicly available real-world social and information networks for graph-analysis development and benchmarking.

  • The collection contains around 80 social and information networks spanning social, citation, collaboration, Internet, Web, and media domains.
  • Most collection graphs contain fewer than 100 million edges and can therefore be analyzed in SNAP.These graph sizes also make the benchmark results indicative of execution times on real-world networks.

8. RESOURCES

SNAP resources include an actively maintained open-source codebase, documentation, tutorials, releases, repositories, and the accompanying dataset collection.

  • SNAP resources include documentation, tutorials, stable releases, GitHub repositories, a programming guide, and the dataset collection.
  • The complete SNAP source code is released under a permissive BSD-type open-source license, with community contributions welcomed.

9. CONCLUSION

SNAP’s graph representation balances efficient structural modification with fast algorithms and compact memory use. Ongoing work extends parallel execution and graph-construction support.

  • SNAP combines efficient node and edge updates with limited overhead for graph algorithms and lower RAM use than alternative representations.
  • Future extensions target faster parallel algorithms and primitives for constructing graphs from data.
Loading 1606.07550v1…