On the Periodicity of Random Walks in Dynamic Networks

Bernard Chazelle

doi:10.1109/TNSE.2019.2924921

On the Periodicity of Random Walks in Dynamic Networks

Bernard Chazelle

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

We investigate random walks in graphs whose edges change over time as a function of the current probability distribution of the walk. We show that such systems can be chaotic and can exhibit 'hyper-torpid' mixing. Our main result is that, if each graph is strongly connected, then the dynamics is asymptotically periodic almost surely.

Original language	English (US)
Article number	8747524
Pages (from-to)	1337-1343
Number of pages	7
Journal	IEEE Transactions on Network Science and Engineering
Volume	7
Issue number	3
DOIs	https://doi.org/10.1109/TNSE.2019.2924921
State	Published - Jul 1 2020
Externally published	Yes

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Computer Science Applications
Computer Networks and Communications

Keywords

Markov influence systems
Random walks
chaos
hyper-torpid mixing
temporal networks

Access to Document

10.1109/TNSE.2019.2924921

Cite this

@article{b75db7e50afb4f549abbeda64ded923b,

title = "On the Periodicity of Random Walks in Dynamic Networks",

abstract = "We investigate random walks in graphs whose edges change over time as a function of the current probability distribution of the walk. We show that such systems can be chaotic and can exhibit 'hyper-torpid' mixing. Our main result is that, if each graph is strongly connected, then the dynamics is asymptotically periodic almost surely.",

keywords = "Markov influence systems, Random walks, chaos, hyper-torpid mixing, temporal networks",

author = "Bernard Chazelle",

note = "Publisher Copyright: {\textcopyright} 2013 IEEE.",

year = "2020",

month = jul,

day = "1",

doi = "10.1109/TNSE.2019.2924921",

language = "English (US)",

volume = "7",

pages = "1337--1343",

journal = "IEEE Transactions on Network Science and Engineering",

issn = "2327-4697",

publisher = "IEEE Computer Society",

number = "3",

}

TY - JOUR

T1 - On the Periodicity of Random Walks in Dynamic Networks

AU - Chazelle, Bernard

PY - 2020/7/1

Y1 - 2020/7/1

N2 - We investigate random walks in graphs whose edges change over time as a function of the current probability distribution of the walk. We show that such systems can be chaotic and can exhibit 'hyper-torpid' mixing. Our main result is that, if each graph is strongly connected, then the dynamics is asymptotically periodic almost surely.

AB - We investigate random walks in graphs whose edges change over time as a function of the current probability distribution of the walk. We show that such systems can be chaotic and can exhibit 'hyper-torpid' mixing. Our main result is that, if each graph is strongly connected, then the dynamics is asymptotically periodic almost surely.

KW - Markov influence systems

KW - Random walks

KW - chaos

KW - hyper-torpid mixing

KW - temporal networks

UR - https://www.scopus.com/pages/publications/85090982681

UR - https://www.scopus.com/pages/publications/85090982681#tab=citedBy

U2 - 10.1109/TNSE.2019.2924921

DO - 10.1109/TNSE.2019.2924921

M3 - Article

AN - SCOPUS:85090982681

SN - 2327-4697

VL - 7

SP - 1337

EP - 1343

JO - IEEE Transactions on Network Science and Engineering

JF - IEEE Transactions on Network Science and Engineering

IS - 3

M1 - 8747524

ER -

On the Periodicity of Random Walks in Dynamic Networks

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this