网络剖析（GIS网络剖析）原创数据派THU2018-08-07 22:00:00
作者：Srivatsa
翻译：和中华
校订：丁楠雅
本文约6300字，建议浏览20+分钟。
本文从图的概念以及历史讲起，并介绍了一些必备的术语，随后引入了networkx库，并以一个航班信息数据集为例，率领读者完成了一些根本剖析。
简介
俗话说一图胜千言。但是“图”（Graph）说的远不止于此。以图情势出现的数据可视化能赞助我们获得看法，并基于它们做出更好的数据驱动型决策。
但要真正懂得图是什么以及为什么应用它们，我们须要懂得一个称为图论（Graph Theory）的概念。懂得它可以使我们成为更好的程序员。
如果你曾经尝试懂得这个概念，应当会遇到大批的公式和干涩的理论。这便是为什么我们要写这篇博文的原因。我们先说明概念，然后供给实例，以便你可以追随并弄明确它的履行方法。这是一篇详细的文章，因为我们以为供给概念的准确说明要比简练的定义更受欢迎。
在本文中，我们将懂得图是什么，它们的运用以及一些历史背景。我们还将介绍一些图论概念，然后应用进行案例研讨以巩固懂得。
预备好了吗？我们开端吧。
目录
图及其运用
图论的历史、为何应用图论
必备术语
图论概念
熟习Python中的图
数据剖析案例
图及其运用
让我们看一个简略的图（Graph）来懂得这个概念。如下图所示：
假设此图代表某个城市的热点景点地位，以及游客所遵守的路径。我们把V视为景点地位，将E视为从一个处所到另一个处所的路径。
V = {v1, v2, v3, v4, v5}
E = {(v1,v2), (v2,v5), (v5, v5), (v4,v5), (v4,v4)}
边（u，v）与边（v，u）雷同 - 它们是无序对。
具体而言，图（Graph）是用于研讨对象和实体之间成对关系的数学构造。它是离散数学的一个分支，在盘算机科学，化学，语言学，运筹学，社会学等范畴有多种运用。
数据科学和剖析范畴也应用图来模仿各种构造和问题。作为一名数据科学家，你应当能以有效的方法解决问题，如果数据是以特定方法排列的，则图可以供给一种解决问题的机制。
情势上看，
图是一对聚集。G = (V, E)，V是顶点聚集，E是边聚集。 E由V中的元素对组成（无序对）
有向图（DiGraph）也是一对聚集。D = (V, A)，V是顶点聚集，A是弧聚集。A由V中的元素对组成（有序对）
在有向图的情形下，（u，v）和（v，u）之间存在差别。通常在这种情形下，边被称为弧，以指导方向的概念。
R和Python中都有应用图论概念剖析数据的包。在本文中，我们将扼要介绍一些概念并应用Networkx Python包剖析一个数据集。
from IPython.display im百思特网port Image
Image('images/network.PNG')
Image('images/usecase.PNG')
从上面的例子可以清晰地看出，图在数据剖析中的运用是普遍的。我们来看几个用例场景：
营销剖析
图可用于找出社交网络中最有影响力的人。广告商和营销人员可以通过社交网络中最有影响力的人员转达他们的信息，从而估算最大的营销价钱。
银行交易
图可用于查找有助于减少讹诈交易的异常模式。有一些例子可以通过火析银行网络的资金流动来侦测恐惧主义运动。
供给链
图有助于肯定送货卡车的最佳路线以及辨认仓库和交付中心的地位。
制药公司
制药公司可以应用图论优化出售人员的路线。这有助于下降成本并缩短出售人员的行程时光。
电信行业
电信公司通常应用图（Voronoi图）来懂得基站的数目和地位，以确保最大的笼罩规模。
图的历史以及为何应用图
图的历史
如果想更多地懂得关于图的想法是如何形成的，请持续浏览！
该理论的来源可以追溯到柯尼斯堡七桥问题（大约1730年代）。它提问是否可以在以下限制条件下遍历柯尼斯堡市的七座桥梁
每座桥只经过一次（即不反复）
从哪动身，最终回到哪
小故事：欧拉于1736年研讨并解决了此问题，他把问题归结为如“一笔画”问题。他的《柯尼斯堡七桥》的论文美满解决了这一问题，同时首创了数学一个新分支---图论。
这等价于讯问4个节点和7个边的多图（multigraph）是否具有欧拉环（欧拉环是在同一个顶点上开端和停止的欧拉路径。而欧拉路径是指在图中仅仅遍历每个边一次的路径。更多术语后文中给出）。这个问题引出了欧拉图的概念。柯尼斯堡七桥问题的答案是否认的，它最早由欧拉解答。
译者注：在图论中，多图（相对于简略图）是指图中许可涌现多边（也叫平行边），即两个顶点可以有多条边衔接，如下图中的红色就是多边，所以该图属于多图。
1840年，A.F Mobius提出了完整图（complete graph）和二分图（bipartite graph）的概念，Kuratowski通过趣味谜题证明它们是平面的。树的概念（没有环的连通图）由Gustav Kirchhoff于1845年提出，他在盘算电网或电路中的电流时应用了图论思想。
1852年，Thomas Gutherie发明了有名的四色问题。然后在1856年，Thomas P. Kirkman和William R.Hamilton研讨了多面体的循环，并通过研讨仅拜访某些地点一次的旅行，创造了称为哈密顿图的概念。1913年，H.Dudeney提到了一个难题。尽管创造了四色问题，但Kenneth Appel和Wolfgang Haken在一个世纪后才解决了这个问题。这一次被以为是图论真正的出生。
Caley研讨了微分学的特定剖析情势来研讨树。这在理论化学中有许多含义。这也导致了枚举图论（enumerative graph theory）的创造。不管怎么说，“图”这个术语是由Sylvester在1878年引入的，他在“量子不变量”与代数和分子图的协变量之间进行了类比。
1941年，Ramsey致力于着色问题，这发生了另一个图论的分支 - 极值图论（Extremal graph theory）。1969年，Heinrich应用盘算机解决了四色问题。对渐近图连通性的研讨发生了随机图论。图论和拓扑学的历史也亲密相干，它们有许多共同的概念和定理。
Image('images/Konigsberg.PNG', width = 800)
为何应用图？
以下几点可以鼓励你在日常数据科学问题中应用图：
图供给了一种处置关系和交互等抽象概念的更好的办法。它还供给了直观的视觉方法来思考这些概念。图很自然地成了剖析社会关系的基本。
图数据库已成为一种常用的盘算工具，并且是SQL和NoSQL数据库的替代计划。
图用于以DAG（定向非循环图）的情势建模剖析工作流。
一些神经网络框架还应用DAG来模仿不同层中的各种操作。
图理论用于研讨和模仿社交网络，讹诈模式，功耗模式，社交媒体的病毒性和影响力。社交网络剖析（SNA）可能是图理论在数据科学中最有名的运用。
它用于聚类算法 - 特殊是K-Means。
体系动力学也应用一些图理论 - 特殊是循环。
路径优化是优化问题的一个子集，它也应用图的概念。
从盘算机科学的角度来看，图供给了盘算效力。某些算法的Big O庞杂度对于以图情势排列的数据更好（与表格数据相比）。
必备术语
在进一步浏览本文之前，建议你熟习这些术语。
顶点u和v称为边（u，v）的末端顶点。
如果两条边具有雷同的末端顶点，则它们是平行的。
情势为（v，v）的边是循环。
如果图没有平行边和循环，则图被称为简略图。
如果图没有边，则称其为Empty，即E是空的。
如果图没有顶点，则称其为Null，即V和E是空的。
只有1个顶点的图是一个Trivial graph。
具有共同顶点的边是相邻的。具有共同边的顶点是相邻的。
顶点v的度，写作d（v），是指以v作为末端顶点的边数。依照通例，我们把一个循环计作两次，并且平行边沿分离贡献一个度。
孤立顶点是度数为1的顶点。d（1）顶点是孤立的。
如果图的边聚集包括了所有顶点之间的所有可能边，则图是完备的。
图G =（V，E）中的步行（Walk）是指由图中顶点和边组成的一个形如ViEiViEi的有限交替序列。
如果初始顶点和最终顶点不同，则Walk是开放的（Open）。如果初始顶点和最终顶点雷同，则Walk是关闭的（Closed）。
如果任何边沿最多遍历一次，则步行是一条Trail。
如果任何顶点最多遍历一次，则Trail是一条路径Path（除了一个封锁的步行）。
封锁路径（Closed Path）是一条回路Circuit，相似于电路。
图论概念
在本节中，我们将介绍一些对数据剖析有用的概念（无特定次序）。请注意，另外还有很多概念的深度超越了本文的规模。我们开端吧。
平均路径长度
所有可能节点对应的最短路径长度的平均值。给出了图的“紧密度”度量，可用于懂得此网络中某些内容的流动速度。
BFS和DFS
广度优先搜索和深度优先搜索是用于在图中搜索节点的两种不同算法。它们通常用于肯定我们是否可以从给定(原创版权www.isoyu.com)节点达到某个节点。这也称为图遍历。
BFS的目标是尽可能接近根节点遍历图，而DFS算法旨在尽可能远离根节点。
中心性（Centrality）
用于剖析网络的最普遍应用和最主要的概念工具之一。中心性旨在寻找网络中最主要的节点。可能存在对“主要”的不同懂得，因此存在许多中心性度量尺度。中心性尺度本身就可以分成好多类。有一些尺度是以沿着边的流动为特点，还有一些尺度以步行构造（Walk Structure）为特点。
一些最常用的尺度是：
度中心性（Degree Centrality）- 第一个也是概念上最简略的中心性定义。表现衔接到某节点的边数。在有向图中，我们可以有2个度中心性度量。流入和流出的中心性。
紧密中心性（Closeness Centrality）- 从某节点到所有其他节点的最短路径的平均长度。
中介中心性（Betweenness Centrality）- 某节点在多少对节点的最短路径上。
这些中心性度量有不同变种，并且可以应用各种算法来实现定义。总而言之，这方面有大批的定义和算法。
网络密度
图的边数的度量。实际定义将依据图的类型和所提问问题的高低文而不同。对于完备的无向图，密度为1，而空图（empty）为0。在某些情形下（包括循环时），图密度可能大于1。
图随机化（Graph Randomization）
尽管一些图度量指标可能很容易盘算，但要懂得它们的相对主要性并不容易。在这种情形下，我们应用网络/图随机化。我们盘算了手头的图和随机生成的另一些相似图的度量。例如，这些类似图可以有雷同数目的密度和节点。通常我们生成1000个类似的随机图并盘算每个图的度量尺度，然后与手头图的雷同度量进行比拟，以得出某些基准（benchmark）。
在数据科学中，当尝试对某个图进行声明时，如果与某些随机生成的图进行比较，则会有所赞助。
熟习Python中的图
我们将在Python中应用networkx包。它可以安装在Anaconda的Root环境中（如果你应用的是Anaconda的Python分发版）。你也可以pip install安装它。
让我们看一下应用Networkx软件包可以完成的一些常见事情。包含导入和创立图以及可视化图的办法。
图形创立
import networkx as nx
# Creating a Graph
G = nx.Graph() # Right now G is empty
# Add a node
G.add_node(1)
G.add_nodes_from([2,3]) # You can also add a list of nodes by passing a list argument
# Add edges
G.add_edge(1,2)
e = (2,3)
G.add_edge(*e) # * unpacks the tuple
G.add_edges_from([(1,2), (1,3)]) # Just like nodes we can add edges from a list
通过传递包括节点和属性dict的元组，可以在创立节点和边的时候添加节点和边的属性。
除了逐个节点或逐个边地构建图形之外，还可以通过一些经典的图操作来生成它们，例如：
subgraph(G, nbunch) - induced subgraph view of G on nodes in nbunch
union(G1,G2) - graph union
disjoint_union(G1,G2) - graph union assuming all nodes are different
cartesian_product(G1,G2) - return Cartesian product graph
compose(G1,G2) - combine graphs identifying nodes common to both
complement(G) - graph complement
create_empty_copy(G) - return an empty copy of the same graph class
convert_to_undirected(G) - return an undirected representation of G
convert_to_directed(G) - return a directed representation of G
对于不同类型的图，存在单独的类。例如，nx.DiGraph类许可创立有向图。可以应用单个办法直接创立包括路径的特定图。有关图创立办法的完全列表，请参阅完全文档。链接在本文末尾给出。
Image('images/graphclasses.PNG', width = 400)
拜访边和节点
可以应用G.nodes和G.edges办法拜访节点和边。可以应用括号/下标法拜访各个节点和边。
G.nodes()
NodeView((1, 2, 3))
G.edges()
EdgeView([(1, 2), (1, 3), (2, 3)])
G[1] # same as G.adj[1]
AtlasView({2: {}, 3: {}})
G[1][2]
{}
G.edges[1, 2]
{}
图可视化
Networkx供给了可视化图的根本功效，但其重要目的是赞助图剖析而不是图的可视化。图可视化很难，我们将应用专门用于此义务的工具。Matplotlib供给了一些方便功效。但是GraphViz可能是最好的工具，因为它供给了一个PyGraphViz的Python接口（链接在文档的末尾）。
%matplotlib inline
import matplotlib.pyplot as plt
nx.draw(G)
首先必需安装Graphviz。然后应用该命令pip install pygraphviz --install-option =“<>。在安装选项中，你必需供给Graphviz 中lib和include文件夹的路径。
import pygraphviz as pgv
d={'1': {'2': None}, '2': {'1': None, '3': None}, '3': {'1': None}}
A = pgv.AGraph(data=d)
print(A) # This is the 'string' or simple representation of the Graph
Output:
strict graph "" {
1 -- 2;
2 -- 3;
3 -- 1;
}
PyGraphviz可以很好地掌握边和节点的各个属性。我们可以应用它获得非常英俊的可视化。
# Let us create another Graph where we can individually control the colour of each node
B = pgv.AGraph()
# Setting node attributes that are common for all nodes
B.node_attr['style']='filled'
B.node_attr['shape']='circle'
B.node_attr['fixedsize']='true'
B.node_attr['fontcolor']='#FFFFFF'
# Creating and setting node attributes that vary for each node (using a for loop)
for i in range(16):
B.add_edge(0,i)
n=B.get_node(i)
n.attr['fillcolor']="#%2x0000"%(i*16)
n.attr['height']="%s"%(i/16.0+0.5)
n.attr['width']="%s"%(i/16.0+0.5)
B.draw('star.png',prog="circo") # This creates a .png file in the local directory. Displayed below.
Image('images/star.png', width=650) # The Graph visualization we created above.
通常，可视化被以为是与图剖析独立的义务。剖析后的图将导出为Dotfile。然后单独显示该Dotfile以展现我们想表达的内容。
数据剖析案例
我们将寻找一个通用数据集（不是专门用于图的数据集）并进行一些操作（在pandas中），以便它可以以边列表（edge list）的情势输入到图中。边列表是一个元组列表，其中的元组包括定义每条边的顶点
我们将关注的数据集来自航空业。它有一些关于航线的根本信息。有某段旅程的起始点和目标地。还有一些列表现每段旅程的达到和腾飞时光。如你所想，这个数据集非常合适作为图进行剖析。想象一下通过航线（边）衔接的几个城市（节点）。如果你是航空公司，你可以问如下几个问题：
从A到B的最短门路是什么？分离从距离和时光角度斟酌。
有没有方法从C到D？
哪些机场的交通最忙碌？
哪个机场位于大多数其他机场“之间”？这样它就可以变成当地的一个中转站。
import pandas as pd
import numpy as np
data = pd.read_csv('data/Airlines.csv')
data.shape
(100, 16)
data.dtypes
year int64
month int64
day int64
dep_time float64
sched_dep_time int64
dep_delay float64
arr_time float64
sched_arr_time int64
arr_delay float64
carrier object
flight int64
tailnum object
origin object
dest object
air_time float64
distance int64
dtype: object
我们注意到起始点和目标地看起来像节点的好人选。然后可以将所有东西想象为节点或边的属性。单条边可以被以为是一段旅程。这样的旅程将有不同的时光，航班号，飞机尾号等相干信息。
我们注意到年，月，日和时光信息疏散在许多列上。所以我们想创立一个包括所有这些信息的日期时光列。我们还须要将预计的（scheduled）和实际的(actual)达到分开时光离开。所以我们最终应当有4个日期时光列（预计达到时光、预计腾飞时光、实际达到时光和实际腾飞时光）。
此外，时光列的格局不准确。下午4:30被表现为1630而不是16:30。该列没有分隔符。一种办法是应用pandas字符串办法和正则表达式。
我们还应当注意到sched_dep_time和sched_arr_time是int64 类型而dep_time和arr_time是float64 类型。
另一个麻烦是NaN值。
# converting sched_dep_time to 'std' - Scheduled time of departure
data['std'] = data.sched_dep_time.astype(str).str.replace('(\d{2}$)', '') + ':' + data.sched_dep_time.astype(str).str.extract('(\d{2}$)', expand=False) + ':00'
# converting sched_arr_time to 'sta' - Scheduled time of arrival
data['sta'] = data.sched_arr_time.astype(str).str.replace('(\d{2}$)', '') + ':' + data.sched_arr_time.astype(str).str.extract('(\d{2}$)', expand=False) + ':00'
# converting dep_time to 'atd' - Actual time of departure
data['atd'] = data.dep_time.fillna(0).astype(np.int64).astype(str).str.replace('(\d{2}$)', '') + ':' + data.dep_time.fillna(0).astype(np.int64).astype(str).str.extract('(\d{2}$)', expand=False) + ':00'
# converting arr_time to 'ata' - Actual time of arrival
data['ata'] = data.arr_time.fillna(0).astype(np.int64).astype(str).str.replace('(\d{2}$)', '') + ':' + data.arr_time.fillna(0).astype(np.int64).astype(str).str.extract('(\d{2}$)', expand=False) + ':00'
现在时光列被转换成了我们想要的格局。最后，我们可能愿望将年，月和日列合并到日期列中。这一步不是绝对必要的。但是，一旦转换为日期时光（datetime）格局，我们就可以轻松获取年，月，日（和其他）信息。
data['date'] = pd.to_datetime(data[['year', 'month', 'day']])
# finally we drop the columns we don't need
data = data.drop(columns = ['year', 'month', 'day'])
现在应用networkx函数导入数据集，该函数直接读如pandas DataFrame。就像图创立一样，多种办法可以将数据从多种格局中输入到图中。
import networkx as nx
FG = nx.from_pandas_edgelist(data, source='origin', target='dest', edge_attr=True,)
FG.nodes()
输出：
NodeView(('EWR', 'MEM', 'LGA', 'FLL', 'SEA', 'JFK', 'DEN', 'ORD', 'MIA', 'PBI', 'MCO', 'CMH', 'MSP', 'IAD', 'CLT', 'TPA', 'DCA', 'SJU', 'ATL', 'BHM', 'SRQ', 'MSY', 'DTW', 'LAX', 'JAX'百思特网, 'RDU', 'MDW', 'DFW', 'IAH', 'SFO', 'STL', 'CVG', 'IND', 'RSW', 'BOS', 'CLE'))
FG.edges()
输出：
EdgeView([('EWR', 'MEM'), ('EWR', 'SEA'), ('EWR', 'MIA'), ('EWR', 'ORD'), ('EWR', 'MSP'), ('EWR', 'TPA'), ('EWR', 'MSY'), ('EWR', 'DFW'), ('EWR', 'IAH'), ('EWR', 'SFO'), ('EWR', 'CVG'), ('EWR', 'IND'), ('EWR', 'RDU'), ('EWR', 'IAD'), ('EWR', 'RSW'), ('EWR', 'BOS'), ('EWR', 'PBI'), ('EWR', 'LAX'), ('EWR', 'MCO'), ('EWR', 'SJU'), ('LGA', 'FLL'), ('LGA', 'ORD'), ('LGA', 'PBI'), ('LGA', 'CMH'), ('LGA', 'IAD'), ('LGA', 'CLT'), ('LGA', 'MIA'), ('LGA', 'DCA'), ('LGA', 'BHM'), ('LGA', 'RDU'), ('LGA', 'ATL'), ('LGA', 'TPA'), ('LGA', 'MDW'), ('LGA', 'DEN'), ('LGA', 'MSP'), ('LGA', 'DTW'), ('LGA', 'STL'), ('LGA', 'MCO'), ('LGA', 'CVG'), ('LGA', 'IAH'), ('FLL', 'JFK'), ('SEA', 'JFK'), ('JFK', 'DEN'), ('JFK', 'MCO'), ('JFK', 'TPA'), ('JFK', 'SJU'), ('JFK', 'ATL'), ('JFK', 'SRQ'), ('JFK', 'DCA'), ('JFK', 'DTW'), ('JFK', 'LAX'), ('JFK', 'JAX'), ('JFK', 'CLT'), ('JFK', 'PBI'), ('JFK', 'CLE'), ('JFK', 'IAD'), ('JFK', 'BOS')])
nx.draw_networkx(FG, with_labels=True) # Quick view of the Graph. As expected we see 3 very busy airports
nx.algorithms.degree_centrality(FG) # Notice the 3 airports from which all of our 100 rows of data originates
nx.density(FG) # Average edge density of the Graphs
输出：
0.09047619047619047
nx.average_shortest_path_length(FG) # Average shortest path length for ALL paths in the Graph
输出：
2.36984126984127
nx.average_degree_connectivity(FG) # For a node of degree k - What is the average of its neighbours' degree?
输出：
{1: 19.307692307692307, 2: 19.0625, 3: 19.0, 17: 2.0588235294117645, 20: 1.95}
从可视化中（上面的方法）可以显著看出 - 从一些机场到其他机场有多条路径。 假如想要盘算2个机场之间的最短路线。我们可以想到几种办法：
距离最短的路径。
飞翔时光最短的路径。
我们可以通过距离或飞翔时光来给路径赋予权重，并用算法盘算最短路径。请注意，这是一个近似的解决计划 - 实际问题是盘算当你达到中转机场时的航班可用性加候机的期待时光，这才是一种更完全的办法，也是人们筹划旅行的方法。出于本文的目标，我们将假设你达到机场时可以随时应用航班并应用飞翔时光作为权重，从而盘算最短路径。
让我们以JAX和DFW机场为例：
# Let us find all the paths available
for path in nx.all_simple_paths(FG, source='JAX', target='DFW'):
print(path)
# Let us find the dijkstra path from JAX to DFW.
# You can read more in-depth on how dijkstra works from this resource - https://courses.csail.mit.edu/6.006/fall11/lectures/lecture16.pdf
dijpath = nx.dijkstra_path(FG, source='JAX', target='DFW')
dijpath
输出：
['JAX', 'JFK', 'SEA', 'EWR', 'DFW']
# Let us try to find the dijkstra path weighted by airtime (approximate case)
shortpath = nx.dijkstra_path(FG, source='JAX', target='DFW', weight='air_time')
shortpath
输出：
['JAX', 'JFK', 'BOS', 'EWR', 'DFW']
结语
本文充其量只是对图论和网络剖析这一非常有趣的范畴进行了粗浅的介绍。对理论和Python软件包的懂得将为任何数据科学家的百思特网工具库增长一个有价值的工具。 对于上面应用的数据集，可以提出一系列其他问题，例如：
在给定成本，飞翔时光和可用性的情形下，找到两个机场之间的最短路径？
作为一家航空公司，你们拥有一队飞机。你懂得航班的需求。假设你有权再运营2架飞机（或者为你的机队添加2架飞机），把这两架飞机投入到哪条航线可以最大限度地进步盈利才能？
你可以重新支配航班和时刻表以优化某个参数吗？（如时效性或盈利才能等）
如果你解决了这些问题，请在下面的评论中告知我们！
网络剖析将有助于解决一些常见的数据科学问题，并在更大范围和抽象的情形下对其进行可视化。如果想懂得更多有关其他内容的信息，请发表评论。
参考文献
1. History of Graph Theory || S.G. Shrinivas et. al
2. Big O Notation cheatsheet
3. Networkx reference documentation
4. Graphviz download
5. Pygraphvix
6. Star visualization
7. Dijkstra Algorithm
原文题目：
An Introduction to Graph Theory and Network Analysis (with Python codes)
链接：
https://www.analyticsvidhya.com/blog/2018/04/introduction-to-graph-theory-network-analysis-python-codes/
译者简介
和中华，留德软件工程硕士。由于对机器学习感兴致，硕士论文选择了应用遗传算法思想改良传统kmeans。目前在杭州进行大数据相干实践。参加数据派THU愿望为IT同行们尽自己一份绵薄之力，也愿望结交许多志趣相投的小伙伴。