Search

Recently, random walks on dynamic graphs have been studied because of their adaptivity to the time-varying structure of real-world networks. In general, there is a tremendous gap between static and dynamic graph settings for the lazy simple random walk: Although $O(n^3)$ cover time was shown for any static graphs of $n$ vertices, there is an edge-changing dynamic graph with an exponential hitting time. On the other hand, previous works indicate that the random walk on a dynamic graph with a time-homogeneous stationary distribution behaves almost identically to that on a static graph. In this paper, we strengthen this insight by obtaining general and improved bounds. Specifically, we consider a random walk according to a sequence $(P_t)_{t\geq 1}$ of irreducible and reversible transition matrices such that all $P_t$ have the same stationary distribution. We bound the mixing, hitting, and cover times in terms of the hitting and relaxation times of the random walk according to the worst fixed $P_t$. Moreover, we obtain the first bounds of the hitting and cover times of multiple random walks and the coalescing time on dynamic graphs. These bounds can be seen as an extension of the well-known bounds of random walks on static graphs. Our results generalize the previous upper bounds for specific random walks on dynamic graphs, e.g., lazy simple random walks and $d_{\max}$-lazy walks, and give improved and tight upper bounds in various cases. As an interesting consequence of our generalization, we obtain tight bounds for the lazy Metropolis walk [Nonaka, Ono, Sadakane, and Yamashita, TCS10] on any dynamic graph: $O(n^2)$ mixing time, $O(n^2)$ hitting time, and $O(n^2\log n)$ cover time. Additionally, our coalescing time bound implies the consensus time bound of the pull voting on a dynamic graph., Comment: 41 pages

In this paper, we seek a natural problem and a natural distribution of instances such that any $O(n^{c-\epsilon})$-time algorithm fails to solve most instances drawn from the distribution, while the problem admits an $n^{c+o(1)}$-time algorithm that correctly solves all instances. Specifically, we consider the $K_{a,b}$ counting problem in a random bipartite graph, where $K_{a,b}$ is a complete bipartite graph for constants $a$ and $b$. We proved that the $K_{a,b}$ counting problem admits an $n^{a+o(1)}$-time algorithm if $a\geq 8$, while any $n^{a-\epsilon}$-time algorithm fails to solve it even on random bipartite graph for any constant $\epsilon>0$ under the Strong Exponential Time Hypotheis. Then, we amplify the hardness of this problem using the direct product theorem and Yao's XOR lemma by presenting a general framework of hardness amplification in the setting of fine-grained complexity.

Real networks are often dynamic. In response to it, analyses of algorithms on {\em dynamic networks} attract more and more attentions in network science and engineering. Random walks on dynamic graphs also have been investigated actively in more than a decade, where in most cases the edge set changes but the vertex set is static. The vertex sets are also dynamic in many real networks. Motivated by a new technology of the analysis of random walks on dynamic graphs, this paper introduces a simple model of graphs with increasing the number of vertices, and presents an analysis of random walks associated with the cover time on such graphs. In particular, we reveal that a random walk asymptotically covers the vertices all but a constant number if the vertex set grows {\em moderately}., Comment: 28 pages

Consider a distributed graph where each vertex holds one of two distinct opinions. In this paper, we are interested in synchronous voting processes where each vertex updates its opinion according to a predefined common local updating rule. For example, each vertex adopts the majority opinion among 1) itself and two randomly picked neighbors in best-of-two or 2) three randomly picked neighbors in best-of-three. Previous works intensively studied specific rules including best-of-two and best-of-three individually. In this paper, we generalize and extend previous works of best-of-two and best-of-three on expander graphs by proposing a new model, quasi-majority functional voting. This new model contains best-of-two and best-of-three as special cases. We show that, on expander graphs with sufficiently large initial bias, any quasi-majority functional voting reaches consensus within $O(\log n)$ steps with high probability. Moreover, we show that, for any initial opinion configuration, any quasi-majority functional voting on expander graphs with higher expansion (e.g., Erd\H{o}s-R\'enyi graph $G(n,p)$ with $p=\Omega(1/\sqrt{n})$) reaches consensus within $O(\log n)$ with high probability. Furthermore, we show that the consensus time is $O(\log n/\log k)$ of best-of-$(2k+1)$ for $k=o(n/\log n)$.

This paper is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the \emph{Best-of-two} and the \emph{Best-of-three}. Here at each synchronous and discrete time step, each vertex updates its opinion to match the majority among the opinions of two random neighbors and itself (the Best-of-two) or the opinions of three random neighbors (the Best-of-three). Previous studies have explored these processes on complete graphs and expander graphs, but we understand significantly less about their properties on graphs with more complicated structures. In this paper, we study the Best-of-two and the Best-of-three on the stochastic block model $G(2n,p,q)$, which is a random graph consisting of two distinct Erd\H{o}s-R\'enyi graphs $G(n,p)$ joined by random edges with density $q\leq p$. We obtain two main results. First, if $p=\omega(\log n/n)$ and $r=q/p$ is a constant, we show that there is a phase transition in $r$ with threshold $r^*$ (specifically, $r^*=\sqrt{5}-2$ for the Best-of-two, and $r^*=1/7$ for the Best-of-three). If $r>r^*$, the process reaches consensus within $O(\log \log n+\log n/\log (np))$ steps for any initial opinion configuration with a bias of $\Omega(n)$. By contrast, if $rr^*$, we show that, for any initial opinion configuration, the process reaches consensus within $O(\log n)$ steps. To the best of our knowledge, this is the first result concerning multiple-choice voting for arbitrary initial opinion configurations on non-complete graphs.

A network topology with low average shortest path length (ASPL) provides efficient data transmission while the number of nodes and the number of links incident to each node are often limited due to physical constraints. In this paper, we consider the construction of low ASPL graphs under these constraints by using stochastic local search (SLS) algorithms. Since the ASPL cannot be calculated efficiently, the ASPL is not suitable for the evaluation function of SLS algorithms. We first derive an equality and bounds for the ASPL of graphs of diameter 3. Then, we propose use the simpliest upper bound represented by the number of triangles and squares in the graph as an evaluation function for graphs of diameter 3. We show that the proposed evaluation function can be evaluated in O(1) time as the number of nodes and the maximum degree tend to infinity by using some data tables. By using the simulated annealing with the proposed evaluation function, we construct low ASPL regular graphs of diameter 3 with 10 000 nodes., Comment: 6 pages, 2 figures

A phenomenological model is developed to explain a new set of detailed torsional oscillator data for hcp 4He. The model is based on Anderson's idea of the vortex fluid (vortex tangle) in solid 4He. Utilizing a well-studied treatment of dynamics of quantized vortices we describe how the "local superfluid component" is involved in rotation (torsional oscillation) via a polaried vortices tangle. The polarization in the tangle appears both due to aligning the remnant or thermal vortices and due to penetration of additional vortices into volume. Both are supposed to occur in a relaxation manner, and the inverse full relaxation time tau^-1 is the sum of them. One of them is found to change linearly with respect to the rim velocity Vac. The developed approach explains the behavior of both NLRS and Delta Q^-1 seen in the experiment. We reproduce not only the unique Vac dependence, but also obtain new information about the vortices tangle, for example, a divergence in tau at extrapolated T ~ 30 mK., Comment: 4 pages, 3 figures

A detailed torsional oscillator (TO) study on a stable solid 4He sample at 49 bar with To = 0.5K, is reported to T below the dissipation peak at Tp . We find hysteretic behavior starting below Tc = about 75 mK, in period shift, as well as in dissipation, with changes of AC excitation amplitude Vac . The derived difference of non-linear rotational susceptibility DeltaNLRS(T)hys across the hysteresis loop under a systematic condition is analyzed as a function of Vac and T . We propose that DeltaN LRS(T)hys is proportional to non- classical rortational inertia fraction, NCRIF, and is actually the supersolid density rho_ss of the 3D supersolid state below Tc . rho_ss changes linearly with T down to about 60 mK and then increases much more steeply, and approaching a finite value towards T = 0. We find an AC velocity of 40 micrometer/s beyond which the hysteresis starts at T < Tc and a critical AC velocity, about 1 cm/s, above which rho_ss is completely destroyed. We discuss also the coherence length of the supersolid., Comment: 4 pages, 5 figures