词条 | 聚类系数 |
释义 | 概述按照图形理论,聚集系数是表示一个图形中节点聚集程度的系数,证据显示,在现实中的网络中,尤其是在特定的网络中,由于相对高密度连接点的关系,节点总是趋向于建立一组严密的组织关系。在现实世界的网络,这种可能性往往比两个节点之间随机设立了一个连接的平均概率更大。 在很多网络中,如果节点v1连接于节点v2,节点v2连接于节点v3,那么节点v3很可能与v1相连接。这种现象体现了部分节点间存在的密集连接性质。可以用聚类系数(CC)来表示,在无向网络中,聚类系数定义为: 其中,n表示在节点v的所有k个邻居间的边数。 全局集聚系数全局集聚系数全局集聚系数是基于结点三元组的。一个三元组是其中有两条(开三元组)或三条(闭三元组)无向边连接的三个结点。一个三角由三个封闭的三元组构成,(三元组)集中在每一个结点上。全局集聚系数是所有三元组(包括开和闭的)中封闭三元组的数目。 局部集聚系数图中一个结点的局部集聚系数表示了它的相邻结点形成一个团(完全图)的紧密程度。Duncan J. Watts和Steven Strogatz在1998年引入了度量一个图是否是小世界网络的方法。 定义 G = (V, E) : 图G包含一系列结点V和连接它们的边E. eij : 连接结点i与结点j的边. Ni = {vj : eij∈E ∩ eji∈E} : vi的第i个相邻结点. ki : vi相邻结点的数量. 结点vi的局部集聚系数Ci是它的相邻结点之间的连接数与它们所有可能存在连接的数量的比值。对于一个有向图,eij 与 eji是不同的,因而对于每个邻结点 Ni在邻结点之间可能存在有 ki(ki − 1)条边(ki 是结点的出入度之和)。 网络的平均集聚系数整个网络的集聚系数由Watts和Strogatz定义为所有结点n的局部集聚系数的均值: 如果一个图的平均集聚系数显著高于相同结点集生成的随机图,而且平均最短距离与相应随机生成的随机图相近,那么这个图被认为是小世界的。 有更高平均集聚系数的网络被发现有着模块结构,同时在不同结点中还有更小的平均距离。 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。