40 Algorithms Every Programmer Should Know

Triangles

In graph theory, finding vertices that are well-connected to each other is important for the purpose of analysis. One technique is to try to identify triangles, which are a subgraph that consists of three nodes directly connected to each other, in the network.

Let's look at the use case of fraud detection, which we have also used as a case study towards the end of this chapter. If an egonet of a node, m, consists of three vertices, including vertex m, then this egonet is a triangle. Vertex m will be the ego and the two connected vertices will be alters, say vertex A and vertex B. If both alters are known fraudulent cases, we can safely declare vertex m as fraudulent as well. If one of the alters is involved in fraud, we cannot ...