Algorithmic applications of random walks to large networks
Colin Cooper
Department of Informatics
King's College London
The talk looks at two examples of uses of random walks. These are for
sampling network properties, and for use in recommender systems.
Estimation of network properties using random walks
We study the use of random walks as an efficient estimator of global
properties of large undirected graphs, for example the number of edges,
vertices, triangles, and generally, the number of small fixed subgraphs. We
consider two methods based on first returns of random walks: the cycle
formula of regenerative processes and weighted random walks with edge
weights defined by the property under investigation. We review the
theoretical foundations for these methods, and indicate how they can be
adapted for the general non-intrusive investigation of large online
networks.
Use of Random Walks in Recommender Systems
A recommender system uses information about known associations between users
and items to compute for a given user, an ordered recommendation list of
items which this user might be interested in acquiring. For example, in the
context of a library, knowing which books have been read by which members of
the library, a recommender system would calculate for a given member an
ordered list of book recommendations for next reading. We consider ordering
rules based on various parameters of random walks on the graph which
represents associations between users and items, and experimentally compare
the quality of recommendations so obtained for the MovieLens data set.