Clustering coefficient

The cluster coefficient ( engl. clustering coefficient) is a measure of the formation of cliques and transitivity in a network in graph theory. If all neighbors of a node connected in pairs, so everyone with everyone, then they form a clique. This is synonymous with the concept of transitivity, for within a clique is true: If A is connected to B and A to C, so are B and C are connected. A distinction between the global cluster coefficient characterizing the entire network and the local cluster coefficients characterizing a single node.

Global cluster coefficient

The global clustering coefficient, also known as transitivity is defined as the ratio of the number of triangles to be " connected triples " in a network ( see figure ).

A triangle are three nodes that are all connected to each other. On the other hand connected a triple node 3, of which at least one is connected to the other two. Each triangle is therefore a connected triples, ie all the triangles form a subset of all connected triples. The factor 3 in the numerator of the formula compensates for the fact that a triangle gillt as 3 connected triples. Only by a factor of 3 is replaced by a network consisting of a single triangle the cluster coefficient, which corresponds to a perfect clique.

Local clustering coefficient

The space defined by Duncan Watts and Steven Strogatz local cluster coefficient of a node in a graph referred to in graph theory, the ratio of the number of edges, which actually extend between its neighbors (), and the number of edges which could extend up between the neighbors ( non-directional graph :):

This formula applies to an undirected graph of a directed graph eliminates the factor of 2, since twice as many edges between the neighbors are possible as in a directed graph.

In the graph of the adjacent node 1 has the neighbor, so that the cluster coefficient is 2, and 5, an edge is possible, and also present between these neighbors. Node 2 has three neighbors, between which three edges are possible, but only the neighboring nodes 1 and 5 are connected by an edge. The cluster coefficient is therefore. The cluster coefficient of node 6, so all nodes of degree 1, calculation results, according to the division by zero is zero. This is - implemented JUNG library with the value 1 and results in unnaturally high global cluster coefficients when many nodes have degree 1. Other authors define the local cluster coefficient for isolated nodes and nodes of degree 1. For the adjacent figure are obtained with the latter convention following local cluster coefficient.

The local cluster coefficient can equivalently as

Be defined.

As a global cluster coefficient is often the means of all local cluster coefficient referred to:

This definition does not provide the same value as the first definition of the global cluster Koeffizientens; the order of the calculation of the delta -to- triad relation one hand and the other hand, the averaging is reversed. The difference is effective in the reversal of the operations of the ratio calculation of triangles and cube corners, and the averaging The latter definition is the average of the triangle -to- triple - ratio, the former is calculated in a way, the ratio of the average number of triangles to the central number of triples. Both definitions and can give very different results: For the network shown results and.

Can be calculated easily on the computer and is therefore often used in numerical studies.

Small - world networks have - regardless of the chosen definition - usually high cluster coefficient, random graphs, however, rather low. Natural networks are mostly from small-world type.