Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Topological analysis of an alternative to the PageRank algorithm in weighted directed graphs
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
2019 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
En topologisk analys av ett alternativ till PageRank-algoritmen för weighted riktade grafer (Swedish)
Abstract [en]

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.

Abstract [sv]

Vi analyserar sju datamängder av viktade, riktade grafer med hjälp av homologi. Det första steget i analysen är att representera graferna som viktade, riktade k-simpliciella komplex. I det andra steget används Flagser av Luetgehetmann för att beskriva egenskaperna hos de erhållna komplexen. För beräkningsändamål används klustret vid TU Darmstadt. Två alternativa versioner av PageRank-algoritmen körs på data. En version där varje nod som besöks tas bort. Den andra versionen raderar bara de besökta noderna med mindre än 3 grannar. Snapshots av erhållen information under körningen av algoritmerna registreras. För varje steg beräknas samma topologiska egenskaper. Vi jämför förändringarna i homologi för att förstå hur algoritmen förändrar grafernas topologi. Vi kör också algoritmerna flera gånger för att få en uppfattning om hur den genomsnittliga grafen ser ut efter att algoritmen har körts. Vi registrerar deras nya topologiska egenskaper för att hitta en korrelation mellan prestandan för algoritmen och förändringen i topologin.

Place, publisher, year, edition, pages
2019.
Series
TRITA-SCI-GRU ; 2019:391
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-263764OAI: oai:DiVA.org:kth-263764DiVA, id: diva2:1375766
Subject / course
Mathematics
Educational program
Master of Science - Mathematics
Supervisors
Examiners
Available from: 2019-12-06 Created: 2019-12-06 Last updated: 2019-12-06Bibliographically approved

Open Access in DiVA

fulltext(4104 kB)7 downloads
File information
File name FULLTEXT01.pdfFile size 4104 kBChecksum SHA-512
49636825f7c87cda83896dad9b3b81a1774e062581a84c4d927de2033fc5f008f08ee7be1c63f5d78b2a251158f2632de93ff0d9d402341ce28d788c009300e6
Type fulltextMimetype application/pdf

By organisation
Mathematics (Dept.)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 7 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 46 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf