20/11/2009 - 16:00

20/11/2009 - 17:00

Seminar Topic:

USYD Basser Seminar Series, School of Information TechnologiesSpeaker:

Dr Taso ViglasSpeaker:

School of Information Technologies, The University of SydneyAbstract:

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.

Location:

The University of Sydney, School of IT BuildingLocation Details:

Lecture Theatre (Room 123), Level 1