0

According to the specifications, the iterative PageRank function given corpus0 should return the following:

PageRank Results from Iteration
  1.html: 0.2202
  2.html: 0.4289
  3.html: 0.2202
  4.html: 0.1307

My code returns

PageRank Results from Iteration
  1.html: 0.2199
  2.html: 0.4292
  3.html: 0.2199
  4.html: 0.1310

I've attached my code below for the iterative function, and I would appreciate any feedback! Thank you so much in advance!

def iterate_pagerank(corpus, damping_factor):
    """
    Return PageRank values for each page by iteratively updating
    PageRank values until convergence.

    Return a dictionary where keys are page names, and values are
    their estimated PageRank value (a value between 0 and 1). All
    PageRank values should sum to 1.
    """
    
    # Assign each page with rank of 1/n
    page_rank = dict()
    for page in corpus:
        page_rank[page] = 1/(len(corpus))

    # Iterate through all pages and calculate page rank
    prev_page_rank = copy.deepcopy(page_rank)
    anticorpus = make_anti(corpus)
    page_rank = iterate_formula(corpus, anticorpus, damping_factor, prev_page_rank)
    while dict_diff_over_threshold(prev_page_rank, page_rank, 0.0001):
        prev_page_rank = copy.deepcopy(page_rank)
        page_rank = iterate_formula(corpus, anticorpus, damping_factor, prev_page_rank)
        


    # Make sure the numbers add up to basically 1
    total = round(sum(page_rank.values()), 3)
    if total != 1:
        print(page_rank)
        raise Exception(f"Distribution sum is {total} instead of 1")

    return page_rank
    
def dict_diff_over_threshold(dict1, dict2, threshold):
    '''
    Returns true if the difference between any two corresponding values
    in the two dictionaries exceed the threshold
    Otherwise returns False
    '''
    if len(dict1) != len(dict2) or dict1.keys() != dict2.keys():
        raise Exception("You messed up")
    new_dict = dict()
    for key in dict1:
        new_dict[key] = abs(dict1[key] - dict2[key])
    if sum(new_dict.values()) > threshold:
        return True
    return False
    
def make_anti(corpus):
    '''
    Creates a dictionary whose keys are pages and values are the pages that 
    link to keys
    '''
    for key in corpus:
        # If page has no links
        if not corpus[key]:
            # Make page have links to all pages in corpus
            corpus[key] = set(link for link in corpus)

    # Find all pages that link to passed page
    anticorpus = dict()

    # Creates opposite of corpus: each key's value is the set of pages that links to that key 
    for page in corpus:
        for backlink in corpus:
            # Check if backlink is a link in the forelink's page
            if backlink in corpus[page]:
                # Check if set has already been made
                if backlink in anticorpus:
                    anticorpus[backlink] = anticorpus[backlink].union([page])
                # Given set doesn't exist yet, make the set
                else:
                    anticorpus[backlink] = set([page])
    
    return anticorpus


def iterate_formula(corpus, anticorpus, damping_factor, current_rank):
    '''
    Finds the pages that link to a given page and their pagerank
    Uses these pageranks to calculate the new pagerank
    '''    
    # Get sum of pagerank/numlinks of backlinks
    total_prob = dict()

    # Iterate through backlinks and add pagerank/num of links on page
    for backlink in anticorpus:
        for page in anticorpus[backlink]:
            
            # If backlink already exists in total_prob
            if backlink in total_prob:
                total_prob[backlink] += current_rank[page]/len(corpus[page])
            else:
                total_prob[backlink] = current_rank[page]/len(corpus[page])

    # Plug into formula
    page_rank = dict()
    for prob in total_prob:
        page_rank[prob] = ((1 - damping_factor)/(len(corpus))) + (damping_factor * total_prob[prob])
    
    # Return the distribution
    return page_rank

0

You must log in to answer this question.

Browse other questions tagged .