Simulation sizes up Web structure
By Ted Smalley Bowen, Technology Research NewsWith every hyperlink added to a Web page the shape of the World Wide Web changes, but the problem of determining that shape is trickier than just estimating the number of links and mapping where they go.
Large, complex, evolving networks have proven difficult to model statistically, and the Web is a particularly challenging case.
A model and simulation that looks at how frequently links are updated and at the relationship between outgoing and incoming links promises to give a clearer picture of the Web's underlying structure.
The model, developed by Slovenian researcher Bosiljka Tadic, suggests that the shape of the Web is largely determined by how and how often Web pages are updated, which in turn is determined by the biases and policies of the people who update the pages. The research also showed that the underlying structure of the Web is still maturing.
"Understanding the underlying dynamic rules that govern the Web may help to design more efficient algorithms for discovering [what makes the Web change] and predicting [its] evolution," said Tadic, a research scientist and physics professor at the Jozef Stefan Institute in Slovenia.
Tadic's 5-million-node simulation represents the Web as a directed graph, showing nodes, or Web pages, connected by arcs, or links. It compares link distribution and the size and depth of nodes with statistical snap-shots of the actual Web. The simulation correlates fairly closely with actual Web topology and growth data, said Tadic.
Although the Web has many similarities with other large, complex networks, one of its differences is how quickly the links between nodes change. In contrast, links in many other social networks change slowly or not at all, Tadic said.
The model assumes that because Web links are constantly updated, the network is being rearranged at the same pace at which it grows.
On the Web, outgoing and incoming links are both hierarchical, but show different patterns and rates of growth, Tadic said. A link is classified according to its relationship to a particular page: clicking on a hyperlink on a page generates an outgoing link, while a visitor arriving at the page via an outside link generates an incoming link.
The key to Tadic's simulation is that it takes into consideration this relationship between the patterns of the two types of links, assuming that separate but related rules govern the growth of inbound and outbound Web links. "In the Web, the incoming links are driven by the dynamics of outgoing links," Tadic said.
Statistical models of the Web generally do not factor in these critical elements of how links to and from sites change and how they might be related, according to Tadic.
The model also draws from recent research into network node sizes. It assumes that the most active Web masters create the bulk of the network's links, that the most popular sites have by far the most links, and that there are many, many nodes with just a few links.
Tadic is applying to the Web general ideas developed in the last year or so about network modeling, said Albert-László Barabási, associate professor of physics at Notre Dame University.
"The basic idea is that if we understand the Web better, then we can design better search engines. Any tool that works on the Web would work better if we start with a better understanding of how the Web develops and what is its topology. In that sense, this paper is very valuable," he said.
Further research into this area might address the Web's clustering properties, and examine the Web as a grouping of several weakly linked networks, Tadic said.
The model could also apply to other types of complex evolving networks, he said.
Tadic's research has been accepted for publication in the journal Physica A: Statistical Mechanics and its Applications. The research was funded by the Ministry of Science and Technology of the Republic of Slovenia.
Timeline: Now
Funding: Government
TRN Categories: Internet, Computers and Society
Story Type: News
Related Elements: Technical paper, "Dynamics of directed graphs: the world-wide Web," accepted for publication in Physica A: Statistical Mechanics and its Applications. It is posted, along with related papers at phobos.ijs.si/~tadic/paperslist.html
Advertisements:
January 17, 2001
Page One
Light spins resin rotors
Crossed nanowires make Lilliputian LEDs
Simulation sizes up Web structure
Quantum bit hangs tough
Sowing strain reaps ordered dots
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
