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 N76717fccd03c428cb3b12dceccbab33b
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 N4e96b69dce0b4e148c8255487b9334fc
22 schema:genre chapter
23 schema:inLanguage en
24 schema:isAccessibleForFree true
25 schema:isPartOf N926786d41fce4aa7afc8d9570b47081e
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 N088fe2d727ae4c9591b1c51b213d2018
29 N85456ae90a01414ebb6309b0501a21d6
30 Nc2edcc1f95a441c2b8f1024ed156f333
31 schema:publisher N209d3d20b97847dab1a53905bfd6adc4
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 N272ec70ea5b84218a36810e21bc6769e
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 N088fe2d727ae4c9591b1c51b213d2018 schema:name readcube_id
42 schema:value 80a1c36529b50025f5d3ff39d1101ad11f5a3928eb83d6dfa5238be925f6c6a9
43 rdf:type schema:PropertyValue
44 N18a03c6f13304822bdf25f15faa10cec rdf:first sg:person.014077576120.58
45 rdf:rest Nc0ab4bd0444f4ee08b48f71cab9e4762
46 N209d3d20b97847dab1a53905bfd6adc4 schema:location Berlin, Heidelberg
47 schema:name Springer Berlin Heidelberg
48 rdf:type schema:Organisation
49 N272ec70ea5b84218a36810e21bc6769e schema:name Springer Nature - SN SciGraph project
50 rdf:type schema:Organization
51 N3a3d587db45c472b8c30a285971cc2ae rdf:first Nfb81cdd118484efd932abaae6bebecaa
52 rdf:rest N688beb6e3e814efe9acd22600c9d239b
53 N4e96b69dce0b4e148c8255487b9334fc rdf:first Nb66ac0008457438da1295d259e063607
54 rdf:rest Nfe84d7e26f4e4048a28943b886c013a2
55 N56f91f21e58945589d40b1c3469ad33e schema:familyName Walukiewicz
56 schema:givenName Igor
57 rdf:type schema:Person
58 N5cb31125f28d4f18bdb64ba7705c0542 rdf:first N56f91f21e58945589d40b1c3469ad33e
59 rdf:rest rdf:nil
60 N688beb6e3e814efe9acd22600c9d239b rdf:first Nfd9a658084324df59dcb8e869374b13d
61 rdf:rest N9dfa569e432f43cf88991f87d642dd70
62 N76717fccd03c428cb3b12dceccbab33b rdf:first sg:person.014314002114.06
63 rdf:rest N18a03c6f13304822bdf25f15faa10cec
64 N85456ae90a01414ebb6309b0501a21d6 schema:name dimensions_id
65 schema:value pub.1027002019
66 rdf:type schema:PropertyValue
67 N926786d41fce4aa7afc8d9570b47081e schema:isbn 978-3-540-70574-1
68 978-3-540-70575-8
69 schema:name Automata, Languages and Programming
70 rdf:type schema:Book
71 N9dfa569e432f43cf88991f87d642dd70 rdf:first Na0fb50e71e8b4c7a908f12fc0afa11a2
72 rdf:rest N5cb31125f28d4f18bdb64ba7705c0542
73 Na0fb50e71e8b4c7a908f12fc0afa11a2 schema:familyName Ingólfsdóttir
74 schema:givenName Anna
75 rdf:type schema:Person
76 Nac26198a62604e3e955c0a40100e0763 schema:familyName Damgård
77 schema:givenName Ivan
78 rdf:type schema:Person
79 Nb66ac0008457438da1295d259e063607 schema:familyName Aceto
80 schema:givenName Luca
81 rdf:type schema:Person
82 Nc0ab4bd0444f4ee08b48f71cab9e4762 rdf:first sg:person.016146173625.97
83 rdf:rest rdf:nil
84 Nc2edcc1f95a441c2b8f1024ed156f333 schema:name doi
85 schema:value 10.1007/978-3-540-70575-8_11
86 rdf:type schema:PropertyValue
87 Nfb81cdd118484efd932abaae6bebecaa schema:familyName Goldberg
88 schema:givenName Leslie Ann
89 rdf:type schema:Person
90 Nfd9a658084324df59dcb8e869374b13d schema:familyName Halldórsson
91 schema:givenName Magnús M.
92 rdf:type schema:Person
93 Nfe84d7e26f4e4048a28943b886c013a2 rdf:first Nac26198a62604e3e955c0a40100e0763
94 rdf:rest N3a3d587db45c472b8c30a285971cc2ae
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)


...