Bounds and algorithms for graph trusses

DOI10.7155/JGAA.00527MaRDI QIDQ5119376zbMATH OpenOpenAlexFDO

Authors Paul Burkhardt, Vance Faber, David G. Harris

Publication date 4 September 2020

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1806.05523

zbMATH Keywords

\(k\)-trussesfast matrix multiplication

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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 Bjorklund et al. (2014) into a dynamic data structure.

Recommendations

• Listing triangles
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• Approximately counting triangles in sublinear time
• Experimental and Efficient Algorithms
• Triangle listing algorithms: back from the diversion

Cites work

• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• Arboricity and Subgraph Listing Algorithms
• Fast algorithms for determining (generalized) core groups in social networks
• Fast sparse matrix multiplication
• Faster multi-witnesses for Boolean matrix multiplication
• Finding and counting given length cycles
• Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
• Listing triangles
• Mining graph patterns
• Network clustering via clique relaxation: a community based approach
• On the asymptotic complexity of rectangular matrix multiplication
• Powers of tensors and fast matrix multiplication
• Smallest-last ordering and clustering and graph coloring algorithms
• Solving the maximum clique and vertex coloring problems on very large sparse networks

Cited in

(6)

• scientific article; zbMATH DE number 1538874 (Why is no real title available?)
• Some graph theoretical aspects of generalized truncations
• A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs
• Algorithms and hardness results for the (k, )-cover problem
• Algorithms and hardness results for the (3, 1)-cover problem
• Triangle-covered graphs: algorithms, complexity, and structure

This page was built for publication: Bounds and algorithms for graph trusses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5119376)