forked from tigergraph/gsql-graph-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
GSQL Graph Algorithms
License
Joecsr24/gsql-graph-algorithms
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
README for GSQL Algorithm Library for TigerGraph version 3.0 or higher 8/19/2020 The GSQL Graph Algorithm Library is a collection of high-performance GSQL queries, each of which implements a standard graph algorithm. Each algorithm is ready to be installed and used, either as a stand-alone query or as a building block of a larger analytics application.GSQL running on the TigerGraph platform is particularly well-suited for graph algorithms: * Turing-complete with full support for imperative and procedural programming, ideal for algorithmic computation. * Parallel and Distributed Processing, enabling computations on larger graphs. * User-Extensible. Because the algorithms are written in standard GSQL and compiled by the user, they are easy to modify and customize. * Open-Source. Users can study the GSQL implementations to learn by example, and they can develop and submit additions to the library. Key Changes since version 3.0 ----------------------------- * New algorithms: estimate_diameter, kcore, maximal_indep_set * Nearly all the algorithms now work as schema-free algorithms, making them much easier to use * Instead of having up to 3 versions of an algorithm, to handle 3 different choices for output style, they have been merge to one version, with parameters for output filename and/or attribute to store the result. * Parameter lists have been updated: - to make an algorithm schema-free, runtime parameters are needed - to specify how to handle the results - other parameters may have been added to make the algorithms easier to tune Library Structure ----------------- You can download the library from github: https://github.com/tigergraph/gsql-graph-algorithms The library contains two main sections: Algorithms and Tests. The Algorithms folder contains template algorithms and scripts to help you customize and install them. There are three folders: schema-free/ contains GSQL queries which are ready to use as is, relying on input parameters to specify vertex types and edge types. templates/ contains template algorithms with some placeholder code and markers which need to be acted on by the installation script. examples/ contains GSQL queries generated from the templates by the installation script. The Tests folder contains small sample graphs that you can use to experiment with the algorithms. In our online documentation, we use the test graphs to show you the expected result for each algorithm. The graphs are small enough that you can manually calculate and sometimes intuitively see what the answers should be. List of GSQL Graph Algorithms ----------------------------- as of Aug 19, 2020 betweenness_cent Betweenness Centrality closeness_cent Closeness Centrality conn_comp Connected Component Detection kcore K-Core wcc_fast Connected Components (Fast) scc Strongly Connected Component Detection label_prop Label Propagation Method for Community Detection louvain_parallel Parallel Louvain Modularity Method with Refinement for Community Detection pageRank [2] PageRank measurement of relative influence of each vertex pageRank_wt [2] Weighted PageRank pageRank_pers [2] Personalized PageRank shortest_ss_no_wt Single-Source Shortest Paths without weight shortest_ss_pos_wt Single-Source Shortest Paths with positive weight shortest_ss_any_wt Single-Source Shortest Paths maximal_indep_set Maximal Independent Set mst Minimum Spanning Tree (MST) msf Minimum Spanning Forest (MSF) cycle_detection Rocha–Thatte algorithm for cycle detection estimate_diameter Heuristic estimate of graph diameter tri_count [1] Count all the triangles, memory effient tri_count_fast [1] Count all the triangles, faster but using more memory cosine_nbor_ss Cosine Similarity from a single vertex cosine_nbor_ap Cosine Similarity for each pair of vertices jaccard_nbor_ss [2] Jaccard Similarity from a single vertex jaccard_nbor_ap [2] Jaccard Similarity for each pair of vertices knn_cosine_ss k-Nearest Neighbor classification, using Cosine Similarity, single source knn_cosine_all k-Nearest Neighbor classification, using Cosine Similarity, batch knn_cosine_cv Cross validation for k-Nearest Neighbor, using Cosine Similarity Notes: [1] This algorithm is not in the schema-first folder; use the install.sh script to customize it for your target graph schema [2] The schema-free version of this algorithm can use only one edge type. If you have a set of edge types, use the template algorithm and the install.sh script Each non-schema-free template algorithm comes in three forms: pageRank.gsql - base version. Results are provided as JSON output. Not persisted to the graph database. pageRank_file.gsql - Results are in CSV format to a file. Not persisted to the graph database. pageRank_attr.gsql - Results are written to vertex or edge attributes which the user specifies. The schema-free algorithms ofter all three options in one algorithm. Get Started ----------- If you want to use one of the test graphs, load it before installing the algorithms: See the README.test file in the tests folder * Install Algorithms: 1) You should create a graph schema in GSQL first. 2) Change into the algorithms folder. 3) Run a installation script, i.e., bash install.sh and answer the questions. * Schema free Algorithms: 1) Change the graph name specified in CREATE statement. 2) Use the script directly. More detailed documentation and examples are available on the web at https://docs.tigergraph.com/graph-algorithm-library
About
GSQL Graph Algorithms
Resources
License
Stars
Watchers
Forks
Packages 0
No packages published
Languages
- Shell 100.0%