The Web as a Graph S. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, and Eli Upfal   View Paper (PDF)   Return to Invited Talk Abstract The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph has about a billion nodes today, several billion links, and appears to grow exponentially with time. There are many reasons--mathematical, sociological, and commercial--for studying the evolution of this graph. We first review a set of algorithms that operate on the Web graph, addressing problems from Web search, automatic community discovery, and classification. We then recall a number of measurements and properties of the Web graph. Noting that traditional random graph models do not explain these observations, we propose a new family of random graph models. References Note: References link to DBLP on the Web. [1] Serge Abiteboul , Dallan Quass , Jason McHugh , Jennifer Widom , Janet L. Wiener : The Lorel Query Language for Semistructured Data. Int. J. on Digital Libraries 1(1) : 68-88(1997) [2] ... [3] ... [4] Gustavo O. Arocena , Alberto O. Mendelzon , George A. Mihaila : Applications of a Web Query Language. WWW6 / Computer Networks 29(8-13) : 1305-1315(1997) [5] Krishna Bharat , Andrei Z. Broder : A Technique for Measuring the Relative Size and Overlap of Public Web Search Engines. WWW7 / Computer Networks 30(1-7) : 379-388(1998) [6] Krishna Bharat , Monika Rauch Henzinger : Improved Algorithms for Topic Distillation in a Hyperlinked Environment. SIGIR 1998 : 104-111 [7] Sergey Brin , Lawrence Page : The Anatomy of a Large-Scale Hypertextual Web Search Engine. WWW7 / Computer Networks 30(1-7) : 107-117(1998) [8] ... [9] ... [10] S. Jeromy Carrière , Rick Kazman : WebQuery: Searching and Visualizing the Web Through Connectivity. WWW6 / Computer Networks 29(8-13) : 1257-1267(1997) [11] Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon M. Kleinberg : Automatic Resource Compilation by Analyzing Hyperlink Structure and Associated Text. WWW7 / Computer Networks 30(1-7) : 65-74(1998) [12] Soumen Chakrabarti , Martin van den Berg , Byron Dom : Focused Crawling: A New Approach to Topic-Specific Web Resource Discovery. WWW8 / Computer Networks 31(11-16) : 1623-1640(1999) [13] ... [14] Soumen Chakrabarti , Byron Dom , Piotr Indyk : Enhanced Hypertext Categorization Using Hyperlinks. SIGMOD Conference 1998 : 307-318 [15] ... [16] ... [17] ... [18] Daniela Florescu , Alon Y. Levy , Alberto O. Mendelzon : Database Techniques for the World-Wide Web: A Survey. SIGMOD Record 27(3) : 59-74(1998) [19] ... [20] ... [21] ... [22] ... [23] Jon M. Kleinberg : Authoritative Sources in a Hyperlinked Environment. JACM 46(5) : 604-632(1999) [24] David Konopnicki , Oded Shmueli : Information Gathering in the World-Wide Web: The W3QL Query Language and the W3QS System. TODS 23(4) : 369-410(1998) [25] S. Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins : Trawling the Web for Emerging Cyber-Communities. WWW8 / Computer Networks 31(11-16) : 1481-1493(1999) [26] S. Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins : Extracting Large-Scale Knowledge Bases from the Web. VLDB 1999 : 639-650 [27] Laks V. S. Lakshmanan , Fereidoon Sadri , Iyer N. Subramanian : A Declarative Language for Querying and Restructuring the WEB. RIDE-NDS 1996 : 12-21 [28] ... [29] ... [30] Alberto O. Mendelzon , George A. Mihaila , Tova Milo : Querying the World Wide Web. Int. J. on Digital Libraries 1(1) : 54-67(1997) [31] Alberto O. Mendelzon , Peter T. Wood : Finding Regular Simple Paths in Graph Databases. SIAM J. Comput. 24(6) : 1235-1258(1995) [32] Ellen Spertus : ParaSite: Mining Structural Information on the Web. WWW6 / Computer Networks 29(8-13) : 1205-1215(1997) [33] George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949 BIBTEX @inproceedings{DBLP:conf/pods/KumarRRSTU00,   author    = {S. Ravi Kumar and                 Prabhakar Raghavan and                 Sridhar Rajagopalan and                 D. Sivakumar and                 Andrew Tomkins and                 Eli Upfal},    title     = {The Web as a Graph},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {1-10},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.