k-Truss

Overview

The k-Truss algorithm identifies the largest cohesive subgraph, called a truss in the graph. It is widely used in fields such as social networks, biology, and transportation. By revealing communities or clusters of closely related nodes, it helps uncover the structure and connectivity of complex networks.

The concept of k-Truss was 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. A k-Truss is thus defined in this way: a tie between A and B is considered legitimate only if it is supported by at least k–2 other people who are each tied to both A and B. In other words, each edge in a k-truss connects two nodes that have at least k–2 common neighbors.

Formally，a k-truss is a maximal subgraph in which every edge is supported by at least k–2 triangles that include that edge.

In the graph below, the 3-Truss and 4-Truss are highlighted in red. The graph does not contain any truss with k equal to or greater than 5.

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 with multiple edges between two nodes, triangles in a truss are counted based on edges. Refer to the Triangle Counting algorithm for additional context.
• The k-Truss algorithm treats all edges as undirected, ignoring their original direction.

Example Graph

Run the following statements on an empty graph to define its structure and insert data:

GQLUQL
INSERT (a:default {_id: "a"}),
       (b:default {_id: "b"}),
       (c:default {_id: "c"}),
       (d:default {_id: "d"}),
       (e:default {_id: "e"}),
       (f:default {_id: "f"}),
       (g:default {_id: "g"}),
       (h:default {_id: "h"}),
       (i:default {_id: "i"}),
       (j:default {_id: "j"}),
       (k:default {_id: "k"}),
       (l:default {_id: "l"}),
       (m:default {_id: "m"}),       
       (b)-[:default]->(a),
       (d)-[:default]->(a),
       (c)-[:default]->(a),
       (d)-[:default]->(c),
       (f)-[:default]->(a),
       (f)-[:default]->(d),
       (d)-[:default]->(f),
       (f)-[:default]->(d),
       (d)-[:default]->(e),
       (e)-[:default]->(f),
       (f)-[:default]->(c),
       (c)-[:default]->(h),
       (i)-[:default]->(m),
       (i)-[:default]->(g),
       (k)-[:default]->(c),
       (k)-[:default]->(c),
       (k)-[:default]->(f),
       (j)-[:default]->(l),
       (k)-[:default]->(l),
       (g)-[:default]->(k),
       (m)-[:default]->(k),
       (l)-[:default]->(f),
       (m)-[:default]->(f),
       (f)-[:default]->(g),
       (g)-[:default]->(m),
       (m)-[:default]->(l);

Creating HDC Graph

To load the entire graph to the HDC server hdc-server-1 as my_hdc_graph:

GQLUQL
CREATE HDC GRAPH my_hdc_graph ON "hdc-server-1" OPTIONS {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static"
}

Parameters

Algorithm name: k_truss

File Writeback

GQLUQL
CALL algo.k_truss.write("my_hdc_graph", {
  k: 4,
  return_id_uuid: "id"
}, {
  file: {
    filename: "4truss"
  }
})

Result:

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

Full Return

GQLUQL
CALL algo.k_truss.run("my_hdc_graph", {
  k: 5
}) YIELD truss
RETURN truss

Result:

Stream Return

GQLUQL
CALL algo.k_truss.stream("my_hdc_graph", {
  k: 5
}) YIELD truss5
FOR node IN pnodes(truss5)
RETURN collect_list(node._id)

Result
["d","a","d","c","d","f","d","e","f","a","f","d","f","d","f","c","e","f"]