======================================================================== SNAP : Stanford Network Analysis Platform http://snap.stanford.edu ======================================================================== Stanford Network Analysis Platform (SNAP) is a general purpose, high performance system for analysis and manipulation of large networks. SNAP is written in C++ and it scales to massive graphs with hundreds of millions of nodes and billions of edges. ///////////////////////////////////////////////////////////////////////////// Directory structure: http://snap.stanford.edu/snap/description.html snap-core: the core SNAP graph library snap-adv: advanced SNAP components, not in the core, but used by examples snap-exp: experimental SNAP components, still in development examples: small sample applications that demonstrate SNAP functionality tutorials: simple programs, demonstrating use of various classes glib-core: STL-like library that implements basic data structures, like vectors (TVec), hash-tables (THash) and strings (TStr), provides serialization and so on test: unit tests for various classes doxygen: SNAP reference manuals Code compiles under Windows (Microsoft Visual Studio, CygWin with gcc) and Linux and Mac (gcc). Use the SnapExamples*.sln or provided makefiles. Some of applications expect that GnuPlot and GraphViz are installed and accessible -- paths are in the system PATH variable or they reside in the working directory. ///////////////////////////////////////////////////////////////////////////// Example applications for advanced SNAP functionality are available in the examples directory and described at: http://snap.stanford.edu/snap/description.html. To compile from the command line, execute: make all # compiles SNAP and all sample applications To compile on Mac OS X, using Xcode: 1. From the Toolbar, select Scheme (e.g. 'bigclam'). 2. Product -> Build. (or Cmd + B). 3. Run executable via the command line; or Choose the scheme's executable (Product -> Edit Scheme -> Run -> Info) and run: Product -> Run (or Cmd + R). Note: If using Gnuplot, add the PATH to the scheme's environment variables. or create symlink to /usr/bin: sudo ln -s <gnuplot_dir>/gnuplot /usr/bin/ For code completion, the "docs" target has been created which includes all Snap-related files and example programs. Description of examples: agmfit : Detects network communities from a given network by fitting AGM to the given network by maximum likelihood estimation. agmgen : Implements the Affiliation Graph Model (AGM). AGM generates a realistic looking graph from the community affiliation of the nodes. bigclam : Formulates community detection problems into non-negative matrix factorization and discovers community membership factors of nodes. cascadegen : Identifies cascades in a list of events. cascades : Simulates a SI (susceptible-infected) model on a network and computes structural properties of cascades. centrality : Computes node centrality measures for a graph: closeness, eigen, degree, betweenness, page rank, hubs and authorities. cesna : Implements a large scale overlapping community detection method for networks with node attributes based on Communities from Edge Structure and Node Attributes (CESNA). circles : Implements a method for identifying users social circles. cliques : Finds overlapping dense groups of nodes in networks, based on the Clique Percolation Method. coda : Implements a large scale overlapping community detection method based on Communities through Directed Affiliations (CoDA), which handles directed as well as undirected networks. The method is able to find 2-mode communities where the member nodes form a bipartite connectivity structure. community : Implements network community detection algorithms: Girvan-Newman, Clauset-Newman-Moore and Infomap. concomp : Computes weakly, strongly and biconnected connected components, articulation points and bridge edges of a graph. flows : Computes the maximum network flow in a network. forestfire : Generates graphs using the Forest Fire model. graphgen : Generates undirected graphs using one of the many SNAP graph generators. graphhash : Demonstrates the use of TGHash graph hash table, useful for counting frequencies of small subgraphs or information cascades. infopath : Implements stochastic algorithm for dynamic network inference from cascade data, see http://snap.stanford.edu/infopath/. kcores : Computes the k-core decomposition of the network and plots the number of nodes in a k-core of a graph as a function of k. kronem : Estimates Kronecker graph parameter matrix using EM algorithm. kronfit : Estimates Kronecker graph parameter matrix. krongen : Generates Kronecker graphs. localmotifcluster : Implements a local method for motif-based clustering using MAPPR. lshtest : Implements locality sensitive hashing. magfit : Estimates Multiplicative Attribute Graph (MAG) model parameter. maggen : Generates Multiplicative Attribute Graphs (MAG). mkdatasets : Demonstrates how to load different kinds of networks in various network formats and how to compute various statistics of the network. motifcluster : Implements a spectral method for motif-based clustering. motifs : Counts the number of occurrence of every possible subgraph on K nodes in the network. ncpplot : Plots the Network Community Profile (NCP). netevol : Computes properties of an evolving network, like evolution of diameter, densification power law, degree distribution, etc. netinf : Implements netinf algorithm for network inference from cascade data, see http://snap.stanford.edu/netinf. netstat : Computes statistical properties of a static network, like degree distribution, hop plot, clustering coefficient, distribution of sizes of connected components, spectral properties of graph adjacency matrix, etc. randwalk : Computes Personalized PageRank between pairs of nodes. rolx : Implements the rolx algorithm for analysing the structural roles in the graph. testgraph : Demonstrates some of the basic SNAP functionality. temporalmotifs : Counts temporal motifs in temporal networks. zygote : Demonstrates how to use SNAP with the Zygote library, which significantly speeds up computations that need to process the same large graph many times. ///////////////////////////////////////////////////////////////////////////// SNAP documentation: http://snap.stanford.edu/snap/doc.html The library defines Graphs (nodes and edges) and Networks (graphs with data associated with nodes and edges). Graph types: TNGraph : directed graph (single directed edge between a pair of nodes) TUNGraph : undirected graph (single undirected edge between a pair of nodes) TNEGraph : directed multi-graph (multiple directed edges can exist between a pair of nodes) Network types: TNodeNet<TNodeData> : like TNGraph, but with TNodeData object for each node TNodeEDatNet<TNodeData,TEdgeData> : like TNGraph, but with TNodeData object for each node and TEdgeData object for each edge TNodeEdgeNet<TNodeData, TEdgeData> : like TNEGraph but with TNodeData object for each node and TEdgeData object for each edge TNEANet : like TNEGraph, but with attributes on nodes and edges. The attributes are dynamic in that they can be defined at runtime TBigNet<TNodeData> : memory efficient implementation of TNodeNet (avoids memory fragmentation) To generate reference manuals, install doxygen (www.doxygen.org), and execute: cd doxygen; make all # generates user and developer reference manuals ///////////////////////////////////////////////////////////////////////////// SNAP tutorials Sample programs demonstrating the use of foundational SNAP classes and functionality are available in the tutorials directory. To compile all the tutorials, execute the following command line: cd tutorials; make all # generates all the tutorials ///////////////////////////////////////////////////////////////////////////// SNAP unit tests Unit tests are available in the test directory. To run unit tests, install googletest (code.google.com/p/googletest) and execute: cd test; make run # compiles and runs all the tests ///////////////////////////////////////////////////////////////////////////// Description of SNAP files: http://snap.stanford.edu/snap/description.html snap-core: alg.h : Simple algorithms like counting node degrees, simple graph manipulation (adding/deleting self edges, deleting isolated nodes) and testing whether graph is a tree or a star. anf.h : Approximate Neighborhood Function: linear time algorithm to approximately calculate the diameter of massive graphs. bfsdfs.h : Algorithms based on Breath First Search (BFS) and Depth First Search (DFS): shortest paths, spanning trees, graph diameter, and similar. bignet.h : Memory efficient implementation of a network with data on nodes. Use when working with very large networks. casc.h : Computes cascades from a list of events. centr.h : Node centrality measures: closeness, betweenness, PageRank, ... cmty.h : Algorithms for network community detection: Modularity, Girvan-Newman, Clauset-Newman-Moore. cncom.h : Connected components: weakly, strongly and biconnected components, articular nodes and bridge edges. ff.h : Forest Fire model for generating networks that densify and have shrinking diameters. flow.h: Maximum flow algorithms. gbase.h : Defines flags that are used to identify functionality of graphs. ggen.h : Various graph generators: random graphs, copying model, preferential attachment, RMAT, configuration model, Small world model. ghash.h : Hash table with directed graphs (<tt>TNGraph</tt>) as keys. Uses efficient adaptive approximate graph isomorphism testing to scale to large graphs. Useful when one wants to count frequencies of various small subgraphs or cascades. gio.h : Graph input output. Methods for loading and saving various textual and XML based graph formats: Pajek, ORA, DynNet, GraphML (GML), Matlab. graph.h : Implements graph types TUNGraph, TNGraph and TNEGraph. gstat.h : Computes many structural properties of static and evolving networks. gsvd.h : Eigen and singular value decomposition of graph adjacency matrix. gviz.h : Interface to GraphViz for plotting small graphs. kcore.h : K-core decomposition of networks. network.h : Implements network types TNodeNet, TNodeEDatNet and TNodeEdgeNet. randwalk.h : Computing random walk scores and personalized PageRank between pairs of nodes Snap.h : Main include file of the library. statplot.h : Plots of various structural network properties: clustering, degrees, diameter, spectrum, connected components. subgraph.h : Extracting subgraphs and converting between different graph/network types. timenet.h : Temporally evolving networks. triad.h : Functions for counting triads (triples of connected nodes in the network) and computing clustering coefficient. util.h : Utilities to manipulate PDFs, CDFs and CCDFs. Quick and dirty string manipulation, URL and domain manipulation routines. snap-adv: agm*.h : Implements the Affiliation Graph Model (AGM). cliques.h : Maximal clique detection and Clique Percolation method. graphcounter.h : Performs fast graph isomorphism testing to count the frequency of topologically distinct sub-graphs. kronecker.h : Kronecker Graph generator and KronFit algorithm for estimating parameters of Kronecker graphs. mag.h : Implements the Multiplicative Attribute Graph (MAG). motifcluster.h : Implements motif-based clustering algorithms. ncp.h : Network community profile plot. Implements local spectral graph partitioning method to efficiently find communities in networks. rolx.h : Node role detection. subgraphenum.h : Enumerates all connected induced sub-graphs of particular size. snap-exp: arxiv.h : Functions for parsing Arxiv data and standardizing author names. dblp.h : Parser for XML dump of DBLP data. imdbnet.h : Actors-to-movies bipartite network of IMDB. mxdag.h Finds the maximum directed-acyclic subgraph of a given directed graph. signnet.h : Networks with signed (+1, -1) edges that can denote trust/distrust between the nodes of the network. sir.h : SIR epidemic model and SIR parameter estimation. spinn3r.h : Past parser for loading blog post data from Spinn3r. trawling.h : Algorithm of extracting bipartite cliques from the network. wgtnet.h : Weighted networks. wikinet.h : Networks based on Wikipedia.