The Web as a Graph: Measurements, Models, and Methods View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1999-06-25

AUTHORS

Jon M. Kleinberg , Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew S. Tomkins

ABSTRACT

The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph is a fascinating object of study: it has several hundred million nodes today, over a billion links, and appears to grow exponentially with time. There are many reasons — mathematical, sociological, and commercial — for studying the evolution of this graph. In this paper we begin by describing two algorithms that operate on the Web graph, addressing problems from Web search and automatic community discovery. We then report a number of measurements and properties of this graph that manifested themselves as we ran these algorithms on the Web. Finally, we observe that traditional random graph models do not explain these observations, and we propose a new family of random graph models. These models point to a rich new sub-field of the study of random graphs, and raise questions about the analysis of graph algorithms on the Web. More... »

PAGES

1-17

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48686-0_1

DOI

http://dx.doi.org/10.1007/3-540-48686-0_1

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1015730489


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Cornell University, 14853, Ithaca, NY", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Department of Computer Science, Cornell University, 14853, Ithaca, NY"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kleinberg", 
        "givenName": "Jon M.", 
        "id": "sg:person.011522233557.04", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Almaden Research Center K53/B1, 650 Harry Road, 95120, San Jose, CA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center K53/B1, 650 Harry Road, 95120, San Jose, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kumar", 
        "givenName": "Ravi", 
        "id": "sg:person.012261427377.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012261427377.07"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Almaden Research Center K53/B1, 650 Harry Road, 95120, San Jose, CA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center K53/B1, 650 Harry Road, 95120, San Jose, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Raghavan", 
        "givenName": "Prabhakar", 
        "id": "sg:person.012437241622.81", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012437241622.81"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Almaden Research Center K53/B1, 650 Harry Road, 95120, San Jose, CA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center K53/B1, 650 Harry Road, 95120, San Jose, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rajagopalan", 
        "givenName": "Sridhar", 
        "id": "sg:person.012761640703.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012761640703.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Almaden Research Center K53/B1, 650 Harry Road, 95120, San Jose, CA", 
          "id": "http://www.grid.ac/institutes/grid.481551.c", 
          "name": [
            "IBM Almaden Research Center K53/B1, 650 Harry Road, 95120, San Jose, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tomkins", 
        "givenName": "Andrew S.", 
        "id": "sg:person.011254402771.90", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011254402771.90"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1999-06-25", 
    "datePublishedReg": "1999-06-25", 
    "description": "The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph is a fascinating object of study: it has several hundred million nodes today, over a billion links, and appears to grow exponentially with time. There are many reasons \u2014 mathematical, sociological, and commercial \u2014 for studying the evolution of this graph. In this paper we begin by describing two algorithms that operate on the Web graph, addressing problems from Web search and automatic community discovery. We then report a number of measurements and properties of this graph that manifested themselves as we ran these algorithms on the Web. Finally, we observe that traditional random graph models do not explain these observations, and we propose a new family of random graph models. These models point to a rich new sub-field of the study of random graphs, and raise questions about the analysis of graph algorithms on the Web.", 
    "editor": [
      {
        "familyName": "Asano", 
        "givenName": "Takano", 
        "type": "Person"
      }, 
      {
        "familyName": "Imai", 
        "givenName": "Hideki", 
        "type": "Person"
      }, 
      {
        "familyName": "Lee", 
        "givenName": "D. T.", 
        "type": "Person"
      }, 
      {
        "familyName": "Nakano", 
        "givenName": "Shin-ichi", 
        "type": "Person"
      }, 
      {
        "familyName": "Tokuyama", 
        "givenName": "Takeshi", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48686-0_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66200-6", 
        "978-3-540-48686-2"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "traditional random graph models", 
      "graph model", 
      "World-Wide Web", 
      "random graph models", 
      "community discovery", 
      "web search", 
      "web graph", 
      "graph algorithms", 
      "algorithm", 
      "Web", 
      "number of measurements", 
      "graph", 
      "random graphs", 
      "hyperlinks", 
      "pages", 
      "nodes", 
      "objects", 
      "model", 
      "search", 
      "today", 
      "new family", 
      "link", 
      "discovery", 
      "edge", 
      "method", 
      "fascinating objects", 
      "problem", 
      "number", 
      "time", 
      "analysis", 
      "evolution", 
      "questions", 
      "properties", 
      "measurements", 
      "family", 
      "observations", 
      "study", 
      "paper", 
      "nodes today", 
      "automatic community discovery"
    ], 
    "name": "The Web as a Graph: Measurements, Models, and Methods", 
    "pagination": "1-17", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1015730489"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48686-0_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48686-0_1", 
      "https://app.dimensions.ai/details/publication/pub.1015730489"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:18", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_318.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-48686-0_1"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-48686-0_1'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-48686-0_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48686-0_1'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-48686-0_1'


 

This table displays all metadata directly associated to this object as RDF triples.

155 TRIPLES      23 PREDICATES      66 URIs      58 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48686-0_1 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 anzsrc-for:0802
4 schema:author N93b49cc1d76d45439d21db09030ec4a9
5 schema:datePublished 1999-06-25
6 schema:datePublishedReg 1999-06-25
7 schema:description The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph is a fascinating object of study: it has several hundred million nodes today, over a billion links, and appears to grow exponentially with time. There are many reasons — mathematical, sociological, and commercial — for studying the evolution of this graph. In this paper we begin by describing two algorithms that operate on the Web graph, addressing problems from Web search and automatic community discovery. We then report a number of measurements and properties of this graph that manifested themselves as we ran these algorithms on the Web. Finally, we observe that traditional random graph models do not explain these observations, and we propose a new family of random graph models. These models point to a rich new sub-field of the study of random graphs, and raise questions about the analysis of graph algorithms on the Web.
8 schema:editor Nf501e01290664684841ad1b87b0dd942
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf Nd4d0f8deaac24fee9208297bb77dae81
13 schema:keywords Web
14 World-Wide Web
15 algorithm
16 analysis
17 automatic community discovery
18 community discovery
19 discovery
20 edge
21 evolution
22 family
23 fascinating objects
24 graph
25 graph algorithms
26 graph model
27 hyperlinks
28 link
29 measurements
30 method
31 model
32 new family
33 nodes
34 nodes today
35 number
36 number of measurements
37 objects
38 observations
39 pages
40 paper
41 problem
42 properties
43 questions
44 random graph models
45 random graphs
46 search
47 study
48 time
49 today
50 traditional random graph models
51 web graph
52 web search
53 schema:name The Web as a Graph: Measurements, Models, and Methods
54 schema:pagination 1-17
55 schema:productId Nd091364de9e14cd7a33d93c81bb9925f
56 Nd3f7181fbf964ffe84d115427e23f05e
57 schema:publisher N7b9218d1b08946b1a3545eb0d5f2f792
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015730489
59 https://doi.org/10.1007/3-540-48686-0_1
60 schema:sdDatePublished 2022-01-01T19:18
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher N6f406c1ef7314dfa9aca4092544e9b94
63 schema:url https://doi.org/10.1007/3-540-48686-0_1
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N1497beaa1ef345e394cf881b798749aa rdf:first sg:person.012437241622.81
68 rdf:rest N90db7f891abf4a34b397015c21167444
69 N1cb30fd033f14dbaaf9870bbaf5dbc4e rdf:first N48b64303451a4c0f86addb3e37b05b74
70 rdf:rest N38a4594aad5247be9e2f3d164852116c
71 N27257086b823407da9b02c869256a0f9 schema:familyName Imai
72 schema:givenName Hideki
73 rdf:type schema:Person
74 N38a4594aad5247be9e2f3d164852116c rdf:first Nf1bb8225fcb549ac8b38f7c296e4b6b9
75 rdf:rest N889f1125daeb4dbeb4b0fc70e86df59b
76 N3a1c54b1aa1c437988589117d82365ec schema:familyName Asano
77 schema:givenName Takano
78 rdf:type schema:Person
79 N3f03ed7cc1324045921ea8cd7850a21e rdf:first N27257086b823407da9b02c869256a0f9
80 rdf:rest N1cb30fd033f14dbaaf9870bbaf5dbc4e
81 N466396c81a8149e6ad2ec8a5b1090067 rdf:first sg:person.012261427377.07
82 rdf:rest N1497beaa1ef345e394cf881b798749aa
83 N48b64303451a4c0f86addb3e37b05b74 schema:familyName Lee
84 schema:givenName D. T.
85 rdf:type schema:Person
86 N4b0f6b15618d4615b7de1300a47ce27a schema:familyName Tokuyama
87 schema:givenName Takeshi
88 rdf:type schema:Person
89 N6f406c1ef7314dfa9aca4092544e9b94 schema:name Springer Nature - SN SciGraph project
90 rdf:type schema:Organization
91 N7b9218d1b08946b1a3545eb0d5f2f792 schema:name Springer Nature
92 rdf:type schema:Organisation
93 N889f1125daeb4dbeb4b0fc70e86df59b rdf:first N4b0f6b15618d4615b7de1300a47ce27a
94 rdf:rest rdf:nil
95 N8b5b375cd0b14dea996f65f5f389f252 rdf:first sg:person.011254402771.90
96 rdf:rest rdf:nil
97 N90db7f891abf4a34b397015c21167444 rdf:first sg:person.012761640703.19
98 rdf:rest N8b5b375cd0b14dea996f65f5f389f252
99 N93b49cc1d76d45439d21db09030ec4a9 rdf:first sg:person.011522233557.04
100 rdf:rest N466396c81a8149e6ad2ec8a5b1090067
101 Nd091364de9e14cd7a33d93c81bb9925f schema:name dimensions_id
102 schema:value pub.1015730489
103 rdf:type schema:PropertyValue
104 Nd3f7181fbf964ffe84d115427e23f05e schema:name doi
105 schema:value 10.1007/3-540-48686-0_1
106 rdf:type schema:PropertyValue
107 Nd4d0f8deaac24fee9208297bb77dae81 schema:isbn 978-3-540-48686-2
108 978-3-540-66200-6
109 schema:name Computing and Combinatorics
110 rdf:type schema:Book
111 Nf1bb8225fcb549ac8b38f7c296e4b6b9 schema:familyName Nakano
112 schema:givenName Shin-ichi
113 rdf:type schema:Person
114 Nf501e01290664684841ad1b87b0dd942 rdf:first N3a1c54b1aa1c437988589117d82365ec
115 rdf:rest N3f03ed7cc1324045921ea8cd7850a21e
116 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
117 schema:name Information and Computing Sciences
118 rdf:type schema:DefinedTerm
119 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
120 schema:name Artificial Intelligence and Image Processing
121 rdf:type schema:DefinedTerm
122 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
123 schema:name Computation Theory and Mathematics
124 rdf:type schema:DefinedTerm
125 sg:person.011254402771.90 schema:affiliation grid-institutes:grid.481551.c
126 schema:familyName Tomkins
127 schema:givenName Andrew S.
128 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011254402771.90
129 rdf:type schema:Person
130 sg:person.011522233557.04 schema:affiliation grid-institutes:grid.5386.8
131 schema:familyName Kleinberg
132 schema:givenName Jon M.
133 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04
134 rdf:type schema:Person
135 sg:person.012261427377.07 schema:affiliation grid-institutes:grid.481551.c
136 schema:familyName Kumar
137 schema:givenName Ravi
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012261427377.07
139 rdf:type schema:Person
140 sg:person.012437241622.81 schema:affiliation grid-institutes:grid.481551.c
141 schema:familyName Raghavan
142 schema:givenName Prabhakar
143 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012437241622.81
144 rdf:type schema:Person
145 sg:person.012761640703.19 schema:affiliation grid-institutes:grid.481551.c
146 schema:familyName Rajagopalan
147 schema:givenName Sridhar
148 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012761640703.19
149 rdf:type schema:Person
150 grid-institutes:grid.481551.c schema:alternateName IBM Almaden Research Center K53/B1, 650 Harry Road, 95120, San Jose, CA
151 schema:name IBM Almaden Research Center K53/B1, 650 Harry Road, 95120, San Jose, CA
152 rdf:type schema:Organization
153 grid-institutes:grid.5386.8 schema:alternateName Department of Computer Science, Cornell University, 14853, Ithaca, NY
154 schema:name Department of Computer Science, Cornell University, 14853, Ithaca, NY
155 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...