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:

  • How many other individuals does the average individual “friend” with?
  • What is the maximum number of “friends” any one individual has?
  • How interconnected are groups of users with one another?
  • How many “friend” relationships does it take to get from one user to another user?
  • Are there isolated groups of individuals who are connected to each other but not to individuals not in their group?

Applications of Graph Analytics include clustering, partitioning, search, shortest path solution, widest path solution, finding connected components, and page rank.

What are Graphs

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.

Types of Graphs

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

Where are Graphs used

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:

  • Partitioning large physical volumes into smaller physical volumes as part of high performance simulations on supercomputers.
  • Parsing speech to determine what is the most likely sequence of words that matches a given set of sounds.
  • Analyzing the way different parts of a complex software program interact in order to proactively find and remove bugs.

Examples of data well-suited to Graphs are road networks, communications networks, social networks, web pages and links, and financial transaction data.

Applications of Graph Algorithms or Graph Analytics:

Graph Algorithms or Graph Analytics are used in a number of applications

  • Clustering - the grouping of objects based on their characteristics such that there is high intra- cluster similarity and low inter-cluster similarity. Applications include machine learning, data mining, statistics, image processing, and numerous physical and social science applications.
  • Cutting or Partitioning – To find the cut with the fewest number of crossing edges. Applications include finding weak spots in data and communications networks, and community detection in social networks.
  • Search – Breadth first search and Depth first search.
  • Shortest path – To find the shortest path between two nodes of interest. Applications include social network analysis, transportation logistics and many other optimization problems.
  • Widest path – To find a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. Applications include IP traffic routing and traffic-sensitive path planning.
  • Connected components – A strongly connected graph is one where you can get to every node in the graph from any starting node. The strongly connected components are the maximal sub- regions of a graph for which each sub-region is strongly connected. Applications include social network analysis.
  • Page Rank – Is a measure of popularity of webpages and is used by internet search for ranking them. Applications also include social network analysis, recommendation systems, and for novel uses in natural science when studying the relationship between proteins and in ecological networks.

Accelerating graph analytics with GPUs

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:

  • 10X reduction in communication costs
  • 2X or greater speedup for BFS with Pascal
  • Much larger problem sizes -> Analyze large graphs faster

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.

Additional Resources: