Betreuer: Harald Sack, Russa Biswas
Forschungsgruppe: Information Service Engineering
Partner: FIZ Karlsruhe
Beginn: 01. Mai 2020
Abgabe: 02. November 2020
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 . 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 . 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.
Ausschreibung: Download (pdf)