{ "cells": [ { "cell_type": "markdown", "metadata": { "hide_cell": true }, "source": [ "Make me look good. Click on the cell below and press Ctrl+Enter." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "hide_cell": true }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.core.display import HTML\n", "HTML(open('css/custom.css', 'r').read())" ] }, { "cell_type": "markdown", "metadata": { "hide_cell": true }, "source": [ "
SM286D · Introduction to Applied Mathematics with Python · Spring 2020 · Uhan
\n", "\n", "
Lesson 13.
\n", "\n", "

Social network analysis

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## This lesson..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We're going to find the key conspirators in the American Revolution through social network analysis. In particular, we will reproduce parts this analysis by Prof. Kieran Healy:\n", "\n", "https://kieranhealy.org/blog/archives/2013/06/09/using-metadata-to-find-paul-revere/\n", "\n", "(If you don't have a working internet connection, you can look at `FindingPaulRevere.pdf` in the same folder as this notebook.)\n", "\n", "Prof. Healy used R to perform his analysis. Naturally, we will use Python." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "First, read Prof. Healy's analysis linked above to get an idea of what's coming next. It's a fun read!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 1\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In the same folder as this notebook, there is an Excel workbook called `PaulRevereAppD.xlsx`. Open the file in Excel. \n", "\n", "You'll see that the first sheet `PaulRevereAppD` has a table with oddly formatted names of revolutionaries in column A. In the next 7 columns we have a 0-1 matrix indicating whether the revolutionary belonged to one of seven clubs and social groups (1 if they did belong and 0 if they didn't). \n", "\n", "Use `xlwings` to get and store the names in a list called `names`. Check your work: two revolutionary cousins should be listed in `names[0]` and `names[1]`. " ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The two revolutionary cousins are Adams.John and Adams.Samuel.\n" ] } ], "source": [ "import xlwings as xw\n", "\n", "# Create workbook object\n", "wb = xw.Book('PaulRevereAppD.xlsx')\n", "\n", "# Grab desired sheet\n", "sht = wb.sheets['PaulRevereAppD']\n", "\n", "# Grab names from sheet\n", "names = sht.range('A1').expand('down').value\n", "\n", "# Check our work\n", "print(f\"The two revolutionary cousins are {names[0]} and {names[1]}.\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now get the 0-1 matrix from the sheet `PaulRevereAppD` and store it in a NumPy array `A`. Use the `.shape` attribute to find the dimensions of the array `A`. Check your work: you should have a NumPy array with 254 rows and 7 columns." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The dimensions of A are (254, 7).\n" ] } ], "source": [ "import numpy as np\n", "\n", "# Grab 0-1 matrix from Excel\n", "# Put 01-matrix into a Numpy array\n", "A = np.array(sht.range('B1').expand('table').value)\n", "\n", "# Print dimensions of the matrix\n", "print(f\"The dimensions of A are {A.shape}.\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we're going to create the adjacency matrix:\n", "\n", "- Use the `@` operator and the `.transpose()` method to create the adjacency matrix $M = AA^T$.\n", "- Print the matrix and take a look. It contains some entries that are different from 0 and 1. \n", "- Replace nonzero entries with 1s. Also, replace all diagonal entries with 0s since each node should not be connected to itself. Check your work by printing the matrix again.\n", "\n", "_Pro tip._ A slick way to get the number of rows and columns of a NumPy array is:\n", "\n", "```python\n", "# m = number of rows\n", "# n = number of columns\n", "m, n = A.shape\n", "```\n", "\n", "Alternatively, you can use `A.shape[0]` and `A.shape[1]`." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[2. 2. 1. ... 1. 0. 1.]\n", " [2. 4. 1. ... 2. 0. 2.]\n", " [1. 1. 1. ... 1. 0. 1.]\n", " ...\n", " [1. 2. 1. ... 2. 0. 1.]\n", " [0. 0. 0. ... 0. 1. 1.]\n", " [1. 2. 1. ... 1. 1. 3.]]\n" ] } ], "source": [ "# Compute M\n", "M = A @ A.transpose()\n", "\n", "# Check our work\n", "print(M)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[0. 1. 1. ... 1. 0. 1.]\n", " [1. 0. 1. ... 1. 0. 1.]\n", " [1. 1. 0. ... 1. 0. 1.]\n", " ...\n", " [1. 1. 1. ... 0. 0. 1.]\n", " [0. 0. 0. ... 0. 0. 1.]\n", " [1. 1. 1. ... 1. 1. 0.]]\n" ] } ], "source": [ "# Get size of matrix\n", "m, n = M.shape\n", "\n", "# Modify adjacency matrix\n", "for i in range(m):\n", " for j in range(n):\n", " # Replace nonzero entries with 1s\n", " if M[i, j] > 0:\n", " M[i, j] = 1\n", " \n", " # Replace diagonal entries with 0s\n", " if i == j:\n", " M[i, j] = 0\n", "\n", "# Check our work\n", "print(M)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Use NetworkX to make a graph `G` whose adjacency matrix is `M`. Recall that `G.degree()[i]` gives you the degree of node `i`. Make a list `degs` whose $i^\\text{th}$ entry is the degree of node $i$. Check your work: `degs[101]` should equal 135. " ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "135\n" ] } ], "source": [ "import networkx as nx\n", "\n", "# Create graph\n", "G = nx.Graph(M)\n", "\n", "# Create list of degrees\n", "# Recall that n is the number of rows of M, \n", "# which is the number of nodes in G\n", "# Here, we've used a list comprehension\n", "# Using a for loop with .append() is OK too\n", "degs = [G.degree()[i] for i in range(n)]\n", "\n", "# Check our work\n", "print(degs[101])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 5" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Define $N$ to be the number of revolutionaries, or vertices in `G`. The _normalized degree_ (also known as *degree centrality*) of vertex $i$ is the degree of vertex $i$ divided by $N-1$. Using the list `degs` you created in Part 4, make a list `ndegs` whose $i^\\text{th}$ entry is the normalized degree of node $i$. Check your work: `ndegs[101]` should be approximately 0.5336.\n", "\n", "(Recall from Lesson 12 that we could have used `nx.degree_centrality()` to compute these values. Let's do this \"manually\" here instead.)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0.5335968379446641\n" ] } ], "source": [ "# Compute N\n", "N = len(G.nodes)\n", "\n", "# Compute normalized degree\n", "ndegs = [d / (N - 1) for d in degs]\n", "\n", "# Check our work\n", "print(ndegs[101])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 6" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We want to print out a list of the five revolutionaries with the highest normalized degrees. We'll do this over the next few parts.\n", "\n", "First, let's see how to print a nicely formatted string. Run the following cell:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Will 2 3.142\n" ] } ], "source": [ "# Define variables for name, rank and value\n", "nm = 'Will'\n", "rk = 2\n", "val = 3.1415\n", "\n", "# Print this information\n", "print(f'{nm:<5s} {rk:>5d} {val:0.3f}')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that the f-string looks different from the ones we've used so far — in particular, what's inside the `{ }`.\n", "\n", "The expressions inside `{ }` before `:` are evaluated at run time, and in this case will take on the values of `Will`, `2`, and `3.1415`, respectively. Python prints the value for each of these variables. \n", "\n", "The `5s` following the first `:` means that the value should be formatted as a string (that's due to the `s`) and that the string should take at least 5 characters. The `<` sign tells Python to left justify the string in the 5 character space. If the string is longer than 5 characters, all characters are printed; the 5 just determines the padding that we'll use if the string is shorter than 5 characters. This is very helpful in lining up printed text in nice columns. \n", "\n", "The value for `rk` is formatted as an integer (that's due to the `d`, think: digit) with at least 5 spaces. The `>` sign tells Python to right justify the string in the 5 character space. If you want your string to be centered in the allotted character space, you should use `^` in place of the `<` or `>`. \n", "\n", "Finally, `val` is formatted as a float (that's due to the `f`). The minimum field is 0 characters but the value following the decimal is important too: it is the precision, the number of characters after the decimal that are printed. If the number has more decimals, the value is rounded. \n", " \n", "[Here's more reading about f-strings.](https://realpython.com/python-f-strings/)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Use code similar to the code given above to print the first American revolutionary's name (left justified, in at least 25 spaces), their rank (1), and their normalized degree (to 4 decimal places accuracy). It might make more sense to print their rank first. Also, print a header with the words `Rank`, `Name`, and `ndeg` on top by using a second print statement. Your output should look like:\n", "\n", "```\n", "Rank Name ndeg\n", "1 Adams.John 0.2885\n", "```" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Rank Name ndeg\n", "1 Adams.John 0.2885\n" ] } ], "source": [ "# Print table heading\n", "rank = 'Rank'\n", "name = 'Name'\n", "measure = 'ndeg'\n", "print(f'{rank:5s} {name:<25s} {measure:s}')\n", "\n", "# Print information for first revolutionary\n", "rank = 1\n", "name = names[0]\n", "measure = ndegs[0]\n", "# Note: < is for left aligned, > is for right aligned, ^ is for center aligned\n", "print(f'{rank:<5d} {name:<25s} {measure:0.4f}') " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 7" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we'd like to sort the list of normalized degrees. We could just use the `sorted` function to do this, but it would help if we knew how the original list was permuted or rearranged. The `np.argsort` method does just that! \n", "\n", "Take a look at this example code:" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1 2 0]\n", "True\n" ] } ], "source": [ "# Define sample list of values\n", "list_of_vals = [1, 3, 2]\n", "\n", "# Get indices of how the values should be sorted\n", "idx = np.argsort(list_of_vals)[::-1]\n", "\n", "# What do the indices look like?\n", "print(idx)\n", "\n", "# Check our work with sorted()\n", "print([list_of_vals[i] for i in idx] == sorted(list_of_vals, reverse=True))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On line 5, we pass `list_of_vals` to the `np.argsort` method, which returns a list-like object (a NumPy array, to be exact). \n", "\n", "Recall the slicing syntax: `[start:stop:step]`. So adding `[::-1]` to a list-like object reverses the order of the list. Since `np.argsort` sorts by increasing order, we want to reverse the order of the list it returns.\n", "\n", "Note that\n", "\n", "```python\n", "list_of_vals[1] > list_of_vals[2] > list_of_vals[0]\n", "```\n", "\n", "so the output of `np.argsort` is a list of the indices for the original list that produce the sorted list. We verify this on line 11, which outputs `True`. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now you should find the indices that sort the normalized degrees from highest to lowest. Check your work: your first 3 values should be 199, 10 and 110. Also find the names of the American revolutionaries with the highest 3 normalized degrees. " ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[199 10 110]\n", "The American revolutionaries with the three highest ndegs values are:\n", "Revere.Paul\n", "Barber.Nathaniel\n", "Hoffins.John\n" ] } ], "source": [ "# Get indices of how the normalized degree \n", "# values should sorted, highest to lowest\n", "idx = np.argsort(ndegs)[::-1]\n", "\n", "# Print the indices corresponding to the \n", "# 3 highest normalized degree values\n", "print(idx[0:3])\n", "\n", "# Print the names of the revolutionaries with the\n", "# 3 highest normalized degree values\n", "print('The American revolutionaries with the three highest ndegs values are:')\n", "print(names[idx[0]])\n", "print(names[idx[1]])\n", "print(names[idx[2]])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 8" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, put the last two parts together to produce a chart with the top 5 American revolutionaries, ranked by normalized degree. Your chart should have columns for rank, name and normalized degree. It should have a row for each of the five revolutionaries.\n", "\n", "_Challenge._ Can you write the names so that they don't have the odd formatting? Hint: use the `.split()` method for strings, described [here in the documentation](https://docs.python.org/3.7/library/stdtypes.html#str.split)." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Rank Name ndeg\n", "1 Paul Revere 0.9802\n", "2 Nathaniel Barber 0.7905\n", "3 John Hoffins 0.7905\n", "4 William Cooper 0.7905\n", "5 William Greenleaf 0.7826\n" ] } ], "source": [ "# Print table heading\n", "rank = 'Rank'\n", "name = 'Name'\n", "measure = 'ndeg'\n", "print(f'{rank:5s} {name:25s} {measure:s}')\n", "\n", "# Print top 5 revolutionaries by normalized degree\n", "for i in range(5):\n", " name_split = names[idx[i]].split('.')\n", " full_name = f'{name_split[1]} {name_split[0]}'\n", " print(f'{(i+1):<5d} {full_name:25s} {ndegs[idx[i]]:0.4f}')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 9" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we're going to package all our work from the last three parts into a function. \n", "\n", "Define a function called `foutput` that takes inputs `measure_list`, `measure_name`, `name_list` and `many`:\n", "\n", "- `measure_list` should be a list of measurements, not necessarily sorted. \n", "- `measure_name` should be a string with the name of the quantity measured in `measure_list`.\n", "- `name_list` should be a list of names, one for each number in `measure_list`. \n", "- `many` should be a number and it should be equal to 5 as a default value. \n", "\n", "The function should print a table. The table should have columns for rank, name and the measured quantity. You should print the top `many` values of `measure_list`, one on each row, with the corresponding names. \n", "\n", "Test your function on your normalized degree data to ensure that it gives the same output as in the previous question. Also test your function if you don't give a value for `many` as input." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Rank Name ndeg\n", "1 Paul Revere 0.9802\n", "2 Nathaniel Barber 0.7905\n", "3 John Hoffins 0.7905\n", "4 William Cooper 0.7905\n", "5 William Greenleaf 0.7826\n" ] } ], "source": [ "def foutput(measure_list, measure_name, name_list, many=5):\n", " \"\"\"\n", " Print top `many` values of `measurelist`, one on each row, with the corresponding names. \n", " \"\"\"\n", " # Get indices of how the measure list should sorted, highest to lowest\n", " idx = np.array(measure_list).argsort()[::-1]\n", " \n", " # Print table heading\n", " rank = 'Rank'\n", " name = 'Name'\n", " print(f'{rank:5s} {name:25s} {measure_name:s}')\n", " \n", " # Print top `many` names by measure\n", " for i in range(many):\n", " name_split = name_list[idx[i]].split('.')\n", " full_name = f'{name_split[1]} {name_split[0]}'\n", " print(f'{(i+1):<5d} {full_name:25s} {measure_list[idx[i]]:0.4f}')\n", " \n", "# Test function \n", "foutput(ndegs, 'ndeg', names, 5) " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 10" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The *normalized closeness* (also known as *closeness centrality*) is another measure of the centrality of nodes in a network (see Lesson 12 and Project 5 for details). Recall that NetworkX has a built-in function to compute normalized closeness: " ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "# Compute closeness centrality\n", "# nx.closeness_centrality returns a dictionary\n", "closeness = nx.closeness_centrality(G)\n", "\n", "# Create list of closeness centrality values\n", "# Recall that n is the number of nodes in G\n", "# Here, we've used a list comprehension\n", "# Using a for loop with .append() is OK too\n", "closeness_list = [closeness[i] for i in range(n)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The code above produces a list `closeness_list` that contains the normalized closeness values. Use your code from the last part to produce a table with the names and scores of the top five American revolutionaries as measured by normalized closeness. " ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Rank Name closeness\n", "1 Paul Revere 0.9806\n", "2 Nathaniel Barber 0.8268\n", "3 John Hoffins 0.8268\n", "4 William Cooper 0.8268\n", "5 William Greenleaf 0.8214\n" ] } ], "source": [ "foutput(closeness_list, 'closeness', names, 5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 11" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Computing the normalized closeness requires us to find all the shortest paths between two people in our relationship graph. \n", "\n", "The NetworkX method `nx.shortest_path` computes a shortest path between two nodes in a graph. Look at the NetworkX documentation to find out how to use this method. Then find a shortest path from Nathaniel Barber (node 10 in our graph) to John Winslow (node 250 in our graph). \n", "\n", "Next, use the NetworkX method `nx.all_shortest_paths` to count the number of shortest paths linking Nathaniel Barber to John Winslow. " ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "A shortest path between nodes 10 and 250 is: [10, 0, 250]\n", "A shortest path between Nathaniel Barber and John Winslow is: ['Barber.Nathaniel', 'Adams.John', 'Winslow.John']\n", "All of the shortest paths between Nathaniel Barber and John Winslow:\n", "[[10, 0, 250], [10, 1, 250], [10, 50, 250], [10, 51, 250], [10, 100, 250], [10, 101, 250], [10, 166, 250], [10, 197, 250], [10, 199, 250], [10, 235, 250]]\n", "There are actually 10 shortest paths between Nathaniel Barber and John Winslow.\n" ] } ], "source": [ "# Find a shortest path betwteen nodes 10 and 250\n", "# Print the path (node numbers)\n", "path = nx.shortest_path(G, source=10, target=250)\n", "print(f'A shortest path between nodes 10 and 250 is: {path}')\n", "\n", "# Print the corresponding names of this path\n", "npath = [names[i] for i in path]\n", "print(f'A shortest path between Nathaniel Barber and John Winslow is: {npath}')\n", "\n", "# Find all shortest paths between nodes 10 and 250\n", "# Print the paths\n", "# Count the paths\n", "paths = list(nx.all_shortest_paths(G, source=10, target=250))\n", "print('All of the shortest paths between Nathaniel Barber and John Winslow:')\n", "print(paths)\n", "print(f'There are actually {len(paths)} shortest paths between Nathaniel Barber and John Winslow.')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 12" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The PageRank algorithm is one of the celebrated algorithms of the internet age. It ranks the importance of web pages on the internet. It can also be used to rank the importance of nodes in a network. The algorithm sets up a transition matrix for some evolving process on the graph and then computes the eigenvector corresponding to the maximum eigenvalue of this matrix. More details are in Project 5.\n", "\n", "The code below computes the PageRank of each node in our network of American revolutionaries. " ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "pr = nx.pagerank(G, alpha=0.85)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`nx.pagerank()` has a parameter `alpha` that is customarily set to 0.85 but other values are also possible. Print a table with the names and scores of the top five American revolutionaries as measured by PageRank. " ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Rank Name PageRank\n", "1 Paul Revere 0.0113\n", "2 Joseph Warren 0.0087\n", "3 John Hoffins 0.0087\n", "4 William Cooper 0.0087\n", "5 Nathaniel Barber 0.0087\n" ] } ], "source": [ "# Compute PageRank\n", "# nx.pagerank eturns a dictionary\n", "pr = nx.pagerank(G, alpha=0.85)\n", "\n", "# Create list of PageRank values\n", "# Recall that n is the number of nodes in G\n", "# Here, we've used a list comprehension\n", "# Using a for loop with .append() is OK too\n", "pr_list = [pr[i] for i in range(n)]\n", "\n", "# Print top 5 revolutionaries by PageRank\n", "foutput(pr_list, 'PageRank', names, 5)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part 13" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**This question is considered challenge material, BUT it is important because you need to do something similar on your assignment.** \n", "\n", "Let's delve into the PageRank method a bit further. In the code cell below, we define the matrix `MM`, which follows the formula given for $M$ in the PageRank section of Project 5." ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [], "source": [ "# Number of nodes\n", "N = G.number_of_nodes()\n", "\n", "# Set damping parameter\n", "d = 0.85\n", "\n", "# Form matrix K whose diagonal entries = out degree\n", "# We can accomplish this by summing the entries in each row or column of A\n", "out_degree = [sum(M[:, i]) for i in range(N)]\n", "K = np.diag(out_degree)\n", "\n", "# Compute PageRank matrix\n", "MM = d * (np.linalg.inv(K) @ M).transpose() + ((1 - d) / N) * np.ones([N, N])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The method we use to find the largest eigenvalue is an _iterative_ method that starts with a _random_ vector with components between 0 and 1. We divide the vector by its 1-norm (the sum of the absolute values of its components) so that it represents a probability distribution on the set of nodes. " ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [], "source": [ "# Make random vector v with components between 0 and 1\n", "v = np.random.rand(N)\n", "\n", "# Divide the vector v by its 1-norm\n", "v = v / np.linalg.norm(v, ord=1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we set a small error threshold (`epsilon`) and initialize our error to a large overestimate (`error`). We iterate until the error between our current vector `v` and the previous version of vector `v` is smaller than the error threshold. At each iteration we multiply `v` by `MM`, and rescale `v` by dividing by its 1-norm (to keep it a probability distribution). We compute the error using the 2-norm." ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "# Iteratively improve v \n", "epsilon = 1e-6\n", "error = float(\"inf\")\n", "iteration = 0\n", "\n", "while error > epsilon: # stop when error <= epsilon\n", " iteration += 1\n", " oldv = v\n", " v = MM @ v\n", " v = v / np.linalg.norm(v, ord=1)\n", " error = np.linalg.norm(v - oldv, ord=2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "First, create a NumPy array `R` consisting of the values computed by `nx.pagerank()`, so that `R[i]` is the PageRank of revolutionary `i`. (You should have already created a list of these values in Part 12. How do you convert the list into a one-dimensional NumPy array?)\n", "\n", "Then, compute the 2-norm distance between the array `v` output by this process and values computed by `nx.pagerank()`.\n", "\n", "Check your work: the distance should be close to $5 \\times 10^{-5}$. In general the vector $v$ is close to the true eigenvector $R$ though it may not be quite as close as the error tolerance. " ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The difference in 2-norm between our v and the output from the Networkx PageRank algorithm is 5.511431603173813e-05.\n" ] } ], "source": [ "# Compare our v with the output from pagerank\n", "R = np.array(pr_list)\n", "diff = np.linalg.norm(v - R, ord=2)\n", "print(f\"The difference in 2-norm between our v and the output from the Networkx PageRank algorithm is {diff}.\")" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.6" } }, "nbformat": 4, "nbformat_minor": 2 }