{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"provenance":[{"file_id":"1pO098keEPsPVypwAwRmFl2UfZ390LfFO","timestamp":1770245674435}],"machine_shape":"hm"},"kernelspec":{"name":"python3","display_name":"Python 3"}},"cells":[{"cell_type":"markdown","metadata":{"id":"kPt5q27L5557"},"source":["# CS246 - Colab 5 (Winter 2025)\n","## PageRank"]},{"cell_type":"code","source":["from IPython.display import Image\n","print(\"Colab 5 Mascot\")\n","Image(url='https://media.giphy.com/media/cCOVfFwDI3awdse5A3/giphy.gif',width=150)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/","height":192},"id":"yUHXnec92vdy","executionInfo":{"status":"ok","timestamp":1770245503307,"user_tz":480,"elapsed":69,"user":{"displayName":"Rishabh Ranjan","userId":"14643331064616738605"}},"outputId":"76ca151b-f1fa-4e04-8ca4-adce3fcea6d0"},"execution_count":null,"outputs":[{"output_type":"stream","name":"stdout","text":["Colab 5 Mascot\n"]},{"output_type":"execute_result","data":{"text/html":["<img src=\"https://media.giphy.com/media/cCOVfFwDI3awdse5A3/giphy.gif\" width=\"150\"/>"],"text/plain":["<IPython.core.display.Image object>"]},"metadata":{},"execution_count":1}]},{"cell_type":"markdown","metadata":{"id":"p0-YhEpP_Ds-"},"source":["### Setup"]},{"cell_type":"markdown","metadata":{"id":"PUUjUvXe3Sjk"},"source":["First of all, we authenticate a Google Drive client to download the dataset we will be processing in this Colab.\n","\n","**Make sure to follow the interactive instructions.**"]},{"cell_type":"code","metadata":{"id":"lRElWs_x2mGh"},"source":["from pydrive2.auth import GoogleAuth\n","from pydrive2.drive import GoogleDrive\n","from google.colab import auth\n","from oauth2client.client import GoogleCredentials\n","\n","# Authenticate and create the PyDrive client\n","auth.authenticate_user()\n","gauth = GoogleAuth()\n","gauth.credentials = GoogleCredentials.get_application_default()\n","drive = GoogleDrive(gauth)"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"QHsFTGUy2n1c"},"source":["id='1EoolSK32_U74I4FeLox88iuUB_SUUYsI'\n","downloaded = drive.CreateFile({'id': id})\n","downloaded.GetContentFile('web-Stanford.txt')"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"qwtlO4_m_LbQ"},"source":["If you executed the cells above, you should be able to see the dataset we will use for this Colab under the \"Files\" tab on the left panel.\n","\n","Next, we import some of the common libraries needed for our task."]},{"cell_type":"code","metadata":{"id":"twk-K-jilWK7"},"source":["import pandas as pd\n","import numpy as np\n","import matplotlib.pyplot as plt\n","%matplotlib inline"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"kAYRX2PMm0L6"},"source":["### Data Loading"]},{"cell_type":"markdown","metadata":{"id":"GXzc_R6ArXtL"},"source":["For this Colab we will be using [NetworkX](https://networkx.github.io), a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks ([tutorial](https://networkx.org/documentation/stable/tutorial.html)).\n","\n","The dataset we will analyze is a snapshot of the Web Graph centered around [stanford.edu](https://stanford.edu), collected in 2002. Nodes represent pages from Stanford University (stanford.edu) and directed edges represent hyperlinks between them. [[More Info]](http://snap.stanford.edu/data/web-Stanford.html)"]},{"cell_type":"code","metadata":{"id":"LPIadGxvLyyq"},"source":["import networkx as nx\n","\n","G = nx.read_edgelist('web-Stanford.txt', create_using=nx.DiGraph)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":["#### Function to print graph information"],"metadata":{"id":"zgVOrXN1EWNh"}},{"cell_type":"code","metadata":{"id":"Smd1XvR7MLyE"},"source":["def print_graph_info(G, directed=True):\n","  print(\"Number of nodes:\", len(G.nodes))\n","  print(\"Number of edges:\", len(G.edges))\n","  if directed:\n","    print(\"Average in-degree:\", sum(dict(G.in_degree).values()) / len(G.nodes))\n","    print(\"Average out-degree:\", sum(dict(G.out_degree).values()) / len(G.nodes))\n","  else:\n","    print(\"Average degree:\", sum(dict(G.degree).values()) / len(G.nodes))"],"execution_count":null,"outputs":[]},{"cell_type":"code","source":["print_graph_info(G, True)"],"metadata":{"id":"gcZxbivxEcDT"},"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"vbmr23B2rJKR"},"source":["### Your Task"]},{"cell_type":"markdown","metadata":{"id":"x15OQeyys1xd"},"source":["To begin with, let's simplify our analysis by ignoring the dangling nodes and the disconnected components in the original graph.\n","\n","Use NetworkX to identify the **largest** weakly connected component in the ```G``` graph.  **From now on, use this connected component for all the following tasks.** [[More Info]](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.weakly_connected_components.html)\n","\n","Print its information."]},{"cell_type":"code","metadata":{"id":"R9tDwRidIw-Q"},"source":["''' 3 lines of code in total expected. Execution time should be less than 30 seconds'''\n","\n","# YOUR CODE HERE\n"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"mbYMNjBhuhK-"},"source":["Compute the PageRank vector, using the default parameters in NetworkX: [https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.link_analysis.pagerank_alg.pagerank.html#networkx.algorithms.link_analysis.pagerank_alg.pageranky](https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.link_analysis.pagerank_alg.pagerank.html#networkx.algorithms.link_analysis.pagerank_alg.pagerank)"]},{"cell_type":"code","metadata":{"id":"ll-rVh7KVoLA"},"source":["''' 1 line of code in total expected. Execution time should be around or less than 15 seconds.'''\n","\n","# YOUR CODE HERE\n"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"xDx905Wk3FKf"},"source":["In 1999, Barabási and Albert proposed an elegant mathematical model which can generate graphs with topological properties similar to the Web Graph (also called Scale-free Networks).\n","\n","If you complete the steps below, you should obtain some empirical evidence that the Random Graph model is inferior compared to the Barabási–Albert model when it comes to generating a graph resembling the World Wide Web!"]},{"cell_type":"markdown","metadata":{"id":"Ox3ksWEFyaP-"},"source":["As such, we will use two different graph generator methods, and then we will test how well they approximate the Web Graph structure by means of comparing the respective PageRank vectors. [[NetworkX Graph generators]](https://networkx.github.io/documentation/stable/reference/generators.html#)\n","\n","Using the parameters ```seed = 1``` and ```directed=False``` where applicable, generate:\n","\n","\n","1.   a random graph (with the fast method), setting ```n``` equal to the number of nodes in the original connected component, and ```p = 0.00008```\n","2.   a Barabasi-Albert graph (with the standard method), setting ```n``` equal to the number of nodes in the original connected component, and finding the right ***integer*** value for ```m``` such as the resulting number of edges **approximates by excess (the value that is closest to and satisfies $\\geq$)** the number of edges in the original connected component (the largest weakly connected component you attained above)\n","\n","and compute the PageRank vectors for both graphs. Print generated graph's information, if needed.\n"]},{"cell_type":"code","metadata":{"id":"5Yd94CE9aPJP"},"source":["''' 6-10 lines of code in total expected but can differ based on your style.\n","For sub-parts of the question (if any), creating different cells of code would be recommended.\n","The execution time for one pagerank computation should be around 20 seconds.'''\n","\n","# YOUR CODE HERE\n"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"BlxK42Pi01vN"},"source":["Compare the PageRank vectors obtained on the generated graphs with the PageRank vector you computed on the original connected component (the largest weakly connected component you attained above).\n","**Sort** the components of each vector by value, and use cosine similarity as similarity measure.\n","\n","Feel free to use any implementation of the cosine similarity available in third-party libraries, or implement your own with ```numpy```."]},{"cell_type":"code","metadata":{"id":"1aUgyeNdUQxs"},"source":["''' 8-10 lines of code in total expected but can differ based on your style.\n","For sub-parts of the question (if any), creating different cells of code would be recommended.'''\n","\n","# YOUR CODE HERE\n"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"SIrXJyVNP2AI"},"source":["Once you have working code for each cell above, **head over to Gradescope, read carefully the questions, and submit your solution for this Colab**!"]}]}