原创 | 斯坦福Machine Learning with Graphs 学习笔记(第一讲）

作者：林夕

本文长度为2900字，建议阅读9分钟

本文为大家介绍图网络的基本概念、网络的应用以及图的结构。

标签：机器学习

目录

一、Why Networks

二、网络的应用

    2.1 应用领域

三、图的结构

    3.1 网络表示的选择

    3.2 点的度（Degree）

    3.3 图的表示方式

        邻接矩阵（Adjacency Matrix）

        边列表（Edge list）

        邻接列表（Adjacency list）

    3.4 图的连通性

参考资料

最近我们小组开始整理CS224W机器学习图网络的一些笔记，这是第一课对应的PPT。

课程相关PPT链接：

http://web.stanford.edu/class/cs224w/slides/01-intro.pdf

一、Why Networks

第一部分简单介绍下关于图网络的一些基本定义，应用和意义。

网络的定义：网络是描述一系列交互实体的复杂系统的一种通用语言。

网络（Network）和图（Graph）的一些区别：

• 网络通常指真实的系统，eg.互联网、社交网络、信息网络、代谢网络、常用的表达有网络、节点、关系等；

• 图是网络的数学表达方式，比如互联网图谱、社交图谱、知识图谱、场景图、分子图（分子预测模型）。常用表达有图、顶点、边等词；

• 网络的概念比图的概念总体来看会大一点，但是总的来说network和graph区别也是比较模糊的，在实际中，这点区别也不会刻意强调，大家大致理解一下也就可以。

常见的网络比如有社会网络，通信网络，基因/蛋白质的互动网络，人脑神经元的连接网络。

现在学习图网络有什么意义呢。首先网络是一种描述复杂数据的通用语言，可以应用在众多领域，比如计算机，社会科学，物理学，经济学，生物都会涉及到对网络数据分析。其次网络数据关系能反应非欧式空间的数据关系，更能反应数据潜在的联系。另一方面，研究图网络将会对这些领域产生很大的影响。

接下来看网络的一些实际应用。

二、网络的应用

从网络分析方法角度来看，网络的应用可以分为以下几类：

• 节点分类（Node classification）：预测一个给定节点的类型；

• 链路预测（Link prediction）：预测两个节点是否是关联；

• 社区发现（Community detection）：识别密集的节点簇；

• 网络相似度分析（Network similarity）：节点或者网络相似度的测量。

2.1 应用领域

社交网络：研究人员从Facebook的数据中发现，人之间的平均距离实际是3.74。提出了新的4度社交网络。除此之外可以利用图聚类算法，识别社交圈。