首页 > 代码库 > Clustering coefficient [转]
Clustering coefficient [转]
Clustering coefficient的定义有两种;全局的和局部的。
全局的算法基于triplet。首先解释triplet。
triplet 包含 open triplet 和 closed triplet 两种(A triplet is three nodes that are connected by either two (open triplet) or three (closed triplet) undirected ties)
例如下图{1,(2,3)}构成的triplet是封闭的,{3,(4,5)}构成的triplet是开放的
1) Global 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
2) Local Clustering Coefficient:
(1/n ) ∑ i=1:n |Ni|*(|Ni|-1)/2
局部计算是面向节点的,对于节点vi,找出其直接邻居节点集合Ni,计算Ni构成的网络中的边数K,除以Ni集合可能的边数|Ni|*(|Ni|-1)/2,即
例如:
1节点的邻居节点(2,3),他们之间构成的边有1条,可能构成的边1条,因此1/1=1
2节点的邻居节点(1,3),他们之间构成的边有1条,可能构成的边1条,因此1/1=1
3节点的邻居节点(1,2,4,5),他们之间构成的边有1条,可能构成的边(4*3)/2条,因此1/6=1/6
4节点的邻居节点(3),他们之间构成的边有0条,可能构成的边0条,因此0
5节点的邻居节点(3),他们之间构成的边有0条,可能构成的边0条,因此0
则网络的平均聚类系数(network average clustering coefficient),5个节点平均local Clustering coefficient = (1+1+1/6)/5=13/30
Cited from: http://blog.csdn.net/pennyliang/article/details/6838956
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。