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 |
---|---|---|
|
Vertex type to count |
(empty string) |
|
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.
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.
The query returns the same result.
{
"error": false,
"message": "",
"version": {
"edition": "developer",
"schema": 0,
"api": "v2"
},
"results": [
{"num_triangles": 4}
]
}