图的基本概念

• 图的定义
• 图的数学表示
• 路径
• 图的连通性
• 最小生成树
• 度，平均度
• 网络的密度
• 网络平均路径长度
• 网络的聚类(clustering coefficient)系数

1. 图(网络)的定义

• 定义：一个具体的网络可以抽象为由一个点集和边集组成的图， 如下图1所示。以编程的角度来看，边集和点集中的点可以称之为一个对象（类）。

• 应用价值：网络这种数据结构在很多方面都具有很强的应用，如：

  1. 医学专家希望了解传染病在社会网络中的传播途径并找到预防与控制策略

  2. 社会学家关心观点和流言蜚语如何在社会网络上进行传播

  3. 工程师希望找到由局部故障而引起大规模故障原因，如由美国次级房屋信贷危机而引起的全球金融危机

     
     图1 简单网络拓扑图.png

2. 图的数学表示

• 定义：将图表示为可以在计算机中处理的形式

• 常见表示方式：

  1. 邻接矩阵
  2. 邻接表
  3. 三元组

3. 路径

• 定义：无向图 的一条路径指的是一个序列 其中每一对相邻节点之间都存在着边，则称P为节点 和节点 的一条路径

• 含义：路径在网络的实际应用中具有巨大的作用，如：

  1. 社交网络中，如果两个节点之间没有路径则可以表示两个人不相互认识
  2. 在Internet中，如果两个节点之间没有路径则可以表示这两个PC之间不能进行通信

• 问1:如何求解两个节点之间是否有路径呢？如果有路径的条数是多少？其中最短路径的长度及其序列是什么？

4. 图的连通性

• 定义： 图 中，任意两个节点直接都存在路径，则称该图是连通的

• 含义：如一个Internet图是连通的则表明图中的每一个定点都能相互通信

• 问2： 如何判断一个图是否是连通的，如果不连通又如何求解出最大连通图？

5. 最小生成树

• 定义：在有权无向（有向）连通图 中，其中N表示节点的数目。仅通过 条边使图G连通并且条边上的权重最小则称该图为最小生成树。

• 含义：最小生成树表示的是使图G连通的最小代价（边数和权重），比如，在修路中，节点表示村庄，道路表示边。最小生成树则可以表示使得所有村庄之间都连通时修建道路所耗费最少的代价。从另一个角度来看，最小生成树象征着一个网络的骨架。

6. 度，平均度

• 定义：节点的度表示与节点所连接的边的数目，其是刻画节点特征的指标之一。平均度表示网络中所有节点的度的平均值。

7. 网络的密度

• 定义：网络的密度等于网络中实际的边的个数 / 网络最大可能的边数

• 含义：网络的密度越大表示网络的边数越多，网络的边数越多则表示网络越稠密，反之，则表示网络越稀疏

8. 网络平均路径长度

• 定义：节点和节点的距离定义为连接这两个节点的最短路径上边的数目。网络的平均路径定义为网络中任意两个节点之间的距离的平均值，即
• 含义：六度空间理论，如社交网络中，任意两个人之间想取得联系，则需要少于六个人进行信息的传递即可

9. 网络的聚类(clustering coefficient)系数

• 定义：网络中有一节点的度为，那么在其所有的邻居节点中，有多少也是邻居，即在你的两个朋友中，他们是否也是朋友。节点的聚类系数记为,其中 是节点的个邻接点之间实际存在的边数。网络的聚类系数为所有节点的聚类系数的平均值

• 含义：就社交网络而言，某一人的聚类系数可以表示该人朋友圈的紧密程度

---

networkx实现

• 图的创建

• 图的使用

问题往往比答案更重要，以下所有实现都基于一个实际的问题而言

#  图的创建
# 1. 由图的定义可知，图由点集对象和边集对象所组成。因此我们定义好点和边即定义出一个图，定义一个图1所示的图
import networkx as nx
# 定义节点集
nodes = [1,2,3,4,5,6,7,8,9,10]
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10])
# 定义边集
edges = [(1, 2),(1, 3),(1, 4),(1, 6),(2, 4),(2, 5),(3, 4),(3, 6),(4, 5),(4, 6),(4, 7),(5, 7),(6, 7),(6, 8),(7, 8),(8, 9)]
G.add_edges_from(edges)

---

# 图的使用
# 定义节点集
nodes = [1,2,3,4,5,6,7,8,9,10]
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10])
# 定义边集
edges = [(1, 2),(1, 3),(1, 4),(1, 6),(2, 4),(2, 5),(3, 4),(3, 6),(4, 5),(4, 6),(4, 7),(5, 7),(6, 7),(6, 8),(7, 8),(8, 9)]
G.add_edges_from(edges)
# 帮我看看1号节点有多少个朋友？(判断节点的度)
print('1号节点有%d个朋友'%G.degree(1))
# 帮我看看1号节点和10节点，9节点分别是不是朋友？（判断节点之间是否有路径）
print('1 和 9 是朋友') if nx.algorithms.shortest_paths.generic.has_path(G, 1, 9) else print('1 和 9 不是朋友')
print('1 和 10 是朋友') if nx.algorithms.shortest_paths.generic.has_path(G, 1, 10) else print('1 和 9 不是朋友')
# 帮我看看网络中所有的节点能不能相互通信（判断网络是不是连通的）
print('网络中所有的节点能相互通信')if approx.node_connectivity(G) == 0 else print('网络中所有的节点不能相互通信')
# 帮我看看这个网络的平均路径长度，聚类系数？我等会有大用
print('聚类系数%f'%nx.algorithms.cluster.average_clustering(G))
print('平均路径长度%d'%nx.algorithms.shortest_paths.generic.average_shortest_path_length(G))