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...

書誌詳細
主要な著者:	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, 等
出版事項: (2015)

Approximately counting H-colourings is BIS-Hard
著者:: Galanis, A, 等
出版事項: (2015)

A complexity trichotomy for approximately counting list H-colourings
著者:: Galanis, A, 等
出版事項: (2017)

A complexity trichotomy for approximately counting list H-colourings
著者:: Goldberg, L, 等
出版事項: (2016)

Approximately counting H-colourings is #BIS-hard
著者:: Galanis, A, 等
出版事項: (2016)

Sampling in iniqueness from the Potts and random-cluster models on random regular graphs
著者:: Blanca, A, 等
出版事項: (2020)

Sampling in uniqueness from the potts and random-cluster models on random regular graphs
著者:: Blanca, A, 等
出版事項: (2018)

The Complexity of Weighted Boolean CSP
著者:: Dyer, M, 等
出版事項: (2009)

An approximation trichotomy for Boolean #CSP
著者:: Dyer, M, 等
出版事項: (2010)

Metastability of the Potts ferromagnet on random regular graphs
著者:: Coja-Oghlan, A, 等
出版事項: (2022)

Metastability of the Potts ferromagnet on random regular graphs
著者:: Coja-Oghlan, A, 等
出版事項: (2023)

Fast algorithms at low temperatures via Markov chains
著者:: Chen, Z, 等
出版事項: (2020)

Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region
著者:: Galanis, A, 等
出版事項: (2015)

Inapproximability of the partition function for the antiferromagnetic ising and hard-core models
著者:: Galanis, A, 等
出版事項: (2016)

Swendsen-Wang algorithm on the mean-field Potts model
著者:: Galanis, A, 等
出版事項: (2018)

The complexity of counting locally maximal satisfying assignments of Boolean CSPs
著者:: Goldberg, L, 等
出版事項: (2016)

Approximating the partition function of the ferromagnetic potts model
著者:: Goldberg, L, 等
出版事項: (2012)

Approximating pairwise correlations in the Ising model
著者:: Goldberg, L, 等
出版事項: (2019)

A complexity classification of spin systems with an external field
著者:: Goldberg, L, 等
出版事項: (2015)

Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
著者:: Galanis, A, 等
出版事項: (2016)

Random walks and diffusion on networks
著者:: Masuda, N, 等
出版事項: (2017)

Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics
著者:: Galanis, A, 等
出版事項: (2024)

Sampling from the random cluster model on random regular graphs at all temperatures via Glauber dynamics
著者:: Galanis, A, 等
出版事項: (2023)

Random walk centrality for temporal networks
著者:: Luis E C Rocha, 等
出版事項: (2014-01-01)

Improved strong spatial mixing for colorings on trees
著者:: Efthymiou, C, 等
出版事項: (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, 等
出版事項: (2021)

Fast mixing via polymers for random graphs with unbounded degree
著者:: Galanis, A, 等
出版事項: (2022)

Random walks on stochastic temporal networks
著者:: Hoffmann, T, 等
出版事項: (2013)

Random walks on stochastic temporal networks
著者:: Hoffmann, T, 等
出版事項: (2013)

Randomised random walk on a random walk /
著者:: 258250 Lee, P. A.
出版事項: (1983)

High-precision Estimation of Random Walks in Small Space
著者:: Ahmadinejad, AmirMahdi, 等
出版事項: (2021)

Random walks in distributed networks and their applications
著者:: Anisur Rahaman Molla
出版事項: (2014)

A Complexity Dichotomy for Partition Functions with Mixed Signs
著者:: Goldberg, L, 等
出版事項: (2010)

Functional brain networks: random, "small world" or deterministic?
著者:: Katarzyna J Blinowska, 等
出版事項: (2013-01-01)

Random walk on temporal networks with lasting edges
著者:: Petit, J, 等
出版事項: (2018)

Functional clones and expressibility of partition functions
著者:: Bulatov, A, 等
出版事項: (2017)

Counting solutions to random CNF formulas
著者:: Galanis, A, 等
出版事項: (2021)

Strong and weak random walks on signed networks
著者:: Babul, SA, 等
出版事項: (2025)

Continuous-time random walks and temporal networks
著者:: Lambiotte, R
出版事項: (2019)