Random walks on computer networks

Lead Research Organisation: King's College London
Department Name: Computer Science

Abstract

The basic theme of this research is to use random walks and interacting particle systems to improve network exploration and structure.

Our aim is to study algorithmic problems in Computer Science modeled by particles (agents, messages, robots) moving more or less randomly on a large network. We suppose such particles may be single or numerous, of various types, and that they may able to interact with each other and with the network. We assume the particles have a purpose either in relation to the network, such as searching the network or modifying its structure; or in relation to other particles, such as passing messages to each other.

Many large networks can be found in modern society, and obtaining information from these networks
is an important problem. Examples of such networks include the World Wide Web, and social networks such as Twitter and FaceBook. These networks are very large, change over time and are essentially unknowable or do not need to be known in detail. They are highly interlinked (e.g. URL's embedded in Twitter and FaceBook) and can be viewed as part of a larger whole. New social networks appear frequently, and the influence of these networks on social, economic and political aspects of everyday life is substantial.

Searching, sampling and indexing the content of such networks is a major application area a substantial user of computer time, and likely to become more so in the future. The evolving use of these networks is changing social and economic behavior. Improving the ability to search such networks is of value to us all.

Random walks are a simple method of network exploration, and as such, are particularly suitable for searching massive networks. A random walk traverses a network by moving from its current position to a neighboring 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 behavior 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.

Suppose we could alter the behavior of the random walk to reduce the search time. How can this be done, and at what cost?

Speeding up random walks, to reduce search time, is a fundamental question in the theory of computing. The price of this speed up, is normally some extra work which is performed locally by the walk, or undertaken by the vertices of the graph. Possible ways of speeding up random walks we have identified include biassed transitions, use of previous history and local exploration around current position.

One way to reduce search time is to use several random walks which search simultaneously. In the simplest model the walks are oblivious of each other and do not interact in any way. Search time should be reduced, but at the expense of using additional walks.

Suppose we could also allow the random walks to interact with each other, or with the underlying network? How should this interaction be designed, in order to speed up search, and what other applications might it have? Historically, interacting particle systems have only been analyzed on infinite networks, and even then not with computer science applications in mind. Recently, we began to make progress in this direction, and found that many related problems such as distributed voting, to elect a leader for example, could be understood in the framework we developed.

Potential applications of interacting particle systems are many and include:
Gossiping and broadcasting among agents moving on a network, Models of epidemics spreading between particles and the graph, Distributed search with intelligent robots, Software agents moving in an intranet. Models of voting and social consensus. Good agents chasing bad agents on a network.

Planned Impact

Our research opens new directions in the algorithmic study of random walks, 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. Economic, social and political behaviour is becoming increasing determined the www and social networks; e.g. the role of Twitter in the recent unrest in Tunisia, Egypt etc.

The 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, films etc. 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. Their evolution and refinement defines the way our world will be in 10 or 20 years time.

The research has applied impact in several areas:

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.

E-commerce applications.
Viral marketing is an epidemic process which provides easy transfer of messages using common motivations and behaviours. For networks such as Twitter, viral marketing is part of their business model. Users pass on Tweets (Twitter messages) which contain entertaining or useful content. This is a process of probabilistic broadcasting which utilizes an existing network. Another business application, the rapid location and retrieval of files, such as sections of a movie-film or music, is central to the function of peer-to-peer systems.

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.

Health applications.
Our project includes a study of innovative methods of auto-diagnosis and repair of failures in networks such as business intra-nets. In the area of health, we consider management of epidemic type processes through overlay networks. An example of this is disease limitation: Infection spreads by direct person to person transmission, prevention occurs by communicating information by a social network (phone, email or Twitter).

Publications

10 25 50
publication icon
Abdullah M (2012) Cover time of a random graph with given degree sequence in Discrete Mathematics

publication icon
Colin Cooper (Author) (2013) Coalescing Random Walks and Voting on Connected Graphs in Siam Journal on Discrete Mathematics

publication icon
Colin Cooper (Author) (2013) Recommender systems based on random walks

publication icon
Cooper C (2012) Stationary distribution and cover time of random walks on random digraphs in Journal of Combinatorial Theory, Series B

publication icon
Cooper C (2013) Coalescing Random Walks and Voting on Connected Graphs in SIAM Journal on Discrete Mathematics

publication icon
Cooper C (2016) Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk in SIAM Journal on Discrete Mathematics

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

publication icon
Cooper C (2013) The cover times of random walks on random uniform hypergraphs in Theoretical Computer Science

 
Description The focus of the research was on speeding up search using random walks. A wide range of approaches were and are still being investigated. Buy adapting the search method more closely to the structure of the network under investigation it is possible to search larhe networks in a resaonable time without imposing impossible storage and computational processing requirements on the computer system.
Exploitation Route The most straightforward applications are in network search. Information ranking and recommender systems used related ideas, indeed Google PageRank is based on the random walk concept.
Sectors Digital/Communication/Information Technologies (including Software)

 
Description Research grant from Samsung
Amount £100,000 (GBP)
Organisation Samsung 
Sector Private
Country Korea, Republic of
Start 11/2012 
End 11/2013
 
Description UNSW Faculty of Science Visiting Researcher Fellowship, June, 2013. 
Organisation University of New South Wales
Country Australia 
Sector Academic/University 
PI Contribution Invited visiting researcher fellowship offered by University of New South Wales, for Martin Dyer to work with Catherine Greenhill on models of dynamic networks, with applications to P2P systems.
Start Year 2013
 
Description Visit to University of Fukuoka (Japan) 
Organisation Fukuoka University
Country Japan 
Sector Academic/University 
PI Contribution Invited visit to Yamashita Laboratory, Dept. of Computer Science, KyuDai (University of Fukuoka) Japan. 7-28 March 2017. To work on topic "Markovian Oscillators".
Collaborator Contribution Office space plus contributions to accomodation for accompanying PhD student (N. Rivera)
Impact To continue research on Markovian Oscillators, and to find out what the KyuDai group are doing. They have a grant to work on models of chemical processes using (e.g.) the Population Protocol model. This seems very interesting and our group at King's want to get involved.
Start Year 2017