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.

Example Graph

To create this graph:

// Runs each row separately in order in an empty graphset
create().node_property(@default, "amount", int32)
insert().into(@default).nodes([{_id:"C1", amount: 1}, {_id:"C2", amount: 6}, {_id:"C3", amount: 2}, {_id:"C4", amount: 5}, {_id:"C5", amount: 5}, {_id:"C6", amount: 2}])
insert().into(@default).edges([{_from:"C4", _to:"C1"}, {_from:"C4", _to:"C1"}, {_from:"C4", _to:"C2"}, {_from:"C1", _to:"C2"}, {_from:"C2", _to:"C3"}, {_from:"C1", _to:"C3"}, {_from:"C3", _to:"C5"}, {_from:"C3", _to:"C6"}])

Running on HDC Graphs

Creating HDC Graph

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

CALL hdc.graph.create("hdc-server-1", "hdc_tri_cnt", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_tri_cnt", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

Parameters

Algorithm name: triangle_counting

File Writeback

CALL algo.triangle_counting.write("hdc_tri_cnt", {
  params: {
    type: 1,
    result_type: 2
  },
  return_params: {
    file: {
      filename: "byEdges.txt"
    }
  }
})

algo(triangle_counting).params({
  projection: "hdc_tri_cnt",
  type: 1,
  result_type: 2  
}).write({
  file: {
      filename: "byEdges.txt"
  }
})

Result:

_edge_uuids
1,3,4
2,3,4
6,5,4

CALL algo.triangle_counting.write("hdc_tri_cnt", {
  params: {
    return_id_uuid: "id",
    type: 2,
    result_type: 2
  },
  return_params: {
    file: {
      filename: "byNodes.txt"
    }
  }
})

algo(triangle_counting).params({
  projection: "hdc_tri_cnt",
  return_id_uuid: "id",
  type: 2,
  result_type: 2  
}).write({
  file: {
      filename: "byNodes.txt"
  }
})

Result:

_node_ids
C1,C4,C2
C1,C3,C2

Stats Writeback

CALL algo.triangle_counting.write("hdc_tri_cnt", {
  params: {},
  return_params: {
    stats: {}
  }
})

algo(triangle_counting).params({
  projection: "hdc_tri_cnt"
}).write({
  stats: {}
})

Result:

Full Return

CALL algo.triangle_counting("hdc_tri_cnt", {
  params: {
    result_type: 1
  },
  return_params: {}
}) YIELD result
RETURN result

exec{
  algo(triangle_counting).params({
    result_type: 1
  }) as result
  return result
} on hdc_tri_cnt

Result:

Stream Return

CALL algo.triangle_counting("hdc_tri_cnt", {
  params: {
    return_id_uuid: "id",
    type: 2,
    result_type: 2
  },
  return_params: {
    stream: {}
  }
}) YIELD r
RETURN r

exec{
  algo(triangle_counting).params({
    return_id_uuid: "id",
    type: 2,
    result_type: 2
  }).stream() as r
  return r
} on hdc_tri_cnt

Result:

Stats Return

CALL algo.triangle_counting("hdc_tri_cnt", {
  params: {
    result_type: 1
  },
  return_params: {
    stats: {}
  }
}) YIELD stats
RETURN stats

exec{
  algo(triangle_counting).params({
    result_type: 1
  }).stats() as stats
  return stats
} on hdc_tri_cnt

Result:

Running on Distributed Projections

Creating Distributed Projection

To project the entire graph to its shard servers as dist_tri_cnt:

create().projection("dist_tri_cnt", {
  nodes: {"*": ["*"]}, 
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true
})

Parameters

Algorithm name: triangle_counting

The distributed version of this algorithm only supports identifying triangles by nodes in the graph.

File Writeback

CALL algo.triangle_counting.write("dist_tri_cnt", {
  params: {
    result_type: 1
  },
  return_params: {
    file: {
      filename: "triCnt"
    }
  }
})

algo(triangle_counting).params({
  projection: "dist_tri_cnt",
  result_type: 1
}).write({
  file: {
      filename: "triCnt"
  }
})

triangle
2

CALL algo.triangle_counting.write("dist_tri_cnt", {
  params: {
    result_type: 2
  },
  return_params: {
    file: {
      filename: "triNodes"
    }
  }
})

algo(triangle_counting).params({
  projection: "dist_tri_cnt",
  result_type: 2
}).write({
  file: {
      filename: "triNodes"
  }
})

triangle
216173881625411585,3386708019294240770,13330655996528295937
216173881625411585,10088064264821538817,13330655996528295937

The results utilize nodes' _uuid values.