Seminar Details
2008-02-21 (16.00) : JEUDI !! THESE DE DOCTORAT "Dominant vectors of nonnegative matrices. Application to information extraction in large graphs".
At BARB93
Organized by Mathematical Engineering
Speaker :
Ninove, Laure
Abstract :
Objects such as documents, people, words or utilities, that are related in
some way, for instance by citations, friendship, appearance in definitions
or physical connections, may be conveniently represented using graphs or
networks. An increasing number of such relational databases, as for instance
the World Wide Web, digital libraries, social networking web sites or phone
calls logs, are available. Relevant information may be hidden in these
networks. A user may for instance need to get authority web pages on a
particular topic or a list of similar documents from a digital library, or
to determine communities of friends from a social networking site or a phone
calls log. Unfortunately, extracting this information may not be easy.
This thesis is devoted to the study of problems related to information
extraction in large graphs with the help of dominant vectors of nonnegative
matrices. The graph structure is indeed very useful to retrieve information
from a relational database. The correspondence between nonnegative matrices
and graphs makes Perron-Frobenius methods a powerful tool for the analysis
of networks.
In a first part, we analyze the fixed points of a normalized affine
iteration used by a database matching algorithm. Then, we consider questions
related to PageRank, a ranking method of the web pages based on a random
surfer model and used by the well known web search engine Google. In a
second part, we study optimal linkage strategies for a web master who wants
to maximize the average PageRank score of a web site. Finally, the third
part is devoted to the study of a nonlinear variant of PageRank. The simple
model that we propose takes into account the mutual influence between web
ranking and web surfing.