41. 网络#

!pip install quantecon-book-networks pandas-datareader
Hide code cell output 
Requirement already satisfied: quantecon-book-networks in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (1.1)
Requirement already satisfied: pandas-datareader in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (0.10.0)
Requirement already satisfied: numpy in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from quantecon-book-networks) (1.26.4)
Requirement already satisfied: scipy in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from quantecon-book-networks) (1.13.1)
Requirement already satisfied: pandas in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from quantecon-book-networks) (2.2.2)
Requirement already satisfied: matplotlib in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from quantecon-book-networks) (3.9.2)
Requirement already satisfied: networkx in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from quantecon-book-networks) (3.3)
Requirement already satisfied: quantecon in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from quantecon-book-networks) (0.7.2)
Requirement already satisfied: POT in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from quantecon-book-networks) (0.9.5)
Requirement already satisfied: lxml in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from pandas-datareader) (5.2.1)
Requirement already satisfied: requests>=2.19.0 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from pandas-datareader) (2.32.3)
Requirement already satisfied: python-dateutil>=2.8.2 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from pandas->quantecon-book-networks) (2.9.0.post0)
Requirement already satisfied: pytz>=2020.1 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from pandas->quantecon-book-networks) (2024.1)
Requirement already satisfied: tzdata>=2022.7 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from pandas->quantecon-book-networks) (2023.3)
Requirement already satisfied: charset-normalizer<4,>=2 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from requests>=2.19.0->pandas-datareader) (3.3.2)
Requirement already satisfied: idna<4,>=2.5 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from requests>=2.19.0->pandas-datareader) (3.7)
Requirement already satisfied: urllib3<3,>=1.21.1 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from requests>=2.19.0->pandas-datareader) (2.2.3)
Requirement already satisfied: certifi>=2017.4.17 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from requests>=2.19.0->pandas-datareader) (2024.8.30)
Requirement already satisfied: contourpy>=1.0.1 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from matplotlib->quantecon-book-networks) (1.2.0)
Requirement already satisfied: cycler>=0.10 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from matplotlib->quantecon-book-networks) (0.11.0)
Requirement already satisfied: fonttools>=4.22.0 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from matplotlib->quantecon-book-networks) (4.51.0)
Requirement already satisfied: kiwisolver>=1.3.1 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from matplotlib->quantecon-book-networks) (1.4.4)
Requirement already satisfied: packaging>=20.0 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from matplotlib->quantecon-book-networks) (24.1)
Requirement already satisfied: pillow>=8 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from matplotlib->quantecon-book-networks) (10.4.0)
Requirement already satisfied: pyparsing>=2.3.1 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from matplotlib->quantecon-book-networks) (3.1.2)

Requirement already satisfied: numba>=0.49.0 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from quantecon->quantecon-book-networks) (0.60.0)
Requirement already satisfied: sympy in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from quantecon->quantecon-book-networks) (1.13.2)
Requirement already satisfied: llvmlite<0.44,>=0.43.0dev0 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from numba>=0.49.0->quantecon->quantecon-book-networks) (0.43.0)
Requirement already satisfied: six>=1.5 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from python-dateutil>=2.8.2->pandas->quantecon-book-networks) (1.16.0)
Requirement already satisfied: mpmath<1.4,>=1.1.0 in /home/runner/miniconda3/envs/quantecon/lib/python3.12/site-packages (from sympy->quantecon->quantecon-book-networks) (1.3.0)

41.1. 概述#

近年来，一个被称为网络科学的领域迅速发展。 网络科学研究对象群体之间的关系。 一个重要的例子是万维网，其中网页通过超链接相互连接。 另一个例子是人脑：对大脑功能的研究强调神经细胞（神经元）之间的连接网络。 人工神经网络基于这一理念，利用数据在简单处理单元之间建立复杂的连接。 研究COVID-19等疾病传播的流行病学家分析人类宿主群体之间的相互作用。 在运筹学中，网络分析用于研究基本问题，如最小成本流、旅行商问题、最短路径和分配问题。 本讲座介绍了经济和金融网络。 本讲座的部分内容来自教材书《经济网络》，但本讲座的水平更为入门。 我们需要以下导入。

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
import pandas as pd
import quantecon as qe

import matplotlib.cm as cm
import quantecon_book_networks.input_output as qbn_io
import quantecon_book_networks.data as qbn_data

import matplotlib.patches as mpatches

41.2. 经济和金融网络#

在经济学中，网络的重要例子包括：

  • 金融网络

  • 生产网络

  • 贸易网络

  • 运输网络

  • 社交网络

社交网络影响市场情绪和消费者决策的趋势。 金融网络的结构有助于确定金融系统的相对脆弱性。 生产网络的结构影响贸易、创新和局部冲击的传播。 为了更好地理解这些网络，让我们深入看一些例子。

41.2.1. 例子：飞机出口#

下图显示了基于国际贸易数据SITC第2修订版的2019年大型商用飞机国际贸易情况。

Hide code cell source 
ch1_data = qbn_data.introduction()
export_figures = False

DG = ch1_data['aircraft_network']
pos = ch1_data['aircraft_network_pos']

centrality = nx.eigenvector_centrality(DG)
node_total_exports = qbn_io.node_total_exports(DG)
edge_weights = qbn_io.edge_weights(DG)

node_pos_dict = pos

node_sizes = qbn_io.normalise_weights(node_total_exports,10000)
edge_widths = qbn_io.normalise_weights(edge_weights,10)

node_colors = qbn_io.colorise_weights(list(centrality.values()),color_palette=cm.viridis)
node_to_color = dict(zip(DG.nodes,node_colors))
edge_colors = []
for src,_ in DG.edges:
    edge_colors.append(node_to_color[src])

fig, ax = plt.subplots(figsize=(10, 10))
ax.axis('off')

nx.draw_networkx_nodes(DG,
                       node_pos_dict,
                       node_color=node_colors,
                       node_size=node_sizes,
                       linewidths=2,
                       alpha=0.6,
                       ax=ax)

nx.draw_networkx_labels(DG,
                        node_pos_dict,
                        ax=ax)

nx.draw_networkx_edges(DG,
                       node_pos_dict,
                       edge_color=edge_colors,
                       width=edge_widths,
                       arrows=True,
                       arrowsize=20,
                       ax=ax,
                       arrowstyle='->',
                       node_size=node_sizes,
                       connectionstyle='arc3,rad=0.15')

plt.show()
_images/78b00b52ca0fbb1c676cde09decfbcd4e6dc04267c763b2fd21c4ef7fc80465a.png

Fig. 41.1 商用飞机网络#

图中的圆圈被称为节点或顶点 – 在这个例子中，它们代表国家。 图中的箭头被称为边或链接。 节点大小与总出口成正比，边的宽度与对目标国家的出口成正比。 （数据针对重量至少15,000公斤的商用飞机贸易，数据来源于CID Dataverse。） 图表显示美国、法国和德国是主要的出口枢纽。 在下面的讨论中，我们将学习如何量化这些概念。

41.2.2. 例子：马尔可夫链#

回想一下，在我们关于马尔可夫链的讲座中，我们研究了一个商业周期的动态模型，其中的状态包括：

  • “ng” = “正常增长”

  • “mr” = “轻度衰退”

  • “sr” = “严重衰退”

让我们来看看下面这个图表

_images/mc.png

这是一个网络的例子，其中节点集 \(V\) 等于状态集： $\( V = \{ \text{"ng", "mr", "sr"} \} \)$ 节点之间的边表示一个月的转移概率。

41.3. 图论简介#

现在我们已经看过一些例子，让我们转向理论部分。

这个理论将帮助我们更好地组织我们的思路。

网络科学的理论部分是使用数学的一个主要分支——图论构建的。

图论可能很复杂，我们只会涉及基础部分。

但是，这些概念已经足以让我们讨论有关经济和金融网络的有趣且重要的想法。

我们关注”有向”图，其中连接通常是不对称的（箭头通常只指向一个方向，而不是双向）。

例如，

  • 银行 \(A\) 向银行 \(B\) 贷款

  • 公司 \(A\) 向公司 \(B\) 供应商品

  • 个人 \(A\) 在特定社交网络上”关注”个人 \(B\) （”无向”图，即连接是对称的，是有向图的一种特殊情况——我们只需要坚持每个从 \(A\) 指向 \(B\) 的箭头都配对一个从 \(B\) 指向 \(A\) 的箭头。）

41.3.1. 关键定义#

一个有向图由两个部分组成：

  1. 一个有限集 \(V\) 和

  2. 一组元素为 \(V\) 中的元素的对 \((u, v)\)。

\(V\) 的元素被称为图的顶点或节点。

对 \((u,v)\) 被称为图的边，所有边的集合通常用 \(E\) 表示。

直观和视觉上，边 \((u,v)\) 被理解为从节点 \(u\) 到节点 \(v\) 的一个箭头。

（表示箭头的一个巧妙方法是记录箭头的尾部和头部的位置，这正是边所做的。）

在 Fig. 41.1 所示的飞机出口例子中

  • \(V\) 是数据集中包含的所有国家。

  • \(E\) 是图中的所有箭头，每个箭头表示从一个国家到另一个国家的某个正数量的飞机出口。

让我们看更多的例子。

下面显示了两个图，每个图都有三个节点。

_images/poverty_trap_1.png

Fig. 41.2 Poverty Trap#

现在，我们构造一个具有相同节点但具有不同边的图。

_images/poverty_trap_2.png

Fig. 41.3 贫困陷阱#

对于这些图，箭头（边）可以被视为表示给定时间单位内的正向转移概率。

通常，如果存在边 \((u, v)\)，则称节点 \(u\) 为 \(v\) 的直接前驱，\(v\) 为 \(u\) 的直接后继。

此外，对于 \(v \in V\)，

  • 入度是 \(i_d(v) = \) \(v\) 的直接前驱数，以及

  • 出度是 \(o_d(v) = \) \(v\) 的直接后继数。

41.3.2. Networkx中的有向图#

Python包 Networkx 为表示有向图提供了一个便捷的数据结构，并实现了许多用于分析它们的常见例程。

作为示例，让我们使用Networkx重新创建 Fig. 41.3。

为此，我们首先创建一个空的 DiGraph 对象：

G_p = nx.DiGraph()

接下来，我们用节点和边来填充它。

为此，我们列出所有边的列表，其中贫穷用p表示，以此类推：

edge_list = [('p', 'p'),
             ('m', 'p'), ('m', 'm'), ('m', 'r'),
             ('r', 'p'), ('r', 'm'), ('r', 'r')]

最后，我们将边添加到我们的 DiGraph 对象中：

for e in edge_list:
    u, v = e
    G_p.add_edge(u, v)

或者，我们可以使用 add_edges_from 方法。

G_p.add_edges_from(edge_list)

添加边会自动添加节点，所以 G_p 现在是我们图的正确表示。

我们可以通过使用以下代码通过Networkx绘制图来验证这一点：

fig, ax = plt.subplots()
nx.draw_spring(G_p, ax=ax, node_size=500, with_labels=True,
               font_weight='bold', arrows=True, alpha=0.8,
               connectionstyle='arc3,rad=0.25', arrowsize=20)
plt.show()
_images/0a8a5f4f21ead4e0a1a154188aa449cb2738b3668ec6109182d5a1f563762fd1.png

上面得到的图形与Fig. 41.3中的原始有向图相匹配。

DiGraph对象有计算节点入度和出度的方法。

例如，

G_p.in_degree('p')

3

41.3.3. 通信#

接下来，我们研究通信和连通性，这对经济网络有重要影响。

如果\(u=v\)或存在一系列从\(u\)到\(v\)的边，则称节点\(v\)从节点\(u\)可达。

  • 在这种情况下，我们写作\(u \to v\) （从视觉上看，有一系列箭头从\(u\)指向\(v\)。）

例如，假设我们有一个表示生产网络的有向图，其中

  • \(V\)的元素是工业部门

  • 边\((i, j)\)的存在意味着\(i\)向\(j\)供应产品或服务。

那么\(m \to \ell\)意味着部门\(m\)是部门\(\ell\)的上游供应商。

如果\(u \to v\)且\(v \to u\)，则称两个节点\(u\)和\(v\)相通。

如果所有节点都相通，则称图是强连通的。

例如，Fig. 41.2是强连通的， 然而在Fig. 41.3中，富人节点从穷人节点不可达，因此它不是强连通的。

我们可以通过首先使用Networkx构建图，然后使用nx.is_strongly_connected来验证这一点。

fig, ax = plt.subplots()
G1 = nx.DiGraph()

G1.add_edges_from([('p', 'p'),('p','m'),('p','r'),
             ('m', 'p'), ('m', 'm'), ('m', 'r'),
             ('r', 'p'), ('r', 'm'), ('r', 'r')])

nx.draw_networkx(G1, with_labels = True)
_images/e55b422662f968cdf7d1c13f60d94e259da6f8cef299ff558dc5273bdeedc084.png 
nx.is_strongly_connected(G1)    #检查上面的图是否强关联

True

fig, ax = plt.subplots()
G2 = nx.DiGraph()

G2.add_edges_from([('p', 'p'),
             ('m', 'p'), ('m', 'm'), ('m', 'r'),
             ('r', 'p'), ('r', 'm'), ('r', 'r')])

nx.draw_networkx(G2, with_labels = True)
_images/33a2d966033884ab9059c34b1710300ca9097e8cc013576929e51bcf03ae9f2f.png 
nx.is_strongly_connected(G2)    #检查上面的图是否强关联

False

41.4. 加权图#

我们现在介绍加权图，其中每条边都附有权重（数字）。

41.4.1. 按国家划分的国际私人信贷流动#

为了说明这个概念，请看下图，它展示了私人银行之间的资金流动（即贷款），按原始国家分组。

Hide code cell source 
Z = ch1_data["adjacency_matrix"]["Z"]
Z_visual= ch1_data["adjacency_matrix"]["Z_visual"]
countries = ch1_data["adjacency_matrix"]["countries"]

G = qbn_io.adjacency_matrix_to_graph(Z_visual, countries, tol=0.03)

centrality = qbn_io.eigenvector_centrality(Z_visual, authority=False)
node_total_exports = qbn_io.node_total_exports(G)
edge_weights = qbn_io.edge_weights(G)

node_pos_dict = nx.circular_layout(G)

node_sizes = qbn_io.normalise_weights(node_total_exports,3000)
edge_widths = qbn_io.normalise_weights(edge_weights,10)


node_colors = qbn_io.colorise_weights(centrality)
node_to_color = dict(zip(G.nodes,node_colors))
edge_colors = []
for src,_ in G.edges:
    edge_colors.append(node_to_color[src])

fig, ax = plt.subplots(figsize=(10, 10))
ax.axis('off')

nx.draw_networkx_nodes(G,
                       node_pos_dict,
                       node_color=node_colors,
                       node_size=node_sizes,
                       edgecolors='grey',
                       linewidths=2,
                       alpha=0.4,
                       ax=ax)

nx.draw_networkx_labels(G,
                        node_pos_dict,
                        font_size=12,
                        ax=ax)

nx.draw_networkx_edges(G,
                       node_pos_dict,
                       edge_color=edge_colors,
                       width=edge_widths,
                       arrows=True,
                       arrowsize=20,
                       alpha=0.8,
                       ax=ax,
                       arrowstyle='->',
                       node_size=node_sizes,
                       connectionstyle='arc3,rad=0.15')

plt.show()
_images/aec93beef883c2580a97eb8331f2a9dbebd0954b6bed94568d7c9262e7c117cb.png

Fig. 41.4 国际信贷网络#

国家代码在下表中给出

代码

国家

代码

国家

代码

国家

代码

国家

AU

澳大利亚

DE

德国

CL

智利

ES

西班牙

PT

葡萄牙

FR

法国

TR

土耳其

GB

英国

US

美国

IE

爱尔兰

AT

奥地利

IT

意大利

BE

比利时

JP

日本

SW

瑞士

SE

瑞典

从日本到美国的箭头表示日本银行对所有在美国注册的银行的总体债权，这些数据由国际清算银行（BIS）收集。

图中每个节点的大小与所有其他节点对该节点的外国债权总额成正比。

箭头的宽度与它们所代表的外国债权成正比。

请注意，在这个网络中，几乎对于每一对节点\(u\)和\(v\)都存在一条边\((u, v)\)（即网络中几乎每个国家之间都有联系）。

（事实上，还有更多的小箭头，为了清晰起见我们省略了。）

因此，仅仅一个节点到另一个节点边的存在与否并不特别有信息量。

为了理解这个网络，我们需要记录的不仅是信贷流动的存在或缺失，还要记录流动的规模。

记录这些信息的正确数据结构是”加权有向图”。

41.4.2. 定义#

加权有向图是一种有向图，我们为其添加了一个权重函数\(w\)，该函数为每条边分配一个正数。

上图显示了一个加权有向图，其中权重是资金流动的大小。

下图显示了一个加权有向图，箭头表示诱导有向图的边。

_images/weighted.png

Fig. 41.5 加权贫困陷阱#

边旁边的数字是权重。

在这个例子中，你可以把箭头上的数字看作是一个家庭在一年内的转移概率。

我们可以看到，一个富裕家庭在一年内有10%的机会变成贫困。

41.5. 邻接矩阵#

另一种表示权重的方法是通过矩阵，这种方法在数值计算中非常方便。

对于一个有节点集 \(\{v_1, \ldots, v_n\}\)、边集 \(E\) 和权重函数 \(w\) 的加权有向图，其邻接矩阵是一个矩阵

\[\begin{split} A = (a_{ij})_{1 \leq i,j \leq n} \quad \text{其中} \quad a_{ij} = % \begin{cases} w(v_i, v_j) & \text{如果} (v_i, v_j) \in E \\ 0 & \text{其他情况} \end{cases} % \end{split}\]

一旦 \(V\) 中的节点被列举出来，权重函数和邻接矩阵本质上提供相同的信息。

例如，将 \(\{\)贫困, 中产, 富裕\(\}\) 分别映射到 \(\{1, 2, 3\}\)， Fig. 41.5 中加权有向图对应的邻接矩阵是

\[\begin{split} \begin{pmatrix} 0.9 & 0.1 & 0 \\ 0.4 & 0.4 & 0.2 \\ 0.1 & 0.1 & 0.8 \end{pmatrix}. \end{split}\]

在 QuantEcon 的 DiGraph 实现中，权重通过关键字 weighted 记录：

A = ((0.9, 0.1, 0.0),
     (0.4, 0.4, 0.2),
     (0.1, 0.1, 0.8))
A = np.array(A)
G = qe.DiGraph(A, weighted=True)    # 储存权重

关于邻接矩阵的一个关键点是，对其进行转置操作会反转相关有向图中的所有箭头。

例如，以下有向图可以被解释为一个金融网络的简化版本，其中节点代表银行， 边表示资金流动。

G4 = nx.DiGraph()

G4.add_edges_from([('1','2'),
                   ('2','1'),('2','3'),
                   ('3','4'),
                   ('4','2'),('4','5'),
                   ('5','1'),('5','3'),('5','4')])
pos = nx.circular_layout(G4)

edge_labels={('1','2'): '100',
             ('2','1'): '50', ('2','3'): '200',
             ('3','4'): '100',
             ('4','2'): '500', ('4','5'): '50',
             ('5','1'): '150',('5','3'): '250', ('5','4'): '300'}

nx.draw_networkx(G4, pos, node_color = 'none',node_size = 500)
nx.draw_networkx_edge_labels(G4, pos, edge_labels=edge_labels)
nx.draw_networkx_nodes(G4, pos, linewidths= 0.5, edgecolors = 'black',
                       node_color = 'none',node_size = 500)

plt.show()
_images/6ac10e3d96569fa478b665772876447f27cceb3519ecbad0ec3d75da1f26b9d0.png

我们看到银行2向银行3发放了200的贷款。

对应的邻接矩阵是

\[\begin{split} A = \begin{pmatrix} 0 & 100 & 0 & 0 & 0 \\ 50 & 0 & 200 & 0 & 0 \\ 0 & 0 & 0 & 100 & 0 \\ 0 & 500 & 0 & 0 & 50 \\ 150 & 0 & 250 & 300 & 0 \end{pmatrix}. \end{split}\]

其转置是

\[\begin{split} A^\top = \begin{pmatrix} 0 & 50 & 0 & 0 & 150 \\ 100 & 0 & 0 & 500 & 0 \\ 0 & 200 & 0 & 0 & 250 \\ 0 & 0 & 100 & 0 & 300 \\ 0 & 0 & 0 & 50 & 0 \end{pmatrix}. \end{split}\]

相应的网络在下图中可视化，显示了贷款发放后的负债网络。

这两个网络（原始和转置）对于分析金融市场都很有用。

G5 = nx.DiGraph()

G5.add_edges_from([('1','2'),('1','5'),
                   ('2','1'),('2','4'),
                   ('3','2'),('3','5'),
                   ('4','3'),('4','5'),
                   ('5','4')])

edge_labels={('1','2'): '50', ('1','5'): '150',
             ('2','1'): '100', ('2','4'): '500',
             ('3','2'): '200', ('3','5'): '250',
             ('4','3'): '100', ('4','5'): '300',
             ('5','4'): '50'}

nx.draw_networkx(G5, pos, node_color = 'none',node_size = 500)
nx.draw_networkx_edge_labels(G5, pos, edge_labels=edge_labels)
nx.draw_networkx_nodes(G5, pos, linewidths= 0.5, edgecolors = 'black',
                       node_color = 'none',node_size = 500)

plt.show()
_images/5bbb209ce3e475bf471e0d846a188af18c041cd773a2d382a1fe0e4027c1efc4.png

一般来说，每个非负的 \(n \times n\) 矩阵 \(A = (a_{ij})\) 都可以被视为加权有向图的邻接矩阵。

要构建图，我们设 \(V = 1, \ldots, n\)，并将边集 \(E\) 取为所有满足 \(a_{ij} > 0\) 的 \((i,j)\)。

对于权重函数，我们对所有边 \((i,j)\) 设置 \(w(i, j) = a_{ij}\)。

我们称这个图为 \(A\) 诱导的加权有向图。

41.6. 性质#

考虑一个加权有向图，其邻接矩阵为 \(A\)。

令 \(a^k_{ij}\) 为 \(A^k\)（\(A\) 的 \(k\) 次方）中的第 \(i,j\) 个元素。

以下结果在许多应用中很有用：

Theorem 41.1

对于 \(V\) 中的不同节点 \(i, j\) 和任意整数 \(k\)，我们有 $\( a^k_{i j} > 0 \quad \text{当且仅当} \quad \text{\)j\( 可从 \)i\( 到达}。 \)$

当 \(k=1\) 时，上述结果是显而易见的，对于一般情况的证明可以在 [Sargent and Stachurski, 2022] 中找到。

现在回想特征值讲座中提到，一个非负矩阵 \(A\) 被称为不可约的，如果对于每个 \((i,j)\)，存在一个整数 \(k \geq 0\)，使得 \(a^{k}_{ij} > 0\)。

根据前面的定理，不难得出下一个结果（详见 [Sargent and Stachurski, 2022]）。

Theorem 41.2

对于一个加权有向图，以下陈述是等价的：

  1. 该有向图是强连通的。

  2. 该图的邻接矩阵是不可约的。

我们用一个简单的例子来说明上述定理。 考虑以下加权有向图。

_images/properties.png

我们首先将上述网络创建为 Networkx DiGraph 对象。

G6 = nx.DiGraph()

G6.add_edges_from([('1','2'),('1','3'),
                   ('2','1'),
                   ('3','1'),('3','2')])

然后我们构建相关的邻接矩阵A。

A = np.array([[0,0.7,0.3],    # 邻接矩阵A。
              [1,0,0],
              [0.4,0.6,0]])
Hide code cell source 
def is_irreducible(P):
    n = len(P)
    result = np.zeros((n, n))
    for i in range(n):
        result += np.linalg.matrix_power(P, i)
    return np.all(result > 0)

is_irreducible(A)      #检查A的不可约性

True

nx.is_strongly_connected(G6)      # 检查图的连接性

True

41.7. 网络中心性#

在研究各种网络时，一个反复出现的话题是不同节点的相对”中心性”或”重要性”。

例子包括：

  • 搜索引擎对网页的排名

  • 确定金融网络中最重要的银行（在金融危机时中央银行应该救助哪一家）

  • 确定经济中最重要的工业部门

在接下来的内容中，中心性度量将每个加权有向图与一个向量\(m\)关联起来，其中\(m_i\)被解释为节点\(v_i\)的中心性（或排名）。

41.7.1. 度中心性#

在给定的有向图中，衡量节点”重要性”的两个基本指标是其入度和出度。

这两者都提供了一种中心性度量。

入度中心性是一个包含图中每个节点入度的向量。

考虑以下简单例子。

G7 = nx.DiGraph()

G7.add_nodes_from(['1','2','3','4','5','6','7'])

G7.add_edges_from([('1','2'),('1','6'),
                   ('2','1'),('2','4'),
                   ('3','2'),
                   ('4','2'),
                   ('5','3'),('5','4'),
                   ('6','1'),
                   ('7','4'),('7','6')])
pos = nx.planar_layout(G7)

nx.draw_networkx(G7, pos, node_color='none', node_size=500)
nx.draw_networkx_nodes(G7, pos, linewidths=0.5, edgecolors='black',
                       node_color='none',node_size=500)

plt.show()
_images/9d32759530ed6631cf87aa247ce64144fa600c4b67a4a71915e3bf2fb6929278.png

Fig. 41.6 样本图#

以下代码显示了所有节点的入度中心性。

iG7 = [G7.in_degree(v) for v in G7.nodes()]   #计算入度中心性
for i, d in enumerate(iG7):
    print(i+1, d)

1 2
2 3
3 1
4 3
5 0
6 2
7 0

考虑Fig. 41.4中显示的国际信贷网络。

以下图表显示了每个国家的入度中心性。

D = qbn_io.build_unweighted_matrix(Z)
indegree = D.sum(axis=0)

def centrality_plot_data(countries, centrality_measures):
    df = pd.DataFrame({'code': countries,
                       'centrality':centrality_measures,
                       'color': qbn_io.colorise_weights(centrality_measures).tolist()
                       })
    return df.sort_values('centrality')

fig, ax = plt.subplots()

df = centrality_plot_data(countries, indegree)

ax.bar('code', 'centrality', data=df, color=df["color"], alpha=0.6)

patch = mpatches.Patch(color=None, label='in degree', visible=False)
ax.legend(handles=[patch], fontsize=12, loc="upper left", handlelength=0, frameon=False)

ax.set_ylim((0,20))

plt.show()
_images/9cc5bb46dcda0e1460670e4d504b1a09aa8cfbe717fe69bb1499f8dc3f0ab7a4.png

虽然入度和出度中心性计算简单，但它们并不总是有用。

在Fig. 41.4中，几乎每个节点之间 都存在边，所以基于入度或出度的中心性排名无法有效区分国家。

这在上图中也可以看到。

另一个例子是网络搜索引擎的任务，它在用户输入搜索时按相关性对页面进行排名。

假设网页A的入站链接是网页B的两倍。

入度中心性告诉我们页面A应该获得更高的排名。

但实际上，页面A可能不如页面B重要。

原因是，假设指向A的链接来自几乎没有流量的页面， 而指向B的链接来自流量非常大的页面。

在这种情况下，页面B可能会收到更多访问者，这反过来表明 页面B包含更有价值（或更有趣）的内容。

这一点告诉我们重要性可能是递归的。 这意味着给定节点的重要性取决于 链接到它的其他节点的重要性。

作为另一个例子，我们可以想象一个生产网络，其中一个 给定部门的重要性取决于它供应的部门的重要性。

这与前面的例子相反：现在给定节点的重要性 取决于它链接到的其他节点的重要性。

下面的中心性度量将具有这些递归特征。

41.8. 特征向量中心性#

假设我们有一个带有邻接矩阵\(A\)的加权有向图。

为简单起见，我们假设图的节点\(V\)就是 整数\(1, \ldots, n\)。 让\(r(A)\)表示\(A\)的谱半径。

图的特征向量中心性被定义为解决以下方程的\(n\)维向量\(e\)

(41.1)#\[ \begin{aligned} e = \frac{1}{r(A)} A e. \end{aligned} \]

换句话说，\(e\)是\(A\)的主特征向量（最大特征值的特征向量 — 请看特征值lecture中关于Perron-Frobenius定理的讨论。

为了更好地理解(41.1)，我们写出某个元素\(e_i\)的完整表达式

(41.2)#\[ \begin{aligned} e_i = \frac{1}{r(A)} \sum_{1 \leq j \leq n} a_{ij} e_j \end{aligned} \]

注意定义的递归性质：节点\(i\)获得的中心性 与所有节点中心性的加权和成正比，权重为 从\(i\)到这些节点的流量率。

如果节点\(i\)满足以下条件，则它的排名很高：

  1. 从\(i\)出发的边很多，

  2. 这些边的权重很大，以及

  3. 这些边指向其他排名很高的节点。

稍后，当我们研究生产网络中的需求冲击时，特征向量中心性将有 更具体的解释。

我们将看到，在生产网络中，具有高特征向量中心性的部门是重要的供应商。

特别是，一旦订单通过网络向后流动，它们就会被各种需求冲击激活。

要计算特征向量中心性，我们可以使用以下函数。

def eigenvector_centrality(A, k=40, authority=False):
    """
   计算矩阵A的主特征向量。假设A是本原矩阵，并使用幂法。

    """
    A_temp = A.T if authority else A
    n = len(A_temp)
    r = np.max(np.abs(np.linalg.eigvals(A_temp)))
    e = r**(-k) * (np.linalg.matrix_power(A_temp, k) @ np.ones(n))
    return e / np.sum(e)

让我们为Fig. 41.6中生成的图计算特征向量中心性。

A = nx.to_numpy_array(G7)         #计算图的邻接矩阵

e = eigenvector_centrality(A)
n = len(e)

for i in range(n):
    print(i+1,e[i])

1 0.18580570704268037
2 0.18580570704268037
3 0.11483424225608219
4 0.11483424225608219
5 0.14194292957319637
6 0.11483424225608219
7 0.14194292957319637

虽然节点 \(2\) 和 \(4\) 具有最高的入度中心性，但我们可以看到节点 \(1\) 和 \(2\) 具有最高的特征向量中心性。

让我们重新审视Fig. 41.4中的国际信贷网络。

eig_central = eigenvector_centrality(Z)

fig, ax = plt.subplots()

df = centrality_plot_data(countries, eig_central)

ax.bar('code', 'centrality', data=df, color=df["color"], alpha=0.6)

patch = mpatches.Patch(color=None, visible=False)
ax.legend(handles=[patch], fontsize=12, loc="upper left", handlelength=0, frameon=False)

plt.show()
_images/be96e3e6ec39439a480649f062980e4f60900876b21b4d4c286e3ac4c2d98362.png

Fig. 41.7 特征向量中心性#

根据这个排名评分较高的国家往往在信贷供应方面扮演重要角色。

日本在这项指标中排名最高，尽管像英国和法国这样拥有大型金融部门的国家也紧随其后。

特征向量中心性的优势在于它在衡量节点重要性的同时考虑了其邻居的重要性。

谷歌的PageRank算法的核心就是特征向量中心性的一个变体，用于对网页进行排名。

其主要原理是来自重要节点（以度中心性衡量）的链接比来自不重要节点的链接更有价值。

41.8.1. 卡茨中心性#

特征向量中心性的一个问题是\(r(A)\)可能为零，这种情况下\(1/r(A)\)是未定义的。

出于这个和其他原因，一些研究者更倾向于使用另一种称为卡茨中心性的网络中心性度量。

固定\(\beta\)在\((0, 1/r(A))\)区间内，带权有向图的卡茨中心性定义为解决以下方程的向量\(\kappa\)：

(41.3)#\[ \kappa_i = \beta \sum_{1 \leq j 1} a_{ij} \kappa_j + 1 \qquad \text{对所有 } i \in \{0, \ldots, n-1\}。 \]

这里\(\beta\)是我们可以选择的参数。

用向量形式我们可以写成：

(41.4)#\[ \kappa = \mathbf 1 + \beta A \kappa \]

其中\(\mathbf 1\)是一个全为1的列向量。

这种中心性度量背后的直觉与特征向量中心性提供的类似：当节点\(i\)被本身具有高中心性的节点链接时，它就会获得高中心性。

只要\(0 < \beta < 1/r(A)\)，卡茨中心性总是有限且定义明确的，因为这时\(r(\beta A) < 1\)。

这意味着方程(41.4)有唯一解：

\[ \kappa = (I - \beta A)^{-1} \mathbf{1} \]

这是由诺伊曼级数定理得出的。

参数\(\beta\)用于确保\(\kappa\)是有限的。

当\(r(A)<1\)时，我们使用\(\beta=1\)作为卡茨中心性计算的默认值。

41.8.2. 权威与枢纽#

搜索引擎设计者认识到网页可以通过两种不同的方式变得重要。

一些页面具有高枢纽中心性，意味着它们链接到有价值的信息来源（例如，新闻聚合网站）。

其他页面具有高权威中心性，意味着它们包含有价值的信息，这一点通过指向它们的链接的数量和重要性来体现（例如，受人尊敬的新闻机构的网站）。

类似的概念也已经应用于经济网络（通常使用不同的术语）。

我们之前讨论的特征向量中心性和Katz中心性衡量的是枢纽中心性。 （如果节点指向其他具有高中心性的节点，则它们具有高中心性。）

如果我们更关心权威中心性，我们可以使用相同的定义，只是取邻接矩阵的转置。

这之所以有效，是因为取转置会反转箭头的方向。

（现在，如果节点接收来自其他具有高中心性的节点的链接，它们将具有高中心性。）

例如，具有邻接矩阵\(A\)的加权有向图的基于权威的特征向量中心性是解决以下方程的向量\(e\)：

(41.5)#\[ e = \frac{1}{r(A)} A^\top e. \]

与原始定义的唯一区别是\(A\)被其转置替代。

（转置不影响矩阵的谱半径，所以我们写成\(r(A)\)而不是\(r(A^\top)\)。）

按元素逐个表示，这可以写成：

(41.6)#\[ e_j = \frac{1}{r(A)} \sum_{1 \leq i \leq n} a_{ij} e_i \]

我们可以看到，如果许多具有高权威排名的节点链接到\(j\)，则\(e_j\)将会很高。

下图显示了Fig. 41.4中所示的国际信贷网络的基于权威的特征向量中心性排名。

ecentral_authority = eigenvector_centrality(Z, authority=True)

fig, ax = plt.subplots()

df = centrality_plot_data(countries, ecentral_authority)

ax.bar('code', 'centrality', data=df, color=df["color"], alpha=0.6)

patch = mpatches.Patch(color=None, visible=False)
ax.legend(handles=[patch], fontsize=12, loc="upper left", handlelength=0, frameon=False)

plt.show()
_images/ebadf622946ac62e7b88604c357941763375847ea14ea941f618e9bae0bde1d7.png

Fig. 41.8 特征向量权威度#

排名靠前的国家是那些吸引大量信贷流入或从其他主要参与者获得信贷流入的国家。 在这种情况下，美国作为银行间信贷的目标显然主导了排名。

41.9. 进一步阅读#

我们将本讲座中讨论的观点应用于：

关于经济和社会网络的教科书包括 [Jackson, 2010]、 [Easley et al., 2010]、[Borgatti et al., 2018]、 [Sargent and Stachurski, 2022] 和 [Goyal, 2023]。

在网络科学领域，[Newman, 2018]、[Menczer et al., 2020] 和 [Coscia, 2021] 的著作都非常出色。

41.10. 练习#

Exercise 41.1

这是一个适合喜欢证明的人的数学练习。

设 \((V, E)\) 是一个有向图，若 \(u\) 和 \(v\) 互通，则记作 \(u \sim v\)。

证明 \(\sim\) 是 \(V\) 上的等价关系。

Exercise 41.2

考虑一个有向图 \(G\)，其节点集为 $\( V = \{0,1,2,3,4,5,6,7\} \)\( 边集为 \)\( E = \{(0, 1), (0, 3), (1, 0), (2, 4), (3, 2), (3, 4), (3, 7), (4, 3), (5, 4), (5, 6), (6, 3), (6, 5), (7, 0)\} \)$

  1. 使用 Networkx 绘制图 \(G\)。

  2. 找出 \(G\) 的相关邻接矩阵 \(A\)。

  3. 使用上面定义的函数计算 \(G\) 的入度中心性、出度中心性和特征向量中心性。

Exercise 41.3

考虑一个有 \(n\) 个节点和 \(n \times n\) 邻接矩阵 \(A\) 的图 \(G\)。

令 \(S = \sum_{k=0}^{n-1} A^k\) 我们可以说对于任意两个节点 \(i\) 和 \(j\)，当且仅当 \(S_{ij} > 0\) 时，\(j\) 可从 \(i\) 到达。

设计一个函数 is_accessible，用于检查给定图中的任意两个节点是否可达。

考虑 Exercise 41.2 中的图，并使用此函数检查

  1. 从 \(2\) 是否可以到达 \(1\)

  2. 从 \(3\) 是否可以到达 \(6\)