Bounds and algorithms for graph trusses

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 c...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-03
Main Authors: Burkhardt, Paul, Faber, Vance, Harris, David G
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Graphs
Multiplication
Social networks
Trusses
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1806.05523