<jupyter_start><jupyter_text>PageRank AlgorithmThis notebook implements the PageRank algorithm, prepared as a homework in BLG202E - Numerical Methods in CE class at ITU, Spring 2020.<jupyter_code>!pip install mechanize
import numpy as np #For arrays and linear algebra routines
from mechanize import Browser #For getting the names of the papers from arXiv in part 3 results
                              #Not necessary, but to use it, above cell must be run to install mechanize library 
eps = 1e-10<jupyter_output><empty_output><jupyter_text>Motivating Example: Academic Ranking System Our motivating example uses the paper citation network of Arxiv High Energy Physics Theory category. We will rank the papers by their influence. Data is represented as a directed graph, and we have the list of edges in a text file. We will start by loading the text file that contains the directed graph into a NumPy array.<jupyter_code>array = np.genfromtxt("cit-HepTh.txt", dtype=int)<jupyter_output><empty_output><jupyter_text>Let's see the first 10 edges.<jupyter_code>print(array[0:10])<jupyter_output>[[   1001 9304045]
 [   1001 9308122]
 [   1001 9309097]
 [   1001 9311042]
 [   1001 9401139]
 [   1001 9404151]
 [   1001 9407087]
 [   1001 9408099]
 [   1001 9501030]
 [   1001 9503124]]<jupyter_text>We will create a transition matrix from the list that contains links between the nodes of the graph. A transition matrix shows transitions from nodes to other nodes and the probability that transition happens.These weights or normalization factors are calculated by taking $\frac{1}{\textrm{(no of outgoing links from that node)}}$. Following code will define a function with parameter **arr**: multidimensional array of edges, and returns **labels**: array consisting of distinct nodes and **weights**: a dictionary that maps these nodes to their weights.<jupyter_code>def createWeights(arr):
    labels, counts = np.unique(arr[:,0], return_counts=True) ##Finds the unique entries in first column, returns their values 
                                                              #and their counts to calculate weights
    weight_dict = dict()
    for index, label in enumerate(labels):                   ##Creates a dictionary that holds the normalization factor,
        weight_dict[label] = 1 / counts[index]               # 1/(number of outgoing links) for every paper ID in labels

    return labels, weight_dict
labels, weights = createWeights(array)<jupyter_output><empty_output><jupyter_text>Following code will initialize transition matrix, finds the cells that represent transitions using a for loop that examines each node and links from that node, and fills in the cell with the weight specified in weights dictionary created above.<jupyter_code>def createTransitionMatrix(arr, labels, weight_dict):
    transitionMatrix = np.zeros((labels.size,labels.size))
    
    for i, label in enumerate(labels):
        links_from_label = arr[np.nonzero(label == arr[:,0]),1][0]
      #  if links_from_label.shape == (0,):                          ##For dangling nodes, nodes that have no outgoing links
      #      weight_dict[label] = 1 / labels.size                     
      #      links_to_label = labels                                  
        transitionMatrix[np.searchsorted(labels, links_from_label),i] = weight_dict[label]
    
    return transitionMatrix
rankMatrix = createTransitionMatrix(array, labels, weights)<jupyter_output><empty_output><jupyter_text>We expect our transition matrix to be column-stochastic, and we also expect it to be a sparse matrix it is mostly populated by zeros. Operations on sparse matrices can be done by some faster methods, so sparsity is an advantage in speed.Now we will define and run two functions to test these attributes of our matrix. Results will show that our expectations hold.<jupyter_code>def checkStochastic(matrix):
    eps = 1e-10
    print("Sums of columns that do not add to 1 in a reasonable error margin {} will be shown.".format(eps))
    for i in matrix.sum(0):
        if not (i - 1 < eps):
            print(i)
    print("Calculation finished, average value of sums of all columns is {}.".format(np.mean(matrix.sum(0))))

def checkSparsity(matrix):
    zeros = np.count_nonzero(matrix==0)
    elements = matrix.size
    sparse_rate = np.divide(zeros,elements)
    print("There are {} elements in total, {} of them are zero.".format(elements, zeros))
    print("Sparsity rate of this matrix is %{}".format(sparse_rate*100))
    return sparse_rate
checkStochastic(rankMatrix)
sparsity = checkSparsity(rankMatrix)<jupyter_output>Sums of columns that do not add to 1 in a reasonable error margin 1e-10 will be shown.
Calculation finished, average value of sums of all columns is 0.9958169865008099.
There are 627953481 elements in total, 627601470 of them are zero.
Sparsity rate of this matrix is %99.94394314059069<jupyter_text>---Now that we have the required matrix, we can solve the equation\begin{equation}A x = x\end{equation}where A is the matrix, and x is the result vector that contains the rank. We will solve this by **power method**, by repeatedly multiplying an arbitrary vector* by our matrix until the difference in resulting vectors of two iterations is smaller than epsilon.*While any arbitrary vector should work, it is better practice to use an all ones vector normalized by the size of itself, so initially every rank is equal and vector sums up to one. We will follow this practice.<jupyter_code>def solveRank(rankMatrix):
    eps = 1e-7
    v0 = np.ones(rankMatrix.shape[0]) / rankMatrix.shape[0]
#   v0 = np.random.random(rankMatrix.shape[0] / rankMatrix.shape[0])

    counter = 1
    while True:
        v = np.dot(rankMatrix, v0)
        v = v / np.linalg.norm(v)
        if (np.mean(np.abs(np.subtract(v,v0))) < 2*eps):
            break
        
#        print("Error: {}".format(np.mean(np.abs(np.subtract(v,v0)))))   ##Uncomment this line to print error in each step
                                                                          #If this function is taking too long, printing the error may be a good idea for debugging
        counter += 1
        v0 = v
    
    print("Appropriate vector found in {} iterations, final difference between two iteration result vectors was less than {}.".format(counter,eps))
    return v
final = solveRank(rankMatrix)<jupyter_output>Appropriate vector found in 80 iterations, final difference between two iteration result vectors was less than 1e-07.<jupyter_text>Finally, we will rank our papers according to the resulting vector, and show the first 10 papers.<jupyter_code>def rankPagesDescending(labels, final):
    return labels[final.argsort()][::-1]
rankPagesDescending(labels, final)[0:10]<jupyter_output><empty_output><jupyter_text>Using the mechanize library, we can collect the information on these papers.<jupyter_code>ranking = rankPagesDescending(labels, final)
br = Browser()

for index,paper_id in enumerate(ranking[0:10]):
    str_id = str(paper_id)
    page_url = "https://arxiv.org/abs/hep-th/"
    while(len(str_id) < 7):
        str_id = '0' + str_id
    page_url += str_id
    br.open(page_url)
    paper_title = br.title()[17:]
    print("{}. paper ID is {}.".format(index + 1, paper_id))
    print("Name of the paper is: {}".format(paper_title))
    print(page_url)<jupyter_output>1. paper ID is 9201015.
Name of the paper is: An Algorithm to Generate Classical Solutions for String Effective Action
https://arxiv.org/abs/hep-th/9201015
2. paper ID is 9207016.
Name of the paper is: Noncompact Symmetries in String Theory
https://arxiv.org/abs/hep-th/9207016
3. paper ID is 9206003.
Name of the paper is: From Form Factors to Correlation Functions: The Ising Model
https://arxiv.org/abs/hep-th/9206003
4. paper ID is 209015.
Name of the paper is: Advances in String Theory in Curved Space Times
https://arxiv.org/abs/hep-th/0209015
5. paper ID is 9205071.
Name of the paper is: Novel Symmetry of Non-Einsteinian Gravity in Two Dimensions
https://arxiv.org/abs/hep-th/9205071
6. paper ID is 9202067.
Name of the paper is: Stringy Domain Walls and Other Stringy Topological Defects
https://arxiv.org/abs/hep-th/9202067
7. paper ID is 9201047.
Name of the paper is: Duality-Invariant Gaugino Condensation and One-Loop Corrected Kahler Potentials in String Theory
https://arxiv.org/abs[...]<jupyter_text>In some edge cases, the transition matrix above may not abide by the conditions algorithm requires. To account for those situations, there is a **damping factor** defined for the algorithm, which takes the weighted average of our transition matrix with a matrix of all ones. While transition matrix represents probabilities of going from one node to another, adding these damping factor will give us a chance to randomly go from any node to another.<jupyter_code>def addDamping(transitionMatrix, labels, p = 0.15):
    if(p < 0 or p > 1):
        print("Please try again with a damping factor in interval [0,1].")
        return None
    rankMatrix = (1 - p) * transitionMatrix + p * ((1/labels.size) * np.ones((labels.size,labels.size)))
    return rankMatrix
rankMatrix = addDamping(rankMatrix, labels)
checkStochastic(rankMatrix)
sparsity = checkSparsity(rankMatrix)<jupyter_output>Sums of columns that do not add to 1 in a reasonable error margin 1e-10 will be shown.
Calculation finished, average value of sums of all columns is 0.9964444385253646.
There are 627953481 elements in total, 0 of them are zero.
Sparsity rate of this matrix is %0.0<jupyter_text>We see that while stochastic structure of the matrix holds, it is no longer a sparse matrix after adding damping factor. This is because now every node has the probability to go to any other node, even if this is a very small probability. So we do not have any 0 cells in our matrix anymore.Now, we will solve out matrix again.<jupyter_code>final = solveRank(rankMatrix)
ranking = rankPagesDescending(labels, final)
br = Browser()

for index,paper_id in enumerate(ranking[0:10]):
    str_id = str(paper_id)
    page_url = "https://arxiv.org/abs/hep-th/"
    while(len(str_id) < 7):
        str_id = '0' + str_id
    page_url += str_id
    br.open(page_url)
    paper_title = br.title()[17:]
    print("{}. paper ID is {}.".format(index + 1, paper_id))
    print("Name of the paper is: {}".format(paper_title))
    print(page_url)<jupyter_output>Appropriate vector found in 30 iterations, final difference between two iteration result vectors was less than 1e-07.
1. paper ID is 9201015.
Name of the paper is: An Algorithm to Generate Classical Solutions for String Effective Action
https://arxiv.org/abs/hep-th/9201015
2. paper ID is 9207016.
Name of the paper is: Noncompact Symmetries in String Theory
https://arxiv.org/abs/hep-th/9207016
3. paper ID is 9205071.
Name of the paper is: Novel Symmetry of Non-Einsteinian Gravity in Two Dimensions
https://arxiv.org/abs/hep-th/9205071
4. paper ID is 209015.
Name of the paper is: Advances in String Theory in Curved Space Times
https://arxiv.org/abs/hep-th/0209015
5. paper ID is 9202067.
Name of the paper is: Stringy Domain Walls and Other Stringy Topological Defects
https://arxiv.org/abs/hep-th/9202067
6. paper ID is 9201047.
Name of the paper is: Duality-Invariant Gaugino Condensation and One-Loop Corrected Kahler Potentials in String Theory
https://arxiv.org/abs/hep-th/9201047
7. paper [...]<jupyter_text>--- Since our dataset is very big, it is not easy to say if our algorithm correctly chooses the rankings. So we will test the same functions on a smaller dataset below, and we will compare the results with our expectation that will be computed by hand mathematically.<jupyter_code>def calculateRankVector(data, damping=False):
    labels, weights = createWeights(data)
    rankMatrix = createTransitionMatrix(data, labels, weights)
    if damping:
        rankMatrix = addDamping(rankMatrix, labels)
    resultVector = solveRank(rankMatrix)
    return resultVector
filename = "testset.txt" #Change the filename to test it with another file 
data = np.genfromtxt(filename, dtype = str)
resultVector = calculateRankVector(data, damping=True)
ranking = rankPagesDescending(labels, resultVector)
print(ranking)
print(resultVector.reshape(resultVector.size,1))<jupyter_output>Appropriate vector found in 20 iterations, final difference between two iteration result vectors was less than 1e-07.
['A' 'D' 'C' 'B']
[[0.63395272]
 [0.34267715]
 [0.444879  ]
 [0.53175087]]
{'fraction_non_alphanumeric': 0.08241714148142204, 'fraction_numerical': 0.04156969745606292, 'mean_word_length': 3.9062992125984253, 'pattern_counts': {'":': 0, '<': 47, '<?xml version=': 0, '>': 43, 'https://': 15, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '332787', 'license': 'MIT', 'n_tokens_mistral': 3998, 'n_tokens_neox': 3519, 'n_words': 1438, 'path': 'pagerank.ipynb', 'repo_name': 'marifdemirtas/pagerank', 'size': '12461'}