Aus Aifbportal
Wechseln zu:Navigation, Suche

Exploring Graph traversal algorithms for Knowledge Graphs

Sven Bulach

Informationen zur Arbeit

Abschlussarbeitstyp: Bachelor
Betreuer: Harald SackRussa Biswas
Forschungsgruppe: Information Service Engineering
Partner: FIZ Karlsruhe
Archivierungsnummer: 4589
Abschlussarbeitsstatus: Abgeschlossen
Beginn: 01. Mai 2020
Abgabe: 02. November 2020

Weitere Informationen

The problem of graph traversal in graph theory refers to the mechanism of traversing every edge and vertex in a graph in a systematic way. Graph walk is one of the ways of graph traversal. A walk is a sequence of vertices and edges of a graph, with repeated nodes and edges. A path is a walk without repeated vertices. This is a well studied problem in the field of Graph Theory [1]. This thesis focuses on exploring different graph traversal algorithms in the pretext of Knowledge Graphs (KG). A KG is a directed graph which consists of a set of entities denoting real world objects and relations between them [2]. The entities are the nodes in the graph and the edge between two nodes represents the relation between these entities. Therefore, every edge in a KG has a label. DBpedia, Wikidata, Freebase, YAGO are some popular open KGs. In this work, the focus would be on exploring the graph traversal algorithms on DBpedia and compare their efficiency w.r.t computational (space and time) complexity considering the fact that KGs contain millions of facts. Therefore, the goal would be finding the existing most efficient graph traversal algorithms which are applicable to find paths between two nodes in KGs by comparison.

[1] [2]

Ausschreibung: Download (pdf)