| Test Of Time Award For Classic Paper On Bow-Tie Structure Of The Web |
| Written by Sue Gee |
| Friday, 14 April 2017 |
|
Researchers whose work revealed the "bow-tie" structure of the web, thereby improving search engines, have been awarded the third Seoul Test of Time Award at this month's World Wide Web Conference, held in Perth, Australia.
Dame Wendy Hall, Chair WWW2017, Perth; Professor Chin-Wan Chung, Co-Chair of WWW2014 Seoul; Andrei Broder, Ravi Kumar and Andrew Tomkins. The Seoul Test of Time Award, set up and funded by the computer scientists who organized the 2014 World Wide Web Conference held in Seoul, is given to the authors of a previous World Wide Web conference paper that has demonstrated significant scientific, technical, or social impact over the years. The paper that has won this year's award, “Graph Structure in the Web” by Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins and Janet Wiener, was originally presented in 2000 at the 9th WWW conference in Amsterdam. According to the Google Reseach blog post announcing the award: At the time of publication, it received the Best Paper Award from the WWW conference, and in the following 17 years proved to be highly influential, accumulating over 3,500 citations. While Google is claiming the credit as five of the authors now work for it, at the time Andrei Broder was with Altavista, where the experimental data was collected in 1999 and four of the authors including Ravi Kumar and Andrew Tomkins were with IBM.
The paper made two major contributions to the understanding of the structure of the Internet. First, its large-scale experiments, showed that Web nodes are distributed according to a power-law. That is, the probability that the Web node has i incoming links is roughly proportional to 1 / i^2.1. Second, unlike previous research that assumed the Web to be almost fully connected, it described a much more elaborate structure of the Web, which since then has been depicted with the iconic “bowtie” shape:
The paper described several characteristic classes of Web pages:
Whereas the core component is fully connected and each node can be reached from any other node, Broder et al. discovered that as a whole the Web is much more loosely connected than previously believed, while the probability that any two given pages can be reached from one another is just under 1/4. In less formal terms. the paper showed the the way web pages linked to each other fell into four roughly equal groups with pages at the web's core the knot in the bow-tie, were all connected to each other by a chain of links. Pages that only linked to the core, such as new pages, were one side of the bow-tie. On the other side were pages that provided no links to any other pages, like many corporate websites. The remainder of the web was not linked to the core. Speaking to the press after the presentation, Andrew Tomkins said the results of the paper were a surprise to the researchers: “We hadn’t realised that so much of the web was not readily accessible to web crawlers", and went on to explain how the research revealed that web crawlers, the programs that constantly browse the web, following links from one page to another, to keep search engines up to date, that only started in one spot could never index everything. Seventeen years after its publication, the paper is viewed as the seminal introduction to the “bow-tie” graph structure of the Web. The same structure has been found in many other large- scale graphs, ranging from Wikipedia citations to networks of interbank loans. It provides a mathematical foundation for Web crawling and indexing that is still in use, and its theoretical underpinnings are taught in Web search and data mining courses around the world. |
| Last Updated ( Friday, 14 April 2017 ) |
