9/14/22, 6:51 AM L5: Clustering Coefficient: Network Science – CS-7280-O01
L5: Clustering Coefficient
In social networks, it is often the case that if A is a friend of B and C, then B and C are also likely to be friends with each other. In other words, A, B, and C form
a “friendship triangle”. The presence of such triangles is quite common in almost all real-world networks.
Copyright By PowCoder代写 加微信 powcoder
To quantify the presence of such triangles of connected nodes, we can use the Clustering Coefficient. For a node-i with at least two neighbors, this metric is defined as the fraction of its neighbors’ pairs that are connected.
Mathematically, suppose that the network is undirected, unweighted, and described by an adjacency matrix A. The clustering coefficient for node-i is defined as:
The denominator at the left fraction is the number of distinct neighbor pairs of node- i, while the numerator is the number of those pairs that form triangles with node-i.
If the degree of node-i is one or zero, the clustering coefficient is not well-defined.
The visualization at the left shows three examples in which node-i
is the purple node. As you see, the clustering coefficient quantifies the extent to which node-i and its direct neighbors form an interconnected cluster. If they form a clique the clustering coefficient is maximized (one) – while if they form a star topology with node-i at the center the clustering coefficient is minimized (zero).
We often want to describe the clustering coefficient not only of one node in the network – but of all nodes. One way to do so is with the plot at the right.
https://gatech. instructure. com/courses/265324/pages/l5-clustering-coefficient?module_item_id=2520338 1/2
9/14/22, 6:51 AM L5: Clustering Coefficient: Network Science – CS-7280-O01
For every degree-k, the plot shows the average clustering coefficient C(k) of all nodes with degree k>1. Typically there is a decreasing trend in C(k) as k increases, suggesting that it becomes less likely to find densely interconnected clusters of many nodes compared to clusters of fewer nodes.
Food For Thought
In signed social networks, where a positive edge may represent friends while a negative edge may represent enemies, the “triadic closure” property also relates to the stability of that triangle. Which signed triangles do you think are unstable, meaning that one or more edges will probably be removed over time?
https://gatech. instructure. com/courses/265324/pages/l5-clustering-coefficient?module_item_id=2520338 2/2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com