# Randomized Algorithms for Computer Networks

Lead Research Organisation:
King's College London

Department Name: Informatics

### 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.

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.

### Planned Impact

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.

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.

### Organisations

- King's College London, United Kingdom (Lead Research Organisation)
- Eindhoven University of Technology (Collaboration)
- University of California, Berkeley (Collaboration)
- Kyushu University, Japan (Collaboration)
- University of New South Wales (Collaboration)
- Carnegie Mellon University, United States (Collaboration)

## People |
## ORCID iD |

Colin Cooper (Principal Investigator) | |

Tomasz Radzik (Co-Investigator) |

### Publications

Berenbrink P
(2020)

*Time-space trade-offs in population protocols for the majority problem*in Distributed Computing
Cooper C
(2019)

*On the Cover Time of Dense Graphs*in SIAM Journal on Discrete Mathematics
Cooper C
(2019)

*New Cover Time Bounds for the Coalescing-Branching Random Walk on Graphs*in ACM Transactions on Parallel Computing
Cooper C
(2019)

*On the rank of a random binary matrix*
Cooper C
(2019)

*Minors of a random binary matroid*in Random Structures & Algorithms
Cooper C
(2019)

*The flip Markov chain for connected regular graphs*in Discrete Applied Mathematics
Cooper C
(2018)

*Discordant Voting Processes on Finite Graphs*in SIAM Journal on Discrete Mathematics
Cooper C
(2018)

*Threshold behaviour of discordant voting on the complete graph*in Journal of Discrete Algorithms
Cooper C
(2017)

*Constructing self-stabilizing oscillators in population protocols*in Information and Computation
Bilke A
(2017)

*Brief Announcement*
David Kohan Marzagao
(2017)

*Multi-Agent Flag Coordination Games*
Abdullah M
(2016)

*Combinatorial Algorithms*
Cooper C
(2016)

*Fast Low-Cost Estimation of Network Properties Using Random Walks*in Internet Mathematics
Cooper C
(2016)

*Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk*in SIAM Journal on Discrete Mathematics
Bal D
(2016)

*Rainbow Arborescence in Random Digraphs Rainbow Arborescence in Random Digraphs*in Journal of Graph Theory
Gao F
(2015)

*Link Prediction Methods and Their Accuracy for Different Social Networks and Network Metrics*in Scientific Programming
Cooper C
(2015)

*Stabilization, Safety, and Security of Distributed Systems*
Dyer M
(2015)

*On the chromatic number of a random hypergraph*in Journal of Combinatorial Theory, Series B
Berenbrink P
(2015)

*Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time*in Random Structures & Algorithms
Berenbrink P
(2015)

*Randomized diffusion for indivisible loads*in Journal of Computer and System Sciences
Cooper C
(2015)

*Structural Information and Communication Complexity*
COOPER C
(2015)

*On the Length of a Random Minimum Spanning Tree*in Combinatorics, Probability and Computing
Cooper C
(2015)

*Distributed Computing*
Cooper C
(2015)

*Long Paths in Random Apollonian Networks*in Internet Mathematics
Cooper C
(2014)

*A Fast Algorithm to Find All High-Degree Vertices in Graphs with a Power-Law Degree Sequence*in Internet Mathematics
Cooper C
(2014)

*Some Typical Properties of the Spatial Preferred Attachment Model*in Internet Mathematics
Cooper C
(2014)

*The height of random k -trees and related branching processes*in Random Structures & Algorithms
Cooper C
(2014)

*Automata, Languages, and Programming*
Dyer M
(2014)

*Structure and eigenvalues of heat-bath Markov chains*in Linear Algebra and its ApplicationsDescription | The main work has been on efficient randomized methods to search and find structure of large networks, and to obtain cnesensus in distributed systems. Basically if the structure of a network is unknown it is not straightforward to find where things are and what typically the network looks like. Similary it is difficult to reach agreement (consensus) without any imposed authority. Randomized algorithms can provide reasonable ways to do these things based on local interactions. |

Exploitation Route | Algorithms can be implemented in real cases with sufficient attention to detail. |

Sectors | Digital/Communication/Information Technologies (including Software) |

Description | Attend Workshop on "Counting complexity and phase transitions" at Simons Institute for Theory of Computing |

Organisation | University of California, Berkeley |

Department | Simons Institute for the Theory of Computing |

Country | United States |

Sector | Academic/University |

PI Contribution | Attend Workshop on "Counting complexity and phase transitions" at Simons Institute for Theory of Computing at UC Berkley for March 2016. |

Collaborator Contribution | Supported local costs of attendence (up to a total of $135 * 35 days= $4725) |

Impact | Ongoing research |

Start Year | 2016 |

Description | Research collaboration with A. Frieze CMU |

Organisation | Carnegie Mellon University |

Department | Department of Mathematical Sciences |

Country | United States |

Sector | Academic/University |

PI Contribution | Research visit to A. Frieze CMU from 24th July-17 August 2015. Research on the vacant set of random walks, and models of distributed voting on graphs. |

Collaborator Contribution | Research on the vacant set of random walks, and models of distributed voting on graphs. Provision of office accommodation at CMU. |

Impact | Outcome publication currently submitted to ICALP 2016. (Cooper, Dyer, Frieze, Rivera. Discordant voting processes on finite graphs. submitted) |

Description | Research cooperation with University of Kyushu (Fukuoka, Japan) |

Organisation | Kyushu University |

Country | Japan |

Sector | Academic/University |

PI Contribution | Yamashita Group at Kyushu University is a cooperating partner on the EPSRC project. Visit to the research group 5th Nov-2nd Dec 2015, by C. Cooper and PhD student N. Rivera. We worked with the Kyushu group on a range of problems in distributed computing. We gave a research seminar. |

Collaborator Contribution | Office space. Paid local accomodation and subsistence costs for King's PhD student N. Rivera, and contributed to C. Cooper local expenses. |

Impact | The outputs are publications, and research cooperation. Coalescing walks on rotor-router systems. (C. Cooper, T. Radzik, N. Rivera, T.Shiraga). Sirocco 2015. Constructing self-stabilizing oscillators in population protocols. (C. Cooper, A. Lamani, G. Vigiletta, M. Yamashita, Y. Yamauchi) SSS 2015. Fast consensus for voting on general expander graphs. (C. Cooper, R. Elsaesser, T. Radzik, N. Rivera, T.Shiraga). DISC 2015 (Symposium on Distributed Computing). A. Lamani, T. Shiraga, M. Yamashita, Y. Yamauchi are from the TCS group at Kyushu. |

Start Year | 2014 |

Description | Research visit to C. Greenhill UNSW Monday 3rd July -- Wednesday 18th July 2017 |

Organisation | University of New South Wales |

Country | Australia |

Sector | Academic/University |

PI Contribution | Work on Markov Processes used to generate and randomize large networks. Models of random graphs with clustering properties typical of social networks. |

Collaborator Contribution | Work on Markov Processes used to generate and randomize large networks. Models of random graphs with clustering properties typical of social networks. |

Impact | The recent outcomes are research publications which are still work in progress. |

Description | Visit to Yamashita Labs, University of Kyushu, Department of Computer Science, Japan 6th-28th March 2017 |

Organisation | Kyushu University |

Country | Japan |

Sector | Academic/University |

PI Contribution | Work on consensus algorithms for distributed computer systems, and models of species interaction in the population protocol model. Much of this work was with T. Shiraga who is now at Chuo University Tokyo, and will be visiting research fellow at King's (Department of Informatics) from March 1st-20th 2018 |

Collaborator Contribution | Work on consensus algorithms for distributed computer systems, and models of species interaction in the population protocol model. |

Impact | The outputs are academic publications, listed in the publications section. |

Start Year | 2008 |

Description | Vist to Alan Frieze at Carnegie Mellon University. Pittsburgh USA. 13th February--3rd march 2018 |

Organisation | Carnegie Mellon University |

Department | Department of Mathematical Sciences |

Country | United States |

Sector | Academic/University |

PI Contribution | Work on rank of random Boolean matrices, dispersion processes and problems in discrete random walks. A full list of publications can be found at https://www.math.cmu.edu/~af1p/papers.html |

Collaborator Contribution | Work on rank of random Boolean matrices, dispersion processes and problems in discrete random walks with A. Frieze and W. Pegden. Provision of office space and use of facilities at CMU. |

Impact | The outputs are academic publications, and are listed in the publications section. |

Description | Vist to Alan Frieze at Carnegie Mellon University. Pittsburgh USA. 17th July-7 August 2016 |

Organisation | Carnegie Mellon University |

Department | Department of Mathematical Sciences |

Country | United States |

Sector | Academic/University |

PI Contribution | Work with Prof. Frieze on problems relating to Random Walks and Random Processes. This work is ongoing and is in preparation for EPSRC proposal EP/M005038/1 Randomized Algorithms for Computer Networks. |

Collaborator Contribution | Made some progress on diameter of multi-type branchings, and random walks on dynamic graphs |

Impact | Outputs from this collaboration are listed in publications portfolio |

Start Year | 2016 |

Description | Workshop "Random walks on random graphs and applications" |

Organisation | Eindhoven University of Technology |

Country | Netherlands |

Sector | Academic/University |

PI Contribution | We organized the theme of the above workshop, nominated and invited the speakers. The workshop took place from 14-16th April 2015 under our supervision, chairing the sessions etc. The workshop focused on 'Discrete random walks and related processes. Analysis on random graph models, and algorithmic applications to large networks'. It was designed to fit the theme of the EPSRC project, an dpromote research in this area at international level. There were 26 speakers. |

Collaborator Contribution | The EURANDOM facility provided the workshop location, (T.U. Eindhoven), local organization and administrative support. |

Impact | The intended outcome is promotion of, and increasing interest in the topic area. EPSRC was a listed sponsor for publicity purposes. |

Start Year | 2014 |

Description | Workshop on Random Graphs and Random Processes. Tuesday 25 April 2017. Kings College London. |

Form Of Engagement Activity | Participation in an activity, workshop or similar |

Part Of Official Scheme? | No |

Geographic Reach | National |

Primary Audience | Postgraduate students |

Results and Impact | The purpose of the workshop was to promote interest in randomized algorithms and random structures and processes at university postgraduate and academic level, and to develop relationships between compter science and mathematics. |

Year(s) Of Engagement Activity | 2017 |

URL | https://nms.kcl.ac.uk/rasp/rasp_workshop/programme_for_website.pdf |

Description | Workshop to promote research in randomized algorithms. Workshop on random graphs and random processes. April 17th, 2018 |

Form Of Engagement Activity | Participation in an activity, workshop or similar |

Part Of Official Scheme? | No |

Geographic Reach | National |

Primary Audience | Study participants or study members |

Results and Impact | The Second King's Workshop on Random Graphs and Random Processes Tuesday 17th April 2018 |

Year(s) Of Engagement Activity | 2018 |

URL | https://nms.kcl.ac.uk/rasp/rasp_workshop/2018_programme_for_website.pdf |

Description | Workshop to promote research in randomized algorithms. Workshop on random graphs and random processes. April 9th, 2019 |

Form Of Engagement Activity | Participation in an activity, workshop or similar |

Part Of Official Scheme? | No |

Geographic Reach | National |

Primary Audience | Study participants or study members |

Results and Impact | Workshop on random graphs and random processes. April 9th, 2019. This wokshop received funding from LMS, and as such part of the workshop aims are to promote postgraduate student engagement and gender equality among speakers and attendees |

Year(s) Of Engagement Activity | 2019 |

URL | https://nms.kcl.ac.uk/rasp/rasp_workshop/2019_programme_for_website.pdf |