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