|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'503'724
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
The mixing time of the Newman--Watts small world | | Louigi Addario-Berry
; Tao Lei
; | | Date: |
18 Jan 2012 | | Abstract: | "Small worlds" are large systems in which any given node has only a few
connections to other points, but possessing the property that all pairs of
points are connected by a short path, typically logarithmic in the number of
nodes. The use of random walks for sampling a uniform element from a large
state space is by now a classical technique; to prove that such a technique
works for a given network, a bound on the mixing time is required. However,
little detailed information is known about the behaviour of random walks on
small-world networks, though many predictions can be found in the physics
literature. The principal contribution of this paper is to show that for a
famous small-world random graph model known as the Newman--Watts small world,
the mixing time is of order (log n)^2. This confirms a prediction of Richard
Durrett, who proved a lower bound of order (log n)^2 and an upper bound of
order (log n)^3. | | Source: | arXiv, 1201.3795 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER