Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00527
Bounds and algorithms for graph trusses
Paul Burkhardt,
Vance Faber, and
David G. Harris
Vol. 24, no. 3, pp. 191-214, 2020. Regular paper.
Abstract The $k$-truss, introduced by Cohen (2005), is a graph where every edge is incident to at least $k$
triangles. This is a relaxation of the clique. It has proved to be a useful tool in identifying cohesive
subnetworks in a variety of real-world graphs. Despite its simplicity and its utility, the combinatorial and algorithmic aspects of trusses have not been thoroughly explored.
We provide nearly-tight bounds on the edge counts of $k$-trusses. We also give two improved algorithms for finding trusses in large-scale
graphs. First, we present a simplified and faster algorithm, based on approach
discussed in Wang & Cheng (2012). Second, we present a theoretical algorithm based on
fast matrix multiplication; this converts a triangle-generation algorithm of Björklund et al. (2014) into a dynamic
data structure.
|
Submitted: November 2018.
Reviewed: June 2019.
Revised: July 2019.
Accepted: January 2020.
Final: April 2020.
Published: April 2020.
Communicated by
Xin He
|
Journal Supporters
|