A Topological analysis of an alternative to the PageRank algorithm in weighted directed graphs

University essay from KTH/Matematik (Inst.)

Author: Natalia Andrea Londono Castrillon; [2019]

Keywords: ;

Abstract: In this thesis I use seven data-sets of weighted, directed graphs and present them as weighted, directed k-simplicial complexes. Then, I analyse the topological properties of each data-set in question using Flagser by \cite{flagser} and the cluster at the TU Darmstadt. I then proceed to run two versions of an alternative to the PageRank algorithm. One version contracting and deleting every node visited, and the other deleting only those visited nodes with less than 3 neighbours. I record snapshots of how the data-sets throughout the run of the algorithm, and compute the same topological properties computed before the run. I compare the changes in their homology to understand how the algorithm alters the topology of the graph. I also run several runs of the algorithms to get an idea of how the average graph looks like after the algorithm has been run. I record their new topological properties to find a correlation between the performance of the algorithm and the change in the topology of the graphs.

  AT THIS PAGE YOU CAN DOWNLOAD THE WHOLE ESSAY. (follow the link to the next page)