Randomized Algorithms for Computer Networks

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.

Our research opens new directions in the study of randomized algorithms on networks, and inspires possible new applications.

In the past two decades the way we access information and services on a day to day basis has changed beyond recognition. Searching large networks to extract information content is a major data processing application, and the efficiency of search engine design, for example, is a matter of concern to all. Our use of online networks affects the way we communicate ideas, organise our lives and make personal choices. Their performance however is sometimes less than perfect. Although they offer an easy way to go shopping, for example, the range of products they suggest often seems out of line with our personal tastes or immediate needs.


This research has potential for impact on the design of information search and retrieval in the \WWW, the latency and robustness of the internet, and the autonomous construction and evolution of peer-to-peer networks for file sharing and distribution of music or films, and the quality of recommendations on social networks. In today's world, the world wide web; its related infrastructure, the internet; and autonomous and social networks such as Facebook and Twitter are a major industry. The successful entrepreneurs of the future will be those who develop the most appropriate apps for our tablet phones. The evolution and refinement of these networks will define the way our world function be in the future, and 10 or 20 years time we can expect it to have changed almost unrecognisably.

The research can have applied impact in many areas. Specific examples include the following:

Information and social networks.
Improved searching of networks for location of files and web page information content can lead to reduced processing overheads, improved web crawling strategies, improved file indexing and decreased user response times in queries on search engines and social network pages. It can lead to more effective methods of viral advertising in networks such as Twitter. Viral advertising can be seen as a particle process on the Twitter network.

Ad-hoc and peer-to-peer networks.
Our research can lead to better methods for the distributed structuring and maintenance of networks, leading to improved distribution and retrieval of fragmented data files (such as films, music etc), with the consequent reduction in processing and response time. This is particularly important for ad-hoc networks of sensors, mobile phones etc, with limited power supplies.

Shopping and personal recommender applications.
Our work here includes the development of low cost recommender systems (already ongoing from the Samsung GRO award). This study on the use of random walks in recommender systems for mobile phone apps, typifies the need for low cost algorithms. It is no exaggeration to say that in the future, whatever you want, you will probably be using an app on a hand held device to search for it. However much the manufacturers push the boundaries of memory and processing power on these devices, the online networks are growing at a faster rate, and their variety proliferating.

Business, information security and health applications.
Our work on distributed random processes and self-modifying networks offers ways to repair failures in networks such as business intra-nets. Our work on management of epidemic type processes through overlay networks has potential applications in the areas of public health and network security. An example of this is limitation of spreading biological or computer viruses: Infection spreads by direct person to person transmission, or direct computer to computer communication, and prevention occurs by communicating information by a social network (phone, email or Twitter), or a peer-to-peer overlay network.