ABSTRACT

"Graphs. Such a simple idea. Map a problem onto a graph then solve it by searching over the graph or by exploring the structure of the graph. What could be easier? Turns out, however, that working with graphs is a vast and complex field. Keeping up is challenging. To help keep up, you just need an editor who knows most people working with graphs, and have that editor gather nearly 70 researchers to summarize their work with graphs. The result is the book Massive Graph Analytics."

Timothy G. Mattson, Senior Principal Engineer, Intel Corp

Expertise in massive-scale graph analytics is key for solving real-world grand challenges from healthcare to sustainability to detecting insider threats, cyber defense, and more. This book provides a comprehensive introduction to massive graph analytics, featuring contributions from thought leaders across academia, industry, and government.

Massive Graph Analytics will be beneficial to students, researchers, and practitioners in academia, national laboratories, and industry who wish to learn about the state-of-the-art algorithms, models, frameworks, and software in massive-scale graph analytics.

part Section I|59 pages

Algorithms: Search and Paths

chapter 2|25 pages

Multi-Objective Shortest Paths

ByStephan Erb, Moritz Kobitzsch, Lawrence Mandow, Peter Sanders

part Section II|98 pages

Algorithms: Structure

chapter 3|22 pages

Multicore Algorithms for Graph Connectivity Problems

ByGeorge M. Slota, Sivasankaran Rajamanickam, Kamesh Madduri

chapter 4|23 pages

Distributed Memory Parallel Algorithms for Massive Graphs

ByMaksudul Alam, Shaikh Arifuzzaman, Hasanuzzaman Bhuiyan, Maleq Khan, V.S. Anil Kumar, Madhav V. Marathe

chapter 6|32 pages

Massive-Scale Distributed Triangle Computation and Applications

ByGeoffrey Sanders, Roger Pearce, Benjamin W. Priest, Trevor Steil

part Section III|172 pages

Algorithms and Applications

chapter 7|32 pages

Computing Top-k Closeness Centrality in Fully Dynamic Graphs

ByEugenio Angriman, Patrick Bisenius, Elisabetta Bergamini, Henning Meyerhenke

chapter 8|29 pages

Ordering Heuristics for Parallel Graph Coloring

ByWilliam Hasenplaugh, Tim Kaler, Tao B. Schardl, Charles E. Leiserson

chapter 9|18 pages

Partitioning Trillion-Edge Graphs

ByGeorge M. Slota, Karen Devine, Kamesh Madduri, Sivasankaran Rajamanickam

chapter 10|45 pages

New Phenomena in Large-Scale Internet Traffic

ByJeremy Kepner, Kenjiro Cho, KC Claffy, Vijay Gadepally, Sarah McGuire, Lauren Milechin, William Arcand, David Bestor, William Bergeron, Chansup Byun, Matthew Hubbell, Michael Houle, Michael Jones, Andrew Prout, Albert Reuther, Antonio Rosa, Siddharth Samsi, Charles Yee, Peter Michaleas

chapter 11|44 pages

Parallel Algorithms for Butterfly Computations

ByJessica Shi, Julian Shun

part Section IV|99 pages

Models

chapter 12|44 pages

Recent Advances in Scalable Network Generation 1

ByManuel Penschuck, Ulrik Brandes, Michael Hamann, Sebastian Lamm, Ulrich Meyer, Ilya Safro, Peter Sanders, Christian Schulz

chapter 13|19 pages

Computational Models for Cascades in Massive Graphs

How to Spread a Rumor in Parallel
ByAjitesh Srivastava, Charalampos Chelmis, Viktor K. Prasanna

chapter 14|33 pages

Executing Dynamic Data-Graph Computations Deterministically Using Chromatic Scheduling

ByTim Kaler, William Hasenplaugh, Tao B. Schardl, Charles E. Leiserson

part Section V|159 pages

Frameworks and Software

chapter 15|25 pages

Graph Data Science Using Neo4j

ByAmy E. Hodler, Mark Needham

chapter 16|23 pages

The Parallel Boost Graph Library 2.0

Active Messages as a Spanning Model for Parallel Graph Computation
ByNicholas Edmonds, Andrew Lumsdaine

chapter 17|11 pages

RAPIDS cuGraph

ByAlex Fender, Brad Rees, Joe Eaton

chapter 18|12 pages

A Cloud-Based Approach to Big Graphs

ByPaul Burkhardt, Christopher A. Waring

chapter 19|18 pages

Introduction to GraphBLAS

ByJeremy Kepner, Peter Aaltonen, David Bader, Aydin Buluc, Franz Franchetti, John Gilbert, Shana Hutchison, Manoj Kumar, Andrew Lumsdaine, Henning Meyerhenke, Scott McMillan, Jose Moreira, John D. Owens, Carl Yang, Marcin Zalewski, Timothy G. Mattson

chapter 20|24 pages

Graphulo: Linear Algebra Graph Kernels

ByLauren Milechin, Shana Hutchison, Hayden Jananthan, Jeremy Kepner, Benjamin A. Miller, Andrew Prout, Siddharth Samsi, Chuck Yee, Vijay Gadepally

chapter 21|41 pages

Interactive Graph Analytics at Scale in Arkouda

ByZhihui Du, Oliver Alvarado Rodriguez, Joseph Patchett, David A. Bader