【图机器学习系列】(二)从传统机器学习角度理解图(一)

微信公众号:leetcode_algos_life,代码随想随记
小红书:412408155
CSDN:https://blog.csdn.net/woai8339?type=blog ,代码随想随记
GitHub: https://github.com/riverind
抖音【暂未开始,计划开始】:tian72530,代码随想随记
知乎【暂未开始,计划开始】:代码随想随记

传统角度学习图

  • 从机器学习的角度学习图
    • 图的表达
    • 选择合适的图
    • 图的分类
      • 节点度
      • 二部图
    • 如何构建图
  • 图的表示
    • 邻接矩阵
    • 邻接列表
    • 附加属性
    • 强弱连通图
  • 传统机器学习角度理解图
    • 机器学习管道构建图特征
    • 问题定义
    • 适应性函数学习
    • 图的特征构造
      • 节点度
      • 节点中心性
        • 节点度中心性
        • 特征向量中心性
        • 介数中心性
        • 紧密中心性
      • 集聚系数
      • 图元(Graphlet)
  • 总结
  • 参考资料

从机器学习的角度学习图

图的表达

图一般分为顶点和边,整个结构成为图。
在这里插入图片描述

选择合适的图

图的数学表达是节点和边,在不同应用场景下选择不同场景下的图。
在这里插入图片描述

图的分类

图有有向图和无向图,无向图顾名思义没有方向的图,有向图是指有起始点及指向方向的图。
在这里插入图片描述

节点度

(一)无向图中有节点度的概念

针对某一个节点A,该节点的节点度的概念是,链接当前节点的边的数量。
在这里插入图片描述
(二)有向图中节点度的概念
有向图中,节点度有节点入度和出度。
入度是指指向节点的边的个数
出度是指节点发出的边的个数
该节点的度即为该节点的入度和出度之和。
在这里插入图片描述

二部图

二部图是指有两种类型的节点,假设分为类型A和B类型的节点。
该图只有类型之间链接,即A类型的节点链接B类型的节点。
而在同一个类型内部,节点不链接。即:A类型或者B类型各自类型的内部节点不链接。
在这里插入图片描述

如何构建图

构建图需要确定两件事情:
(1)节点如何定义
(2)边如何定义
在这里插入图片描述

图的表示

图有,主要常见的有:邻接矩阵,

邻接矩阵

如果说,Aij表示从节点i到节点j的链接,如果链接存在,表示为1;如果链接不存在,表示为0。
则有向图和无向图的表示如下:
无向图的邻接矩阵是对称的,正定矩阵。
在这里插入图片描述

在这里插入图片描述

邻接列表

邻接列表是用其中一个节点为key,其value表示的是以该节点为输出的节点list。
具体举例如下:
1节点没有以1节点为起始节点的输出节点,因此,为空。
2节点有以2节点为输出指向3/4节点,因此,2: 3,4。
3节点有以3为节点输出指向2和4节点的,因此,3: 2,4
4节点有以4为节点输出指向5节点的,因此,4:5
5节点有以5节点为输出指向1/2节点的,因此,5: 1,2
因此,邻接列表如下:

1:
2:3,4
3:2,4
4:5
5:1,2

在这里插入图片描述

附加属性

图可以加一些属性,比如,权重等。
在这里插入图片描述
权重在邻接矩阵中也可以表示,
在这里插入图片描述

多图结构的表示如下:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

强弱连通图

强连通图:简单理解,从节点A到节点B能够形成闭环循环。
在这里插入图片描述
在这里插入图片描述

传统机器学习角度理解图

机器学习管道构建图特征

传统机器学习角度来看,主要是通过构造特征来对目标进行训练。其核心思想是,如何对节点、边和图进行特征设计。
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
因此,针对无向图,本文进行详细阐述如何构造图中的节点、边和整个图的特征。
在这里插入图片描述

问题定义

以无向图为例,该问题定义成,给定顶点和边,如何求解一适应性函数,使得其满足给定特征,预测出目标。
具体接下来,就是如何让适应性函数进行学习?
在这里插入图片描述

适应性函数学习

这里用无向图中的节点分类例子进行说明。
场景:
假设有给定一些节点,预测这些节点的类型。
主要看右侧的图。
在这里插入图片描述
从机器学习角度看,该问题需要构造特征,那么图怎么构造特征呢?

图的特征构造

在这里插入图片描述
图中的各个节点中心度概要简介如下:
在这里插入图片描述

节点度

可以将某一个节点的度数看成是其中一个特征。
但该特征无法反映节点的区别。
在这里插入图片描述

节点中心性

节点中心性有节点度中心性(Degrree centrality)、介数中心性(Betweeness centrality)、紧密中心性(Closeness centrality)、特征向量中心性( Eigenvector centrality)。

在这里插入图片描述

节点度中心性

在这里,节点度中心性的理解是,当前节点连接的节点总数。
背后逻辑是说,一个节点度越大,表示其节点越重要。

归一化的节点度中心性,在节点度的中心性上除以<节点总数-1>,这个可以理解成,一个节点最多和n-1个节点产生链接(自环暂不考虑)。具体计算逻辑如下:
在这里插入图片描述

这里分两个大的情况:

  • 无向图
    无向图不加权图其节点边权重看作1。
    无向图权重图其节点边权重是其权重。

  • 有向图
    有向图不加权图其节点边权重看作1,分入度和出度,总的度数是入度和出度之和。
    有向权重图其节点边权重是其权重,分入度和出度,总的度数是入度和出度之和。

优缺点:
优点:简单,直观,计算复杂度低
缺点:仅考虑节点最局部信息,没有对节点周围环境进行探讨。一个典型例子是微博中的僵尸粉。

特征向量中心性

特征向量中心性数学含义上就是特征向量。作用是为了衡量节点在整个网络中的重要性。
为了解决节点度中的缺点问题,考虑周围节点的向量,但其计算复杂度有所增加。因此,在求解的时候,采用幂代法进行高效求解。后续介绍幂代法。
(一)特征向量中心性介绍
假设邻接矩阵为A,存在一个向量x,则其特征向量中心性为A*x。
在这里插入图片描述
在这里插入图片描述

(二)幂代法求解
整体思路:假设邻接矩阵A(具有特征值和特征向量),给定非零向量x0,则:
x1 = Ax0
x2 = A
x1
x3 = Ax2

xn = A
x(n-1)

考虑到数值可能越界,因此,需要归一化,即:
在这里插入图片描述
其中,
在这里插入图片描述
表示一个向量的2范数,其数值等于向量中各个元素的平方和开根号。

作为代码化,伪代码如下:

for i in range(1, n, 1):x = A*xx = x / sqrt(x*x)

(三)举例
假设一邻接矩阵A和初始向量x0,数值如下图片里数值。
采用幂代法求解特征向量过程如下:
在这里插入图片描述
(四)优缺点
优点:
考虑到不同节点的不同重要程度。比如,院士节点和杰青节点的重要程度肯定不一样。

缺点:
计算复杂度相对较高

介数中心性

介数中心性(Betweenness centrality,BC)度量节点在最短路径中的重要程度。通常认为是最短路径介数中心性(BC),认为网络中所有节点对的最短路径中(一般情况下,一对节点之间存在多条最短路径),经过一个节点的最短路径数越多,这个节点就越重要。
在这里插入图片描述

紧密中心性

紧密度中心性计算的是某一个结点到当前网络内其他所有结点的平均距离,该距离的倒数值称为紧密中心性。
紧密度中心性也叫接近中心性,用于评价一个结点到其他所有结点的紧密程度,适合发掘关键节点。

紧密中心性计算公式如下:
在这里插入图片描述

集聚系数

集聚系数(也称群聚系数、集群系数)是用来描述一个图中的顶点之间结集成团的程度的系数。具体来说,是一个点的邻接点之间相互连接的程度。集聚系数分为整体和局部的,局部是单一节点的,整体为整个图的所有节点的平均值。

在这里插入图片描述

假设当前节点为V,与之连接的节点个数计作 K。
与节点V连接的节点间连接的个数计作 N,
那么 该节点V的集聚系数是:
CC(V) = 2N/(K(K-1))

举例如下:
在这里插入图片描述

在这里插入图片描述

图元(Graphlet)

(一)Graphlet介绍
首先,介绍下连通诱导子图。
所谓,连通诱导子图是指该图中的顶点和边都是从图(Graph)中顶点和边的真子集。
graphlets是指大图(Graph)中节点数目相对较少的连通诱导子图。
即:graphlets指的是连通的非同构子图。

举例如下:

在这里插入图片描述
(二)k节点Graphlets
含 k 个节点的 graphlet记为 k-graphlets.
在这里插入图片描述

在这里插入图片描述
(三)Graphlet度向量
节点的graphlet degree 为包含节点的 graphlet 的个数。
Graphlet Degree Vector指的是各种子图出现的次数(必须包含v,并且必须是完全符合子图,子图包含的节点之间不能有多余的边)。
在这里插入图片描述
上图中,以节点v为参考,

  • a类型的graphlet有两种情况,
  • b类型有1种情况,
  • c类型没有(因为和b的情况,差了一个竖着的边连接),
  • d类型有两种情况,即d旁边的灰色节点当作是节点v。
    这种情况下,组成当前节点的 graphlet degree 为[2,1,0,2]。
    在这里插入图片描述
    在这里插入图片描述

总结

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

参考资料

1、cs224w
2、bilibili图机器学习网址
3、图表示学习书籍
4、图深度学习
5、GNN介绍
6、网络重要节点排序方法综述
7、幂代法样例
8、特征向量中心度及scala源码解析
9、紧密中心性
10、聚类系数视频解释
11、聚类系数论文
12、graphlets诱导子图介绍-论文

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/407431.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

面试题详解

前言&#xff1a;这一期我们专门来巩固所学知识&#xff0c;同时见识一些面试题。对知识做出一个总结。 1 不创建临时变量交换两个整数 . 第一种方法 #include<stdio.h> int main() {int a 0;int b 0;scanf("%d %d", &a, &b);printf("交换前…

深度学习 --- VGG16卷积核的可视化(JupyterNotebook实战)

VGG16卷积核的可视化 在前一篇文章中&#xff0c;我对VGG16输入了一张图像&#xff0c;并实现了VGG16各层feature map的可视化。深度学习 --- VGG16各层feature map可视化(JupyterNotebook实战)-CSDN博客文章浏览阅读615次&#xff0c;点赞13次&#xff0c;收藏15次。在VGG16模…

Linux三剑客-sedawk

一、三剑客-sed命令 1、格式 sed 找谁干啥 文件 找谁:条件&#xff0c;匹配哪一行&#xff0c;哪些行. 干啥:动作&#xff0c;增删改查. #显示文件的第3行 sed -n 3p /etc/passwd选项说明-n取消默认输出-p查找-rsed支持扩展正则-i修改文件内容&#xff0c;这个选项放在最后…

【C++ Primer Plus习题】3.5

问题: 解答: #include <iostream> using namespace std;int main() {long long populationWorld 0;long long populationChina 0;cout << "请输入全球的人口数:";cin >> populationWorld;cout << "请输入中国的人口数:";cin &g…

XSS- - - DOM 破坏案例与靶场

目录 链接靶场&#xff1a; 第一关 Ma Spaghet 第二关 Jefff 第三关 Ugandan Knuckles 第四关 Ricardo Milos 第五关 Ah Thats Hawt 第六关 Ligma 第七关 Mafia 第八关 Ok, Boomer 链接靶场&#xff1a; XS…

GenAI 的产品:快速行动,但失败

2022 年秋季&#xff0c;我正在做一个很酷的项目。是的&#xff0c;你猜对了——使用公司特定的数据对预先训练的 LLM&#xff08;Bert&#xff09;进行微调。 然而&#xff0c;很快 ChatGPT 就发布了&#xff0c;并席卷了全世界。既然已经有一门非常强大的 LLM 了&#xff0c…

ARM——驱动——inmod加载内核模块

在上一篇文章的代码上添加出错处理 #include <linux/init.h> // 包含初始化宏和函数 #include <linux/kernel.h> // 包含内核函数和变量 #include <linux/fs.h> // 包含文件操作的结构和函数 #include <linux/kdev_t.h> /…

PyTorch——transforms

接着上一篇&#xff0c;我们这一篇讲transforms 1、什么是transform 首先transform是来自PyTorch的一个扩展库——【torchvision】&#xff0c;【torchvision】这个库提供了许多计算机视觉相关的工具和功能&#xff0c;能够在神经网络中&#xff0c;将图像、数据集、预处理模型…

【系统架构设计】软件架构设计(1)

【系统架构设计】软件架构设计&#xff08;1&#xff09; 软件架构概述架构需求与软件质量属性软件架构风格数据流风格批处理序列管道-过滤器2者风格比较 仓库风格--黑板系统 层次系统架构风格二层及三层C/S架构风格MVCMVP 面向服务的架构 软件架构概述 基于架构的软件开发模型…

网络通信tcp

一、udp案例 二、基于tcp: tcp //c/s tcp 客户端: 1.建立连接 socket bind connect 2.通信过程 read write close tcp服务器: 1.建立连接 socket bind listen accept 2.通信过程 read write close connect函数 int connect(int sockfd, con…

postgresql 集群文档

https://www.cnblogs.com/Alicebat/p/14148933.html [命令] Pacemaker 命令 pcs cluster &#xff08;管理节点&#xff09; – Eternal Center PostgreSQL实战之物理复制和逻辑复制&#xff08;五&#xff09;_postgresql 流复制和物理复制-CSDN博客 https://jingyan.baidu…

【Windows】深度学习环境部署

引言 1 Windows环境准备 1.1 VSCode Visual Studio Code&#xff08;简称 VSCode&#xff09;是一款由微软开发的开源代码编辑器。它非常受开发者欢迎&#xff0c;因为它功能强大、扩展性好&#xff0c;并且支持多种编程语言。VSCode 尤其适合 Python 开发&#xff0c;特别是…

网络 通信

一、客户端接收(也可以bind) 1. socket socket 函数 用于创建一个套接字&#xff08;socket&#xff09;&#xff0c;这是网络通信的基础。 它的原型如下&#xff1a;int socket(int domain, int type, int protocol); 参数&#xff1a; domain&#xff1a;指定协议族&…

虚幻5|AI视力系统,听力系统,预测系统(3)预测系统

虚幻5|AI视力系统&#xff0c;听力系统&#xff0c;预测系统&#xff08;2&#xff09;听力系统-CSDN博客 一&#xff0c;添加一个AI预感感官配置 1.选中我们的AIPerception,右侧细节添加一个AI预感感官配置&#xff0c;然后我们把所有感官的年龄都调成5&#xff0c;是所有 2…

全网最简单的Java设计模式【九】策略模式-实战中最常用的设计模式之一

策略模式是一种行为设计模式&#xff0c;它允许你定义一系列的算法&#xff0c;把它们一个个封装起来&#xff0c;并且使它们可以相互替换。该模式让算法的变化独立于使用算法的客户。在实际开发中&#xff0c;策略模式可以帮助我们减少大量的 if-else 或 switch 条件判断语句&…

premiere2023暴力压缩视频

目录 1. 需求说明2. 压缩流程 1. 需求说明 要将三段视频拼接起来&#xff0c;时长超过了1h&#xff0c;然后压缩到200M以内的视频。 这是三段视频的信息&#xff1a; 合并三个视频文件意味着总时长增加了。较长的视频文件通常也会更大&#xff0c;即使比特率相同。 当我把三段…

vscode 阅读linux内核(vscode+clangd)

此插件曾在vim里用过&#xff0c;非常好用。 首先先在vscode 里下载clangd插件 这只是客户端&#xff0c;还需下载个服务器&#xff08;这在coc插件里也有说明&#xff09; sudo apt install clangd 下载完后可以 clangd --version 查看版本信息&#xff0c;如果能查看&#x…

UE5 日期时间蓝图变量 加减节点

参考链接&#xff1a;Having troubles with DateTime in UE5 - General / Feedback & Requests - Epic Developer Community Forums (unrealengine.com) 直接粘贴到UE5蓝图图表可用。&#xff08;反之相加&#xff0c;用负号操作一下&#xff09; 减号蓝图节点&#xff08;…

8.22-docker的部署及其使用

docker 1.docker环境部署以及语法 [rootdocker ~]# cat << EOF | tee /etc/modules-load.d/k8s.conf> overlay> br_netfilter> EOFoverlaybr_netfilter[rootdocker ~]# modprobe overlay[rootdocker ~]# modprobe br_netfilter[rootdocker ~]# cat /etc/module…

AI绘画工具 Stable Diffusion【插画转绘】:建筑 | 风景| 人像照片的插画转绘制作教程,照片秒变插画风格图片!

大家好&#xff0c;我是画画的小强 关于Stable Diffusion 的插画转绘&#xff0c;今天给大家分享一种制作方法。我们先看一下效果图。 一. 图片转插画的制作方法 本期教程我们将使用AI绘画工具Stable Diffusion&#xff0c;关于SD的安装和入门使用可以看看我的往期入门教程…