Upfal project explores dynamic behavior of networks

See additional articles:

• Charniak and others push into new areas of speech recognition
  
• Van Dam project hopes to marry 3-D graphics with interactive electronic books that one day may train surgeons using virtual reality
  
• Trio collaborates on modeling brain cell behavior
  
• Van Hentenryck in the hunt for algorithm that takes uncertainty into account
  

Computer Science Professor Eliezer Upfal will bring his extensive background in probability and stochastic processes to a project designed to unlock some of the mysteries surrounding large-scale dynamic networks, particularly the Web/Internet.

The National Science Foundation awarded Upfal and colleague Michael Mitzenmacher of Harvard University $524,000 to develop mathematical models and algorithms that are expected to be of great use to those who design search engines, Web crawlers, Web caches and routers.

"Existing algorithms, say for searching the Web, make few defensible assumptions about Web structure and therefore do not take sufficient advantage of it," says Upfal, who views the Web environment as a combination of three interrelated layers. The top layer contains the textual content of the pages themselves. The second layer is the Web graph defined by the hyperlink structure among those pages. The third layer is the physical network — servers and communication links — that supports the logical web. It is the hyperlink graph structure that is most peculiar to the Web, and the layer that is of most interest to Upfal in this project.

Scientists in two companies that specialize in search engines and related Web applications — Altavista and Verity — are collaborating with Upfal and Mitzenmacher on this project. Drawing on their work in probability and stochastic processes, Upfal and Mitzenmacher hope to generate models that can make reliable predictions about such things as connectivity, information content and the dynamics of a given network.

What makes this work so challenging is that networks like the Web are dynamic — or continually changing. "Pages and links are constantly added and deleted from the Web, dynamically altering the structure of the underlying graph," explains Upfal. "Furthermore, these changes are made locally with no global plan or coordination. We believe the best way to model this dynamic behavior is through a stochastic model that would reflect the seemingly random local changes in the graph structure and could account for phenomena of global organization."

Developers of search engines, Upfal notes, have two goals. First, they want to cover as many sites as possible, including isolated groups of pages that go unseen. Currently, no engine comes close to covering the whole Web.

Second, a search engine needs to rank this information so that a user is given the most relevant sites first. "This involves very sophisticated mathematics," Upfal says. This project will address both goals.

Upfal is intrigued also by the peer-to-peer (P2P) networks that have emerged since the collapse of Napster. Users of these networks share files, often music, with each other, avoiding the legal problems Napster faced because no centralized organization can be held accountable. Queries in a P2P network do not go to a central server, but instead fan out over the network; results are collected and propagated back to the originating node.

Every node in a P2P network is both a server and a client and runs what is called "servent" software. Upfal explains that when "servents" are implemented to a standard, their local behavior results in good global information. A stochastic analysis of local behavior will allow Upfal to develop models that he believes will be intuitive and practical enough to be used in the new P2P products.