# Local Clustering Coefficient (LCC)

#### Definition

**Clustering Coefficient**

The clustering coefficient C(p) is defined as follows. Suppose that a vertex v has k

_{v}neighbours; then at most k

_{v}(k

_{v}-1)/2 edges can exist between them (this occurs when every neighbour of v is connected to every other neighbour of v). Let C

_{v}denote the fraction of these allowable edges that actually exist. Define C as the average of C

_{v}over all v. For friendship networks, these statistic have intuitive meanings: C

_{v}reflects the extent to which friends of v are also friends of each other; and thus C measures the cliquishness of a typical friendship circle. [WATTS, D. 1998]

**Local Clustering Coefficient**

The local clustering coefficient of a vertex (node) in a graph quantifies how close its neighbors are to being a clique (complete graph).

The local clustering coefficient C_{i} for a vertex V_{i}
is then given by the proportion of links between the vertices within its
neighbourhood divided by the number of links that could possibly exist between
them.

For a directed graph, e_{ij} is distinct from e_{ji},
and therefore for each neighbourhood N_{i}
there are K_{i}(K_{i}-1)
links that could exist among the vertices within the neighbourhood (K_{i}
is the number of neighbors of a vertex). Thus, the local clustering coefficient
for directed graphs is given as:

An undirected graph has the property that e_{ij}
and e_{ji}
are considered identical. Therefore, if a vertex Vi
has K_{i}
neighbours, K_{i}(K_{i}-1)/2
edges could exist among the vertices within the neighbourhood. Thus, the local clustering coefficient for undirected graphs can be defined as

**Transitivity**

Transitivity measures the probability that the adjacent vertices of a vertex are connected. This is sometimes also called the clustering coefficient.

The local transitivity of a vertex is the ratio of the triangles connected to the vertex and the triples centered on the vertex. For directed graph the direction of the edges is ignored.

**Weighted Transitivity**

There are several generalizations of transitivity to weighted graphs, and the definition by A. Barrat, is a local vertex-level quantity, its formula is

_{i}is the strength of vertex i, a

_{ij}are elements of the adjacency matrix, k

_{i}is the vertex degree, w

_{ij}are the weights. This formula gives back the normal not-weighted local transitivity if all the edge weights are the same. The barrat type of transitivity does not work for graphs with multiple and/or loop edges. [CSARDI, G. 2008]

**In Bipartite Networks**

LIEBIG, J. & RAO, A. 2014. A Clustering Coefficient to Identify Important Nodes in Bipartite Networks. arXiv preprint arXiv:1406.5814.

#### Software

- GTNA

https://www.p2p.tu-darmstadt.de/research/gtna/ - Functional Genomics Assistant (FUGA)

http://code.google.com/p/fuga - JUNG

http://jung.sourceforge.net - igraph

http://igraph.org - NetworkAnalyzer

http://med.bioinf.mpi-inf.mpg.de/networkanalyzer/ - NodeXL

http://nodexl.codeplex.com/ - Pajek

http://pajek.imfm.si/ - SBEToolbox

https://github.com/biocoder/SBEToolbox/releases

#### References

- WATTS, D. J. & STROGATZ, S. H. 1998. Collective dynamics of 'small-world' networks. Nature, 393, 440-2.
- CSARDI, G. & NEPUSZ, T. 2006. The igraph software package for complex network research. InterJournal, Complex Systems, 1695. [http://igraph.org]
- BARRAT, A., BARTHELEMY, M., PASTOR-SATORRAS, R. & VESPIGNANI, A. 2004. The architecture of complex weighted networks. Proceedings of the National Academy of Sciences of the United States of America, 101, 3747-3752.
- JUNG, the Java Universal Network/Graph Framework [http://jung.sourceforge.net]