How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs) View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

Chen Avin , Michal Koucký , Zvi Lotker

ABSTRACT

Motivated by real world networks and use of algorithms based on random walks on these networks we study the simple random walks on dynamic undirected graphs with fixed underlying vertex set, i.e., graphs which are modified by inserting or deleting edges at every step of the walk. We are interested in the expected time needed to visit all the vertices of such a dynamic graph, the cover time, under the assumption that the graph is being modified by an oblivious adversary. It is well known that on connected static undirected graphs the cover time is polynomial in the size of the graph. On the contrary and somewhat counter-intuitively, we show that there are adversary strategies which force the expected cover time of a simple random walk on connected dynamic graphs to be exponential. We relate this result to the cover time of static directed graphs. In addition we provide a simple strategy, the lazy random walk, that guarantees polynomial cover time regardless of the changes made by the adversary. More... »

PAGES

121-132

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-70574-1
978-3-540-70575-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-70575-8_11

DOI

http://dx.doi.org/10.1007/978-3-540-70575-8_11

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Ben-Gurion University of the Negev", 
          "id": "https://www.grid.ac/institutes/grid.7489.2", 
          "name": [
            "Communication Systems Engineering, Ben Gurion University of the Negev, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Avin", 
        "givenName": "Chen", 
        "id": "sg:person.014314002114.06", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014314002114.06"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Mathematics", 
          "id": "https://www.grid.ac/institutes/grid.425493.d", 
          "name": [
            "Institute of Mathematics, Academy of Sciences of the Czech Republic,"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kouck\u00fd", 
        "givenName": "Michal", 
        "id": "sg:person.014077576120.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014077576120.58"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Ben-Gurion University of the Negev", 
          "id": "https://www.grid.ac/institutes/grid.7489.2", 
          "name": [
            "Communication Systems Engineering, Ben Gurion University of the Negev, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lotker", 
        "givenName": "Zvi", 
        "id": "sg:person.016146173625.97", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016146173625.97"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/1378533.1378557", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016488827"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/15427951.2004.10129078", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024887618"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1022630.1022635", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035052568"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s1389-1286(99)00016-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036300508"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/984622.984663", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037526827"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/rsa.3240060406", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045548779"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/rsa.3240060106", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049928949"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.adhoc.2003.08.001", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052155863"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/mnet.2004.1337732", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061411423"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0218077", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842176"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1979.34", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086254113"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.2003.1238221", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094284548"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/infcom.2004.1354487", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094745491"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/nca.2007.35", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095154447"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2008", 
    "datePublishedReg": "2008-01-01", 
    "description": "Motivated by real world networks and use of algorithms based on random walks on these networks we study the simple random walks on dynamic undirected graphs with fixed underlying vertex set, i.e., graphs which are modified by inserting or deleting edges at every step of the walk. We are interested in the expected time needed to visit all the vertices of such a dynamic graph, the cover time, under the assumption that the graph is being modified by an oblivious adversary. It is well known that on connected static undirected graphs the cover time is polynomial in the size of the graph. On the contrary and somewhat counter-intuitively, we show that there are adversary strategies which force the expected cover time of a simple random walk on connected dynamic graphs to be exponential. We relate this result to the cover time of static directed graphs. In addition we provide a simple strategy, the lazy random walk, that guarantees polynomial cover time regardless of the changes made by the adversary.", 
    "editor": [
      {
        "familyName": "Aceto", 
        "givenName": "Luca", 
        "type": "Person"
      }, 
      {
        "familyName": "Damg\u00e5rd", 
        "givenName": "Ivan", 
        "type": "Person"
      }, 
      {
        "familyName": "Goldberg", 
        "givenName": "Leslie Ann", 
        "type": "Person"
      }, 
      {
        "familyName": "Halld\u00f3rsson", 
        "givenName": "Magn\u00fas M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Ing\u00f3lfsd\u00f3ttir", 
        "givenName": "Anna", 
        "type": "Person"
      }, 
      {
        "familyName": "Walukiewicz", 
        "givenName": "Igor", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-70575-8_11", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-70574-1", 
        "978-3-540-70575-8"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "name": "How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)", 
    "pagination": "121-132", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-70575-8_11"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "80a1c36529b50025f5d3ff39d1101ad11f5a3928eb83d6dfa5238be925f6c6a9"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027002019"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-70575-8_11", 
      "https://app.dimensions.ai/details/publication/pub.1027002019"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T01:23", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8700_00000566.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-540-70575-8_11"
  }
]
 

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/978-3-540-70575-8_11'

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/978-3-540-70575-8_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-70575-8_11'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-70575-8_11'


 

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

149 TRIPLES      23 PREDICATES      41 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-70575-8_11 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N8ff4d3f5223144f5844df4121b6160e7
4 schema:citation https://doi.org/10.1002/rsa.3240060106
5 https://doi.org/10.1002/rsa.3240060406
6 https://doi.org/10.1016/j.adhoc.2003.08.001
7 https://doi.org/10.1016/s1389-1286(99)00016-x
8 https://doi.org/10.1080/15427951.2004.10129078
9 https://doi.org/10.1109/infcom.2004.1354487
10 https://doi.org/10.1109/mnet.2004.1337732
11 https://doi.org/10.1109/nca.2007.35
12 https://doi.org/10.1109/sfcs.1979.34
13 https://doi.org/10.1109/sfcs.2003.1238221
14 https://doi.org/10.1137/0218077
15 https://doi.org/10.1145/1022630.1022635
16 https://doi.org/10.1145/1378533.1378557
17 https://doi.org/10.1145/984622.984663
18 schema:datePublished 2008
19 schema:datePublishedReg 2008-01-01
20 schema:description Motivated by real world networks and use of algorithms based on random walks on these networks we study the simple random walks on dynamic undirected graphs with fixed underlying vertex set, i.e., graphs which are modified by inserting or deleting edges at every step of the walk. We are interested in the expected time needed to visit all the vertices of such a dynamic graph, the cover time, under the assumption that the graph is being modified by an oblivious adversary. It is well known that on connected static undirected graphs the cover time is polynomial in the size of the graph. On the contrary and somewhat counter-intuitively, we show that there are adversary strategies which force the expected cover time of a simple random walk on connected dynamic graphs to be exponential. We relate this result to the cover time of static directed graphs. In addition we provide a simple strategy, the lazy random walk, that guarantees polynomial cover time regardless of the changes made by the adversary.
21 schema:editor N98f7a81a3f1342d595e84ecef1a93dcc
22 schema:genre chapter
23 schema:inLanguage en
24 schema:isAccessibleForFree true
25 schema:isPartOf N4e3f8d40ddde40faa07608bd07692a8c
26 schema:name How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
27 schema:pagination 121-132
28 schema:productId N8c9a459aae024f36a21c25e1921c0046
29 Nc9a032a0ea2a411ba7a667e0a557f2c6
30 Nd519fd772f4b44c58c8a6246ca582aaa
31 schema:publisher N79675c3844a0429281c2c9798147c342
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027002019
33 https://doi.org/10.1007/978-3-540-70575-8_11
34 schema:sdDatePublished 2019-04-16T01:23
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher Nfd978e9dc8854483aff2b0198d7d521b
37 schema:url http://link.springer.com/10.1007/978-3-540-70575-8_11
38 sgo:license sg:explorer/license/
39 sgo:sdDataset chapters
40 rdf:type schema:Chapter
41 N0356aa39067240afbfef934a17c29949 schema:familyName Halldórsson
42 schema:givenName Magnús M.
43 rdf:type schema:Person
44 N03a76a2fb4eb419fa45eca141070c2a0 schema:familyName Ingólfsdóttir
45 schema:givenName Anna
46 rdf:type schema:Person
47 N08c3706818e0458cb2b84b9e280cd42f rdf:first N8158f620051e491e96430a6f32bb6800
48 rdf:rest N2a2488f42789478f95fdbc257784a24e
49 N2a2488f42789478f95fdbc257784a24e rdf:first N0356aa39067240afbfef934a17c29949
50 rdf:rest N422446a1c5bb4285b317cb0ef17bca91
51 N422446a1c5bb4285b317cb0ef17bca91 rdf:first N03a76a2fb4eb419fa45eca141070c2a0
52 rdf:rest Na15feab28bde4994bb44eed79e4b00a8
53 N4e3f8d40ddde40faa07608bd07692a8c schema:isbn 978-3-540-70574-1
54 978-3-540-70575-8
55 schema:name Automata, Languages and Programming
56 rdf:type schema:Book
57 N5151a3a060be4ef49abe490031513d1e rdf:first Nf333e6792f6042298676ca8aa7b4adc6
58 rdf:rest N08c3706818e0458cb2b84b9e280cd42f
59 N79675c3844a0429281c2c9798147c342 schema:location Berlin, Heidelberg
60 schema:name Springer Berlin Heidelberg
61 rdf:type schema:Organisation
62 N8158f620051e491e96430a6f32bb6800 schema:familyName Goldberg
63 schema:givenName Leslie Ann
64 rdf:type schema:Person
65 N8c9a459aae024f36a21c25e1921c0046 schema:name dimensions_id
66 schema:value pub.1027002019
67 rdf:type schema:PropertyValue
68 N8ff4d3f5223144f5844df4121b6160e7 rdf:first sg:person.014314002114.06
69 rdf:rest Nc5d07a19f0424992bc3e68390e6e12dd
70 N98f7a81a3f1342d595e84ecef1a93dcc rdf:first Nbc6e310a7bf24483b0ba49bd33c57c3d
71 rdf:rest N5151a3a060be4ef49abe490031513d1e
72 Na15feab28bde4994bb44eed79e4b00a8 rdf:first Ndcd944d27fb747019d3fddbf76cd56d1
73 rdf:rest rdf:nil
74 Nbc6e310a7bf24483b0ba49bd33c57c3d schema:familyName Aceto
75 schema:givenName Luca
76 rdf:type schema:Person
77 Nc5d07a19f0424992bc3e68390e6e12dd rdf:first sg:person.014077576120.58
78 rdf:rest Ne7734eea2be144a7ab708fb882f6d57a
79 Nc9a032a0ea2a411ba7a667e0a557f2c6 schema:name doi
80 schema:value 10.1007/978-3-540-70575-8_11
81 rdf:type schema:PropertyValue
82 Nd519fd772f4b44c58c8a6246ca582aaa schema:name readcube_id
83 schema:value 80a1c36529b50025f5d3ff39d1101ad11f5a3928eb83d6dfa5238be925f6c6a9
84 rdf:type schema:PropertyValue
85 Ndcd944d27fb747019d3fddbf76cd56d1 schema:familyName Walukiewicz
86 schema:givenName Igor
87 rdf:type schema:Person
88 Ne7734eea2be144a7ab708fb882f6d57a rdf:first sg:person.016146173625.97
89 rdf:rest rdf:nil
90 Nf333e6792f6042298676ca8aa7b4adc6 schema:familyName Damgård
91 schema:givenName Ivan
92 rdf:type schema:Person
93 Nfd978e9dc8854483aff2b0198d7d521b schema:name Springer Nature - SN SciGraph project
94 rdf:type schema:Organization
95 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
96 schema:name Information and Computing Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
99 schema:name Computation Theory and Mathematics
100 rdf:type schema:DefinedTerm
101 sg:person.014077576120.58 schema:affiliation https://www.grid.ac/institutes/grid.425493.d
102 schema:familyName Koucký
103 schema:givenName Michal
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014077576120.58
105 rdf:type schema:Person
106 sg:person.014314002114.06 schema:affiliation https://www.grid.ac/institutes/grid.7489.2
107 schema:familyName Avin
108 schema:givenName Chen
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014314002114.06
110 rdf:type schema:Person
111 sg:person.016146173625.97 schema:affiliation https://www.grid.ac/institutes/grid.7489.2
112 schema:familyName Lotker
113 schema:givenName Zvi
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016146173625.97
115 rdf:type schema:Person
116 https://doi.org/10.1002/rsa.3240060106 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049928949
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1002/rsa.3240060406 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045548779
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1016/j.adhoc.2003.08.001 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052155863
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1016/s1389-1286(99)00016-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1036300508
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1080/15427951.2004.10129078 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024887618
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1109/infcom.2004.1354487 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094745491
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1109/mnet.2004.1337732 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061411423
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1109/nca.2007.35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095154447
131 rdf:type schema:CreativeWork
132 https://doi.org/10.1109/sfcs.1979.34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086254113
133 rdf:type schema:CreativeWork
134 https://doi.org/10.1109/sfcs.2003.1238221 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094284548
135 rdf:type schema:CreativeWork
136 https://doi.org/10.1137/0218077 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842176
137 rdf:type schema:CreativeWork
138 https://doi.org/10.1145/1022630.1022635 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035052568
139 rdf:type schema:CreativeWork
140 https://doi.org/10.1145/1378533.1378557 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016488827
141 rdf:type schema:CreativeWork
142 https://doi.org/10.1145/984622.984663 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037526827
143 rdf:type schema:CreativeWork
144 https://www.grid.ac/institutes/grid.425493.d schema:alternateName Institute of Mathematics
145 schema:name Institute of Mathematics, Academy of Sciences of the Czech Republic,
146 rdf:type schema:Organization
147 https://www.grid.ac/institutes/grid.7489.2 schema:alternateName Ben-Gurion University of the Negev
148 schema:name Communication Systems Engineering, Ben Gurion University of the Negev, Israel
149 rdf:type schema:Organization
 




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


...