Format

Send to

Choose Destination
Inf Vis. 2017 Jul;16(3):157-166. doi: 10.1177/1473871616666393. Epub 2016 Sep 12.

Graphing trillions of triangles.

Author information

1
US National Security Agency, USA.

Abstract

The increasing size of Big Data is often heralded but how data are transformed and represented is also profoundly important to knowledge discovery, and this is exemplified in Big Graph analytics. Much attention has been placed on the scale of the input graph but the product of a graph algorithm can be many times larger than the input. This is true for many graph problems, such as listing all triangles in a graph. Enabling scalable graph exploration for Big Graphs requires new approaches to algorithms, architectures, and visual analytics. A brief tutorial is given to aid the argument for thoughtful representation of data in the context of graph analysis. Then a new algebraic method to reduce the arithmetic operations in counting and listing triangles in graphs is introduced. Additionally, a scalable triangle listing algorithm in the MapReduce model will be presented followed by a description of the experiments with that algorithm that led to the current largest and fastest triangle listing benchmarks to date. Finally, a method for identifying triangles in new visual graph exploration technologies is proposed.

KEYWORDS:

Graph; MapReduce; parallel programming; scalable algorithms; triangle counting; visual analytics

Supplemental Content

Full text links

Icon for PubMed Central
Loading ...
Support Center