Copyrights to these papers may be held by the publishers. The download files are preprints. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Tze-Meng Low, Daniele G. Spampinato, A. Kutuluru, U. Sridhar, Thom Popovici, Franz Franchetti and S. McMillan (Proc. High Performance Extreme Computing (HPEC), 2018)
Linear Algebraic Formulation of Edge-centric K-truss Algorithms with Adjacency Matrices
Comment: MIT GraphChallenge Finalist
Preprint (501 KB)
Published paper (link to publisher)
Bibtex

Edge-centric algorithms using the linear algebraic approach typically require the use of both the incidence and adjacency matrices. Due to the two different data formats, the information contained in the graph is replicated, thereby incurring both time and space for the replication. Using K-truss as an example, we demonstrate that an edge-centric K-truss algorithm, the Eager K-truss algorithm, can be identified from a linear algebraic formulation using only the adjacency matrix. In addition, we demonstrate that our implementation of the linear algebraic edge-centric K-truss algorithm out-performs a Galois’ K-truss implementation by an average (over 53 graphs) of more than 13 times, and up to 71 times.

Keywords:
Graph-algorithms, Algorithm, High performance, Algebraic, Linear algebra, K-truss, Edge-centric, Graphs