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 N9a33b17892a64fa6bdf86599bda216c8
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 Ne855c14d1cab4d009b793c8088d53c98
22 schema:genre chapter
23 schema:inLanguage en
24 schema:isAccessibleForFree true
25 schema:isPartOf N157d7f50b9ea420da84e63499aee8de0
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 N1928fc98e4ee4c9da42be9d1543732d8
29 N44c719dba36a4f79baecc0c5fbb97632
30 Ndc7496f7b97340b38a9c2c8fa7ab365e
31 schema:publisher Naf5ebab7ba2f42c998cc98f3f53567aa
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 Nab1456d0936b411795a2bcd93f3b44b6
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 N0d7ea2cb34ae42a1b36fee03ec9dc39b rdf:first N97f4ac9752544887b952e2e726ba47b1
42 rdf:rest Nd2bb63c2cf5f4d2ea6f348ed9f803b84
43 N157d7f50b9ea420da84e63499aee8de0 schema:isbn 978-3-540-70574-1
44 978-3-540-70575-8
45 schema:name Automata, Languages and Programming
46 rdf:type schema:Book
47 N1928fc98e4ee4c9da42be9d1543732d8 schema:name dimensions_id
48 schema:value pub.1027002019
49 rdf:type schema:PropertyValue
50 N388eb8042bbc4cc78ef43f5007b02000 schema:familyName Walukiewicz
51 schema:givenName Igor
52 rdf:type schema:Person
53 N44c719dba36a4f79baecc0c5fbb97632 schema:name doi
54 schema:value 10.1007/978-3-540-70575-8_11
55 rdf:type schema:PropertyValue
56 N4c24f9977bae4c279ecd46af6a20c5e6 rdf:first N388eb8042bbc4cc78ef43f5007b02000
57 rdf:rest rdf:nil
58 N53b3aba1564941bf8d6bd57c0c4bcbdb rdf:first sg:person.014077576120.58
59 rdf:rest Ne394724606b345fe940401981ced423a
60 N87673ca226244503a217f14df83a80eb rdf:first Nbf4416e533c74fec8bd7db794fb7131e
61 rdf:rest N0d7ea2cb34ae42a1b36fee03ec9dc39b
62 N97f4ac9752544887b952e2e726ba47b1 schema:familyName Halldórsson
63 schema:givenName Magnús M.
64 rdf:type schema:Person
65 N9a33b17892a64fa6bdf86599bda216c8 rdf:first sg:person.014314002114.06
66 rdf:rest N53b3aba1564941bf8d6bd57c0c4bcbdb
67 N9a587cfdec254e5ea482b9f7c8233adb schema:familyName Damgård
68 schema:givenName Ivan
69 rdf:type schema:Person
70 Na3196238ce52437e97d0243bd9deafd6 schema:familyName Ingólfsdóttir
71 schema:givenName Anna
72 rdf:type schema:Person
73 Nab1456d0936b411795a2bcd93f3b44b6 schema:name Springer Nature - SN SciGraph project
74 rdf:type schema:Organization
75 Naf5ebab7ba2f42c998cc98f3f53567aa schema:location Berlin, Heidelberg
76 schema:name Springer Berlin Heidelberg
77 rdf:type schema:Organisation
78 Nb06f0541d8d24d3fa9fc85f30126c869 rdf:first N9a587cfdec254e5ea482b9f7c8233adb
79 rdf:rest N87673ca226244503a217f14df83a80eb
80 Nb589d62da94d4d2ba6edfa754ce442e5 schema:familyName Aceto
81 schema:givenName Luca
82 rdf:type schema:Person
83 Nbf4416e533c74fec8bd7db794fb7131e schema:familyName Goldberg
84 schema:givenName Leslie Ann
85 rdf:type schema:Person
86 Nd2bb63c2cf5f4d2ea6f348ed9f803b84 rdf:first Na3196238ce52437e97d0243bd9deafd6
87 rdf:rest N4c24f9977bae4c279ecd46af6a20c5e6
88 Ndc7496f7b97340b38a9c2c8fa7ab365e schema:name readcube_id
89 schema:value 80a1c36529b50025f5d3ff39d1101ad11f5a3928eb83d6dfa5238be925f6c6a9
90 rdf:type schema:PropertyValue
91 Ne394724606b345fe940401981ced423a rdf:first sg:person.016146173625.97
92 rdf:rest rdf:nil
93 Ne855c14d1cab4d009b793c8088d53c98 rdf:first Nb589d62da94d4d2ba6edfa754ce442e5
94 rdf:rest Nb06f0541d8d24d3fa9fc85f30126c869
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)


...