Randomized algorithms for computer networks

Lead Research Organisation: University of Leeds
Department Name: Sch of Computing

Abstract

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.

Publications

10 25 50
publication icon
Cooper C (2018) Discordant Voting Processes on Finite Graphs in SIAM Journal on Discrete Mathematics

publication icon
Cooper C (2019) The flip Markov chain for connected regular graphs in Discrete Applied Mathematics

publication icon
Dyer J (2019) Practical homomorphic encryption over the integers for secure computation in the cloud in International Journal of Information Security

publication icon
Dyer M (2014) A simple randomised algorithm for convex optimisation in Mathematical Programming Ser. A

publication icon
Dyer M (2015) On the chromatic number of a random hypergraph in Journal of Combinatorial Theory, Series B

publication icon
Dyer M (2015) Graph classes and the switch Markov chain for matchings in Annales de la faculté des sciences de Toulouse Mathématiques

publication icon
Dyer M (2019) Counting Perfect Matchings and the Switch Chain in SIAM Journal on Discrete Mathematics

publication icon
Dyer M (2019) Quasimonotone graphs in Discrete Applied Mathematics

publication icon
Dyer M (2014) Structure and eigenvalues of heat-bath Markov chains in Linear Algebra and its Applications