Triangle Counting

Supported Graph Characteristics

Unweighted edges

Undirected edges

Homogeneous vertex types

Algorithm link: Triangle Counting

Why triangles? Think of it in terms of a social network:

  • If A knows B, and A also knows C, then we complete the triangle if B knows C. If this situation is common, it indicates a community with a lot of interaction.

  • The triangle is in fact the smallest multi-edge "complete subgraph," where every vertex connects to every other vertex.

Triangle count (or density) is a measure of community and connectedness. In particular, it addresses the question of transitive relationships: If A-→ B and B-→C, then what is the likelihood of A-→ C?

Note that it is computing a single number: How many triangles are in this graph? It is not finding communities within a graph.

It is not common to count triangles in directed graphs, though it is certainly possible. If you choose to do so, you need to be very specific about the direction of interest: In a directed graph, If A-→ B and B-→ C, then

  • if A→C, we have a "shortcut".

  • if C→A, then we have a feedback loop.

Notes

This algorithm can only be run on TigerGraph v3.1 or higher.

Most applications of Triangle Count for a directed graph are better served by Cycle Detection.

Specifications

We present two different algorithms for counting triangles. The first, tri_count(), is the classic edge-iterator algorithm. For each edge and its two endpoint vertices S and T, count the overlap between S’s neighbors and T’s neighbors.

tg_tri_count(STRING v_type, STRING e_type)

One side effect of the simple edge-iterator algorithm is that it ends up considering each of the three sides of a triangle. The count needs to be divided by 3, meaning we did 3 times more work than a smaller algorithm would have.

tri_count_fast() is a smarter algorithm which does two passes over the edges. In the first pass we mark which of the two endpoint vertices has fewer neighbors. In the second pass, we count the overlap only between marked vertices. The result is that we eliminate 1/3 of the neighborhood matching, the slowest 1/3, but at the cost of some additional memory.

tg_tri_count_fast(STRING v_type, STRING e_type)

Parameters

Parameter Description Default

STRING v_type

Vertex type to count

(empty string)

e_type

Edge type to traverse

(empty string)

Output

Returns the number of triangles in the graph, in JSON format.

{
  "results": [
    {"num_triangles": 0}
  ]
}

This algorithm does not list out the members of each triangle or assign triangle IDs to each vertex.

Time complexity

This algorithm has a time complexity of \$O(V*E)\$, where \$V\$ is equal to the number of vertices and \$E\$ is equal to the number of edges.

Example

Consider a graph with Person vertices and Coworker edges.

From the vertex display alone, a human can clearly see that there are 4 triangles.

gr social10 coworker

The query returns the same result.

{
  "error": false,
  "message": "",
  "version": {
    "edition": "developer",
    "schema": 0,
    "api": "v2"
  },
  "results": [
    {"num_triangles": 4}
  ]
}