{
"cells": [
{
"cell_type": "markdown",
"id": "7499c539",
"metadata": {},
"source": [
"# Networks"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6615d3b4",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"!pip install quantecon-book-networks pandas-datareader"
]
},
{
"cell_type": "markdown",
"id": "5d7f8953",
"metadata": {},
"source": [
"## Outline\n",
"\n",
"In recent years there has been rapid growth in a field called [network science](https://en.wikipedia.org/wiki/Network_science).\n",
"\n",
"Network science studies relationships between groups of objects.\n",
"\n",
"One important example is the [world wide web](https://en.wikipedia.org/wiki/World_Wide_Web#Linking)\n",
", where web pages are connected by hyperlinks.\n",
"\n",
"Another is the [human brain](https://en.wikipedia.org/wiki/Neural_circuit): studies of brain function emphasize the network of\n",
"connections between nerve cells (neurons).\n",
"\n",
"[Artificial neural networks](https://en.wikipedia.org/wiki/Artificial_neural_network) are based on this idea, using data to build\n",
"intricate connections between simple processing units.\n",
"\n",
"Epidemiologists studying [transmission of diseases](https://en.wikipedia.org/wiki/Network_medicine#Network_epidemics)\n",
"like COVID-19 analyze interactions between groups of human hosts.\n",
"\n",
"In operations research, network analysis is used to study fundamental problems\n",
"as on minimum cost flow, the traveling salesman, [shortest paths](https://en.wikipedia.org/wiki/Shortest_path_problem),\n",
"and assignment.\n",
"\n",
"This lecture gives an introduction to economic and financial networks.\n",
"\n",
"Some parts of this lecture are drawn from the text\n",
"[https://networks.quantecon.org/](https://networks.quantecon.org/) but the level of this lecture is more\n",
"introductory.\n",
"\n",
"We will need the following imports."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ca15af05",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"import numpy as np\n",
"import networkx as nx\n",
"import matplotlib.pyplot as plt\n",
"import pandas as pd\n",
"import quantecon as qe\n",
"\n",
"import matplotlib.cm as cm\n",
"import quantecon_book_networks\n",
"import quantecon_book_networks.input_output as qbn_io\n",
"import quantecon_book_networks.data as qbn_data\n",
"\n",
"import matplotlib.patches as mpatches"
]
},
{
"cell_type": "markdown",
"id": "1462f639",
"metadata": {},
"source": [
"## Economic and financial networks\n",
"\n",
"Within economics, important examples of networks include\n",
"\n",
"- financial networks \n",
"- production networks \n",
"- trade networks \n",
"- transport networks and \n",
"- social networks \n",
"\n",
"\n",
"Social networks affect trends in market sentiment and consumer decisions.\n",
"\n",
"The structure of financial networks helps to determine relative fragility of the financial system.\n",
"\n",
"The structure of production networks affects trade, innovation and the propagation of local shocks.\n",
"\n",
"To better understand such networks, let’s look at some examples in more depth."
]
},
{
"cell_type": "markdown",
"id": "897d1fc4",
"metadata": {},
"source": [
"### Example: Aircraft Exports\n",
"\n",
"The following figure shows international trade in large commercial aircraft in 2019 based on International Trade Data SITC Revision 2."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2cb48b7f",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"ch1_data = qbn_data.introduction()\n",
"export_figures = False\n",
"\n",
"DG = ch1_data['aircraft_network']\n",
"pos = ch1_data['aircraft_network_pos']\n",
"\n",
"centrality = nx.eigenvector_centrality(DG)\n",
"node_total_exports = qbn_io.node_total_exports(DG)\n",
"edge_weights = qbn_io.edge_weights(DG)\n",
"\n",
"node_pos_dict = pos\n",
"\n",
"node_sizes = qbn_io.normalise_weights(node_total_exports,10000)\n",
"edge_widths = qbn_io.normalise_weights(edge_weights,10)\n",
"\n",
"node_colors = qbn_io.colorise_weights(list(centrality.values()),color_palette=cm.viridis)\n",
"node_to_color = dict(zip(DG.nodes,node_colors))\n",
"edge_colors = []\n",
"for src,_ in DG.edges:\n",
" edge_colors.append(node_to_color[src])\n",
"\n",
"fig, ax = plt.subplots(figsize=(10, 10))\n",
"ax.axis('off')\n",
"\n",
"nx.draw_networkx_nodes(DG,\n",
" node_pos_dict,\n",
" node_color=node_colors,\n",
" node_size=node_sizes,\n",
" linewidths=2,\n",
" alpha=0.6,\n",
" ax=ax)\n",
"\n",
"nx.draw_networkx_labels(DG,\n",
" node_pos_dict,\n",
" ax=ax)\n",
"\n",
"nx.draw_networkx_edges(DG,\n",
" node_pos_dict,\n",
" edge_color=edge_colors,\n",
" width=edge_widths,\n",
" arrows=True,\n",
" arrowsize=20,\n",
" ax=ax,\n",
" arrowstyle='->',\n",
" node_size=node_sizes,\n",
" connectionstyle='arc3,rad=0.15')\n",
"\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "6095b235",
"metadata": {},
"source": [
"The circles in the figure are called **nodes** or **vertices** – in this case they represent countries.\n",
"\n",
"The arrows in the figure are called **edges** or **links**.\n",
"\n",
"Node size is proportional to total exports and edge width is proportional to exports to the target country.\n",
"\n",
"(The data is for trade in commercial aircraft weighing at least 15,000kg and was sourced from CID Dataverse.)\n",
"\n",
"The figure shows that the US, France and Germany are major export hubs.\n",
"\n",
"In the discussion below, we learn to quantify such ideas."
]
},
{
"cell_type": "markdown",
"id": "d70c2c6a",
"metadata": {},
"source": [
"### Example: A Markov Chain\n",
"\n",
"Recall that, in our lecture on [Markov chains](https://intro.quantecon.org/markov_chains_I.html#mc-eg2) we studied a dynamic model of business cycles\n",
"where the states are\n",
"\n",
"- “ng” = “normal growth” \n",
"- “mr” = “mild recession” \n",
"- “sr” = “severe recession” \n",
"\n",
"\n",
"Let’s examine the following figure\n",
"\n",
"![https://intro.quantecon.org/_static/lecture_specific/networks/mc.png](https://intro.quantecon.org/_static/lecture_specific/networks/mc.png)\n",
"\n",
"This is an example of a network, where the set of nodes $ V $ equals the states:\n",
"\n",
"$$\n",
"V = \\{ \\text{\"ng\", \"mr\", \"sr\"} \\}\n",
"$$\n",
"\n",
"The edges between the nodes show the one month transition probabilities."
]
},
{
"cell_type": "markdown",
"id": "bc1271d8",
"metadata": {},
"source": [
"## An introduction to graph theory\n",
"\n",
"Now we’ve looked at some examples, let’s move on to theory.\n",
"\n",
"This theory will allow us to better organize our thoughts.\n",
"\n",
"The theoretical part of network science is constructed using a major branch of\n",
"mathematics called [graph theory](https://en.wikipedia.org/wiki/Graph_theory).\n",
"\n",
"Graph theory can be complicated and we will cover only the basics.\n",
"\n",
"However, these concepts will already be enough for us to discuss interesting and\n",
"important ideas on economic and financial networks.\n",
"\n",
"We focus on “directed” graphs, where connections are, in general, asymmetric\n",
"(arrows typically point one way, not both ways).\n",
"\n",
"E.g.,\n",
"\n",
"- bank $ A $ lends money to bank $ B $ \n",
"- firm $ A $ supplies goods to firm $ B $ \n",
"- individual $ A $ “follows” individual $ B $ on a given social network \n",
"\n",
"\n",
"(“Undirected” graphs, where connections are symmetric, are a special\n",
"case of directed graphs — we just need to insist that each arrow pointing\n",
"from $ A $ to $ B $ is paired with another arrow pointing from $ B $ to $ A $.)"
]
},
{
"cell_type": "markdown",
"id": "c2c364b0",
"metadata": {},
"source": [
"### Key definitions\n",
"\n",
"A **directed graph** consists of two things:\n",
"\n",
"1. a finite set $ V $ and \n",
"1. a collection of pairs $ (u, v) $ where $ u $ and $ v $ are elements of $ V $. \n",
"\n",
"\n",
"The elements of $ V $ are called the **vertices** or **nodes** of the graph.\n",
"\n",
"The pairs $ (u,v) $ are called the **edges** of the graph and the set of all edges will usually be denoted by $ E $\n",
"\n",
"Intuitively and visually, an edge $ (u,v) $ is understood as an arrow from node $ u $ to node $ v $.\n",
"\n",
"(A neat way to represent an arrow is to record the location of the tail and\n",
"head of the arrow, and that’s exactly what an edge does.)\n",
"\n",
"In the aircraft export example shown in Fig. 33.1\n",
"\n",
"- $ V $ is all countries included in the data set. \n",
"- $ E $ is all the arrows in the figure, each indicating some positive amount of aircraft exports from one country to another. \n",
"\n",
"\n",
"Let’s look at more examples.\n",
"\n",
"Two graphs are shown below, each with three nodes.\n",
"\n",
"![https://intro.quantecon.org/_static/lecture_specific/networks/poverty_trap_1.png](https://intro.quantecon.org/_static/lecture_specific/networks/poverty_trap_1.png)\n",
"\n",
"Poverty Trap \n",
"We now construct a graph with the same nodes but different edges.\n",
"\n",
"![https://intro.quantecon.org/_static/lecture_specific/networks/poverty_trap_2.png](https://intro.quantecon.org/_static/lecture_specific/networks/poverty_trap_2.png)\n",
"\n",
"Poverty Trap \n",
"For these graphs, the arrows (edges) can be thought of as representing\n",
"positive transition probabilities over a given unit of time.\n",
"\n",
"In general, if an edge $ (u, v) $ exists, then the node $ u $ is called a\n",
"**direct predecessor** of $ v $ and $ v $ is called a **direct successor** of $ u $.\n",
"\n",
"Also, for $ v \\in V $,\n",
"\n",
"- the **in-degree** is $ i_d(v) = $ the number of direct predecessors of $ v $ and \n",
"- the **out-degree** is $ o_d(v) = $ the number of direct successors of $ v $. "
]
},
{
"cell_type": "markdown",
"id": "ad053ba6",
"metadata": {},
"source": [
"### Digraphs in Networkx\n",
"\n",
"The Python package [Networkx](https://networkx.org/) provides a convenient\n",
"data structure for representing directed graphs and implements many common\n",
"routines for analyzing them.\n",
"\n",
"As an example, let us recreate Fig. 33.3 using Networkx.\n",
"\n",
"To do so, we first create an empty `DiGraph` object:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "afd29524",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"G_p = nx.DiGraph()"
]
},
{
"cell_type": "markdown",
"id": "2a8bfe68",
"metadata": {},
"source": [
"Next we populate it with nodes and edges.\n",
"\n",
"To do this we write down a list of\n",
"all edges, with *poor* represented by *p* and so on:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6629b4b6",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"edge_list = [('p', 'p'),\n",
" ('m', 'p'), ('m', 'm'), ('m', 'r'),\n",
" ('r', 'p'), ('r', 'm'), ('r', 'r')]"
]
},
{
"cell_type": "markdown",
"id": "8dbf43b0",
"metadata": {},
"source": [
"Finally, we add the edges to our `DiGraph` object:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "eadebbed",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"for e in edge_list:\n",
" u, v = e\n",
" G_p.add_edge(u, v)"
]
},
{
"cell_type": "markdown",
"id": "83608ede",
"metadata": {},
"source": [
"Alternatively, we can use the method `add_edges_from`."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "20b22507",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"G_p.add_edges_from(edge_list)"
]
},
{
"cell_type": "markdown",
"id": "801e67be",
"metadata": {},
"source": [
"Adding the edges automatically adds the nodes, so `G_p` is now a\n",
"correct representation of our graph.\n",
"\n",
"We can verify this by plotting the graph via Networkx with the following code:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3d212e10",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"nx.draw_spring(G_p, ax=ax, node_size=500, with_labels=True,\n",
" font_weight='bold', arrows=True, alpha=0.8,\n",
" connectionstyle='arc3,rad=0.25', arrowsize=20)\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "83c75f14",
"metadata": {},
"source": [
"The figure obtained above matches the original directed graph in Fig. 33.3.\n",
"\n",
"`DiGraph` objects have methods that calculate in-degree and out-degree\n",
"of nodes.\n",
"\n",
"For example,"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "745de466",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"G_p.in_degree('p')"
]
},
{
"cell_type": "markdown",
"id": "b6556c4f",
"metadata": {},
"source": [
"\n",
""
]
},
{
"cell_type": "markdown",
"id": "0f18977b",
"metadata": {},
"source": [
"### Communication\n",
"\n",
"Next, we study communication and connectedness, which have important\n",
"implications for economic networks.\n",
"\n",
"Node $ v $ is called **accessible** from node $ u $ if either $ u=v $ or there\n",
"exists a sequence of edges that lead from $ u $ to $ v $.\n",
"\n",
"- in this case, we write $ u \\to v $ \n",
"\n",
"\n",
"(Visually, there is a sequence of arrows leading from $ u $ to $ v $.)\n",
"\n",
"For example, suppose we have a directed graph representing a production network, where\n",
"\n",
"- elements of $ V $ are industrial sectors and \n",
"- existence of an edge $ (i, j) $ means that $ i $ supplies products or services to $ j $. \n",
"\n",
"\n",
"Then $ m \\to \\ell $ means that sector $ m $ is an upstream supplier of sector $ \\ell $.\n",
"\n",
"Two nodes $ u $ and $ v $ are said to **communicate** if both $ u \\to v $ and $ v \\to u $.\n",
"\n",
"A graph is called **strongly connected** if all nodes communicate.\n",
"\n",
"For example, Fig. 33.2 is strongly connected\n",
"however in Fig. 33.3 rich is not accessible from poor, thus it is not strongly connected.\n",
"\n",
"We can verify this by first constructing the graphs using Networkx and then using `nx.is_strongly_connected`."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d3de55ec",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"G1 = nx.DiGraph()\n",
"\n",
"G1.add_edges_from([('p', 'p'),('p','m'),('p','r'),\n",
" ('m', 'p'), ('m', 'm'), ('m', 'r'),\n",
" ('r', 'p'), ('r', 'm'), ('r', 'r')])\n",
"\n",
"nx.draw_networkx(G1, with_labels = True)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6d719a08",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"nx.is_strongly_connected(G1) #checking if above graph is strongly connected"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "68d68d3b",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"G2 = nx.DiGraph()\n",
"\n",
"G2.add_edges_from([('p', 'p'),\n",
" ('m', 'p'), ('m', 'm'), ('m', 'r'),\n",
" ('r', 'p'), ('r', 'm'), ('r', 'r')])\n",
"\n",
"nx.draw_networkx(G2, with_labels = True)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c4fe54a8",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"nx.is_strongly_connected(G2) #checking if above graph is strongly connected"
]
},
{
"cell_type": "markdown",
"id": "b5eb83e1",
"metadata": {},
"source": [
"## Weighted graphs\n",
"\n",
"We now introduce weighted graphs, where weights (numbers) are attached to each\n",
"edge."
]
},
{
"cell_type": "markdown",
"id": "490d2031",
"metadata": {},
"source": [
"### International private credit flows by country\n",
"\n",
"To motivate the idea, consider the following figure which shows flows of funds (i.e.,\n",
"loans) between private banks, grouped by country of origin."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ebfa6b4d",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"Z = ch1_data[\"adjacency_matrix\"][\"Z\"]\n",
"Z_visual= ch1_data[\"adjacency_matrix\"][\"Z_visual\"]\n",
"countries = ch1_data[\"adjacency_matrix\"][\"countries\"]\n",
"\n",
"G = qbn_io.adjacency_matrix_to_graph(Z_visual, countries, tol=0.03)\n",
"\n",
"centrality = qbn_io.eigenvector_centrality(Z_visual, authority=False)\n",
"node_total_exports = qbn_io.node_total_exports(G)\n",
"edge_weights = qbn_io.edge_weights(G)\n",
"\n",
"node_pos_dict = nx.circular_layout(G)\n",
"\n",
"node_sizes = qbn_io.normalise_weights(node_total_exports,3000)\n",
"edge_widths = qbn_io.normalise_weights(edge_weights,10)\n",
"\n",
"\n",
"node_colors = qbn_io.colorise_weights(centrality)\n",
"node_to_color = dict(zip(G.nodes,node_colors))\n",
"edge_colors = []\n",
"for src,_ in G.edges:\n",
" edge_colors.append(node_to_color[src])\n",
"\n",
"fig, ax = plt.subplots(figsize=(10, 10))\n",
"ax.axis('off')\n",
"\n",
"nx.draw_networkx_nodes(G,\n",
" node_pos_dict,\n",
" node_color=node_colors,\n",
" node_size=node_sizes,\n",
" edgecolors='grey',\n",
" linewidths=2,\n",
" alpha=0.4,\n",
" ax=ax)\n",
"\n",
"nx.draw_networkx_labels(G,\n",
" node_pos_dict,\n",
" font_size=12,\n",
" ax=ax)\n",
"\n",
"nx.draw_networkx_edges(G,\n",
" node_pos_dict,\n",
" edge_color=edge_colors,\n",
" width=edge_widths,\n",
" arrows=True,\n",
" arrowsize=20,\n",
" alpha=0.8,\n",
" ax=ax,\n",
" arrowstyle='->',\n",
" node_size=node_sizes,\n",
" connectionstyle='arc3,rad=0.15')\n",
"\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "1290f339",
"metadata": {},
"source": [
"The country codes are given in the following table\n",
"\n",
"|Code|Country|Code|Country|Code|Country|Code|Country|\n",
"|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|\n",
"|AU|Australia|DE|Germany|CL|Chile|ES|Spain|\n",
"|PT|Portugal|FR|France|TR|Turkey|GB|United Kingdom|\n",
"|US|United States|IE|Ireland|AT|Austria|IT|Italy|\n",
"|BE|Belgium|JP|Japan|SW|Switzerland|SE|Sweden|\n",
"An arrow from Japan to the US indicates aggregate claims held by Japanese\n",
"banks on all US-registered banks, as collected by the Bank of International\n",
"Settlements (BIS).\n",
"\n",
"The size of each node in the figure is increasing in the\n",
"total foreign claims of all other nodes on this node.\n",
"\n",
"The widths of the arrows are proportional to the foreign claims they represent.\n",
"\n",
"Notice that, in this network, an edge $ (u, v) $ exists for almost every choice\n",
"of $ u $ and $ v $ (i.e., almost every country in the network).\n",
"\n",
"(In fact, there are even more small arrows, which we have dropped for clarity.)\n",
"\n",
"Hence the existence of an edge from one node to another is not particularly informative.\n",
"\n",
"To understand the network, we need to record not just the existence or absence\n",
"of a credit flow, but also the size of the flow.\n",
"\n",
"The correct data structure for recording this information is a “weighted\n",
"directed graph”."
]
},
{
"cell_type": "markdown",
"id": "82a5a752",
"metadata": {},
"source": [
"### Definitions\n",
"\n",
"A **weighted directed graph** is a directed graph to which we have added a\n",
"**weight function** $ w $ that assigns a positive number to each edge.\n",
"\n",
"The figure above shows one weighted directed graph, where the weights are the size of fund flows.\n",
"\n",
"The following figure shows a weighted directed graph, with arrows\n",
"representing edges of the induced directed graph.\n",
"\n",
"![https://intro.quantecon.org/_static/lecture_specific/networks/weighted.png](https://intro.quantecon.org/_static/lecture_specific/networks/weighted.png)\n",
"\n",
"Weighted Poverty Trap \n",
"The numbers next to the edges are the weights.\n",
"\n",
"In this case, you can think of the numbers on the arrows as transition\n",
"probabilities for a household over, say, one year.\n",
"\n",
"We see that a rich household has a 10% chance of becoming poor in one year."
]
},
{
"cell_type": "markdown",
"id": "0c6b69b4",
"metadata": {},
"source": [
"## Adjacency matrices\n",
"\n",
"Another way that we can represent weights, which turns out to be very\n",
"convenient for numerical work, is via a matrix.\n",
"\n",
"The **adjacency matrix** of a weighted directed graph with nodes $ \\{v_1, \\ldots, v_n\\} $, edges $ E $ and weight function $ w $ is the matrix\n",
"\n",
"$$\n",
"A = (a_{ij})_{1 \\leq i,j \\leq n}\n",
"\\quad \\text{with} \\quad\n",
"a_{ij} =\n",
"%\n",
"\\begin{cases}\n",
" w(v_i, v_j) & \\text{ if } (v_i, v_j) \\in E\n",
" \\\\\n",
" 0 & \\text{ otherwise}.\n",
"\\end{cases}\n",
"%\n",
"$$\n",
"\n",
"Once the nodes in $ V $ are enumerated, the weight function and\n",
"adjacency matrix provide essentially the same information.\n",
"\n",
"For example, with $ \\{ $poor, middle, rich$ \\} $ mapped to $ \\{1, 2, 3\\} $ respectively,\n",
"the adjacency matrix corresponding to the weighted directed graph in Fig. 33.5 is\n",
"\n",
"$$\n",
"\\begin{pmatrix}\n",
" 0.9 & 0.1 & 0 \\\\\n",
" 0.4 & 0.4 & 0.2 \\\\\n",
" 0.1 & 0.1 & 0.8\n",
"\\end{pmatrix}.\n",
"$$\n",
"\n",
"In QuantEcon’s `DiGraph` implementation, weights are recorded via the\n",
"keyword `weighted`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5740a1a7",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"A = ((0.9, 0.1, 0.0),\n",
" (0.4, 0.4, 0.2),\n",
" (0.1, 0.1, 0.8))\n",
"A = np.array(A)\n",
"G = qe.DiGraph(A, weighted=True) # store weights"
]
},
{
"cell_type": "markdown",
"id": "9032094b",
"metadata": {},
"source": [
"One of the key points to remember about adjacency matrices is that taking the\n",
"transpose *reverses all the arrows* in the associated directed graph.\n",
"\n",
"For example, the following directed graph can be\n",
"interpreted as a stylized version of a financial network, with nodes as banks\n",
"and edges showing the flow of funds."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "714199bf",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"G4 = nx.DiGraph()\n",
"\n",
"G4.add_edges_from([('1','2'),\n",
" ('2','1'),('2','3'),\n",
" ('3','4'),\n",
" ('4','2'),('4','5'),\n",
" ('5','1'),('5','3'),('5','4')])\n",
"pos = nx.circular_layout(G4)\n",
"\n",
"edge_labels={('1','2'): '100',\n",
" ('2','1'): '50', ('2','3'): '200',\n",
" ('3','4'): '100',\n",
" ('4','2'): '500', ('4','5'): '50',\n",
" ('5','1'): '150',('5','3'): '250', ('5','4'): '300'}\n",
"\n",
"nx.draw_networkx(G4, pos, node_color = 'none',node_size = 500)\n",
"nx.draw_networkx_edge_labels(G4, pos, edge_labels=edge_labels)\n",
"nx.draw_networkx_nodes(G4, pos, linewidths= 0.5, edgecolors = 'black',\n",
" node_color = 'none',node_size = 500)\n",
"\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "54cf63d0",
"metadata": {},
"source": [
"We see that bank 2 extends a loan of size 200 to bank 3.\n",
"\n",
"The corresponding adjacency matrix is\n",
"\n",
"$$\n",
"A =\n",
"\\begin{pmatrix}\n",
" 0 & 100 & 0 & 0 & 0 \\\\\n",
" 50 & 0 & 200 & 0 & 0 \\\\\n",
" 0 & 0 & 0 & 100 & 0 \\\\\n",
" 0 & 500 & 0 & 0 & 50 \\\\\n",
" 150 & 0 & 250 & 300 & 0\n",
"\\end{pmatrix}.\n",
"$$\n",
"\n",
"The transpose is\n",
"\n",
"$$\n",
"A^\\top =\n",
"\\begin{pmatrix}\n",
" 0 & 50 & 0 & 0 & 150 \\\\\n",
" 100 & 0 & 0 & 500 & 0 \\\\\n",
" 0 & 200 & 0 & 0 & 250 \\\\\n",
" 0 & 0 & 100 & 0 & 300 \\\\\n",
" 0 & 0 & 0 & 50 & 0\n",
"\\end{pmatrix}.\n",
"$$\n",
"\n",
"The corresponding network is visualized in the following figure which shows the network of liabilities after the loans have been granted.\n",
"\n",
"Both of these networks (original and transpose) are useful for analyzing financial markets."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c6bb34bc",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"G5 = nx.DiGraph()\n",
"\n",
"G5.add_edges_from([('1','2'),('1','5'),\n",
" ('2','1'),('2','4'),\n",
" ('3','2'),('3','5'),\n",
" ('4','3'),('4','5'),\n",
" ('5','4')])\n",
"\n",
"edge_labels={('1','2'): '50', ('1','5'): '150',\n",
" ('2','1'): '100', ('2','4'): '500',\n",
" ('3','2'): '200', ('3','5'): '250',\n",
" ('4','3'): '100', ('4','5'): '300',\n",
" ('5','4'): '50'}\n",
"\n",
"nx.draw_networkx(G5, pos, node_color = 'none',node_size = 500)\n",
"nx.draw_networkx_edge_labels(G5, pos, edge_labels=edge_labels)\n",
"nx.draw_networkx_nodes(G5, pos, linewidths= 0.5, edgecolors = 'black',\n",
" node_color = 'none',node_size = 500)\n",
"\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "a44b5f20",
"metadata": {},
"source": [
"In general, every nonnegative $ n \\times n $ matrix $ A = (a_{ij}) $ can be\n",
"viewed as the adjacency matrix of a weighted directed graph.\n",
"\n",
"To build the graph we set $ V = 1, \\ldots, n $ and take the edge set $ E $ to be\n",
"all $ (i,j) $ such that $ a_{ij} > 0 $.\n",
"\n",
"For the weight function we set $ w(i, j) = a_{ij} $ for all edges $ (i,j) $.\n",
"\n",
"We call this graph the weighted directed graph induced by $ A $."
]
},
{
"cell_type": "markdown",
"id": "ce8bfb0a",
"metadata": {},
"source": [
"## Properties\n",
"\n",
"Consider a weighted directed graph with adjacency matrix $ A $.\n",
"\n",
"Let $ a^k_{ij} $ be element $ i,j $ of $ A^k $, the $ k $-th power of $ A $.\n",
"\n",
"The following result is useful in many applications:"
]
},
{
"cell_type": "markdown",
"id": "08680a39",
"metadata": {},
"source": [
"## \n",
"\n",
"For distinct nodes $ i, j $ in $ V $ and any integer $ k $, we have\n",
"\n",
"$$\n",
"a^k_{i j} > 0\n",
"\\quad \\text{if and only if} \\quad\n",
"\\text{ \\$j\\$ is accessible from \\$i\\$}.\n",
"$$\n",
"\n",
"The above result is obvious when $ k=1 $ and a proof of the general case can be\n",
"found in [[SS22](https://intro.quantecon.org/zreferences.html#id276)].\n",
"\n",
"Now recall from the eigenvalues lecture that a\n",
"nonnegative matrix $ A $ is called [irreducible](https://intro.quantecon.org/eigen_II.html#irreducible) if for each $ (i,j) $ there is an integer $ k \\geq 0 $ such that $ a^{k}_{ij} > 0 $.\n",
"\n",
"From the preceding theorem, it is not too difficult (see\n",
"[[SS22](https://intro.quantecon.org/zreferences.html#id276)] for details) to get the next result."
]
},
{
"cell_type": "markdown",
"id": "36bd2fca",
"metadata": {},
"source": [
"## \n",
"\n",
"For a weighted directed graph the following statements are equivalent:\n",
"\n",
"1. The directed graph is strongly connected. \n",
"1. The adjacency matrix of the graph is irreducible. \n",
"\n",
"\n",
"We illustrate the above theorem with a simple example.\n",
"\n",
"Consider the following weighted directed graph.\n",
"\n",
"![https://intro.quantecon.org/_static/lecture_specific/networks/properties.png](https://intro.quantecon.org/_static/lecture_specific/networks/properties.png)\n",
"\n",
"We first create the above network as a Networkx `DiGraph` object."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "068f9b6f",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"G6 = nx.DiGraph()\n",
"\n",
"G6.add_edges_from([('1','2'),('1','3'),\n",
" ('2','1'),\n",
" ('3','1'),('3','2')])"
]
},
{
"cell_type": "markdown",
"id": "662c38dd",
"metadata": {},
"source": [
"Then we construct the associated adjacency matrix A."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3ed54735",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"A = np.array([[0,0.7,0.3], # adjacency matrix A\n",
" [1,0,0],\n",
" [0.4,0.6,0]])"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "18d8d0ad",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"def is_irreducible(P):\n",
" n = len(P)\n",
" result = np.zeros((n, n))\n",
" for i in range(n):\n",
" result += np.linalg.matrix_power(P, i)\n",
" return np.all(result > 0)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "52861277",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"is_irreducible(A) # check irreducibility of A"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "249ec114",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"nx.is_strongly_connected(G6) # check connectedness of graph"
]
},
{
"cell_type": "markdown",
"id": "704a92c7",
"metadata": {},
"source": [
"## Network centrality\n",
"\n",
"When studying networks of all varieties, a recurring topic is the relative\n",
"“centrality” or “importance” of different nodes.\n",
"\n",
"Examples include\n",
"\n",
"- ranking of web pages by search engines \n",
"- determining the most important bank in a financial network (which one a\n",
" central bank should rescue if there is a financial crisis) \n",
"- determining the most important industrial sector in an economy. \n",
"\n",
"\n",
"In what follows, a **centrality measure** associates to each weighted directed\n",
"graph a vector $ m $ where the $ m_i $ is interpreted as the centrality (or rank)\n",
"of node $ v_i $."
]
},
{
"cell_type": "markdown",
"id": "46156acb",
"metadata": {},
"source": [
"### Degree centrality\n",
"\n",
"Two elementary measures of “importance” of a node in a given directed\n",
"graph are its in-degree and out-degree.\n",
"\n",
"Both of these provide a centrality measure.\n",
"\n",
"In-degree centrality is a vector containing the in-degree of each node in\n",
"the graph.\n",
"\n",
"Consider the following simple example."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "871d1544",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"G7 = nx.DiGraph()\n",
"\n",
"G7.add_nodes_from(['1','2','3','4','5','6','7'])\n",
"\n",
"G7.add_edges_from([('1','2'),('1','6'),\n",
" ('2','1'),('2','4'),\n",
" ('3','2'),\n",
" ('4','2'),\n",
" ('5','3'),('5','4'),\n",
" ('6','1'),\n",
" ('7','4'),('7','6')])\n",
"pos = nx.planar_layout(G7)\n",
"\n",
"nx.draw_networkx(G7, pos, node_color='none', node_size=500)\n",
"nx.draw_networkx_nodes(G7, pos, linewidths=0.5, edgecolors='black',\n",
" node_color='none',node_size=500)\n",
"\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "9f259e5f",
"metadata": {},
"source": [
"The following code displays the in-degree centrality of all nodes."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e56c357d",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"iG7 = [G7.in_degree(v) for v in G7.nodes()] # computing in-degree centrality\n",
"\n",
"for i, d in enumerate(iG7):\n",
" print(i+1, d)"
]
},
{
"cell_type": "markdown",
"id": "4776124f",
"metadata": {},
"source": [
"Consider the international credit network displayed in Fig. 33.4.\n",
"\n",
"The following plot displays the in-degree centrality of each country."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "82e26da2",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"D = qbn_io.build_unweighted_matrix(Z)\n",
"indegree = D.sum(axis=0)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "01a144d5",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"def centrality_plot_data(countries, centrality_measures):\n",
" df = pd.DataFrame({'code': countries,\n",
" 'centrality':centrality_measures,\n",
" 'color': qbn_io.colorise_weights(centrality_measures).tolist()\n",
" })\n",
" return df.sort_values('centrality')"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f9815b71",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"\n",
"df = centrality_plot_data(countries, indegree)\n",
"\n",
"ax.bar('code', 'centrality', data=df, color=df[\"color\"], alpha=0.6)\n",
"\n",
"patch = mpatches.Patch(color=None, label='in degree', visible=False)\n",
"ax.legend(handles=[patch], fontsize=12, loc=\"upper left\", handlelength=0, frameon=False)\n",
"\n",
"ax.set_ylim((0,20))\n",
"\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "23922e71",
"metadata": {},
"source": [
"Unfortunately, while in-degree and out-degree centrality are simple to\n",
"calculate, they are not always informative.\n",
"\n",
"In Fig. 33.4, an edge exists between almost every node,\n",
"so the in- or out-degree based centrality ranking fails to effectively separate the countries.\n",
"\n",
"This can be seen in the above graph as well.\n",
"\n",
"Another example is the task of a web search engine, which ranks pages\n",
"by relevance whenever a user enters a search.\n",
"\n",
"Suppose web page A has twice as many inbound links as page B.\n",
"\n",
"In-degree centrality tells us that page A deserves a higher rank.\n",
"\n",
"But in fact, page A might be less important than page B.\n",
"\n",
"To see why, suppose that the links to A are from pages that receive almost no traffic,\n",
"while the links to B are from pages that receive very heavy traffic.\n",
"\n",
"In this case, page B probably receives more visitors, which in turn suggests\n",
"that page B contains more valuable (or entertaining) content.\n",
"\n",
"Thinking about this point suggests that importance might be *recursive*.\n",
"\n",
"This means that the importance of a given node depends on the importance of\n",
"other nodes that link to it.\n",
"\n",
"As another example, we can imagine a production network where the importance of a\n",
"given sector depends on the importance of the sectors that it supplies.\n",
"\n",
"This reverses the order of the previous example: now the importance of a given\n",
"node depends on the importance of other nodes that *it links to*.\n",
"\n",
"The next centrality measures will have these recursive features."
]
},
{
"cell_type": "markdown",
"id": "78f88088",
"metadata": {},
"source": [
"### Eigenvector centrality\n",
"\n",
"Suppose we have a weighted directed graph with adjacency matrix $ A $.\n",
"\n",
"For simplicity, we will suppose that the nodes $ V $ of the graph are just the\n",
"integers $ 1, \\ldots, n $.\n",
"\n",
"Let $ r(A) $ denote the [spectral radius](https://intro.quantecon.org/eigen_I.html#neumann-series-lemma) of $ A $.\n",
"\n",
"The **eigenvector centrality** of the graph is defined as the $ n $-vector $ e $ that solves\n",
"\n",
"\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" e = \\frac{1}{r(A)} A e.\n",
"\\end{aligned} \\tag{33.1}\n",
"$$\n",
"\n",
"In other words, $ e $ is the dominant eigenvector of $ A $ (the eigenvector of the\n",
"largest eigenvalue — see the discussion of the [Perron-Frobenius theorem](https://intro.quantecon.org/eigen_II.html#perron-frobe) in the eigenvalue lecture.\n",
"\n",
"To better understand [(33.1)](#equation-ev-central), we write out the full expression\n",
"for some element $ e_i $\n",
"\n",
"\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" e_i = \\frac{1}{r(A)} \\sum_{1 \\leq j \\leq n} a_{ij} e_j\n",
"\\end{aligned} \\tag{33.2}\n",
"$$\n",
"\n",
"Note the recursive nature of the definition: the centrality obtained by node\n",
"$ i $ is proportional to a sum of the centrality of all nodes, weighted by\n",
"the *rates of flow* from $ i $ into these nodes.\n",
"\n",
"A node $ i $ is highly ranked if\n",
"\n",
"1. there are many edges leaving $ i $, \n",
"1. these edges have large weights, and \n",
"1. the edges point to other highly ranked nodes. \n",
"\n",
"\n",
"Later, when we study demand shocks in production networks, there will be a more\n",
"concrete interpretation of eigenvector centrality.\n",
"\n",
"We will see that, in production networks, sectors with high eigenvector\n",
"centrality are important *suppliers*.\n",
"\n",
"In particular, they are activated by a wide array of demand shocks once orders\n",
"flow backwards through the network.\n",
"\n",
"To compute eigenvector centrality we can use the following function."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "be47bb30",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"def eigenvector_centrality(A, k=40, authority=False):\n",
" \"\"\"\n",
" Computes the dominant eigenvector of A. Assumes A is\n",
" primitive and uses the power method.\n",
"\n",
" \"\"\"\n",
" A_temp = A.T if authority else A\n",
" n = len(A_temp)\n",
" r = np.max(np.abs(np.linalg.eigvals(A_temp)))\n",
" e = r**(-k) * (np.linalg.matrix_power(A_temp, k) @ np.ones(n))\n",
" return e / np.sum(e)"
]
},
{
"cell_type": "markdown",
"id": "f1d8c58d",
"metadata": {},
"source": [
"Let’s compute eigenvector centrality for the graph generated in Fig. 33.6."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "50a2fc77",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"A = nx.to_numpy_array(G7) # compute adjacency matrix of graph"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "153cabab",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"e = eigenvector_centrality(A)\n",
"n = len(e)\n",
"\n",
"for i in range(n):\n",
" print(i+1,e[i])"
]
},
{
"cell_type": "markdown",
"id": "757e5b19",
"metadata": {},
"source": [
"While nodes $ 2 $ and $ 4 $ had the highest in-degree centrality, we can see that nodes $ 1 $ and $ 2 $ have the\n",
"highest eigenvector centrality.\n",
"\n",
"Let’s revisit the international credit network in Fig. 33.4."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ae75cb3b",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"eig_central = eigenvector_centrality(Z)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4340d35c",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"\n",
"df = centrality_plot_data(countries, eig_central)\n",
"\n",
"ax.bar('code', 'centrality', data=df, color=df[\"color\"], alpha=0.6)\n",
"\n",
"patch = mpatches.Patch(color=None, visible=False)\n",
"ax.legend(handles=[patch], fontsize=12, loc=\"upper left\", handlelength=0, frameon=False)\n",
"\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "cee289de",
"metadata": {},
"source": [
"Countries that are rated highly according to this rank tend to be important\n",
"players in terms of supply of credit.\n",
"\n",
"Japan takes the highest rank according to this measure, although\n",
"countries with large financial sectors such as Great Britain and France are\n",
"not far behind.\n",
"\n",
"The advantage of eigenvector centrality is that it measures a node’s importance while considering the importance of its neighbours.\n",
"\n",
"A variant of eigenvector centrality is at the core of Google’s PageRank algorithm, which is used to rank web pages.\n",
"\n",
"The main principle is that links from important nodes (as measured by degree centrality) are worth more than links from unimportant nodes."
]
},
{
"cell_type": "markdown",
"id": "149237fe",
"metadata": {},
"source": [
"### Katz centrality\n",
"\n",
"One problem with eigenvector centrality is that $ r(A) $ might be zero, in which\n",
"case $ 1/r(A) $ is not defined.\n",
"\n",
"For this and other reasons, some researchers prefer another measure of\n",
"centrality for networks called Katz centrality.\n",
"\n",
"Fixing $ \\beta $ in $ (0, 1/r(A)) $, the **Katz centrality** of a weighted\n",
"directed graph with adjacency matrix $ A $ is defined as the vector $ \\kappa $\n",
"that solves\n",
"\n",
"\n",
"\n",
"$$\n",
"\\kappa_i = \\beta \\sum_{1 \\leq j 1} a_{ij} \\kappa_j + 1\n",
"\\qquad \\text{for all } i \\in \\{0, \\ldots, n-1\\}. \\tag{33.3}\n",
"$$\n",
"\n",
"Here $ \\beta $ is a parameter that we can choose.\n",
"\n",
"In vector form we can write\n",
"\n",
"\n",
"\n",
"$$\n",
"\\kappa = \\mathbf 1 + \\beta A \\kappa \\tag{33.4}\n",
"$$\n",
"\n",
"where $ \\mathbf 1 $ is a column vector of ones.\n",
"\n",
"The intuition behind this centrality measure is similar to that provided for\n",
"eigenvector centrality: high centrality is conferred on $ i $ when it is linked\n",
"to by nodes that themselves have high centrality.\n",
"\n",
"Provided that $ 0 < \\beta < 1/r(A) $, Katz centrality is always finite and well-defined\n",
"because then $ r(\\beta A) < 1 $.\n",
"\n",
"This means that [(33.4)](#equation-katz-central-vec) has the unique solution\n",
"\n",
"$$\n",
"\\kappa = (I - \\beta A)^{-1} \\mathbf{1}\n",
"$$\n",
"\n",
"This follows from the [Neumann series theorem](https://intro.quantecon.org/eigen_I.html#neumann-series-lemma).\n",
"\n",
"The parameter $ \\beta $ is used to ensure that $ \\kappa $ is finite\n",
"\n",
"When $ r(A)<1 $, we use $ \\beta=1 $ as the default for Katz centrality computations."
]
},
{
"cell_type": "markdown",
"id": "21827641",
"metadata": {},
"source": [
"### Authorities vs hubs\n",
"\n",
"Search engine designers recognize that web pages can be important in two\n",
"different ways.\n",
"\n",
"Some pages have high **hub centrality**, meaning that they link to valuable\n",
"sources of information (e.g., news aggregation sites).\n",
"\n",
"Other pages have high **authority centrality**, meaning that they contain\n",
"valuable information, as indicated by the number and significance of incoming\n",
"links (e.g., websites of respected news organizations).\n",
"\n",
"Similar ideas can and have been applied to economic networks (often using\n",
"different terminology).\n",
"\n",
"The eigenvector centrality and Katz centrality measures we discussed above\n",
"measure hub centrality.\n",
"\n",
"(Nodes have high centrality if they point to other nodes with high centrality.)\n",
"\n",
"If we care more about authority centrality, we can use the same definitions\n",
"except that we take the transpose of the adjacency matrix.\n",
"\n",
"This works because taking the transpose reverses the direction of the arrows.\n",
"\n",
"(Now nodes will have high centrality if they receive links from other nodes\n",
"with high centrality.)\n",
"\n",
"For example, the **authority-based eigenvector centrality** of a weighted\n",
"directed graph with adjacency matrix $ A $ is the vector $ e $ solving\n",
"\n",
"\n",
"\n",
"$$\n",
"e = \\frac{1}{r(A)} A^\\top e. \\tag{33.5}\n",
"$$\n",
"\n",
"The only difference from the original definition is that $ A $ is replaced by\n",
"its transpose.\n",
"\n",
"(Transposes do not affect the spectral radius of a matrix so we wrote $ r(A) $ instead of $ r(A^\\top) $.)\n",
"\n",
"Element-by-element, this is given by\n",
"\n",
"\n",
"\n",
"$$\n",
"e_j = \\frac{1}{r(A)} \\sum_{1 \\leq i \\leq n} a_{ij} e_i \\tag{33.6}\n",
"$$\n",
"\n",
"We see $ e_j $ will be high if many nodes with high authority rankings link to $ j $.\n",
"\n",
"The following figurenshows the authority-based eigenvector centrality ranking for the international\n",
"credit network shown in Fig. 33.4."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0e773ca2",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"ecentral_authority = eigenvector_centrality(Z, authority=True)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f350e193",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"fig, ax = plt.subplots()\n",
"\n",
"df = centrality_plot_data(countries, ecentral_authority)\n",
"\n",
"ax.bar('code', 'centrality', data=df, color=df[\"color\"], alpha=0.6)\n",
"\n",
"patch = mpatches.Patch(color=None, visible=False)\n",
"ax.legend(handles=[patch], fontsize=12, loc=\"upper left\", handlelength=0, frameon=False)\n",
"\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "c7786f8e",
"metadata": {},
"source": [
"Highly ranked countries are those that attract large inflows of credit, or\n",
"credit inflows from other major players.\n",
"\n",
"In this case the US clearly dominates the rankings as a target of interbank credit."
]
},
{
"cell_type": "markdown",
"id": "fd550e98",
"metadata": {},
"source": [
"## Further reading\n",
"\n",
"We apply the ideas discussed in this lecture to:\n",
"\n",
"Textbooks on economic and social networks include [[Jac10](https://intro.quantecon.org/zreferences.html#id273)],\n",
"[[EK+10](https://intro.quantecon.org/zreferences.html#id274)], [[BEJ18](https://intro.quantecon.org/zreferences.html#id275)],\n",
"[[SS22](https://intro.quantecon.org/zreferences.html#id276)] and [[Goy23](https://intro.quantecon.org/zreferences.html#id277)].\n",
"\n",
"Within the realm of network science, the texts\n",
"by [[New18](https://intro.quantecon.org/zreferences.html#id278)], [[MFD20](https://intro.quantecon.org/zreferences.html#id279)] and\n",
"[[Cos21](https://intro.quantecon.org/zreferences.html#id280)] are excellent."
]
},
{
"cell_type": "markdown",
"id": "016429fe",
"metadata": {},
"source": [
"## Exercises"
]
},
{
"cell_type": "markdown",
"id": "40b7febc",
"metadata": {},
"source": [
"## Exercise 33.1\n",
"\n",
"Here is a mathematical exercise for those who like proofs.\n",
"\n",
"Let $ (V, E) $ be a directed graph and write $ u \\sim v $ if $ u $ and $ v $ communicate.\n",
"\n",
"Show that $ \\sim $ is an [equivalence relation](https://en.wikipedia.org/wiki/Equivalence_relation) on $ V $."
]
},
{
"cell_type": "markdown",
"id": "95b6d192",
"metadata": {},
"source": [
"## Solution to[ Exercise 33.1](https://intro.quantecon.org/#networks_ex1)\n",
"\n",
"**Reflexivity:**\n",
"\n",
"Trivially, $ u = v \\Rightarrow u \\rightarrow v $.\n",
"\n",
"Thus, $ u \\sim u $.\n",
"\n",
"**Symmetry:**\n",
"Suppose, $ u \\sim v $\n",
"\n",
"$ \\Rightarrow u \\rightarrow v $ and $ v \\rightarrow u $.\n",
"\n",
"By definition, this implies $ v \\sim u $.\n",
"\n",
"**Transitivity:**\n",
"\n",
"Suppose, $ u \\sim v $ and $ v \\sim w $\n",
"\n",
"This implies, $ u \\rightarrow v $ and $ v \\rightarrow u $ and also $ v \\rightarrow w $ and $ w \\rightarrow v $.\n",
"\n",
"Thus, we can conclude $ u \\rightarrow v \\rightarrow w $ and $ w \\rightarrow v \\rightarrow u $.\n",
"\n",
"Which means $ u \\sim w $."
]
},
{
"cell_type": "markdown",
"id": "a02bdfe7",
"metadata": {},
"source": [
"## Exercise 33.2\n",
"\n",
"Consider a directed graph $ G $ with the set of nodes\n",
"\n",
"$$\n",
"V = \\{0,1,2,3,4,5,6,7\\}\n",
"$$\n",
"\n",
"and the set of edges\n",
"\n",
"$$\n",
"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)\\}\n",
"$$\n",
"\n",
"1. Use `Networkx` to draw graph $ G $. \n",
"1. Find the associated adjacency matrix $ A $ for $ G $. \n",
"1. Use the functions defined above to compute in-degree centrality, out-degree centrality and eigenvector centrality\n",
" of G. "
]
},
{
"cell_type": "markdown",
"id": "da8862a8",
"metadata": {},
"source": [
"## Solution to[ Exercise 33.2](https://intro.quantecon.org/#networks_ex2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "5716f019",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"# First, let's plot the given graph\n",
"\n",
"G = nx.DiGraph()\n",
"\n",
"G.add_nodes_from(np.arange(8)) # adding nodes\n",
"\n",
"G.add_edges_from([(0,1),(0,3), # adding edges\n",
" (1,0),\n",
" (2,4),\n",
" (3,2),(3,4),(3,7),\n",
" (4,3),\n",
" (5,4),(5,6),\n",
" (6,3),(6,5),\n",
" (7,0)])\n",
"\n",
"nx.draw_networkx(G, pos=nx.circular_layout(G), node_color='gray', node_size=500, with_labels=True)\n",
"\n",
"plt.show()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6a5a2dae",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"A = nx.to_numpy_array(G) #find adjacency matrix associated with G\n",
"\n",
"A"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "32558c49",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"oG = [G.out_degree(v) for v in G.nodes()] # computing in-degree centrality\n",
"\n",
"for i, d in enumerate(oG):\n",
" print(i, d)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1c18cbc6",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"e = eigenvector_centrality(A) # computing eigenvector centrality\n",
"n = len(e)\n",
"\n",
"for i in range(n):\n",
" print(i+1, e[i])"
]
},
{
"cell_type": "markdown",
"id": "9c775047",
"metadata": {},
"source": [
"## Exercise 33.3\n",
"\n",
"Consider a graph $ G $ with $ n $ nodes and $ n \\times n $ adjacency matrix $ A $.\n",
"\n",
"Let $ S = \\sum_{k=0}^{n-1} A^k $\n",
"\n",
"We can say for any two nodes $ i $ and $ j $, $ j $ is accessible from $ i $ if and only if\n",
"$ S_{ij} > 0 $.\n",
"\n",
"Devise a function `is_accessible` that checks if any two nodes of a given graph are accessible.\n",
"\n",
"Consider the graph in Exercise 33.2 and use this function to check if\n",
"\n",
"1. $ 1 $ is accessible from $ 2 $ \n",
"1. $ 6 $ is accessible from $ 3 $ "
]
},
{
"cell_type": "markdown",
"id": "ee899762",
"metadata": {},
"source": [
"## Solution to[ Exercise 33.3](https://intro.quantecon.org/#networks_ex3)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e7b5ca20",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"def is_accessible(G,i,j):\n",
" A = nx.to_numpy_array(G)\n",
" n = len(A)\n",
" result = np.zeros((n, n))\n",
" for i in range(n):\n",
" result += np.linalg.matrix_power(A, i)\n",
" if result[i,j]>0:\n",
" return True\n",
" else:\n",
" return False"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ef7eb4d2",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"G = nx.DiGraph()\n",
"\n",
"G.add_nodes_from(np.arange(8)) # adding nodes\n",
"\n",
"G.add_edges_from([(0,1),(0,3), # adding edges\n",
" (1,0),\n",
" (2,4),\n",
" (3,2),(3,4),(3,7),\n",
" (4,3),\n",
" (5,4),(5,6),\n",
" (6,3),(6,5),\n",
" (7,0)])"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "93f7b3e3",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"is_accessible(G, 2, 1)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "17de46b1",
"metadata": {
"hide-output": false
},
"outputs": [],
"source": [
"is_accessible(G, 3, 6)"
]
}
],
"metadata": {
"date": 1696997366.542909,
"filename": "networks.md",
"kernelspec": {
"display_name": "Python",
"language": "python3",
"name": "python3"
},
"title": "Networks"
},
"nbformat": 4,
"nbformat_minor": 5
}