Short Course: Ranking and labeling graphs: Analysis of links and node attributes

Instructor: Soumen Chakrabarti, IIT Bombay


We will study techniques for ranking and labeling nodes in a graph, based on the link structure of the graph as well as attributes of the nodes. Ranking and labeling have obvious applications in Web search and page classification, but the range of applications is widening to finer-grained entity-relationship graphs where nodes represent entities like people, emails, papers, organizations and locations and edges represent relations like works-for, wrote, cited, is-located-in and so on. Applications also include annotating unstructured and semistructured sources with type tags which can then be indexed for search.

On the subject of ranking, we will cover the following topics (two hours):

On the subject of labeling, we will cover the following topics (1.5 hours):

Only basic calculus and matrix algebra will be assumed. There might be some small experiments using Scilab and Java and small-scale data sets.