Clustering coefficient

Image:Clustering coefficient example.svg The local clustering coefficient of a vertex (node) in a graph quantifies how close its neighbours are to being a clique (complete graph). Duncan J. Watts and Steven Strogatz introduced the measure in 1998 to determine whether a graph is a small-world network.

A graph $G=(V,E)$ formally consists of a set of vertices $V$ and a set of edges $E$ between them. An edge $e\_\{ij\}$ connects vertex $v\_i$ with vertex $v\_j$.

The neighborhood $N\_i$ for a vertex $v\_i$ is defined as its immediately connected neighbours as follows:

: $N\_i\; =\; \backslash \{v\_j\; :\; e\_\{ij\}\; \backslash in\; E\; \backslash lor\; e\_\{ji\}\; \backslash in\; E\backslash \}.$

We define $k\_i$ as the number of vertices, $|N\_i|$, in the neighbourhood, $N\_i$, of vertex $v\_i$.

The local clustering coefficient $C\_i$ for a vertex $v\_i$ is then given by a proportion of the number 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 neighbours of a vertex). Thus, the local clustering coefficient for directed graphs is given as

: $C\_i\; =\; \backslash frac$

An undirected graph has the property that $e\_\{ij\}$ and $e\_\{ji\}$ are considered identical. Therefore, if a vertex $v\_i$ has $k\_i$ neighbours, $\backslash frac\{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

: $C\_i\; =\; \backslash frac\{2|\backslash \{e\_\{jk\}:\; v\_j,v\_k\; \backslash in\; N\_i,\; e\_\{jk\}\; \backslash in\; E\backslash \}|\}\{k\_i(k\_i-1)\}.$

Let $\backslash lambda\_G(v)$ be the number of triangles on $v\; \backslash in\; V(G)$ for undirected graph $G$. That is, $\backslash lambda\_G(v)$ is the number of subgraphs of $G$ with 3 edges and 3 vertices, one of which is $v$. Let $\backslash tau\_G(v)$ be the number of triples on $v\; \backslash in\; G$. That is, $\backslash tau\_G(v)$ is the number of subgraphs (not necessarily induced) with 2 edges and 3 vertices, one of which is $v$ and such that $v$ is incident to both edges. Then we can also define the clustering coefficient as

: $C\_i\; =\; \backslash frac\{\backslash lambda\_G(v)\}\{\backslash tau\_G(v)\}.$

It is simple to show that the two preceding definitions are the same, since

: $\backslash tau\_G(v)\; =\; C(\{k\_i\},2)\; =\; \backslash frac\{1\}\{2\}k\_i(k\_i-1).$

These measures are 1 if every neighbour connected to $v\_i$ is also connected to every other vertex within the neighbourhood, and 0 if no vertex that is connected to $v\_i$ connects to any other vertex that is connected to $v\_i$.

Since any graph is fully specified by its adjacency matrix A, the local clustering coefficient for a simple undirected graph can be expressed in terms of A as:{{cite journal |last1=Wang |first1=Yu |last2=Ghumare |first2=Eshwar |last3=Vandenberghe |first3=Rik |last4=Dupont |first4=Patrick |date=2017 |title=Comparison of Different Generalizations of Clustering Coefficient and Local Efficiency for Weighted Undirected Graphs |url=https://www.mitpressjournals.org/ |journal=Neural Computation |volume=29 |issue=2 |pages=313–331 |doi=10.1162/NECO_a_00914 |pmid=27870616 |s2cid=11000115 |access-date=August 8, 2020 |doi-access=free |archive-date=August 10, 2020 |archive-url=https://web.archive.org/web/20200810032708/https://www.mitpressjournals.org/ |url-status=live }}

:$$

C_i=\frac{1}{k_i(k_i-1)}\sum_{j,k} A_{ij}A_{jk}A_{ki}

where:

:$$

k_i=\sum_j A_{ij}

and C_i=0 when k_i is zero or one. In the above expression, the numerator counts twice the number of complete triangles that vertex i is involved in. In the denominator, k_i² counts the number of edge pairs that vertex i is involved in plus the number of single edges traversed twice. k_i is the number of edges connected to vertex i, and subtracting k_i then removes the latter, leaving only a set of edge pairs that could conceivably be connected into triangles. For every such edge pair, there will be another edge pair which could form the same triangle, so the denominator counts twice the number of conceivable triangles that vertex i could be involved in.

The global clustering coefficient is based on triplets of nodes. A triplet is three nodes that are connected by either two (open triplet) or three (closed triplet) undirected ties. A triangle graph therefore includes three closed triplets, one centred on each of the nodes (n.b. this means the three triplets in a triangle come from overlapping selections of nodes). The global clustering coefficient is the number of closed triplets (or 3 x triangles) over the total number of triplets (both open and closed). The first attempt to measure it was made by Luce and Perry (1949).{{Cite journal

| author = R. D. Luce

| author-link = R. D. Luce

| author2 = A. D. Perry

| author2-link = A. D. Perry

| name-list-style = amp

| title = A method of matrix analysis of group structure

| year = 1949

| journal = Psychometrika

| volume = 14

| pages = 95–116

| doi = 10.1007/BF02289146

| issue = 1

| pmid=18152948

| hdl = 10.1007/BF02289146

| s2cid = 16186758

| hdl-access = free

}} This measure gives an indication of the clustering in the whole network (global), and can be applied to both undirected and directed networks (often called transitivity, see Wasserman and Faust, 1994, page 243Stanley Wasserman, Katherine Faust, 1994. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press.).

The global clustering coefficient is defined as:

: $C\; =\; \backslash frac\{\backslash mbox\{number\; of\; closed\; triplets\}\}\{\backslash mbox\{number\; of\; all\; triplets\; (open\; and\; closed)\}\}$.

The number of closed triplets has also been referred to as 3 × triangles in the literature, so:

: $C\; =\; \backslash frac\{3\; \backslash times\; \backslash mbox\{number\; of\; triangles\}\}\{\backslash mbox\{number\; of\; all\; triplets\}\}$.

A generalisation to weighted networks was proposed by Opsahl and Panzarasa (2009),{{Cite journal

| author = Tore Opsahl

| author-link = Tore Opsahl

| author2 = Pietro Panzarasa

| author2-link = Pietro Panzarasa

| name-list-style = amp

| title = Clustering in Weighted Networks

| url = http://toreopsahl.com/2009/04/03/article-clustering-in-weighted-networks/

| year = 2009

| journal = Social Networks

| volume = 31

| pages = 155–163

| doi = 10.1016/j.socnet.2009.02.002

| issue = 2

| access-date = 2009-06-11

| archive-date = 2019-07-01

| archive-url = https://web.archive.org/web/20190701224513/https://toreopsahl.com/2009/04/03/article-clustering-in-weighted-networks/

| url-status = live

}} and a redefinition to two-mode networks (both binary and weighted) by Opsahl (2009).{{Cite journal

| author = Tore Opsahl

| author-link = Tore Opsahl

| title = Clustering in Two-mode Networks

| url = http://toreopsahl.com/2009/09/11/clustering-in-two-mode-networks/

| year = 2009

| journal = Conference and Workshop on Two-Mode Social Analysis (Sept 30-Oct 2, 2009)

| access-date = September 11, 2009

| archive-date = March 21, 2016

| archive-url = https://web.archive.org/web/20160321002314/http://toreopsahl.com/2009/09/11/clustering-in-two-mode-networks/

| url-status = live

}}

Since any simple graph is fully specified by its adjacency matrix A, the global clustering coefficient for an undirected graph can be expressed in terms of A as:

:$$

C=\frac{\sum_{i,j,k} A_{ij}A_{jk}A_{ki}}{\frac{1}{2}\sum_i k_i(k_i-1)}

where:

:$$

k_i=\sum_j A_{ij}

and C=0 when the denominator is zero.

As an alternative to the global clustering coefficient, the overall level of clustering in a network is measured by Watts and Strogatz as the average of the local clustering coefficients of all the vertices $n$ :{{Cite book|last= Kemper |first=Andreas|title=Valuation of Network Effects in Software Markets: A Complex Networks Approach|publisher=Springer|year=2009|isbn=9783790823660|page=142|url=https://books.google.com/books?id=isdza0IiXbUC&pg=PA142}}

: $\backslash bar\{C\}\; =\; \backslash frac\{1\}\{n\}\backslash sum\_\{i=1\}^\{n\}\; C\_i.$

This metric places more weight on the low degree nodes, while the transitivity ratio places more weight on the high degree nodes.

A generalisation to weighted networks was proposed by Barrat et al. (2004),{{Cite journal | first1= A. |last1= Barrat |first2= M. |last2= Barthelemy |first3= R. |last3= Pastor-Satorras |first4= A. |last4= Vespignani | title = The architecture of complex weighted networks | year = 2004 | journal = Proceedings of the National Academy of Sciences | volume = 101 | pages = 3747–3752 | doi = 10.1073/pnas.0400087101 | issue = 11 | pmid = 15007165 | pmc = 374315 | bibcode=2004PNAS..101.3747B|arxiv = cond-mat/0311416 |doi-access= free }} and a redefinition to bipartite graphs (also called two-mode networks) by Latapy et al. (2008){{Cite journal | first1 = M. |last1= Latapy |first2= C. |last2= Magnien |first3= N. |last3= Del Vecchio | title = Basic Notions for the Analysis of Large Two-mode Networks | year = 2008 | journal = Social Networks | volume = 30 | pages = 31–48 | issue = 1 | doi = 10.1016/j.socnet.2007.04.006|url= https://hal.archives-ouvertes.fr/hal-01146080/file/Latapy2008.pdf }} and Opsahl (2009).

Alternative generalisations to weighted and directed graphs have been provided by Fagiolo (2007){{Cite journal | first1= G. |last1= Fagiolo | title = Clustering in complex directed networks | year = 2007 | journal = Physical Review E | volume = 76|issue= 2 Pt 2 |pages= 026107 | arxiv=physics/0612169 | doi= 10.1103/PhysRevE.76.026107 |pmid= 17930104 |citeseerx= 10.1.1.262.1006 |s2cid= 2317676 }} and Clemente and Grassi (2018).{{Cite journal | first1 = G.P. |last1= Clemente |first2= R. |last2= Grassi | title = Directed clustering in weighted networks: A new perspective | year = 2018 | journal = Chaos, Solitons & Fractals | volume = 107 | pages = 26–38 | doi = 10.1016/j.chaos.2017.12.007|arxiv= 1706.07322 |bibcode= 2018CSF...107...26C |s2cid= 21919524 }}

This formula is not, by default, defined for graphs with isolated vertices; see Kaiser (2008){{Cite journal | first= Marcus | last= Kaiser |title = Mean clustering coefficients: the role of isolated nodes and leafs on clustering measures for small-world networks | year = 2008 | journal = New Journal of Physics | volume = 10 | pages = 083042 | issue = 8 | doi = 10.1088/1367-2630/10/8/083042|bibcode = 2008NJPh...10h3042K |arxiv = 0802.2512 | s2cid= 16480565 }} and Barmpoutis et al.{{Cite arXiv | first1= D. |last1= Barmpoutis |first2=R. M. |last2= Murray | title = Networks with the Smallest Average Distance and the Largest Average Clustering | eprint = 1007.4031 | year = 2010 | class = q-bio.MN}} The networks with the largest possible average clustering coefficient are found to have a modular structure, and at the same time, they have the smallest possible average distance among the different nodes.

For a random tree-like network without degree-degree correlation, it can be shown that such network can have a giant component, and the percolation threshold (transmission probability) is given by $p\_c\; =\; \backslash frac\{1\}\{g\_1\text{'}(1)\}$, where $g\_1(z)$ is the generating function corresponding to the excess degree distribution.

In networks with low clustering, $$

0 < C \ll 1

, the critical point gets scaled by $$

(1-C)^{-1}

such that:

$p\_c\; =\; \backslash frac\{1\}\{1-C\}\backslash frac\{1\}\{g\_1\text{'}(1)\}.${{Cite journal|last1=Berchenko|first1=Yakir|last2=Artzy-Randrup|first2=Yael|last3=Teicher|first3=Mina|last4=Stone|first4=Lewi|date=2009-03-30|title=Emergence and Size of the Giant Component in Clustered Random Graphs with a Given Degree Distribution|url=https://link.aps.org/doi/10.1103/PhysRevLett.102.138701|journal=Physical Review Letters|language=en|volume=102|issue=13|pages=138701|doi=10.1103/PhysRevLett.102.138701|pmid=19392410|issn=0031-9007|access-date=2022-02-24|archive-date=2023-02-04|archive-url=https://web.archive.org/web/20230204143725/https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.102.138701|url-status=live}}

This indicates that for a given degree distribution, the clustering leads to a larger percolation threshold, mainly because for a fixed number of links, the clustering structure reinforces the core of the network with the price of diluting the global connections. For networks with high clustering, strong clustering could induce the core–periphery structure, in which the core and periphery might percolate at different critical points, and the above approximate treatment is not applicable.{{Cite journal|last1=Berchenko|first1=Yakir|last2=Artzy-Randrup|first2=Yael|last3=Teicher|first3=Mina|last4=Stone|first4=Lewi|date=2009-03-30|title=Emergence and Size of the Giant Component in Clustered Random Graphs with a Given Degree Distribution|url=https://link.aps.org/doi/10.1103/PhysRevLett.102.138701|journal=Physical Review Letters|language=en|volume=102|issue=13|pages=138701|doi=10.1103/PhysRevLett.102.138701|pmid=19392410|issn=0031-9007|access-date=2022-02-24|archive-date=2023-02-04|archive-url=https://web.archive.org/web/20230204143725/https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.102.138701|url-status=live}}

For studying the robustness of clustered networks a percolation approach is developed.{{cite journal |title =Random Graphs with Clustering|author=M. E. J. Newman |journal=Phys. Rev. Lett. |date=2009 |volume=103 |issue=5 |pages=058701|doi=10.1103/PhysRevLett.103.058701 |pmid=19792540 |arxiv=0903.4009 |s2cid=28214709 }}{{cite journal |title=Cascades on a class of clustered random networks|author=A. Hackett|author2=S. Melnik|author3=J. P. Gleeson |name-list-style=amp|journal=Phys. Rev. E |date=2011 |volume=83 |issue=5 Pt 2|pages=056107|doi=10.1103/PhysRevE.83.056107|pmid=21728605|arxiv=1012.3651|s2cid=18071422}}

• Directed graph
• Graph theory
• Network theory
• Network science
• Percolation theory
• Scale free network
• Small world

{{Reflist}}

• {{Commons category-inline}}

{{DEFAULTSORT:Clustering Coefficient}}

Category:Graph invariants

Category:Algebraic graph theory

Category:Network theory

Category:Network analysis