Basser Seminar Series

Approximation algorithms for the link building game using backlinks

Speaker: Dr Taso Viglas
School of Information Technologies, The University of Sydney

Time: Friday 20 November 2009, 4:00-5:00pm
Refreshments will be available from 3:30pm

Location: The University of Sydney, School of IT Building, Lecture Theatre (Room 123), Level 1

Add seminar to my diary

Abstract

The PageRank algorithm is an example of a ranking algorithm that assigns scores to the nodes in a network, or any other entities in a linked structure such as webpages and the internet or sets of documents with references/citations. The PageRank score provides (defines) a measure of "importance" for the nodes, based on the link structure of the network.

In this work we look at the problem of maximizing the ranking of a given target node in a large linked structure, by adding k new links. We consider the case where the new links must point towards the given target node (backlinks), and the ranking is computed using the PageRank algorithm. We consider variants of greedy selection algorithms for choosing the backlinks and show lower bounds for the approximation ratio they can achieve. The bounds imply that these simple greedy algorithms will return solutions that are far from the optimal for certain cases. Starting from a natural mixed integer linear program formulation for the link building problem, we show that the selection of backlinks can be restricted to a subset of "good" candidate vertices that has a simple and intuitive characterization. Based on that result, we present an algorithm that has good practical performance in terms of approximation ratio.

This is joint work with Martin Olsen from the University of Aarhus.

Speaker's biography

Taso Viglas is a senior lecturer in the School of IT, University of Sydney. His main research interests include algorithmic game theory and computational complexity theory. Taso received his PhD from Princeton University in 2002. He was a postoctoral fellow at the University of Toronto for two years, before joining the University of Sydney in July 2004.