Triangle Counting

Overview

The Triangle Counting algorithm identifies triangles in a graph, where a triangle represents a set of three nodes that are connected to each other. Triangles are important in graph analysis as they reflect the presence of loops or strong connectivity patterns within the graph.

Triangles in social networks indicate the presence of cohesive communities. Identifying triangles helps in understanding the clustering and interconnectedness of individuals or groups within the network. In financial networks or transaction networks, the presence of triangles can be indicative of suspicious or fraudulent activities. Triangle counting can help identify patterns of collusion or interconnected transactions that might require further investigation.

Concepts

Triangle

In a complex graph, it is possible for multiple edges to exist between two nodes. This can lead to the formation of more than one triangle involving three nodes. Take the graph below as an example:

• Counting triangles assembled by edges, there are 4 different triangles.
• Counting triangles assembled by nodes, there are 2 different triangles.

The number of triangles assembled by edges tends to be greater than those assembled by nodes in complex graph. The choice of assembly principle should align with the objectives of the analysis and the insights sought from the graph data. In social network analysis, where the focus is often on understanding connectivity patterns among individuals, the assembling by node principle is commonly adopted. In financial network analysis or other similar domains, the assembling by edge principle is often preferred. Here, the emphasis is on the relationships between nodes, such as financial transactions or interactions. Assembling triangles based on edges allows for the examination of how tightly nodes are connected and how funds or information flow through the network.

Considerations

• The Triangle Counting algorithm ignores the direction of edges but calculates them as undirected edges.

Syntax

• Command: algo(triangle_counting)
• Parameters:

Examples

The example graph is as follows:

File Writeback

UQL
algo(triangle_counting).params({
  type: 1,
  result_type: 2
}).write({
  file:{
    filename: "te"
}})

Statistics: triangle_count = 3
Results: File te

File
103,104,101
103,104,102
105,104,106

UQL
algo(triangle_counting).params({
  type: 2,
  result_type: 2
}).write({
  file:{
    filename: "tn"
}})

Statistics: triangle_count = 2
Results: Files tn

File
C4,C2,C1
C3,C2,C1

Direct Return

UQL
algo(triangle_counting).params({
  result_type: 1
}) as count 
return count

Results: count

UQL
algo(triangle_counting).params({
  result_type: 2
}) as triangles 
return triangles

Results: triangles

Stream Return

UQL
algo(triangle_counting).params({
  type: 2, 
  result_type:2 
}).stream() as t
call {
  with t
  find().nodes({_uuid in [t.node1, t.node2, t.node3]}) as nodes
  return sum(nodes.amount) as sumAmount
}
return table(t.node1, t.node2, t.node3, sumAmount)

Results: table(t.node1, t.node2, t.node3, sumAmount)

UQL
algo(triangle_counting).params({
  type: 2, 
  result_type:1
}).stream() as tNodes 
algo(triangle_counting).params({
  type: 1, 
  result_type:1
}).stream() as tEdges
return table(tNodes.triangle_count, tEdges.triangle_count)

Results: table(tNodes.triangle_count, tEdges.triangle_count)

Stats Return

UQL
algo(triangle_counting).params({
  result_type: 1
}).stats() as sta 
return sta

Results: sta