Scalable Triadic Analysis of Large-Scale Graphs: Multi-core vs. Multi-processor vs. Multi-threaded Shared Memory Architectures

摘要

Triadic analysis encompasses a useful set of graph mining methods that arecentered on the concept of a triad, which is a subgraph of three nodes. Suchmethods are often applied in the social sciences as well as many other diversefields. Triadic methods commonly operate on a triad census that counts thenumber of triads of every possible edge configuration in a graph. Like othergraph algorithms, triadic census algorithms do not scale well when graphs reachtens of millions to billions of nodes. To enable the triadic analysis oflarge-scale graphs, we developed and optimized a triad census algorithm toefficiently execute on shared memory architectures. We then conductedperformance evaluations of the parallel triad census algorithm on threespecific systems: Cray XMT, HP Superdome, and AMD multi-core NUMA machine.These three systems have shared memory architectures but with markedlydifferent hardware capabilities to manage parallelism.