Graph structure in the Web
Computer NetworksPublished 1 June 2000
Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata
Citations2,760
SJR quartileQ1
SJR score1.17
SNIP1.37
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The study of the web as a graph yields valuable insight into web algorithms for crawling, searching and community discovery, and the sociological phenomena which characterize its evolution.
Abstract
The study of the Web as a graph is not only fascinating in its own right, but also yields valuable insight into Web algorithms for crawling, searching and community discovery, and the sociological phenomena which characterize its evolution. We report on experiments on local and global properties of the Web graph using two AltaVista crawls each with over 200 million pages and 1.5 billion links. Our study indicates that the macroscopic structure of the Web is considerably more intricate than suggested by earlier experiments on a smaller scale.
Keywords
Computer SciencePhysics and Astronomy
ScienceEmergence of Scaling in Random Networks
36,366 Citations1999Albert-Ĺaszló Barabási, Réka Albert
A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
Computer Networks and ISDN SystemsThe anatomy of a large-scale hypertextual Web search engine
15,828 Citations1998Sergey Brin, Lawrence M. Page
This paper provides an in-depth description of Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext and looks at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want.
NatureDiameter of the World-Wide Web
4,285 Citations1999Réka Albert, Hawoong Jeong +1 more
The World-Wide Web becomes a large directed graph whose vertices are documents and whose edges are links that point from one document to another, which determines the web's connectivity and consequently how effectively the authors can locate information on it.
On power-law relationships of the Internet topology
4,222 Citations1999Michalis Faloutsos, Petros Faloutsos +1 more
These power-laws hold for three snapshots of the Internet, between November 1997 and December 1998, despite a 45% growth of its size during that period, and can be used to generate and select realistic topologies for simulation purposes.
Symposium on Discrete AlgorithmsAuthoritative sources in a hyperlinked environment
1,836 Citations1998Jon Kleinberg
Computer NetworksTrawling the Web for emerging cyber-communities
1,010 Citations1999Ravi Kumar, Prabhakar Raghavan +2 more
The subject of this paper is the systematic enumeration of over 100,000 emerging communities from a Web crawl, motivating a graph-theoretic approach to locating such communities, and describing the algorithms and algorithmic engineering necessary to find structures that subscribe to this notion.
A random graph model for massive graphs
925 Citations2000William Aiello, Fan Chung +1 more
A random graph model is proposed which is a special case of sparse random graphs with given degree sequences which involves only a small number of parameters, called logsize and log-log growth rate, which capture some universal characteristics of massive graphs.
ScienceStrong Regularities in World Wide Web Surfing
761 Citations1998Bernardo A. Huberman, Peter Pirolli +2 more
A model that assumes that users make a sequence of decisions to proceed to another page, continuing as long as the value of the current page exceeds some threshold, yields the probability distribution for the number of pages that a user visits within a given Web site.
Computer Networks and ISDN SystemsAutomatic resource compilation by analyzing hyperlink structure and associated text
700 Citations1998Soumen Chakrabarti, Byron Dom +4 more
An evaluation of ARC suggests that the resources found by ARC frequently fare almost as well as, and sometimes better than, lists of resources that are manually compiled or classified into a topic.
ACM SIGIR ForumImproved Algorithms for Topic Distillation in a Hyperlinked Environment
677 Citations2017Krishna Bharat, Monika Henzinger
This paper addresses the problem of topic distillation on the World Wide Web, namely, given a typical user query to find quality documents related to the query topic, by augmenting a previous connectivity analysis based algorithm with content analysis.
Improved algorithms for topic distillation in a hyperlinked environment
439 Citations1998Krishna Bharat, Monika Henzinger
This paper addresses the problem of topic distillation on the World Wide Web, namely, given a typical user query to find quality documents related to the query topic, by augmenting a previous connectivity analysis based algorithm with content analysis.
Silk from a sow's ear
382 Citations1996Peter Pirolli, James E. Pitkow +1 more
This paper presents the exploration into techniques that utilize both the topology and textual similarity between items as well as usage data collected by servers and page meta-information lke title and size.
World Wide WebChanges in Web client access patterns: Characteristics and caching implications
377 Citations1999Paul Barford, Azer Bestavros +2 more
This study compares two measurements of Web client workloads separated in time by three years, both captured from the same computing facility at Boston University and finds that for the computing facility represented by traces between 1995 and 1998, the benefits of using size‐based caching policies have diminished and the potential for caching requested files in the network has declined.
ACM SIGMOD RecordSynchronizing a database to improve freshness
348 Citations2000Junghoo Cho, Héctor García-Molina
Computer Networks and ISDN SystemsA caching relay for the World Wide Web
294 Citations1994S. Glassman
The design and performance of a caching relay for the World Wide Web is described and the data gathered from the relay is used to make some general characterizations about the web.
SSRN Electronic JournalThe Nature of Markets in the World Wide Web
270 Citations2000Lada A. Adamic, Bernardo A. Huberman
It is found that the distribution of visitors per site follows a universal power law similar to that found by Pareto for income distributions, which implies that a small number of sites commands the traffic of a large segment of the Web population, a phenomenon reminiscent of winner-take-all markets.
Extracting Large-Scale Knowledge Bases from the Web
232 Citations1999Ravi Kumar, Prabhakar Raghavan +2 more
This paper develops novel algorithms for enumerating and organizing all web occurrences of certain subgraphs that are signatures of web phenomena such as tightly-focused topic communities, webrings, taxonomy trees, keiretsus, etc, and argues that these algorithms run efficiently in this model.
Computer Networks and ISDN SystemsThe Connectivity Server: fast access to linkage information on the Web
187 Citations1998Krishna Bharat, Andrei Broder +3 more
A server that provides linkage information for all pages indexed by the AltaVista search engine and can produce the entire neighbourhood of L up to a given distance, and envisage numerous other applications such as ranking, visualization, and classification.
Computer Networks and ISDN SystemsWebQuery: searching and visualizing the Web through connectivity
174 Citations1997S. Jeromy Carrière, Rick Kazman
This work examines links among the nodes returned in a keyword-based query, finding “interesting” sites that are highly connected to those sites returned by the original query by finding ‘hot spots’ on the Web that contain information germane to a user's query.
Synchronizing a database to improve freshness
167 Citations2000Junghoo Cho, Héctor García-Molina
This paper studies how to refresh a local copy of an autonomous data source to maintain the copy up-to-date, and defines two freshness metrics, change models of the underlying data, and synchronization policies.
Identifying aggregates in hypertext structures
155 Citations1991Rodrigo A. Botafogo, Ben Shneiderman
This paper studies the hypertext structure, i.e., the way nodes are linked to each other in order to find aggregates in hypertext databases, using two graph theoretical algorithms: biconnected components and strongly connected components.
Life, death, and lawfulness on the electronic frontier
152 Citations1997James E. Pitkow, Peter Pirolli
To facilitate users’ ability to make sense of large collections of hypertext, two new techniques for inducing clusters of related documents on the World Wide Web are presented.
Computer NetworksSurfing the Web backwards
45 Citations1999Soumen Chakrabarti, David Gibson +1 more
This work investigates the effects of discovering `backlinks' from Web resources, namely links pointing to the resource, and describes tools for backlink navigation on both the client and server side, using an applet for the client or module for the Apache Web server.
Computers & ChemistryOligonucleotide frequencies in DNA follow a Yule distribution
40 Citations1996Colin Martindale, Andrzej K. Konopka
It is shown that ranked oligonucleotide frequencies in both protein-coding and non-Coding regions from several genomes fit poorly to the Zipf distribution, but that the same frequency data give excellent fit to the Yule distribution.
Surfing as a real option
17 Citations1998Rajan M. Lukose, Bernardo A. Huberman
The options viewpoint is considered as a descriptive theory of information foraging by Internet users, and it is shown how it leads to a kind of “law of surfing” which has been verified experimentally in several large independent datasets.