Local Clustering Coefficient

From SONIVIS:Wiki

Local Clustering Coefficient This metric is implemented in v0.9. This metric is calculated with R.

The Local Clustering Coefficient calculates the probability that adjacent nodes of a single node are connected.

Objective

With the measure Local Clustering Coefficient we calculate the probability of neighbors (adjacent nodes) of a node to be neighbors to each other as well. If node A is connected to node B, and node B is connected to node C, then there is a heightened probability that node A is also connected to node C. It is also called transitivity.

The Local Clustering Coefficient can also show the replaceability of a node. If neighbors of a single node are neighbors to each other as well, these neighbors do not depend on this single node for their connection. Therefore the intermediate node is completely needless for the connection between these two neighbors.

In comparison the Network Local Clustering Coefficient measures the Local Clustering Coefficient for the whole network.

Calculation

Simple example for calculating the Local Clustering Coefficient for node 1 (Please click to enlarge)

The Local Clustering Coefficient is calculated by the fraction of permitted edges between the neighbors of a single node to them that actually exist for these neighbors^[1]. If a node is connected to an unordered pair of other nodes (neighbors) these three build a triple. The number of triples indicates the number of permitted edges between the neighbors of a node. If two neighbors of a node are also connected by an edge then these three nodes build a triangle. Counting the number of triangles reveals the number of edges that actually exist for the neighbors of a certain node.

^[1]

A network consists of a set of nodes (vertices) and a set of edges between them. A node has neighbors defined in the neighborhood N. For neighbors of exist at most edges in an undirected network (this occurs when every neighbor of is connected to every other neighbor of ). The edge is an edge between the neighbors and of node .

The result of this calculation is a number between 0 and 1, with 1 meaning all neighbors of n_i are neighbors of each other as well.

In SONIVIS directed networks are considered as undirected ones as well, therefore the calculation for directed and undirected networks is the same. Furthermore, in SONIVIS we consider only unweighted networks for the calculation of the Local Clustering Coefficient. A calculation with weighted networks was proposed by Barrat et al. (2004)^[1].

Statement

Reference

• R documentation of transitivity (igraph)

Additional Readings

• Wasserman, S., and Faust, K. (1994). Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press. Bib
• Wikipedia article: Clustering Coefficient