<jupyter_start><jupyter_text>Group 3 - Assignment 4<NAME>, <NAME>, <NAME>  Libraries<jupyter_code>import networkx as nx
import numpy as np
import operator
import matplotlib.pyplot as plt
from matplotlib.pyplot import figure<jupyter_output><empty_output><jupyter_text>Documents opening<jupyter_code>#read the document of edges and create a dictionary with the following format:
#dic = {node_0 : {'Degree': d, 'Destinations':[]}, node_1 : ... }

edges = dict()
doc_edges = open('example_arcs').read().split('\n')

for i in range(len(doc_edges)-1):
    edge = doc_edges[i].split('\t')
    
    edge[0] = int(edge[0])
    edge[1] = int(edge[1])
    
    if edge[0] not in edges.keys():
        edges[edge[0]] = {"Degree": 1, "Destinations": [edge[1]]}
    else:
        edges[edge[0]]["Degree"] +=1
        edges[edge[0]]["Destinations"].append(edge[1])     
#print the table built as in slide 48

for key, values in edges.items():
    print("Node: %i"%key)
    print("Values:")
    print(values)
    print('-----------------------------------------------------------------------')
#read the document of indexes and build a dictionary
nodes = dict()
doc_nodes = open('example_index').read().split('\n')

for i in range(len(doc_nodes)-1):
    node = doc_nodes[i].split('\t')
    nodes[int(node[1])] = node[0]
nodes<jupyter_output><empty_output><jupyter_text>Page Ranking: *networkx*<jupyter_code>def printRanking(nodes, score):

    ''' 
    Given a dictionary of nodes ({"website1" node_1, "website2": node2, ...})
    prints the ranking of the nodes according to the array of scores
    
    '''
    
    pagerank = dict()
    
    for node in nodes.keys():
        pagerank[nodes[node]] = score[node]
    
    pagerank = sorted(pagerank.items(),key=operator.itemgetter(1),reverse=True)
    
    i = 1
    for node, score in pagerank:
        print("%i : %s --> %f"%(i, node, score))
        print("-----------------------------")
        i += 1
G = nx.read_edgelist("example_arcs", create_using=nx.DiGraph())
pr=nx.pagerank(G,0.85)
scores = np.full(shape=len(nodes.keys()), fill_value=0.0)

for node_id in pr.keys():
    scores[int(node_id)] = pr[node_id]

printRanking(nodes, scores)
nx.draw(G, with_labels=True)
figure(figsize=(1000, 1000), dpi=80);
#plt.draw()<jupyter_output><empty_output><jupyter_text>Page Ranking: MatrixFor a better understanding we decided to implement the ranking also using the adjaciency matrix A. Two different functions were implemented: the first one creates the matrix without caring about dead ends while the second one affords also that problem. In the ranking we don't see any differences but the scores. Indeed, if dead ends are not considered, all the scores will converges to 0.<jupyter_code>def findDeadEnds(edges):

    dead_ends = set()
    
    for node in edges.keys():
        for dest_j in edges[node]['Destinations']:
            if dest_j not in edges.keys():
                dead_ends.add(dest_j)
            
    dead_ends = list(dead_ends)
    
    return dead_ends
def createMatrix(nodes, edges, beta=0.85):
    
    '''
    Given a graph of websites it creates the adjaciency matrix dealing just
    with spidertraps
    
    '''
    
    N = len(nodes.keys())
    A = np.full(shape=(N,N) , fill_value=((1.0-beta)/N))
    
    for node in edges.keys():
        for dest_j in edges[node]['Destinations']:
            
            A[node, dest_j] += beta/edges[node]["Degree"]
                                 
    return A
def createMatrixWithDeadEnds(nodes, edges, beta=0.85):

    '''
    Given a graph of websites it creates the adjaciency matrix dealing
    with spidertraps and dead ends
    
    '''
    
    N = len(nodes.keys())
    A = np.full(shape=(N,N) , fill_value=((1.0-beta)/N))
    
    for node in edges.keys():
        for dest_j in edges[node]['Destinations']:
            
            A[node, dest_j] += beta/edges[node]["Degree"]
            
    dead_ends = findDeadEnds(edges)
    
    for dead_end in dead_ends:
        for node in nodes.keys():
            A[dead_end, node] += beta/N
            
            
    return A
            
def PageRankWithMatrix(nodes, edges, A, beta=0.85, threshold=1.0e-6, max_iterations=100):

    '''
    Given a dictionary of nodes, a dictionary of edges of the form: 
    edges = {node_i : {'Degree': d, 'Destinations':[]}, node_j : ... } 
    the parameter beta, the adjaciency matrix A, the threshold of errors tol and the maximum
    number of iteration to be done max_iterations, returns the ranking of the nodes

    '''
    
    N = len(nodes.keys())
    
    #initialize r_old 
    r_old = np.full(shape=N , fill_value=1.0/N)

    for _ in range (max_iterations):
        
        r_new = np.dot(r_old, A)
        
        #check if the error is small enough 
        err = sum(abs(r_new - r_old))
        
        if err < N*threshold:
            return r_new
        else:
            #update r_old 
            r_old = r_new.copy()
            
         
    return r_new
    
print("Ranking")
print("")
A = createMatrix(nodes, edges)
scores = PageRankWithMatrix(nodes, edges, A)
printRanking(nodes, scores)
print("Ranking")
print("")
A = createMatrixWithDeadEnds(nodes, edges)
scores = PageRankWithMatrix(nodes, edges, A)
printRanking(nodes, scores)<jupyter_output>Ranking

1 : blogspot.com --> 0.085424
-----------------------------
2 : creativecommons.org --> 0.024220
-----------------------------
3 : wikipedia.org --> 0.021583
-----------------------------
4 : canalblog.com --> 0.017731
-----------------------------
5 : youtube.com --> 0.016119
-----------------------------
6 : google.com --> 0.015904
-----------------------------
7 : tumblr.com --> 0.015904
-----------------------------
8 : wikimedia.org --> 0.015600
-----------------------------
9 : rea-group.com --> 0.015058
-----------------------------
10 : yahoo.com --> 0.013151
-----------------------------
11 : lockerz.com --> 0.012801
-----------------------------
12 : wordpress.com --> 0.012604
-----------------------------
13 : flickr.com --> 0.012587
-----------------------------
14 : dpreview.com --> 0.012143
-----------------------------
15 : apple.com --> 0.010850
-----------------------------
16 : twitter.com --> 0.010656
-----------------------------
17 : typepad.com --> 0.0106[...]<jupyter_text>Page Ranking: No MatrixHere comes the real problem of this assignment. Below three different ways of computing the ranking are described:- PageRank computes the ranking without considering dead ends; this means that the rows of the sparse matrix does not sum to 1. However, as said before, the ranking remains the same.- PageRank2 uses the description of https://snap-stanford.github.io/cs224w-notes/network-methods/pagerank. This method considers the scoring that is been lost because of dead ends (that is 1-sum(r_new)) and divide this quantity to all the nodes.- PageRank3 uses the method of *networkx* by computing the sums of dead ends' scores.All this methods were implemented because, at the beginning, it was difficult to understand how implement dead ends in the sparse matrix.<jupyter_code>def PageRank(nodes, edges, beta=0.85, threshold=1.0e-6, max_iterations=100):

    '''
    Given a dictionary of nodes, a dictionary of edges of the form: 
    edges = {node_i : {'Degree': d, 'Destinations':[]}, node_j : ... } 
    the parameter beta, the threshold of errors tol and the maximum
    number of iteration to be done max_iterations, returns the ranking of the nodes

    '''
    
    N = len(nodes.keys())
    
    #initialize r_old and r_new
    r_old = np.full(shape=N , fill_value=1.0/N)
    r_new = np.full(shape=N , fill_value=((1.0-beta)/N))

    for _ in range (max_iterations):
        for node in edges.keys():
            
            #update just the destinations of the considered node
            for dest_j in edges[node]["Destinations"]:
                r_new[dest_j] += beta*(r_old[node]/edges[node]["Degree"])  
                         
        #check if the error is small enough 
        err = sum(abs(r_new - r_old))
        
        if err < N*threshold:
            return r_new
        else:
            #update r_old and re-inizialize r_new
            r_old = r_new.copy()
            r_new = np.full(shape=N, fill_value=((1.0-beta)/N))
            
         
    return r_new
    
print("Ranking")
print("")
scores = PageRank(nodes, edges)
printRanking(nodes, scores)
def PageRank2(nodes, edges, beta=0.85, threshold=1.0e-6, max_iterations=100):

    '''
    Given a dictionary of nodes, a dictionary of edges of the form: 
    edges = {node_i : {'Degree': d, 'Destinations':[]}, node_j : ... } 
    the parameter beta, the threshold of errors tol and the maximum
    number of iteration to be done max_iterations, returns the ranking of the nodes 
    considering dead ends

    '''
    
    N = len(nodes.keys())
    
    #initialize r_old and r_new
    r_old = np.full(shape=N, fill_value=1.0/N)
    r_new_temp = np.full(shape=N, fill_value=0.0)

    for _ in range (max_iterations):
        for node in edges.keys():
            
            #update just the destinations of the considered node
            for dest_j in edges[node]["Destinations"]:
                r_new_temp[dest_j] += beta*(r_old[node]/edges[node]["Degree"])
                         
        r_new = r_new_temp.copy() + np.full(shape=N, fill_value=((1-sum(r_new_temp))/N))
        
        #check if the error is small enough 
        err = sum(abs(r_new - r_old))
        if err < N*threshold:
            return r_new
        
        #update r_old and re-inizialize r_new
        r_old = r_new.copy()
        r_new_temp = np.full(shape=N , fill_value=0.0)
    
    return r_new
    
print("Ranking")
print("")
scores = PageRank2(nodes, edges)
printRanking(nodes, scores)
def PageRank3(nodes, edges, beta=0.85, threshold=1.0e-6, max_iterations=100):

    '''
    Given a dictionary of nodes, a dictionary of edges of the form: 
    edges = {node_i : {'Degree': d, 'Destinations':[]}, node_j : ... } 
    the parameter beta, the threshold of errors tol and the maximum
    number of iteration to be done max_iterations, returns the ranking of the nodes
    considering dead ends

    '''
    
    N = len(nodes.keys())
    
    #initialize r_old and r_new
    r_old = np.full(shape=N , fill_value=1.0/N)
    r_new = np.full(shape=N , fill_value=((1.0-beta)/N))
    
    dead_ends = findDeadEnds(edges)

    for _ in range (max_iterations):
        
        dead_ends_sum = sum(r_old[j] for j in dead_ends)
        for node in nodes.keys():
            
            if node in edges.keys():
                #update just the destinations of the considered node
                for dest_j in edges[node]["Destinations"]:                    
                    r_new[dest_j] += beta*(r_old[node]/edges[node]["Degree"])  
                
            r_new[node] += (beta/N)*dead_ends_sum
                         
        #check if the error is small enough 
        err = sum(abs(r_new - r_old))
        
        if err < N*threshold:
            return r_new
        else:
            #update r_old and re-inizialize r_new
            r_old = r_new.copy()
            r_new = np.full(shape=N , fill_value=((1.0-beta)/N))
    
    return r_new
    
    
print("Ranking")
print("")
scores = PageRank3(nodes, edges)
printRanking(nodes, scores)<jupyter_output>Ranking

1 : blogspot.com --> 0.085424
-----------------------------
2 : creativecommons.org --> 0.024220
-----------------------------
3 : wikipedia.org --> 0.021583
-----------------------------
4 : canalblog.com --> 0.017731
-----------------------------
5 : youtube.com --> 0.016119
-----------------------------
6 : google.com --> 0.015904
-----------------------------
7 : tumblr.com --> 0.015904
-----------------------------
8 : wikimedia.org --> 0.015600
-----------------------------
9 : rea-group.com --> 0.015058
-----------------------------
10 : yahoo.com --> 0.013151
-----------------------------
11 : lockerz.com --> 0.012801
-----------------------------
12 : wordpress.com --> 0.012604
-----------------------------
13 : flickr.com --> 0.012587
-----------------------------
14 : dpreview.com --> 0.012143
-----------------------------
15 : apple.com --> 0.010850
-----------------------------
16 : twitter.com --> 0.010656
-----------------------------
17 : typepad.com --> 0.0106[...]
{'fraction_non_alphanumeric': 0.19559072922555115, 'fraction_numerical': 0.03286764112089154, 'mean_word_length': 1.9097744360902256, 'pattern_counts': {'":': 3, '<': 26, '<?xml version=': 0, '>': 57, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '439634', 'license': 'MIT', 'n_tokens_mistral': 4032, 'n_tokens_neox': 3756, 'n_words': 1058, 'path': '03_information_retrieval/assignments/03_pagerank/pagerank_assignment.ipynb', 'repo_name': 'rachelfanti/data_science', 'size': '12409'}