<jupyter_start><jupyter_text>Initialisation of variables:<jupyter_code>import random
import numpy as np
import pandas as pd

edges = {(0,2),(2,0),(1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(6,3),(4,6),(6,4),(6,6),(5,6),(5,5)} # Dictionary containing graph edges 
list_of_edges = list(edges)                                                                   # A list of the edges - for slicing
number_of_edges = len(edges)                                                                  # Number of edges
pageDict = {}                                                           
    
for edge in edges:
    pageDict[edge[0]] = 0                                                                     # adds the unique pages to dictionary

pages = list(pageDict)                                                                        # converts dictionary to a list
number_of_pages = len(pages)                                                                  # calculate number of pages in graph<jupyter_output><empty_output><jupyter_text>Define a getNeighbours function:A page is passed as an argument into the method and a list of its adjacent neighbours is outputted.<jupyter_code># neigh = a list of neighbours
# edge = the edge currently being used from the list of edges

def getNeighbours(page):
    neigh=[]
    
    for x in range(number_of_edges):
        edge = list_of_edges[x]                 # Gets the specific edge from the list
        
        if edge[0] == page:                     # Checks the first value as this is where the edge comes from
            neigh.append(edge[1])               # This is where the edeg leads to. This page is appended to a list
    
    return neigh<jupyter_output><empty_output><jupyter_text>Testing the getNeighbours function:When the function is applied to the page 1, the neighbouring pages are 1 and 2, and when the function is applied to page 6, the neighbouring pages are 3, 4, and 6. Therefore the function works.<jupyter_code>print("Page 1 neighbours are: " + str(getNeighbours(1)))
print("Page 3 neighbours are: " + str(getNeighbours(6)))<jupyter_output>Page 1 neighbours are: [2, 1]
Page 3 neighbours are: [4, 6, 3]<jupyter_text>The random walk method: A random page is selected as a starting node. If the current iteration is divisable by the tel variable (the frequency of teleportations) with no remainder, then the page is randomly teleported to any other page within the graph to prevent dead ends, otherwise the walker randomly selects one of the neighbouring pages to move to. The frequencies of the pages are stored in a dicitonary and then divided by the total number of iterations to give normalised values.<jupyter_code># iters = the number of iterations
# a = the teleportation probability
# edges = the edges within the graph
# currentPage = the page which the walker is currently at
# dict_counter = the frequencies for each of the pages
# pageDict = dictionary for unique pages

def randomwalk(edges, a, iters):
    
    pageDict = {}                                                           
    dict_counter = {}                                                       
    
    for edge in edges:
        pageDict[edge[0]] = 0                                               # adds the unique pages to dictionary

    pages = list(pageDict)                                                  # converts dictionary to a list
    number_of_pages = len(pages)                                            # calculate number of pages in graph
    currentPage = random.choice(pages)                                      # randomly selects any page in the graph to start    
    
    for page in range(number_of_pages):
        dict_counter[page] = 0                                              # initialise dictionary with 0's for page freqencies 

    for _ in range(iters):            
        if random.uniform(0,1) < a:                                         # random float number from 0 to 1 selected
            currentPage = random.choice(pages)                              # randomly selects any page in the graph
        else:
            currentPage = random.choice(getNeighbours(currentPage))         # randomly selects a neighboured page 
        dict_counter[currentPage] += 1                                      # adds 1 to the frequency of current page
            
    for page in range(len(dict_counter)):
        dict_counter[page] = dict_counter[page] / iters                     # normalises the frequencies

    return dict_counter<jupyter_output><empty_output><jupyter_text>Running the random walk method:The method outputs the scores of each of the pages. It should be noted that the values will slightly change for this method each time it is run as it uses a randomiser. The dictionary is stored in the variable 'frequencies' so that it can be accessed later.<jupyter_code>frequencies = randomwalk(edges, 0.14, 10000)
frequencies<jupyter_output><empty_output><jupyter_text>Pagerank function:<jupyter_code># matrix = list of every probability for the page connections - transition matrix
# T = an N x N matrix full of 1/N
# alpha = the teleportation probability
# bias = the additional value added to every probability
# dictionary for unique pages

def pagerank(edges, a, iters):
    
    pageDict = {}                                                           
    
    for edge in edges:
        pageDict[edge[0]] = 0                          # adds the unique pages to dictionary

    pages = list(pageDict)                             # converts dictionary to a list
    number_of_pages = len(pages)                       # calculate number of pages in graph
    matrix = []
    T = 1/number_of_pages
    alpha = a
    bias = T * alpha

           
    for page in range(number_of_pages):
        connectedPages = getNeighbours(page)           # gets neighbours of current page
        row = [0] * number_of_pages                    # initialising list with a 0 frequency for each page of length 'number_of_pages'  


        if len(connectedPages) == 1:
            prob = 1                                   # probability is 1 if there's only 1 connected page
        else:
            prob = 1/len(connectedPages)               # probabilities are 1/n where n = number of nighbours 

        prob = (((1-alpha)*prob) + bias)               # teleportation formula applied to every page that is not equal to 0  
    
        for x in connectedPages:
            row[x] = prob                              # the pages probabilities stored in the list of row

        for y in range(len(row)):                      
            if row[y] == 0:
                row[y] += bias                         # teleportation formula applied to every page that is equal to 0

        matrix.append(row)                             # appends the row to the matrix

    trans_matrix = np.array(matrix)                    # convert the list of rows to a numpy array so it can be reshaped
    trans_matrix.reshape(7,7)                          # reshaped the array to be 
    
    a = [T] * number_of_pages                          # initialises each of the pages in the 'a' matrix to 1/n (T)

    for i in range(iters):
        a = np.matmul(a, trans_matrix)                 # multiplies the two matrixes (a and trans_matrix) iters amount of times,
                                                       # updating the value of a each time
    return a<jupyter_output><empty_output><jupyter_text>Running the pagerank method:The method outputs the scores of each of the pages. Unlike the random walk method, the values in the pagerank method will not change each time it is run. The final vector is stored in the variable 'vector' so that it can be accessed later.<jupyter_code>vector = pagerank(edges, 0.14, 10000)
vector<jupyter_output><empty_output><jupyter_text>The following is used to output the ranking results in order of both methods:Note that pages 1 and 5 will swap in the ranking with one another for the random walk method as they are both similar (they can loop back to themselves and have no incoming edges), and therefore the randomiser will have an impact upon there ranking order. The output helps to prove that both of the methods do converge to a steady state.<jupyter_code>import operator

pagedict = {}                                                                              # dictionary for the pagerank results
randomdict = {}                                                                            # dictionary for the random walk results

for x in range(number_of_pages):
    pagedict[x] = vector[x]                                                                # copies the vector dictionary across 

sortingPage = sorted(pagedict.items(), key=operator.itemgetter(1), reverse=True)           # sorts the pagerank method results
sortingRandom = sorted(frequencies.items(), key=operator.itemgetter(1), reverse=True)      # sorts the random walk method results

for x in range(number_of_pages):
    currentPage = sortingPage[x]                                                           # the current pagerank score for output
    currentRandom = sortingRandom[x]                                                       # the current random walk score for output
    
    print("\033[1mRanking number " + str(x+1) + ": \n\033[0mRandom Walk Method:       \033[1mPage " + str(currentRandom[0]) + " : " + str(currentRandom[1]))
    print("\033[0mPagerank Method:          \033[1mPage " + str(currentPage[0]) + " : " + str(currentPage[1]) + "\n")<jupyter_output>[1mRanking number 1: 
[0mRandom Walk Method:       [1mPage 6 : 0.3002
[0mPagerank Method:          [1mPage 6 : 0.3065874740538629

[1mRanking number 2: 
[0mRandom Walk Method:       [1mPage 3 : 0.2534
[0mPagerank Method:          [1mPage 3 : 0.24561198915656474

[1mRanking number 3: 
[0mRandom Walk Method:       [1mPage 4 : 0.2106
[0mPagerank Method:          [1mPage 4 : 0.21350156456609684

[1mRanking number 4: 
[0mRandom Walk Method:       [1mPage 2 : 0.1174
[0mPagerank Method:          [1mPage 2 : 0.1120131090365158

[1mRanking number 5: 
[0mRandom Walk Method:       [1mPage 0 : 0.0527
[0mPagerank Method:          [1mPage 0 : 0.05211042459046785

[1mRanking number 6: 
[0mRandom Walk Method:       [1mPage 1 : 0.0354
[0mPagerank Method:          [1mPage 5 : 0.0350877192982456

[1mRanking number 7: 
[0mRandom Walk Method:       [1mPage 5 : 0.0303
[0mPagerank Method:          [1mPage 1 : 0.03508771929824559<jupyter_text>A better way of visualising this can be seen below in a dataframe:<jupyter_code>final_res = []                                    # A list of the pageranking scores for each of the iterations
col=[]                                            # List of names of the dataframe columns (the number of iterations) 
x = 12                                            # The number of iterations

for i in range(x):
    final_res.append(pagerank(edges, 0.14, i))    # Calls the pagerank function and appends the vector to the final_res list
    if i == 0:
        col.append("x")                           # The starting value of choosing any possible page 
    else:
        col.append("xP^" + str(i))                # The column name

trans_matrix = np.array(final_res)                # Puts array into a numpy array so it can be adapted with ease
trans_matrix = trans_matrix.reshape(x,7)          # Reshapes matrix so it becomes matrix rather than 1D array
trans_matrix = trans_matrix.transpose()           # Transposed to ensure the pages are listed as rows rather than columns
dataframe=pd.DataFrame(trans_matrix, columns=col) #Put into a dataframe for an easier visalisation 
dataframe<jupyter_output><empty_output><jupyter_text>Q3:To determine that both methods result in a steady state can easily be done by simply setting the iteration values of the methods to a high number such as 10000. By doing so, this outputs the resulting ranking of 6, 4, 3, 2, 0, 1, 5 and this ranking does not change no matter how many times the methods are run (with the exception of pages 1 and 5 for the random walk method as previously explained). However, it's difficult to determine a specific number of iterations required for the random walk method to result in a steady state, as the randomness of the approach causes the page scores to change slightly each time the function is run. Therefore as the steady state of the pagerank is reached after approximately 7 iterations, this number of iterations should be used in the randomwalk method as a benchmark to test. The random walk method does not even converge to a steady state after 12 iterations and therefore the pagerank method is proven to converge faster.      Q4:Users cannot improve their page ranking score by changing the number of outgoing edges to other pages. If they were to do so, this would simply give their page a poorer ranking score as other pages which now have an additional incoming edge will be the pages that gain a better score from doing this instead. Pagerank uses the incoming edges to determine their rankings rather than the outgoing edges. Therefore if a page with a high page ranking score is pointing to their page, their page will then have a higher score as it is more likely to be accessed than a page with none or very few incoming edges from low frequently visited pages. Proof of this follows:     This is the set of results which will be compared with the tests:![Title](comparingResults.png) As you can see with the first example below, the edges dictionary contains more outgoing links to other pages from page 6. It is therefore expected that the ranking score of page 6 should be a smaller value than the original 0.304274, whilst the other pages which now have an additional input edge (pages 1, 2 and 5) should have larger page ranking scores:<jupyter_code>import random
import numpy as np
import pandas as pd

edges = {(0,2),(2,0),(1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(6,3),(4,6),(6,4),(6,6),(5,6),(5,5),    
         (6,1),(6,2),(6,5)}                       # The edges that are added to the original edges dictionary for testing 

pageDict = {}                                                           
    
for edge in edges:
    pageDict[edge[0]] = 0                         # adds the unique pages to dictionary

pages = list(pageDict)                            # converts dictionary to a list
number_of_pages = len(pages)                      # calculate number of pages in graph
list_of_edges = list(edges)                       # A list of the edges - for slicing
number_of_edges = len(edges)                      # Number of edges
dict_counter = {}                                 # Dictionary of pages & their scores
final_res = []                                    # A list of the pagerankings of each of the iterations
col=[]                                            # List of names of the dataframe columns (the number of iterations) 
x = 12                                            # The number of iterations

for i in range(x):
    final_res.append(pagerank(edges, 0.14, i))    # Calls the pagerank function
    if i == 0:
        col.append("x")                           # The starting value of choosing any possible page 
    else:
        col.append("xP^" + str(i))                # The column name

trans_matrix = np.array(final_res)                # Puts array into a numpy array so it can be adapted with ease
trans_matrix = trans_matrix.reshape(x,7)          # Reshapes matrix so it becomes matrix rather than 1D array
trans_matrix = trans_matrix.transpose()           # Transposed to ensure the pages are listed as rows rather than columns
dataframe=pd.DataFrame(trans_matrix, columns=col) #Put into a dataframe for an easier visalisation 
dataframe<jupyter_output><empty_output><jupyter_text>The dataframe that is outputted proves this theory as the score is now 0.199284 whilst the scores of pages 1, 2 and 5 have improved. Another test to prove this can be seen below where page 6 has three more input edges than in the original graph. This therefore should have an improved page ranking score for page 6 (0.304274), whilst pages 1 (0.035098), 2 (0.114326) and 3 (0.245602) should have smaller page ranking scores.<jupyter_code>import random
import numpy as np
import pandas as pd

edges = {(0,2),(2,0),(1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(6,3),(4,6),(6,4),(6,6),(5,6),(5,5),    
         (1,6),(2,6),(3,6)}                       # The edges that are added to the original edges dictionary for testing 

pageDict = {}                                                           
    
for edge in edges:
    pageDict[edge[0]] = 0                         # adds the unique pages to dictionary

pages = list(pageDict)                            # converts dictionary to a list
number_of_pages = len(pages)                      # calculate number of pages in graph
list_of_edges = list(edges)                       # A list of the edges - for slicing
number_of_edges = len(edges)                      # Number of edges
dict_counter = {}                                 # Dictionary of pages & their scores
final_res = []                                    # A list of the pagerankings of each of the iterations
col=[]                                            # List of names of the dataframe columns (the number of iterations) 
x = 12                                            # The number of iterations

for i in range(x):
    final_res.append(pagerank(edges, 0.14, i))    # Calls the pagerank function
    if i == 0:
        col.append("x")                           # The starting value of choosing any possible page 
    else:
        col.append("xP^" + str(i))                # The column name

trans_matrix = np.array(final_res)                # Puts array into a numpy array so it can be adapted with ease
trans_matrix = trans_matrix.reshape(x,7)          # Reshapes matrix so it becomes matrix rather than 1D array
trans_matrix = trans_matrix.transpose()           # Transposed to ensure the pages are listed as rows rather than columns
dataframe=pd.DataFrame(trans_matrix, columns=col) # Put into a dataframe for an easier visalisation 
dataframe<jupyter_output><empty_output><jupyter_text>The outputted results prove this theory once again. The score of page 6 has increased to 0.409981, whilst the scores of 1, 2 and 3 have decreased to 0.028038, 0.075699, and 0.215593 respectively.         The code below used was used for testing purposes:  The pagerank function which returns a transition matrix<jupyter_code># matrix = list of every probability for the page connections - transition matrix
# T = an N x N matrix full of 1/N
# alpha = the teleportation probability
# bias = the additional value added to every probability
# dictionary for unique pages

def pagerank(edges, a, iters):
    
    pageDict = {}                                                           
    
    for edge in edges:
        pageDict[edge[0]] = 0                          # adds the unique pages to dictionary

    pages = list(pageDict)                             # converts dictionary to a list
    number_of_pages = len(pages)                       # calculate number of pages in graph
    matrix = []
    T = 1/number_of_pages
    alpha = a
    bias = T * alpha


    for page in range(number_of_pages):
        connectedPages = getNeighbours(page)           # gets neighbours of current page
        row = [0] * number_of_pages                    # initialising list with a 0 frequency for each page of length 'number_of_pages'  

        if len(connectedPages) == 1:
            prob = 1                                   # probability is 1 if there's only 1 connected page
        else:
            prob = 1/len(connectedPages)               # probabilities are 1/n where n = number of nighbours 


        for y in range(number_of_pages):
            for x in connectedPages: 
                if y == x:
                    row[x] = prob                      # adds each of the pages probabilities to the row list

        matrix.append(row)                             # appends the row to the matrix

    trans_matrix = np.array(matrix)                    # convert the list of rows to a numpy array so it can be reshaped
    trans_matrix.reshape(7,7)                          # reshaped the array to be 


    return trans_matrix
trans_matrix = pagerank(edges, 0.14, 100)

dataframe=pd.DataFrame(trans_matrix, columns=['0','1','2', '3', '4', '5', '6']) #Put into a dataframe for an easier visalisation 
dataframe<jupyter_output><empty_output><jupyter_text>The pagerank function which returns a transition matrix including teleporting<jupyter_code># matrix = list of every probability for the page connections - transition matrix
# T = an N x N matrix full of 1/N
# alpha = the teleportation probability
# bias = the additional value added to every probability
# dictionary for unique pages

edges = {(0,2),(2,0),(1,1),(1,2),(2,2),(2,3),(3,3),(3,4),(6,3),(4,6),(6,4),(6,6),(5,6),(5,5)} # Dictionary containing graph edges 

def pagerank(edges, a, iters):
    
    pageDict = {}                                                           
    
    for edge in edges:
        pageDict[edge[0]] = 0                          # adds the unique pages to dictionary

    pages = list(pageDict)                             # converts dictionary to a list
    number_of_pages = len(pages)                       # calculate number of pages in graph
    matrix = []
    T = 1/number_of_pages
    alpha = a
    bias = T * alpha

           
    for page in range(number_of_pages):
        connectedPages = getNeighbours(page)           # gets neighbours of current page
        row = [0] * number_of_pages                    # initialising list with a 0 frequency for each page of length 'number_of_pages'  


        if len(connectedPages) == 1:
            prob = 1                                   # probability is 1 if there's only 1 connected page
        else:
            prob = 1/len(connectedPages)               # probabilities are 1/n where n = number of nighbours 

        prob = (((1-alpha)*prob) + bias)               # teleportation formula applied to every page that is not equal to 0  
    
        for x in connectedPages:
            row[x] = prob                              # the pages probabilities stored in the list of row

        for y in range(len(row)):                      
            if row[y] == 0:
                row[y] += bias                         # teleportation formula applied to every page that is equal to 0

        matrix.append(row)                             # appends the row to the matrix

    trans_matrix = np.array(matrix)                    # convert the list of rows to a numpy array so it can be reshaped
    trans_matrix.reshape(7,7)                          # reshaped the array to be 
    
    
    return trans_matrix
trans_matrix = pagerank(edges, 0.14, 100)

dataframe=pd.DataFrame(trans_matrix, columns=['0','1','2', '3', '4', '5', '6']) #Put into a dataframe for an easier visalisation 
dataframe<jupyter_output><empty_output><jupyter_text>Function which returns the amount of pages each page links to:<jupyter_code># outgoing_dict = dictionary with pages as keys and their frequencies as values
# edge = the current edge from the list of edges which is being utilised

outgoing_dict = dict.fromkeys(range(number_of_pages),0)

for page in range(number_of_pages):
    for x in range(number_of_edges):
        edge = list_of_edges[x]                 # Gets the specific edge from the list

        if edge[0] == page:                     # Checks the first value as this is where the edge comes from
            outgoing_dict[page] += 1 

outgoing_dict<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0684493777329297, 'fraction_numerical': 0.026446350487722838, 'mean_word_length': 2.044285165749392, 'pattern_counts': {'":': 1, '<': 56, '<?xml version=': 0, '>': 55, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 87, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '14', 'dir': 'jupyter-structured-clean-dedup', 'id': '621308', 'license': 'MIT', 'n_tokens_mistral': 6514, 'n_tokens_neox': 5918, 'n_words': 2541, 'path': 'Page Rank.ipynb', 'repo_name': 'dan050100/Random-Walk-and-Page-Ranking', 'size': '23784'}