原文：
zh.annas-archive.org/md5/8ddea683d78e7bd756401ec665273969译者：飞龙
第五章：图算法
有一类计算问题最好以图的术语来表示。这类问题可以使用一类称为图算法的算法来解决。例如，图算法可以用于在数据的图形表示中高效搜索值。为了高效工作，这些算法首先需要发现图的结构。它们还需要找到正确的策略来跟随图的边以读取顶点中存储的数据。由于图算法需要搜索值才能工作，因此高效的搜索策略是设计高效图算法的核心。使用图算法是在复杂的相互关联的数据结构中搜索信息的最有效方式之一。在当今的大数据、社交媒体和分布式数据时代，这些技术变得越来越重要和有用。
在本章中，我们将首先介绍图算法背后的基本概念。然后，我们将介绍网络分析理论的基础知识。接下来，我们将看看可以用来遍历图的各种技术。最后，我们将看一个案例研究，展示图算法如何用于欺诈检测。
在本章中，我们将介绍以下概念：
- 表示图的不同方式
- 引入网络理论分析
- 理解图的遍历
- 案例研究：欺诈分析
- 在我们的问题空间中建立邻域的技术
在本章结束时，您将对图是什么以及如何使用它们来表示相互关联的数据结构并从直接或间接关系的实体中挖掘信息有很好的理解，以及如何使用它们来解决一些复杂的现实世界问题。
图的表示
图是一种以顶点和边的形式表示数据的结构。图表示为aGraph = (𝓥, 𝓔)，其中𝓥表示一组顶点，𝓔表示一组边。注意aGraph有|𝓥|个顶点和|𝓔|条边。
一个顶点，𝓋 ∈ 𝓥，表示现实世界的对象，如人、计算机或活动。一条边，𝓋 ∈ 𝓔，连接网络中的两个顶点：
e(𝓋[1], 𝓋[2]) | e ∈ 𝓔 & 𝓋[i] ∈ 𝓥
前面的方程表明，在图中，所有边属于一个集合𝓔，所有顶点属于一个集合𝓥。
一条边连接两个顶点，因此代表它们之间的关系。例如，它可以代表以下关系：
- 人与人之间的友谊
- 一个人在 LinkedIn 上连接了一个朋友
- 一个集群中两个节点的物理连接
- 一个人参加研究会议
在本章中，我们将使用networkx Python 包来表示图。让我们尝试使用 Python 中的networtx包创建一个简单的图。首先，让我们尝试创建一个空图aGraph，没有顶点或节点：
import networkx as nx G = nx.Graph()
让我们添加一个单个顶点：
G.add_node("Mike")
我们还可以使用列表添加一堆顶点：
G.add_nodes_from(["Amine", "Wassim", "Nick"])
我们还可以在现有的顶点之间添加一条边，如下所示：
G.add_edge("Mike", "Amine")
现在让我们打印边和顶点：
请注意，如果我们添加一条边，这也会导致添加相关的顶点，如果它们尚不存在，如下所示：
G.add_edge("Amine","Imran")
如果我们打印节点列表，我们将看到以下输出：
请注意，对已经存在的顶点进行添加的请求会被静默忽略。请求的忽略或接受取决于我们创建的图的类型。
图的类型
图可以分为四种类型，即以下四种：
- 无向图
- 有向图
- 无向多重图
- 有向多重图
现在让我们逐个详细查看每一个。
无向图
在大多数情况下，图的组成节点之间表示的关系可以被认为是无方向的。这种关系不对关系施加任何顺序。这样的边被称为无向边，结果图被称为无向图。以下是一个无向图的示例：
一些无向关系的例子如下：
- 迈克和阿敏（迈克和阿敏互相认识）。
- 节点 A 和节点 B 相连（这是一种点对点的连接）。
有向图
图中节点之间的关系具有某种方向感的图被称为有向图。以下是一个有向图的示例：
一些有向关系的例子如下：
- 迈克和他的房子（迈克住在一所房子里，但他的房子不住在迈克里）。
- 约翰管理保罗（约翰是保罗的经理）。
无向多重图
有时，节点之间有多种关系。在这种情况下，可以有多条边连接相同的两个节点。这种图称为多重图，在同一节点上允许多条平行边。我们必须明确指出一个特定的图是否是多重图。平行边可以表示节点之间的不同类型的关系。
以下图显示了一个多重图：
多向关系的一个例子是迈克和约翰既是同学又是同事。
有向多重图
如果多重图中的节点之间存在方向关系，则称为有向多重图：
有向多重图的一个例子是迈克在办公室向约翰汇报，并且约翰教迈克 Python 编程语言。
特殊类型的边
边将图的各个顶点连接在一起，并表示它们之间的关系。除了简单的边，它们还可以是以下特殊类型：
- 自边：有时，特定的顶点可以与自己有关系。例如，约翰把钱从他的商业账户转到他的个人账户。这种特殊关系可以用自导向边来表示。
- 超边：有时，多个顶点由同一条边连接。连接多个顶点以表示这种关系的边被称为超边。例如，假设迈克、约翰和莎拉三人一起参与一个特定项目。
具有一个或多个超边的图被称为超图。
这里显示了自边和超边图的图示：
请注意，一个特定的图可以有多种特殊类型的边节点。这意味着一个特定的图可以同时具有自边和超边。
自我中心网络
特定顶点m的直接邻域可能包含足够重要的信息，以进行对节点的决定性分析。自我中心，或者称为 egonet，就是基于这个想法的。特定顶点m的 egonet 包括所有直接连接到m的顶点以及节点m本身。节点m被称为自我，与之连接的一跳邻居被称为替代者。
特定节点 3 的自我网络在以下图中显示：
请注意，egonet 代表一度邻域。这个概念可以扩展到 n 度邻域，包括所有 n 跳离感兴趣的顶点的顶点。
社交网络分析
社交网络分析（SNA）是图论的重要应用之一。如果满足以下条件，网络图分析被认为是社交网络分析：
- 图的顶点代表人。
- 它们之间的边代表着它们之间的社会关系，如友谊、共同爱好、血缘关系、性关系、厌恶等等。
- 我们通过图分析试图回答的商业问题具有很强的社会方面。
人类行为在 SNA 中得到反映，并且在进行 SNA 时应始终牢记。通过在图中绘制人际关系，SNA 可以深入了解人际互动，这有助于我们理解他们的行为。
通过在每个个体周围创建邻域，并根据其社会关系分析个体的行为，您可以产生有趣的，有时令人惊讶的见解。基于个体的个人工作职能对个体进行分析的替代方法只能提供有限的见解。
因此，SNA 可以用于以下方面：
- 理解用户在社交媒体平台上的行为，如 Facebook、Twitter 或 LinkedIn
- 理解欺诈
- 理解社会的犯罪行为
LinkedIn 在 SNA 相关的新技术的研究和开发方面做出了很大贡献。事实上，LinkedIn 可以被认为是该领域许多算法的先驱。
因此，由于社交网络的固有分布和相互连接的架构，SNA 是图论最强大的用例之一。另一种抽象图的方法是将其视为网络，并应用设计用于网络的算法。这整个领域被称为网络分析理论，我们将在下面讨论。
介绍网络分析理论
我们知道，互连的数据可以表示为网络。在网络分析理论中，我们研究了开发用于探索和分析表示为网络的数据的方法的细节。让我们在本节中看一些网络分析理论的重要方面。
首先，注意网络中的一个顶点充当基本单元。网络是一个由顶点相互连接而成的网络，其中每个连接代表着调查对象之间的关系。在解决问题的背景下，量化网络中顶点的有用性和重要性是很重要的。有各种技术可以帮助我们量化重要性。
让我们看一些网络分析理论中使用的重要概念。
理解最短路径
路径是起始节点和结束节点之间的节点序列，路径上没有节点出现两次。路径代表了所选起始和结束顶点之间的路线。它将是一组连接起始顶点和结束顶点的顶点p。在p中没有重复的顶点。
路径的长度是通过计算组成边来计算的。在所有选项中，具有最小长度的路径称为最短路径。最短路径的计算在图论算法中被广泛使用，但并不总是直接计算。有不同的算法可以用来找到起始节点和结束节点之间的最短路径。其中一个最流行的算法是Dijkstra 算法，它在 20 世纪 50 年代末出版。它可以计算图中的最短路径。它可以被全球定位系统（GPS）设备用来计算源和目的地之间的最小距离。Dijkstra 算法也用于网络路由算法。
谷歌和苹果之间存在一场争夺，他们要设计出最佳的谷歌地图和苹果地图的最短距离算法。他们面临的挑战是使算法足够快，可以在几秒内计算出最短路径。
在本章后面，我们将讨论广度优先搜索（BFS）算法，它可以修改为迪杰斯特拉算法。BFS 假设在给定图中遍历每条路径的成本相同。对于迪杰斯特拉算法，遍历图的成本可能不同，需要将其纳入修改 BFS 为迪杰斯特拉算法。
正如所示，迪杰斯特拉算法是一种计算最短路径的单源算法。如果我们想解决所有最短路径对，那么可以使用弗洛伊德-沃舍尔算法。
创建邻域
为了图算法的关键节点周围创建邻域的策略至关重要。创建邻域的方法基于选择与感兴趣的顶点直接关联的方法。创建邻域的一种方法是选择一个k阶策略，该策略选择与感兴趣的顶点相距k跳的顶点。
让我们看看创建邻域的各种标准。
三角形
在图论中，找到彼此连接良好的顶点对于分析很重要。一种技术是尝试识别三角形，在网络中，三角形是由三个直接相连的节点组成的子图。
让我们看看欺诈检测的用例，我们在本章末尾也将其用作案例研究。如果节点m的 egonet 包括三个顶点，包括顶点m，那么这个 egonet 就是一个三角形。顶点m将是 ego，而两个连接的顶点将是 alter，比如顶点A和顶点B。如果两个 alter 都是已知的欺诈案例，我们可以安全地宣布顶点m也是欺诈的。如果其中一个 alter 涉及欺诈，我们无法得出结论性证据，但我们需要进一步调查欺诈证据。
密度
让我们首先定义一个完全连接的网络。我们称每个顶点直接连接到每个其他顶点的图为完全连接的网络。
如果我们有一个完全连接的网络N，那么网络中的边数可以表示如下：
现在，这就是密度发挥作用的地方。密度测量观察到的边的数量与最大边数的比值，如果**Edges****[Observed]**是我们想要观察的边的数量。它可以表述如下：
请注意，对于三角形，网络的密度为1，这代表了最高可能的连接网络。
理解中心性度量
有不同的度量方法来理解图或子图中特定顶点的中心性。例如，它们可以量化社交网络中一个人的重要性，或者城市中建筑物的重要性。
以下中心性度量在图分析中被广泛使用：
- 度
- 介数
- 紧密度
- 特征向量
让我们详细讨论它们。
度
顶点连接的边的数量称为其度。它可以指示特定顶点的连接情况以及其在网络中快速传播消息的能力。
让我们考虑aGraph = (𝓥, 𝓔)，其中𝓥表示顶点集合，𝓔表示边集合。回想一下，aGraph有|𝓥|个顶点和|𝓔|条边。如果我们将节点的度除以(|𝓥|-1)，则称为度中心性：
现在，让我们看一个具体的例子。考虑以下图：
现在，在上述图中，顶点 C 的度为 4。其度中心性可以计算如下：
介数
介数是图中的中心性度量。在社交媒体的背景下，它将量化一个人在子群中参与通信的概率。对于计算机网络，介数将量化在顶点故障的情况下对图节点之间通信的负面影响。
要计算aGraph中顶点a的介数，按照以下步骤进行：
- 计算
aGraph中每对顶点之间的最短路径。让我们用
- 来表示这一点。
- 从
- ，计算通过顶点a的最短路径数量。让我们用
- 来表示这一点。
- 使用
来计算介数。
公平和亲近
让我们拿一个图g。图g中顶点a的公平性被定义为顶点a到其他顶点的距离之和。请注意，特定顶点的中心性量化了它与所有其他顶点的总距离。
公平性的对立面是亲近度。
特征向量中心性
特征向量中心性给出了图中所有顶点的分数，衡量它们在网络中的重要性。该分数将是特定节点与整个网络中其他重要节点的连接性的指标。当谷歌创建了PageRank 算法时，该算法为互联网上的每个网页分配一个分数（以表达其重要性），这个想法就是源自特征向量中心性度量。
使用 Python 计算中心性度量
让我们创建一个网络，然后尝试计算其中心性度量。以下代码块说明了这一点：
import networkx as nx import matplotlib.pyplot as plt vertices = range(1,10) edges = [(7,2), (2,3), (7,4), (4,5), (7,3), (7,5), (1,6),(1,7),(2,8),(2,9)] G = nx.Graph() G.add_nodes_from(vertices) G.add_edges_from(edges) nx.draw(G, with_labels=True,node_color='y',node_size=800)
这段代码生成的图如下所示：
到目前为止，我们已经研究了不同的中心性度量。让我们为前面的例子计算这些度量：
请注意，中心性的度量应该给出图或子图中特定顶点的中心性度量。从图中看，标记为 7 的顶点似乎具有最中心的位置。顶点 7 在中心性的四个度量中具有最高值，因此反映了它在这个上下文中的重要性。
现在让我们看看如何从图中检索信息。图是复杂的数据结构，存储了大量的信息，既在顶点中又在边中。让我们看一些可以用来有效地遍历图以从中收集信息以回答查询的策略。
理解图遍历
要利用图，需要从中挖掘信息。图遍历被定义为用于确保以有序方式访问每个顶点和边的策略。努力确保每个顶点和边都被访问一次，不多不少。广义上讲，可以有两种不同的遍历图的方式来搜索其中的数据。按广度进行称为广度优先搜索（BFS），按深度进行称为深度优先搜索（DFS）。让我们依次看一下它们。
广度优先搜索
当我们处理aGraph时，如果存在层次或邻域级别的概念，BFS 效果最好。例如，当 LinkedIn 中一个人的联系被表示为图时，有一级联系，然后有二级联系，这直接对应于层次。
BFS 算法从根顶点开始，探索邻居顶点，然后移动到下一个邻居级别并重复这个过程。
让我们看一个 BFS 算法。为此，让我们首先考虑以下无向图：
让我们从计算每个顶点的直接邻居开始，并将其存储在一个称为邻接表的列表中。在 Python 中，我们可以使用字典数据结构来存储它：
graph={ 'Amin' : {'Wasim', 'Nick', 'Mike'}, 'Wasim' : {'Imran', 'Amin'}, 'Imran' : {'Wasim','Faras'}, 'Faras' : {'Imran'}, 'Mike' : {'Amin'}, 'Nick' : {'Amin'}}
为了在 Python 中实现它，我们按照以下步骤进行。
我们将首先解释初始化，然后是主循环。
初始化
我们将使用两种数据结构：
visited：包含所有已经被访问的顶点。最初，它将是空的。queue：包含我们希望在下一次迭代中访问的所有顶点。
主循环
接下来，我们将实现主循环。它将一直循环，直到队列中没有一个元素。对于队列中的每个节点，如果它已经被访问过，那么它就会访问它的邻居。
我们可以在 Python 中实现这个主循环，如下所示：
- 首先，我们从队列中弹出第一个节点，并将其选择为此次迭代的当前节点。
node = queue.pop(0)
- 然后，我们检查节点是否不在已访问列表中。如果不在，我们将其添加到已访问节点的列表中，并使用邻居来表示其直接连接的节点
visited.append(node) neighbours = graph[node]
- 现在我们将节点的邻居添加到队列中：
for neighbour in neighbours: queue.append(neighbour)
- 主循环完成后，将返回包含所有遍历节点的
visited数据结构。 - 完整的代码，包括初始化和主循环，如下所示：
让我们来看看使用 BFS 定义的图的详尽搜索遍历模式。为了访问所有节点，遍历模式如下图所示。可以观察到，在执行过程中，它始终保持两种数据结构：
- 已访问：包含所有已经被访问的节点
- 队列：包含尚未被访问的节点
算法的工作原理如下：
- 它从第一个节点开始，也就是第一级上唯一的节点 Amin。
- 然后，它移动到第二级，并依次访问所有三个节点 Wasim、Nick 和 Mike。
- 然后，它移动到第三级和第四级，每个级别只有一个节点，Imran 和 Faras。
一旦所有节点都被访问，它们将被添加到已访问的数据结构中，迭代就会停止：
现在，让我们尝试使用 BFS 从这个图中找到特定的人。让我们指定我们正在搜索的数据，并观察结果：
现在让我们来看看深度优先搜索算法。
深度优先搜索
DFS 是 BFS 的替代方法，用于从图中搜索数据。将 DFS 与 BFS 区分开的因素是，在从根顶点开始后，算法会逐个沿着每条唯一的路径尽可能深入。对于每条路径，一旦成功到达最终深度，它就会标记所有与该路径相关的顶点为已访问。完成路径后，算法会回溯。如果它能找到另一条从根节点开始但尚未被访问的路径，算法会重复之前的过程。算法会在新分支中不断移动，直到所有分支都被访问。
请注意，图可能具有循环方法。如前所述，我们使用布尔标志来跟踪已处理的顶点，以避免在循环中迭代。
为了实现 DFS，我们将使用一个栈数据结构，这在第二章中已经详细讨论过，算法中使用的数据结构。请记住，栈是基于后进先出（LIFO）原则的。这与队列相反，队列用于 BFS，它基于先进先出（FIFO）原则。
以下代码用于 DFS：
def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) print(start) for next in graph[start] - visited: dfs(graph, next, visited) return visited
让我们再次使用以下代码来测试先前定义的dfs函数：
graph={ 'Amin' : {'Wasim', 'Nick', 'Mike'}, 'Wasim' : {'Imran', 'Amin'}, 'Imran' : {'Wasim','Faras'}, 'Faras' : {'Imran'}, 'Mike' :{'Amin'}, 'Nick' :{'Amin'}}
如果我们运行这个算法，输出将如下所示：
让我们使用 DFS 方法来查看这个图的详尽遍历模式：
- 迭代从顶部节点 Amin 开始。
- 然后，它移动到第二级，Wasim。从那里，它向下一级移动，直到达到末端，即 Imran 和 Fares 节点。
- 完成第一个完整分支后，它回溯然后到达第二级访问 Nick 和 Mike。
遍历模式如下图所示：
请注意，DFS 也可以用于树。
现在，让我们看一个案例研究，解释了本章迄今为止讨论的概念如何用于解决现实世界的问题。
案例研究 - 欺诈分析
让我们看看如何使用 SNA 来检测欺诈。人类是社会动物，人的行为据说受到周围的人的影响。同质性一词被创造出来代表他们的社交网络对一个人的影响。扩展这个概念，同质网络是一群人，他们由于某些共同因素而可能与彼此关联；例如，具有相同的起源或爱好，是同一个团伙或同一个大学的一部分，或其他因素的组合。
如果我们想在同质网络中分析欺诈，我们可以利用调查对象与网络中其他人之间的关系，这些人已经仔细计算了他们参与欺诈的风险。有时因为某人的公司而标记一个人也被称为因陋就寡。
为了理解这个过程，让我们首先看一个简单的案例。为此，让我们使用一个具有九个顶点和八条边的网络。在这个网络中，有四个顶点是已知的欺诈案例，并被分类为fraud (F)。剩下的五个人中有五个没有欺诈相关历史，被分类为non-fraud (NF)。
我们将编写以下步骤的代码来生成这个图表：
- 让我们导入我们需要的包：
import networkx as nx import matplotlib.pyplot as plt
- 定义
vertices和edges的数据结构：
vertices = range(1,10) edges= [(7,2), (2,3), (7,4), (4,5), (7,3), (7,5), (1,6),(1,7),(2,8),(2,9)]
- 让我们首先实例化图表：
G = nx.Graph()
- 现在，让我们绘制图表：
G.add_nodes_from(vertices) G.add_edges_from(edges) pos=nx.spring_layout(G)
- 让我们定义 NF 节点：
nx.draw_networkx_nodes( G,pos, nodelist=[1,4,3,8,9], with_labels=True, node_color='g', node_size=1300)
- 现在，让我们创建已知涉及欺诈的节点：
nx.draw_networkx_nodes(G,pos, nodelist=[2,5,6,7], with_labels=True, node_color='r', node_size=1300)
- 让我们为节点创建标签：
nx.draw_networkx_edges(G,pos,edges,width=3,alpha=0.5,edge_color='b') labels={} labels[1]=r'1 NF' labels[2]=r'2 F' labels[3]=r'3 NF' labels[4]=r'4 NF' labels[5]=r'5 F' labels[6]=r'6 F' labels[7]=r'7 F' labels[8]=r'8 NF' labels[9]=r'9 NF' nx.draw_networkx_labels(G,pos,labels,font_size=16)
一旦前面的代码运行，它将显示出一个这样的图：
请注意，我们已经进行了详细的分析，将每个节点分类为图或非图。假设我们在网络中添加另一个名为q的顶点，如下图所示。我们对这个人没有先前的信息，也不知道这个人是否涉及欺诈。我们希望根据他们与社交网络中现有成员的联系来将这个人分类为NF或F：
我们已经设计了两种方法来对代表节点q的新人进行分类，分为F或NF：
- 使用一种不使用中心性指标和有关欺诈类型的附加信息的简单方法
- 使用了一个名为“瞭望塔”的方法，这是一种先进的技术，利用了现有节点的中心性指标，以及有关欺诈类型的其他信息
我们将详细讨论每种方法。
每个程序员都应该知道的 40 个算法（二）（2）https://developer.aliyun.com/article/1506336
