Graph Algorithms or Graph Analytics are analytic tools used to determine strength and direction of relationships between objects in a graph. The focus of graph analytics is on pairwise relationship between two objects at a time and structural characteristics of the graph as a whole.
For example, in a graph representing relationships (such as “liking” or “friending” another individual’s profile or site) between individuals, graph analytics can help answer questions like the following:
Graphs are mathematical structures used to model many types of relationships and processes in physical, biological, social and information systems. A graph consists of nodes or vertices (representing the entities in the system) which are connected by edges (representing relationships between those entities). Graphs, however, are more than just nodes and edges ‐ They are powerful data structures you can use to represent complex dependencies in your data.
Graphs can either be directed or undirected based on whether the edges have orientations or not. An undirected graph is connected if every pair of vertices is connected by a path.
A graph that has weights associated with each edge is called a weighted graph.
A cyclic graph is a graph containing at least one graph cycle. A cycle is a path for which the first node corresponds to the last. A graph that is not cyclic is said to be acyclic.
A cyclic graph possessing exactly one (undirected, simple) cycle is called a unicyclic graph.
A cyclic graph is bipartite if all its cycles are of even length
Graphs are sometimes used in surprising ways. There are many problems which may not initially appear to take the form of graphs but can be solved more quickly if they are transformed into a graph:
Examples of data well-suited to Graphs are road networks, communications networks, social networks, web pages and links, and financial transaction data.
Graph Algorithms or Graph Analytics are used in a number of applications
The memory bandwidth advantages of GPUs provide a great way to accelerate data-intensive analytics and graph analytics in particular.
GPUs have many different processing units that can be used at the same time. As such they are well suited for the computational task of “for every X do Y” which can apply to sets of vertices or edges within a large graph.
The computational requirements of large-scale graph processing for cyber analytics, genomics, social network analysis and other fields demand powerful and efficient computing performance that only accelerators can provide.
Implications of using GPUs for graph analytics:
The NVIDIA Graph Analytics library (nvGRAPH) comprises of parallel algorithms for high performance analytics on graphs with up to 2 billion edges. nvGRAPH accelerates analysis of large graphs by making efficient use of the massive parallelism available in NVIDIA Tesla GPUs and makes it possible to build interactive and high throughput graph analytics applications. The nvGRAPH library is freely available as part of the CUDA Toolkit.