<jupyter_start><jupyter_text>CS246 - Colab 5 PageRank  Setup First of all, we authenticate a Google Drive client to download the dataset we will be processing in this Colab.**Make sure to follow the interactive instructions.**<jupyter_code>from pydrive.auth import GoogleAuth
from pydrive.drive import GoogleDrive
from google.colab import auth
from oauth2client.client import GoogleCredentials

# Authenticate and create the PyDrive client
auth.authenticate_user()
gauth = GoogleAuth()
gauth.credentials = GoogleCredentials.get_application_default()
drive = GoogleDrive(gauth)
id='<KEY>'
downloaded = drive.CreateFile({'id': id})
downloaded.GetContentFile('web-Stanford.txt')<jupyter_output><empty_output><jupyter_text>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.Next, we import some of the common libraries needed for our task.<jupyter_code>import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline<jupyter_output><empty_output><jupyter_text>Data Loading 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.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)<jupyter_code>import networkx as nx

G = nx.read_edgelist('web-Stanford.txt', create_using=nx.DiGraph)
nb_nodes = G.number_of_nodes()
nb_edges = G.number_of_edges()
print(f'Graph G with {nb_nodes} nodes and {nb_edges} edges')<jupyter_output>Graph G with 281903 nodes and 2312497 edges<jupyter_text>Your Task To begin with, let's simplify our analysis by ignoring the dangling nodes and the disconnected components in the original graph.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.<jupyter_code># YOUR CODE HERE
lst_max_weakly_connected_components = max(nx.weakly_connected_components(G))
len(lst_max_weakly_connected_components)
G.remove_nodes_from(set(G.nodes()) - lst_max_weakly_connected_components)
print(nx.info(G))<jupyter_output>DiGraph with 255265 nodes and 2234572 edges<jupyter_text>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.htmlnetworkx.algorithms.link_analysis.pagerank_alg.pageranky](https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.link_analysis.pagerank_alg.pagerank.htmlnetworkx.algorithms.link_analysis.pagerank_alg.pagerank)<jupyter_code># YOUR CODE HERE
pageRank = nx.pagerank(G)
len(pageRank)<jupyter_output><empty_output><jupyter_text>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).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! 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)Using for both methods ```seed = 1```, generate: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```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 number of edges in the original connected componentand compute the PageRank vectors for both graphs.<jupyter_code># YOUR CODE HERE
nb_nodes = G.number_of_nodes()
nb_edges = G.number_of_edges()

randomGraph = nx.fast_gnp_random_graph(n=nb_nodes, p = 0.00008, seed=1)
barabasiAlbertGraph = nx.barabasi_albert_graph(n=nb_nodes, m=nb_edges// nb_nodes+1, seed=1)
print(nx.info(G))
print(nx.info(randomGraph))
print(nx.info(barabasiAlbertGraph))<jupyter_output>Graph with 255265 nodes and 2297304 edges<jupyter_text>Compare the PageRank vectors obtained on the generated graphs with the PageRank vector you computed on the original connected component.**Sort** the components of each vector by value, and use cosine similarity as similarity measure. Feel free to use any implementation of the cosine similarity available in third-party libraries, or implement your own with ```numpy```.<jupyter_code># YOUR CODE HERE
pageRankRandomGraph = nx.pagerank(randomGraph)
len(pageRankRandomGraph)
pageRankBarabasiAlbertGraph = nx.pagerank(barabasiAlbertGraph)
len(pageRankBarabasiAlbertGraph)
sortedPageRank = np.array(sorted(pageRank.values()))
sortedPageRankRandomGraph = np.array(sorted(pageRankRandomGraph.values()))
sortedPageRankBarabasiAlbertGraph = np.array(sorted(pageRankBarabasiAlbertGraph.values()))
from scipy import spatial


def cosine_distance(a, b):
    cosine_distance = float(spatial.distance.cosine(a, b))
    return cosine_distance

print(cosine_distance(sortedPageRank, sortedPageRankRandomGraph))
print(cosine_distance(sortedPageRank, sortedPageRankBarabasiAlbertGraph))<jupyter_output>0.896044352960356
0.3511326339032764
{'fraction_non_alphanumeric': 0.08200922603792926, 'fraction_numerical': 0.017597813087305656, 'mean_word_length': 6.889487870619946, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 26, 'https://': 5, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '92524', 'license': 'MIT', 'n_tokens_mistral': 1792, 'n_tokens_neox': 1684, 'n_words': 564, 'path': 'CS246_Colab_5.ipynb', 'repo_name': 'x3pi/mining-massive-datasets', 'size': '5881'}