Department of Computing

COMP348 Document Processing and the Semantic Web

Tutorial Week 10

Graphs for NLP

Consider the following directed graph with weights on the edges:

G = (V,E)
V = {A,B,C,D,E}
E = {<A,B>:1, <A,D>:4, <C,A>:3, <D,B>:2, <D,E>:4, <E,C>:2}

1. Draw the graph.
2. Represent the graph as an adjacency matrix; how would you represent the edge weights in this matrix?
3. Represent the graph as an adjacency list; how would you represent the edge weights in this list?
4. Find a minimum spanning tree by applying Prim's algorihm.
5. Do three iterations of the method to compute the PageRank of all of the vertices in the graph.

A simple method to build a graph out of this text is to represent each word as a vertex, and add edges according to cooccurrence of words in a context window. For example, suppose that you use a context window of 5 words. Two words are connected if they occur in the window. The edges can be weighted according to the number of times the pair of words appears in a context window.

1. Draw the graph of the above text. In groups, discuss what would be the use of such a graph.

The specifications of assignment 2 are ready. We will use part of this tutorial to discuss issues related with the assignment.