查看原文
其他

什么是聚类系数:全局与局部 | 集智百科

集智百科 集智俱乐部 2022-04-08


“集智百科精选”是一个长期专栏,持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目,集智百科希望打造复杂性科学领域最全面的百科全书,欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入!

本文是对集智百科中“聚类系数”词条的摘录,参考资料及相关词条请参阅百科词条原文。

本词条由集智俱乐部众包生产,难免存在纰漏和问题,欢迎大家留言反馈或者前往对应的百科词条页面进行修改,一经修改,可以获得对应的积分奖励噢!

本词条由集智俱乐部众包生产,难免存在纰漏和问题,欢迎大家留言反馈或者前往对应的百科词条页面进行修改,一经修改,可以获得对应的积分奖励噢!


目录


一、全局聚类系数二、局部聚类系数三、编者推荐四、集智百科词条志愿者招募

图论中,聚类系数用于衡量节点聚集的程度。有证据表明,大多数现实世界的网络中,特别是在社交网络中,节点倾向于创建相对紧密联系的群体; 这种可能性往往大于在两个节点之间随机建立关系的平均概率(Holland 和 Leinhardt,1971;  Watts 和 Strogatz,1998)。





全局聚类系数




全局聚类系数以节点三重性 triplets为基础。一个三元组是由两个(开三元组)或三个(闭三元组)无向联系相连接的三个节点。因此,一个三角形图包括三个闭合的三联体,每个节点中心为一个(注意,这意味着三角形中的三联体来自节点的重叠选择)。全局聚类系数是三联体总数除以闭合三联体(或3 x 三角形)的个数。Luce和Perry(1949年)第一次尝试对其进行测量。这个度量概括了整个网络(全局)中的集群,并可应用于无向和有向网络(通常称为传递性,见 Wasserman 和 Faust,1994,第243页。)全局聚类系数的定义是:

闭合三联体的数目在文献中也被称为3×三角形,所以:

Opsahl 和 Panzarasa (2009)提出了加权网络的一般化,和一种双模式网络(包括二进制和加权)。





局部聚类系数




图中某顶点(节点)的局部聚类系数量化了其邻居节点相互聚集构成团(完全图)的程度。邓肯·沃茨 Duncan J Watts和斯蒂文·斯特罗加茨 Steven H. Strogatz在1998年引入该测量方法来确定一个图是否构成小世界网络。


一个图 G=(V,E),形式上由一组节点和节点之间的连边组成。边连接节点。一个节点Vi的邻域Ni被定义为其紧邻的节点,具体如下:

我们将Ki定义为节点的个数,|Ni|为邻域,Ni为邻域节点数目。

一个节点Vi的局部聚类系数Ci由邻域内节点之间的连边除以它们之间可能存在的连边数量的比例给出。对于有向图,eij 不同于eij因此对于每个邻域Ni,邻域内的节点之间可能存Ki(Ki-1)链(Ki是一个顶点的邻域数)。 因此,有向图的局部聚类系数为

无向图的eij 和eij 被认为具有相同的性质。因此,如果一个顶点有Vi邻域,Ki边可以存在于邻域内的顶点之间。因此,无向图的局部聚类系数可以定义为
设 λG(V)是无向图G上的三角形个数v∈V(G)。也就是说,λG(v)是G的3条边和3个节点的子图的个数,其中一个是v 。τG(v)是v∈V(G)上的三倍数。即,τG(v)具有2条边和3个顶点的子图(不一定是诱导的)的个数,其中一条边与两条边相关。那么我们也可以将聚类系数定义为


易证明前面的两个定义是相同的,因为

如果所连接的每个邻居也连接到邻近的每个其他节点Vi,则这些测量值为1; 如果没有任何节点Vi连接到所连接的任何其他节点Vi,则这些测量值为0

网络整体聚类水平

作为全局聚类聚类系数的代替,Watts 和 Strogatz 将所有顶点局部聚类系数的平均值作为网络整体聚类水平n:

值得注意的是,该度量将更多权重放在低度节点上,而传递性比率将更多权重放在高度节点上。事实上,每个局部聚类分数由Ki(Ki-1)的加权平均数模型与全局聚类聚类系数模型是相同的。如果图有一个小的平均最短路径长度与网络中节点数量的自然对数lnN一起延展,那么这个图被认为是小世界。例如,随机图是小世界图,而格子图不是,无标度图通常被认为是超小世界图,因为它们的平均最短路径长度随ln lnN延展。Barrat 等人提出了广义的加权网络(2004) ,Latapy 等人(2008)和 Opsahl (2009)重新定义了二部图(也称为双模网络)。Fagiolo (2007), Clemente 和Grassi (2018) 提出了另一种加权有向图网络的推广概念。默认情况下,这个公式不适用于具有孤立顶点的图; 参见 Kaiser (2008)和 Barmpoutis 等。具有最大可能平均聚类系数的网络被发现具有模块结构,且不同节点之间存在尽可能小的平均距离。





编者推荐



网络动力学课程

集智学园特邀陈关荣、项林英、樊瑛、宣琦、李翔、史定华、李聪、荣智海、周进、王琳等网络科学专家作为导师,依托汪小帆、李翔、陈关荣的经典教材《网络科学导论》,自2月27日起开展系列上线课程,以网络动力学为主线构建网络科学知识体系。欢迎希望进入网络科学领域、提高网络分析能力、与一线专家探讨问题的朋友报名参加!



点击查看课程详情

2021重磅新课:探索网络动力学——网络科学第二期


课程推荐:网络科学导论 | 网络科学集智课堂第二期 
https://campus.swarma.org/course/2328





百科项目志愿者招募




作为集智百科项目团队的成员,本文内容由 Gravity PHY苏格兰薄荷参与贡献。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页,更多信息可以访问其集智百科个人主页。


以上内容都是我们做这项目的起点,作为来自不同学科和领域的志愿者,我们建立起一个有效的百科团队,分配有审校、翻译、编辑、宣传等工作。我们秉持:知识从我而来,问题到我为止的信念,认真负责编撰每一个词条。




在这里从复杂性知识出发与伙伴同行,同时我们希望有更多志愿者加入这个团队,使百科词条内容得到扩充,并为每位志愿者提供相应奖励与资源,建立个人主页与贡献记录,使其能够继续探索复杂世界。


如果你有意参与更加系统精细的分工,扫描二维码填写报名表,我们期待你的加入!



集智百科报名表


来源:集智百科

编辑:王建萍



推荐阅读



点击“阅读原文”,阅读聚类系数相关内容与参考文献

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存