Large scale properties of the Webgraph
The European Physical Journal BPublished 1 March 2004
Debora Donato, Luigi Laura, Stefano Leonardi, Stefano Millozzi
Citations97
SJR quartileQ3
SJR score0.38
SNIP0.63
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
Experimental findings on the topological properties of web graphs, such as the number of bipartite cores and the distribution of degree, PageRank values and strongly connected components are reported.
Abstract
\n In this paper we present an experimental study of the\nproperties of web graphs. We study a large crawl from 2001 of 200M\npages and about 1.4 billion edges made available by the WebBase\nproject at Stanford [CITE]. We report our experimental\nfindings on the topological properties of such graphs, such as the\nnumber of bipartite cores and the distribution of degree, PageRank\nvalues and strongly connected components. \n \n \n
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.
Journal of the ACMAuthoritative sources in a hyperlinked environment
9,060 Citations1999Jon Kleinberg
This work proposes and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure, and has connections to the eigenvectors of certain matrices associated with the link graph.
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.
Computer NetworksGraph structure in the Web
2,760 Citations2000Andrei Broder, Ravi Kumar +6 more
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.
Internet MathematicsA Brief History of Generative Models for Power Law and Lognormal Distributions
1,802 Citations2004Michael Mitzenmacher
A rich and long history is found of how lognormal distributions have arisen as a possible alternative to power law distributions across many fields, focusing on underlying generative models that lead to these distributions.
Physical Review LettersDynamical and Correlation Properties of the Internet
1,452 Citations2001Romualdo Pastor‐Satorras, Alexei Vázquez +1 more
It is found that the Internet is characterized by non-trivial correlations among nodes and different dynamical regimes, and the importance of node hierarchy and aging in the Internet structure and growth is pointed out.
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.
Journal of Statistical PhysicsModels of the Small World
714 Citations2000M. E. J. Newman
A review of the six degrees of separation phenomenon, which is believed that almost any pair of people in the world can be connected to one another by a short chain of intermediate acquaintances, of typical length about six.
Proceedings of the National Academy of SciencesWinners don't take all: Characterizing the competition for links on the web
461 Citations2002David M. Pennock, Gary William Flake +3 more
A simple generative model quantifies the degree to which the rich nodes grow richer, and how new (and poorly connected) nodes can compete, and accurately accounts for the true connectivity distributions of category-specific web pages, the web as a whole, and other social networks.
Efficient Computation of PageRank
294 Citations1999Taher H. Haveliwala
It is shown that PageRank can be computed for very large subgraphs of the web (up to hundreds of millions of nodes) on machines with limited main memory.
Internet MathematicsRobustness and Vulnerability of Scale-Free Random Graphs
279 Citations2004Béla Bollobás, Oliver Riordan
It is shown that the LCD graph is much more robust than classical random graphs with the same number of edges, but also more vulnerable to attack, namely robustness to random damage, and vulnerability to malicious attack.
Self-similarity in the Web
64 Citations2001Stephen Dill, Ravi Kumar +4 more
Lecture notes in computer scienceA General Model of Undirected Web Graphs
56 Citations2001Colin Cooper, Alan Frieze
A general model of a random graph process whose degree sequence obeys a power law, which has recently been observed in graphs associated with the world wide web, is described.
Lecture notes in computer scienceAlgorithms and Experiments for the Webgraph
44 Citations2003Luigi Laura, Stefano Leonardi +3 more
Heuristics for semi-external depth first search on directed graphs
33 Citations2002Jop F. Sibeyn, James Abello +1 more
A set of heuristics is developed which together allow the performance of semi-external DFS for directed graphs in practice, and is between 10 and 200 times faster than the best alternative, a factor that will further increase with future technological developments.