选自towardsdatascience
作者：Maël Fabien
机器之心编译
参与：熊猫
图（graph）近来正逐渐变成机器学习的一大核心领域，比如你可以通过预测潜在的连接来理解社交网络的结构、检测欺诈、理解汽车租赁服务的消费者行为或进行实时推荐。近日，数据科学家 Maël Fabien 在其博客上发布了涉及图论、图算法和图学习的系列文章《图论与图学习》。
本文是其中第一篇，介绍了图的一些基础知识并给出了 Python 示例。更多文章和对应代码可访问：https://github.com/maelfabien/Machine_Learning_Tutorials。
本文涵盖以下主题：
- 图是什么？
- 如何存储图？
- 图的类型和性质
- Python 示例
首先进行一些准备工作，打开 Jupyter Notebook，导入以下软件包：
后面的文章会使用 networkx 最新的 2.0 版本。networkx 是一个用于复杂网络的结构、动态和功能的创建、操作和研究的 Python 软件包。
import numpy as np import random import networkx as nx from IPython.display import Image import matplotlib.pyplot as plt
我会尽量以实用为目标，努力阐释每个概念。
图是什么？
图是互连节点的集合。
举个例子，一个简单的图可能是这样：
节点（node）用红色标出，通过黑色的边（edge）连接。
图可用于表示：
- 社交网络
- 网页
- 生物网络
- …
我们可以在图上执行怎样的分析？
- 研究拓扑结构和连接性
- 群体检测
- 识别中心节点
- 预测缺失的节点
- 预测缺失的边
- …
过几分钟你就能明白所有这些概念。
我们首先在我们的笔记本中导入第一个预构建的图：
# Load the graph G_karate = nx.karate_club_graph() # Find key-values for the graph pos = nx.spring_layout(G_karate) # Plot the graph nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos)
空手道图
这个「空手道」图表示什么？Wayne W. Zachary 在 1970 到 1972 年这三年中研究的一个空手道俱乐部的社交网络。该网络包含了这个空手道俱乐部的 34 个成员，成员对之间的连接表示他们在俱乐部之外也有联系。在研究期间，管理员 JohnA 与教练 Mr.Hi（化名）之间出现了冲突，导致俱乐部一分为二。一半成员围绕 Mr.Hi 形成了一个新的俱乐部，另一半则找了一个新教练或放弃了空手道。基于收集到的数据，除了其中一个成员，Zachary 正确分配了所有成员在分裂之后所进入的分组。
图的基本表示方法
图 G=(V, E) 由下列要素构成：
- 一组节点（也称为 verticle）V=1,…,n
- 一组边 E⊆V×V
- 边 (i,j) ∈ E 连接了节点 i 和 j
- i 和 j 被称为相邻节点（neighbor）
- 节点的度（degree）是指相邻节点的数量
节点、边和度的示意图
- 如果一个图的所有节点都有 n-1 个相邻节点，则该图是完备的（complete）。也就是说所有节点都具备所有可能的连接方式。
- 从 i 到 j 的路径（path）是指从 i 到达 j 的边的序列。该路径的长度（length）等于所经过的边的数量。
- 图的直径（diameter）是指连接任意两个节点的所有最短路径中最长路径的长度。
举个例子，在这个案例中，我们可以计算出一些连接任意两个节点的最短路径。该图的直径为 3，因为没有任意两个节点之间的最短路径的长度超过 3。
