Random walks on small world networks

Random walks on small world networks

We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices {𝑢, 𝑣 } with distance 𝑑 > 1 is added as a “long-range" edge with probability proportional to 𝑑−𝑟, where 𝑟 ≥ 0 is a parameter of the model...

书目详细资料
Main Authors:	Dyer, ME, Galanis, A, Goldberg, L, Jerrum, M, Vigoda, E
格式:	Journal article
语言:	English
出版:	Association for Computing Machinery 2020

相似书籍

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
由: Goldberg, L, et al.
出版: (2015)

Approximately counting H-colourings is BIS-Hard
由: Galanis, A, et al.
出版: (2015)

A complexity trichotomy for approximately counting list H-colourings
由: Galanis, A, et al.
出版: (2017)

A complexity trichotomy for approximately counting list H-colourings
由: Goldberg, L, et al.
出版: (2016)

Approximately counting H-colourings is #BIS-hard
由: Galanis, A, et al.
出版: (2016)

Sampling in iniqueness from the Potts and random-cluster models on random regular graphs
由: Blanca, A, et al.
出版: (2020)

Sampling in uniqueness from the potts and random-cluster models on random regular graphs
由: Blanca, A, et al.
出版: (2018)

The Complexity of Weighted Boolean CSP
由: Dyer, M, et al.
出版: (2009)

An approximation trichotomy for Boolean #CSP
由: Dyer, M, et al.
出版: (2010)

Metastability of the Potts ferromagnet on random regular graphs
由: Coja-Oghlan, A, et al.
出版: (2022)

Metastability of the Potts ferromagnet on random regular graphs
由: Coja-Oghlan, A, et al.
出版: (2023)

Fast algorithms at low temperatures via Markov chains
由: Chen, Z, et al.
出版: (2020)

Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region
由: Galanis, A, et al.
出版: (2015)

Inapproximability of the partition function for the antiferromagnetic ising and hard-core models
由: Galanis, A, et al.
出版: (2016)

Swendsen-Wang algorithm on the mean-field Potts model
由: Galanis, A, et al.
出版: (2018)

The complexity of counting locally maximal satisfying assignments of Boolean CSPs
由: Goldberg, L, et al.
出版: (2016)

Approximating the partition function of the ferromagnetic potts model
由: Goldberg, L, et al.
出版: (2012)

Approximating pairwise correlations in the Ising model
由: Goldberg, L, et al.
出版: (2019)

A complexity classification of spin systems with an external field
由: Goldberg, L, et al.
出版: (2015)

Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
由: Galanis, A, et al.
出版: (2016)

Random walks and diffusion on networks
由: Masuda, N, et al.
出版: (2017)

Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics
由: Galanis, A, et al.
出版: (2024)

Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics
由: Galanis, A, et al.
出版: (2023)

Random walk centrality for temporal networks
由: Luis E C Rocha, et al.
出版: (2014-01-01)

Improved strong spatial mixing for colorings on trees
由: Efthymiou, C, et al.
出版: (2019)

Statistical analysis of random walks on network
由: A. Kalikova
出版: (2021-03-01)

Fast mixing via polymers for random graphs with unbounded degree
由: Galanis, A, et al.
出版: (2021)

Fast mixing via polymers for random graphs with unbounded degree
由: Galanis, A, et al.
出版: (2022)

Random walks on stochastic temporal networks
由: Hoffmann, T, et al.
出版: (2013)

Random walks on stochastic temporal networks
由: Hoffmann, T, et al.
出版: (2013)

Randomised random walk on a random walk /
由: 258250 Lee, P. A.
出版: (1983)

High-precision Estimation of Random Walks in Small Space
由: Ahmadinejad, AmirMahdi, et al.
出版: (2021)

Random walks in distributed networks and their applications
由: Anisur Rahaman Molla
出版: (2014)

A Complexity Dichotomy for Partition Functions with Mixed Signs
由: Goldberg, L, et al.
出版: (2010)

Functional brain networks: random, "small world" or deterministic?
由: Katarzyna J Blinowska, et al.
出版: (2013-01-01)

Random walk on temporal networks with lasting edges
由: Petit, J, et al.
出版: (2018)

Functional clones and expressibility of partition functions
由: Bulatov, A, et al.
出版: (2017)

Counting solutions to random CNF formulas
由: Galanis, A, et al.
出版: (2021)

Strong and weak random walks on signed networks
由: Babul, SA, et al.
出版: (2025)

Continuous-time random walks and temporal networks
由: Lambiotte, R
出版: (2019)