Deterministic Versus Stochastic Consensus Dynamics on Graphs

Journal of Statistical Physics - We study two agent based models of opinion formation—one stochastic in nature and one deterministic. Both models are defined in terms of an underlying graph;...     

Constrained Markovian Dynamics of Random Graphs

We introduce a statistical mechanics formalism for the study of constrained graph evolution as a Markovian stochastic process, in analogy with that available for spin systems, deriving its basic properties and highlighting the role of the ‘mobility’ (the number of allowed moves for any given graph). As an application of the general theory we analyze the properties of degree-preserving Markov chains based on elementary edge switchings. We give an exact yet simple formula for the mobility in terms of the graph’s adjacency matrix and its spectrum. This formula allows us to define acceptance probabilities for edge switchings, such that the Markov chains become controlled Glauber-type detailed balance processes, designed to evolve to any required invariant measure (representing the asymptotic frequencies with which the allowed graphs are visited during the process). As a corollary we also derive a condition in terms of simple degree statistics, sufficient to guarantee that, in the limit where the number of nodes diverges, even for state-independent acceptance probabilities of proposed moves the invariant measure of the process will be uniform. We test our theory on synthetic graphs and on realistic larger graphs as studied in cellular biology, showing explicitly that, for instances where the simple edge swap dynamics fails to converge to the uniform measure, a suitably modified Markov chain instead generates the correct phase space sampling.     

Randomness in Competitions

We study the effects of randomness on competitions based on an elementary random process in which there is a finite probability that a weaker team upsets a stronger team. We apply this model to sports leagues and sports tournaments, and compare the theoretical results with empirical data. Our model shows that single-elimination tournaments are efficient but unfair: the number of games is proportional to the number of teams N, but the probability that the weakest team wins decays only algebraically with N. In contrast, leagues, where every team plays every other team, are fair but inefficient: the top $\sqrt{N}$ of teams remain in contention for the championship, while the probability that the weakest team becomes champion is exponentially small. We also propose a gradual elimination schedule that consists of a preliminary round and a championship round. Initially, teams play a small number of preliminary games, and subsequently, a few teams qualify for the championship round. This algorithm is fair and efficient: the best team wins with a high probability and the number of games scales as N ^9/5, whereas traditional leagues require N ³ games to fairly determine a champion.     

Cryptohermitian Hamiltonians on Graphs

A family of nonhermitian quantum graphs is proposed and studied via their discretization.     

Quantum Tunneling on Graphs

We explore the tunneling behavior of a quantum particle on a finite graph in the presence of an asymptotically large potential with two or three potential wells. The behavior of the particle is primarily governed by the local spectral symmetry of the graph around the wells. In the case of two wells the behavior is stable in the sense that it can be predicted from a sufficiently large neighborhood of the wells. However in the case of three wells we are able to exhibit examples where the tunneling behavior can be changed significantly by perturbing the graph arbitrarily far from the wells.     

Swarming on Random Graphs

We consider a compromise model in one dimension in which pairs of agents interact through first-order dynamics that involve both attraction and repulsion. In the case of all-to-all coupling of agents, this system has a lowest energy state in which half of the agents agree upon one value and the other half agree upon a different value. The purpose of this paper is to study the behavior of this compromise model when the interaction between the N agents occurs according to an Erd?s-Rényi random graph $\mathcal{G}(N,p)$ . We study the effect of changing p on the stability of the compromised state, and derive both rigorous and asymptotic results suggesting that the stability is preserved for probabilities greater than $p_{c}=O(\frac{\log N}{N})$ . In other words, relatively few interactions are needed to preserve stability of the state. The results rely on basic probability arguments and the theory of eigenvalues of random matrices.     

Lattice Green‘s Function for Infinite Square Lattice in the Second Nearest-Neighbour Interaction Approximation

In dealing with the square lattice model,we replace the traditionally needed Born-Von Karmann periodic boundary condition with additional Hamiltonian terms to make up a ring lattice.In doing so,the lattice Green‘s function of an infinite square lattice in the second nearest-neighbour interaction approximation can be derived by means of the matrix Green‘s function method.It is shown that the density of states may change when the second nearest-neighbour interaction is turned on.``     

Boolean Percolation on Doubling Graphs

Journal of Statistical Physics - We consider the discrete Boolean model of percolation on weighted graphs satisfying a doubling metric condition. We study sufficient conditions on the distribution...     

n-Particle Quantum Statistics on Graphs

We develop a full characterization of abelian quantum statistics on graphs. We explain how the number of anyon phases is related to connectivity. For 2-connected graphs the independence of quantum statistics with respect to the number of particles is proven. For non-planar 3-connected graphs we identify bosons and fermions as the only possible statistics, whereas for planar 3-connected graphs we show that one anyon phase exists. Our approach also yields an alternative proof of the structure theorem for the first homology group of n-particle graph configuration spaces. Finally, we determine the topological gauge potentials for 2-connected graphs.     

Dimers on Graphs in Non-Orientable Surfaces

The main result of this article is a Pfaffian formula for the partition function of the dimer model on any graph Γ embedded in a closed, possibly non-orientable surface Σ. This formula is suitable for computational purposes, and it is obtained using purely geometrical methods. The key step in the proof consists of a correspondence between some orientations on Γ and the set of pin^? structures on Σ. This generalizes (and simplifies) the results of a previous article (Cimasoni and Reshetikhin in Commun Math Phys 275:187–208, 2007).     

Ising Models on Hyperbolic Graphs II

We consider Ising models with ferromagnetic interactions and zero external magnetic field on the hyperbolic graph (v, f), where v is the number of neighbors of each vertex and f is the number of sides of each face. Let T _c be the critical temperature and T _c =supTT _c: ^f=( ⁺+ ^–)/2, where ^f is the free boundary condition (b.c.) Gibbs state, ⁺ is the plus b.c. Gibbs state and ^– is the minus b.c. Gibbs state. We prove that if the hyperbolic graph is self-dual (i.e., v=f) or if v is sufficiently large (how large depends on f, e.g., v35 suffices for any f3 and v17 suffices for any f17) then 0<T _c <T _c, in contrast with that T _c =T _c for Ising models on the hypercubic lattice Z ^d with d2, a result due to Lebowitz.⁽²²⁾ While whenever T<T _c , ^f=( ⁺+ ^–)/2. The last result is an improvement in comparison with the analogous statement in refs. 28 and 33, in which it was only proved that ^f=( ⁺+ ^–)/2 when TT _c and it remains to show in both papers that ^f =( ⁺+ ^–)/2 whenever T<T _c . Therefore T _c and T _c divide [0, ] into three intervals: [0, T _c ), (T _c , T _c), and (T _c, ] in which ^{+ –} but ^f =( ⁺+ ^–)/2, ^{+ –} and ^f ( ⁺+ ^–)/2, and ⁺= ^–, respectively.     

Ising Models on Power-Law Random Graphs

We study a ferromagnetic Ising model on random graphs with a power-law degree distribution and compute the thermodynamic limit of the pressure when the mean degree is finite (degree exponent τ>2), for which the random graph has a tree-like structure. For this, we closely follow the analysis by Dembo and Montanari (Ann. Appl. Probab. 20(2):565–592, 2010) which assumes finite variance degrees (τ>3), adapting it when necessary and also simplifying it when possible. Our results also apply in cases where the degree distribution does not obey a power law.     

Inference of Kinetic Ising Model on Sparse Graphs

Based on dynamical cavity method, we propose an approach to the inference of kinetic Ising model, which asks to reconstruct couplings and external fields from given time-dependent output of original system. Our approach gives an exact result on tree graphs and a good approximation on sparse graphs, it can be seen as an extension of Belief Propagation inference of static Ising model to kinetic Ising model. While existing mean field methods to the kinetic Ising inference e.g., naïve mean-field, TAP equation and simply mean-field, use approximations which calculate magnetizations and correlations at time t from statistics of data at time t?1, dynamical cavity method can use statistics of data at times earlier than t?1 to capture more correlations at different time steps. Extensive numerical experiments show that our inference method is superior to existing mean-field approaches on diluted networks.     

Percolation on Infinite Graphs and Isoperimetric Inequalities

We consider the Bernoulli bond percolation process (with parameter p) on infinite graphs and we give a general criterion for bounded degree graphs to exhibit a non-trivial percolation threshold based either on a single isoperimetric inequality if the graph has a bi-infinite geodesic, or two isoperimetric inequalities if the graph has not a bi-infinite geodesic. This new criterion extends previous criteria and brings together a large class of amenable graphs (such as regular lattices) and non-amenable graphs (such trees). We also study the finite connectivity in graphs satisfying the new general criterion and show that graphs in this class with a bi-infinite geodesic always have finite connectivity functions with exponential decay when p is sufficiently close to one. On the other hand, we show that there are graphs in the same class with no bi-infinite geodesic for which the finite connectivity decays sub-exponentially (down to polynomially) in the highly supercritical phase even for p arbitrarily close to one.     

Network Models in Class C on Arbitrary Graphs

We consider network models of quantum localisation in which a particle with a two-component wave function propagates through the nodes and along the edges of an arbitrary directed graph, subject to a random SU(2) rotation on each edge it traverses. The propagation through each node is specified by an arbitrary but fixed S-matrix. Such networks model localisation problems in class C of the classification of Altland and Zirnbauer [1], and, on suitable graphs, they model the spin quantum Hall transition. We extend the analyses of Gruzberg, Ludwig and Read [5] and of Beamond, Cardy and Chalker [2] to show that, on an arbitrary graph, the mean density of states and the mean conductance may be calculated in terms of observables of a classical history-dependent random walk on the same graph. The transition weights for this process are explicitly related to the elements of the S-matrices. They are correctly normalised but, on graphs with nodes of degree greater than 4, not necessarily non-negative (and therefore interpretable as probabilities) unless a sufficient number of them happen to vanish. Our methods use a supersymmetric path integral formulation of the problem which is completely finite and rigorous.     

Localization on Quantum Graphs with Random Vertex Couplings

We consider Schrödinger operators on a class of periodic quantum graphs with randomly distributed Kirchhoff coupling constants at all vertices. We obtain necessary conditions for localization on quantum graphs in terms of finite volume criteria for some energy-dependent discrete Hamiltonians. These conditions hold in the strong disorder limit and at the spectral edges.     

Total Flooding Time and Rumor Propagation on Graphs

We study the discrete time version of the flooding time problem as a model of rumor propagation where each site in the graph has initially a distinct piece of information; we are interested in the number of “conversations” before the entire graph knows all pieces of information. For the complete graph we compare the ratio between the expected propagation time for all pieces of information and the corresponding time for a single piece of information, obtaining the asymptotic ratio 3 / 2 between them.     

The Einstein Relation for Random Walks on Graphs

This paper investigates the Einstein relation; the connection between the volume growth, the resistance growth and the expected time a random walk needs to leave a ball on a weighted graph. The Einstein relation is proved under different set of conditions. In the simplest case it is shown under the volume doubling and time comparison principles. This and the other set of conditions provide the basic framework for the study of (sub-) diffusive behavior of the random walks on weighted graphs.