图的概念（1）

图是什么？

首先，我们导入需要的包？

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)
1
2
3
4
5
6

在这里插入图片描述

空手道俱乐部图

这个「空手道」图表示什么？Wayne W. Zachary 在 1970 到 1972 年这三年中研究的一个空手道俱乐部的社交网络。该网络包含了这个空手道俱乐部的 34 个成员****，成员对之间的连接表示他们在俱乐部之外也有联系。在研究期间，管理员 JohnA 与教练 Mr.Hi（化名）之间出现了冲突，导致俱乐部一分为二。一半成员围绕 Mr.Hi 形成了一个新的俱乐部，另一半则找了一个新教练或放弃了空手道。基于收集到的数据，除了其中一个成员，Zachary 正确分配了所有成员在分裂之后所进入的分组。

图的基本表示方法

图 $G = （ V ， E ）$ 由下列要素构成：
一组节点，（也称为verticle) $V = 1, 2, . . ., n$
一组边:E $\subseteq$ V $\times$ V
边 $\in E连接了节点i和j$
$i$ 和 $j$ 被称为相邻节点。
节点的度（degree）是指相邻节点的数量。

节点、边和度的示意图
如果一个图的所有节点都有 $n - 1$ 个相邻节点，则该图是完备的（complete). 也就是说所有节点都具备所有可能的连接方式。
从 $i$ 到 $j$ 的路径，是指从 $i$ 到达 $j$ 的边的序列，该路径的长度等于所经过边的数量。
图的直径，是指连接任意两个节点的所有最短路径中的最长路径长度。
举个例子，在这个案例中，我们可以计算出一些连接任意两个节点的最多路径，该图直径为3，因为，没有任意两个节点之间最多路径长度超过3.

一个直径为3的图。
测地路径，指两个节点之间的最短路径。
如果所有节点都可通过某个路径连接到彼此，则它们构成一个连通分支。
如果一个图仅有一个连通分支，则该图是连通的。
举个例子：下面是一个有两个不同连通分支的图：

一个有两个连通分支的图。
如果一个图的边是有顺序的配对，则该图是有向的， $i$ 的入度是指向 $i$ 的边的数量，出度(out-degree)是远离 $i$ 的边的数量。

有向图
如果可以回到一个给定的节点，则改图是有环的。相对地，如果至少有一个节点无法回到，则该图是无环的。
图可以被加权，即在节点或关系上施加权重。
如果一个图边的数量相比节点的数量较小，则该图是稀疏的。相对地，如果节点之间的边非常多，则该图是密集的。
Neo4J关于图算法给出的清晰明了的总结：

可以用代码实现上面的东西都行啦

.degree() 属性会返回该图的每个节点的度（相邻节点的数量）的列表：

n=34
print(G_karate.degree())
degree_sequence = list(G_karate.degree())

计算边的数量，但也计算度序列的度量：

nb_nodes = n
nb_arr = len(G_karate.edges())
avg_degree = np.mean(np.array(degree_sequence)[:,1])
med_degree = np.median(np.array(degree_sequence)[:,1])
max_degree = max(np.array(degree_sequence)[:,1])
min_degree = np.min(np.array(degree_sequence)[:,1])
》# 最后，打印所有信息：
print("Number of nodes : " + str(nb_nodes))
print("Number of edges : " + str(nb_arr))
print("Maximum degree : " + str(max_degree))
print("Minimum degree : " + str(min_degree))
print("Average degree : " + str(avg_degree))
print("Median degree : " + str(med_degree))

绘制度的直方图

平均而言，该图中的每个人都连接了 4.6 个人。

我们可以绘出这些度的直方图：

degree_freq = np.array(nx.degree_histogram(G_karate)).astype(‘float’)
plt.figure(figsize=(12, 8))
plt.stem(degree_freq)
plt.ylabel(“Frequence”)
plt.xlabel(“Degre”)
plt.show()

在这里插入图片描述
通过上图可以看出，度的直方图相当重要，上图可以用于确定我们图的种类。