Linear Algebraic Formulation of Edge-Centric K-truss Algorithms with Adjacency Matrices

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2019
Accession Number
AD1090847

Entities

People

  • Anurag Kutuluru
  • Daniele G. Spampinato
  • Doru T. Popovici
  • Franz Franchetti
  • Scott McMillan
  • Tze M. Low
  • Upasana Sridhar

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Advanced Electronics

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Department Of Defense
  • Engineering
  • Equations
  • Governments
  • Iterations
  • Linear Algebra
  • Materials
  • Observation
  • Optimization
  • Quadrants
  • Side Effects
  • Software Development
  • Triangles
  • Universities

Fields of Study

  • Computer science

Readers

  • Computational Modeling and Simulation
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space