图机器学习中传统方法 - 结点特征 - 集聚系数
2021/5/4 10:26:08
本文主要是介绍图机器学习中传统方法 - 结点特征 - 集聚系数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
集聚系数(clustering coefficient)
用来描述一个图中的顶点之间结集成团的程度的系数。具体来说,是一个点的邻接节点之间相互连接的程度。集聚系数分为整体,局部两种。整体集聚系数可以给出一个图中整体的集聚程度的评估,而局部集聚系数则可以测量图中的每个结点附近的集聚程度。
整体集聚系数:定义在闭点三点组之上。假设图中有一部分点是两两相连的,那么可以找出很多个“三角形”,其对应的三点两两相连,成为闭三点组。除此之外,还有开三点组,也就是三个点中只有两条边(三角形缺少一条边)。这两种三点组构成了所有的连通三点组。整体的集聚系数定义为一个图中所有闭三点组数量与所有连通三点组(开三点组数量+闭三点组数量)的总量之比。
假设图,表示顶点的集合,表示边的集合(表示连接顶点与的边)。每个顶点连接的顶点有多少,可以用L(i)表示与顶点相连的边的集合:
,L(i)中边的数量就是顶点的度,记作。
表示整体集聚系数,表示图中闭三点组的个数,表示图中开三点组的个数,则
或者用来表示:
从n个物品中选择k个物品,选择的顺序无所谓,那么选择的方式共有:
, 可以写作:
局部系数:图中一个顶点的局部集聚系数C(i)等于所有与它相连的顶点之间所连的边的数量,除以这些顶点之间可以连出的最大边数。一般来说,对应无向图,这个最大边数等于,对于有向图,由于每两个顶点之间可以连两条边,最大边数等于,这时候表示的是指向顶点的边与从顶点指出去的边的总数。
在无向图中,如果一个顶点的相连的闭三角数量为,也就是G中所有包括了顶点的闭三点组(三点中连有三条边)的数目;的相连的开三角数量为,也就是G中所有包括了顶点,且满足两条边都与相连的开三点组(三点中恰好连有两条边)。这是时候,无向图中顶点的局部聚集系数:
或 ,
有向图中局部聚集系数:
一个顶点的局部聚集系数C(i)总是在[0,1],C(i)越是接近1,则表示的邻居越是抱成一团,接近完全图。C(i)越接近0,则结点的邻接结点之间不相连,整个结构接近树状。
参考文献:
[1] https://zh.wikipedia.org/wiki/%E9%9B%86%E8%81%9A%E7%B3%BB%E6%95%B0
这篇关于图机器学习中传统方法 - 结点特征 - 集聚系数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-01-24手把手教你使用MDK仿真调试
- 2024-01-10基于“小数据”的机器学习
- 2024-01-08扩展卡尔曼滤波:提高机器学习性能的利器
- 2023-12-26各种二端口滤波器网络仿真遇到的问题
- 2023-12-14机器学习-搜索技术:从技术发展到应用实战的全面指南
- 2023-12-12机器学习 - 决策树:技术全解与案例实战
- 2023-12-05机器学习-学习率:从理论到实战,探索学习率的调整策略
- 2023-12-04解锁机器学习-梯度下降:从技术到实战的全面指南
- 2023-11-30回归算法全解析!一文读懂机器学习中的回归模型
- 2023-11-30机器学习 - 似然函数:概念、应用与代码实例