The basic theme of this research is how to use randomized algorithms to improve network exploration, organisation and structure. The good thing about randomized algorithms is that they are easy to visualise and implement, and are often highly effective both in theory and in practice.
In the case of networks, these algorithms can often be modelled by particles moving more or less randomly on the network. The word particle is a generic term for agents, messages, robots. We assume the particles are used with a distinct purpose in relation to the network. Examples include searching the network, modifying its structure, passing messages or opinions between vertices of the network, distributing or hiding information, or validating the integrity of the network structure and content. The outcome of this process, although random in detail, is designed to do useful work. Moreover the particles are assumed to be cheap and to impose low processing costs on the network, so that the desired results can be obtained easily.
The remarkable fact about randomized algorithms, is that although the local behaviour is random, the global outcome is often quite predictable. With all randomized algorithms, the work is in the intellectual design of the process rather than its deployment in practice. It seems to us that it is best to have a well designed product which is simple and easy to use. Moreover, such processes are often very robust, and will continue to work effectively in practice in situations more general than the ones they were designed for.
Many large networks can be found in modern society, and obtaining information about these networks, or improving their functionality is an important problem. Examples of such networks include the world wide web, connections between internet routers, peer to peer networks, social networks (Twitter, Facebook) , and repositories of videos, photos (YouTube, Flickr) etc. Such networks are very large, change over time and are essentially unknowable or do not need to be known in detail.
Searching, sampling and ordering the content of such networks is a major application area and a substantial user of computer time. The evolving use of these networks is changing social behaviour, and improving our ability to explore such networks is of value to us all.
Random walks are a good example of a randomized algorithm. They are a simple method of network exploration, and are particularly suitable for searching massive networks. A random walk traverses a network by moving from its current position to a neighbouring vertex chosen at random. Decisions about where to go next can be taken locally, and only limited resources are needed for the search. The exploration is carried out in a fully distributed manner, and can adapt easily to dynamic networks. The long run behaviour of the walk acts as a distributed voting mechanism, in which the number of visits to a vertex is proportional to its popularity or accessability.
Fundamental questions are: At any time how much of the network has the walk seen, and what is the structure of the part left behind? Are there large chunks of the network which have been completely ignored, or are the unvisited fragments rather small and of uniform size? How can we alter the behaviour of the walk to improve uniformity of searching, or to reduce search time? How can we use information gleaned by the walk to improve the quality of recommendations provided about the system?
Speeding up random walks to reduce search time, or altering their behaviour to make searching more uniform and effective are fundamental questions in the theory of computing. The price of these improvements is typically some extra work which is performed locally by the walk. It is important to understand how well this can be done, as it can be useful in practice.
|