Graph Analytics

Improving Scheduling for Irregular Applications with Logarithmic Radix Binning

Effective scheduling and load balancing of applications on massively multi-threading systems remains challenging despite decades of research, especially for irregular and data dependent problems where the execution control path is unknown until …

Scalable K-Core Decomposition for Static Graphs Using a Dynamic Graph Data Structure

Scalable K-Core Decomposition for Static Graphs Using a Dynamic Graph Data Structure

The k-core of a graph is a metric used in a wide range of applications, including social networks analytics, visualization, and graph coloring. Finding the maximal k-core of a graph can be be done in near linear time. The low computational …

Logarithmic Radix Binning and Vectorized Triangle Counting

Triangle counting is a building block for numerous graph applications and given the fact that graphs continue to grow in size, its scalability is important. As such, numerous algorithms have been designed for triangle counting-some of which are …

Scaling Betweenness Centrality in Dynamic Graphs

The Betweenness Centrality of a vertex is an important metric used for determining how “central” a vertex is in a graph based on the number of shortest paths going through that vertex. Computing the betweenness centrality of a graph is …