聚类系数（clustering coefficient）计算

忘是亡心i 2022-07-15 03:38 299阅读 0赞

转自[http://blog.csdn.net/pennyliang/article/details/6838956][http_blog.csdn.net_pennyliang_article_details_6838956]

Clustering coefficient的定义有两种；全局的和局部的。

全局的算法基于triplet。triplet分为开放的triplet(open triplet)和封闭的triplet(closed triplet)两种（A triplet is three nodes that are connected by either two (open triplet) or three (closed triplet) undirected ties）。  
可以用下面结构定义一个triplet

struct triplet     \{    int key;    set<int> pair;\};  
例如下图\{1，(2,3)\}构成的triplet是封闭的，\{3,（4,5）\}构成的triplet是开放的  
![18092453-ef6f3f064112453aa29ce17c29824188.jpg][]  
全局的Clustering coefficient比较简单，公式如下：Clustering coefficient(global) = number of closed triplet / number of triplet(closed+open)  
以上图为例:

closed triplet =\{1，(2,3)\}，\{2，(1,3)\}，\{3，(1,2)\}

all triplet = \{1，(2,3)\}，\{2，(1,3)\}，\{3，(1,2)\}，\{3，（2,4）\}，\{3，（4,5）\}，\{3，（1,5）\}，\{3，（2,5）\}，\{3，（1,4）\}

number of closed triplet = 3

number of  triplet = 8

number of triplet / number of  triplet = 3/8

局部的Clustering coefficient的计算方法：局部计算是面向节点的，对于节点vi，找出其直接邻居节点集合Ni，计算Ni构成的网络中的边数K，除以Ni集合可能的边数|Ni|\*（|Ni|-1）/2例如：1节点的邻居节点（2,3），他们之间构成的边有1条，可能构成的边1条，因此1/1=12节点的邻居节点（1,3），他们之间构成的边有1条，可能构成的边1条，因此1/1=13节点的邻居节点（1,2,4,5），他们之间构成的边有1条，可能构成的边(4\*3)/2条，因此1/6=1/6  
4节点的邻居节点（3），他们之间构成的边有0条，可能构成的边0条，因此0  
5节点的邻居节点（3），他们之间构成的边有0条，可能构成的边0条，因此0  
则，5个节点平均local Clustering coefficient = (1+1+1/6)/5=13/30

参考

1）[http://en.wikipedia.org/wiki/Clustering\_coefficient][http_en.wikipedia.org_wiki_Clustering_coefficient]  
2）<<Complex Network>> 3.2 properties of real-world networks  p25

[http_blog.csdn.net_pennyliang_article_details_6838956]: http://blog.csdn.net/pennyliang/article/details/6838956
[18092453-ef6f3f064112453aa29ce17c29824188.jpg]: /images/20220715/0f0bd8d44c4f4fec9d735fb24ebe3d74.png
[http_en.wikipedia.org_wiki_Clustering_coefficient]: http://en.wikipedia.org/wiki/Clustering_coefficient