Natalia Andrea Londono Castrillon: A Topological analysis of an alternative to the PageRank algorithm in weighted directed graphs

Time: Thu 2019-11-21 13.00 - 14.00

Lecturer: Natalia Andrea Londono Castrillon

Location: KTH, 3418

Abstract

We provide a first test and overview of an alternative to Google's PageRank algorithm using persistent homology and topological data analysis. First, we present a data-set consisting of weighted, directed graphs. Then, we explain how we can transform said graphs to weighted, directed simplicial complexes. After that, we compute the persistent homology of the resulting complexes using Flagser by Daniel Luetgehetmann.

Once we have the starting homological data, we introduce the two versions of the algorithm. One version contracts and deletes every node visited. The other deletes only visited nodes with less than 3 neighbours. We run the algorithm and re-compute persistent homology. Using the results, we analyse changes in the homology to determine how the algorithm changes the topological structure of our data-sets. Subsequently, we try to answer the question on whether there is a correlation between the changes in the persistent homology and the effectiveness and speed of the algorithm.

Page responsible:webmaster@math.kth.se
Belongs to: Department of Mathematics
Last changed: Nov 15, 2019