k-Truss

Overview

The k-Truss algorithm identifies the maximal cohesive subgraph called truss in the graph. It has wide-ranging applications across various domains, including social networks, biological networks, and transportation networks. By uncovering communities or clusters of closely related nodes, the k-Truss algorithm provides valuable insights into the structure and connectivity of complex networks.

k-Truss were originally defined by J. Cohen in 2005:

• J. Cohen, Trusses: Cohesive Subgraphs for Social Network Analysis (2005)

Concepts

k-Truss

The truss is motivated by a natural observation of social cohesion: if two people are strongly tied, it is likely that they also share ties to others. k-Truss is thus created in this way: a tie between A and B is considered legitimate only if supported by at least k–2 other people who are each tied to A and to B. In other words, each edge in a k-truss joins two nodes that have at least k–2 common neighbors.

The formal definition is, a k-truss is a maximal subgraph in the graph such that each edge is supported by at least k–2 pairs of edges making triangles with the that edge.

The entire graph is shown below, the 3-truss and 4-truss are highlighted in red. This graph does not have truss with 5 or larger value of k.

Ultipa's k-Truss algorithm identifies the maximal truss in each connected component.

Considerations

• At least 3 nodes are contained in a truss (when k≥3).
• In a complex graph where multiple edges can exist between two nodes, the triangles in a truss are counted by edges. Please also refer to the Triangle Counting algorithm.
• The k-Truss algorithm ignores the direction of edges but calculates them as undirected edges.

Syntax

• Command: algo(k_truss)
• Parameters:

Examples

The example graph is as follows:

File Writeback

UQL
algo(k_truss).params({k: 4}).write({
  file:{
      filename: 'truss'
  }
})

Results: File truss

File
d--[102]--a
c--[103]--a
d--[104]--c
f--[105]--a
f--[106]--d
d--[107]--f
f--[108]--d
d--[109]--e
e--[110]--f
f--[111]--c
k--[117]--f
k--[119]--l
g--[120]--k
m--[121]--k
i--[122]--f
m--[123]--f
f--[124]--g
g--[125]--m
m--[126]--l

Direct Return

UQL
algo(k_truss).params({k: 5}) as truss return truss

Results: subgraph

Stream Return

UQL
algo(k_truss).params({k: 5}).stream() as truss5
with pedges(truss5) as e
find().edges(e) as edges
return edges{*}

Results: edges