顶点v的度 ， 写作d（v） ， 是指以v作为末端顶点的边数 。按照惯例 ， 我们把一个循环计作两次 ， 并且平行边缘分别贡献一个度 。
孤立顶点是度数为1的顶点 。d（1）顶点是孤立的 。
如果图的边集合包含了所有顶点之间的所有可能边 ， 则图是完备的 。
图G =（V ， E）中的步行（Walk）是指由图中顶点和边组成的一个形如ViEiViEi的有限交替序列 。
如果初始顶点和最终顶点不同 ， 则Walk是开放的（Open） 。如果初始顶点和最终顶点相同 ， 则Walk是关闭的（Closed） 。
如果任何边缘最多遍历一次 ， 则步行是一条Trail 。
如果任何顶点最多遍历一次 ， 则Trail是一条路径Path（除了一个封闭的步行） 。
封闭路径（Closed Path）是一条回路Circuit ， 类似于电路 。
图论概念
在本节中 ， 我们将介绍一些对数据分析有用的概念（无特定顺序） 。请注意 ， 另外还有很多概念的深度超出了本文的范围 。我们开始吧 。
平均路径长度
所有可能节点对应的最短路径长度的平均值 。给出了图的“紧密度”度量 ， 可用于了解此网络中某些内容的流动速度 。
BFS和DFS
广度优先搜索和深度优先搜索是用于在图中搜索节点的两种不同算法 。它们通常用于确定我们是否可以从给定节点到达某个节点 。这也称为图遍历 。
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

• 上一页
• 1
• 2
• 3
• 4
• 5
• 6
• 下一页

• 走出洞穴
• 网络小说|十大巅峰网络小说排行榜 最顶级的网络小说推荐
• 绘本《重阳节》
• 神兽|网络最火十大神兽,网络神兽有什么
• 网络工程师转正述职报告怎么写？
• 网络营销工作计划怎么写？
• 年网络管理员简历模版如何写？
• 考试后总结范文有没有？
• 职场礼仪的重要性分析怎么写？
• 网络工程求职信格式怎么样？