Steiner Tree Generation in Relationship Graphs[go to overview]
We introduce an algorithm currently studied by us for relationship query over large relationship graphs, which can be considered from algorithmic point of view as a Steiner Tree problem. The algorithm runs in two phases. In the first phase, it tries to quickly build a first tree that interconnects all nodes from a graph. In the second phase it aims to iteratively improve the current tree by scanning and pruning its neighborhood. We want to apply the algorithm to Project Reveal, where sets of entities detected in social media are matched onto public linked data knowledge graphs to find the coherence relations between context items.
03.04.14 - 08:15