Transitivity in a Graph

Transitivity in a Graph

Transitivity is the overall probability for the network to have adjacent nodes interconnected, thus revealing the existence of tightly connected communities (or clusters, subgroups, cliques). It is calculated by the ratio between the observed number of closed triplets and the maximum possible number of closed triplets in the graph. Complex networks and notably small-world networks often have a high transitivity and a low diameter. Because triplets are not the only way to look at neighborhood density among nodes, this measure can be extended to cycles of lengths 4 and 5. The above figure depicts graphs of growing transitivity levels.