Random walks on computer networks

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.

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