Coloring random graphs

We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring, whereas graphs with high connectivity are uncolorable. Depending on q, we find the precise value of the critical average connectivity c(q). Moreover, we show that below c(q) there exists a clustering phase c in [c(d),c(q)] in which ground states spontaneously divide into an exponential number of clusters and where the proliferation of metastable states is responsible for the onset of complexity in local search algorithms.     

Ensemble inequivalence in random graphs

We present a complete analytical solution of a system of Potts spins on a random k-regular graph in both the canonical and microcanonical ensembles, using the Large Deviation Cavity Method (LDCM). The solution is shown to be composed of three different branches, resulting in a non-concave entropy function. The analytical solution is confirmed with numerical Metropolis and Creutz simulations and our results clearly demonstrate the presence of a region with negative specific heat and, consequently, ensemble inequivalence between the canonical and microcanonical ensembles.     

Cross over of recurrence networks to random graphs and random geometric graphs

Recurrence networks are complex networks constructed from the time series of chaotic dynamical systems where the connection between two nodes is limited by the recurrence threshold. This condition makes the topology of every recurrence network unique with the degree distribution determined by the probability density variations of the representative attractor from which it is constructed. Here we numerically investigate the properties of recurrence networks from standard low-dimensional chaotic attractors using some basic network measures and show how the recurrence networks are different from random and scale-free networks. In particular, we show that all recurrence networks can cross over to random geometric graphs by adding sufficient amount of noise to the time series and into the classical random graphs by increasing the range of interaction to the system size. We also highlight the effectiveness of a combined plot of characteristic path length and clustering coefficient in capturing the small changes in the network characteristics.     

Localization of random walks in one-dimensional random environments

We consider a random walk on the one-dimensional semi-lattice ={0, 1, 2,...}. We prove that the moving particle walks mainly in a finite neighbourhood of a point depending only on time and a realization of the random environment. The size of this neighbourhood is estimated. The limit parameters of the walks are also determined.     

Symmetry-adapted linear combinations for the eigenvalues and eigenvectors of reciprocal graphs

ABSTRACT

Three classes of reciprocal graphs, viz. monocycle (G^C_n), linear chain (G^L_n) and star (G^K_n) with reciprocal pairs of eigenvalues (λ, 1/λ), are well known. Reciprocal graphs of monocycle (G^C_n) and linear chain (G^L_n) are obtained by putting a pendant vertex to each vertex of simple monocycle (C_n) and simple linear chain (L_n), respectively. A star graph of such kind is obtained by attaching a pendant vertex to the central vertex and to each of the (n ? 1) peripheral vertices of the star graph (K_{1, (n?1)}). An n-fold rotational axis of symmetry for G^C_n and (n ? 1)-fold rotational axis of symmetry for G^K_n have been exploited for obtaining their respective condensed graphs. The condensed graph for G^L_n has been generated from that of G^C_n incorporating proper boundary conditions. Condensed graphs are lower dimensional graphs and are capable of keeping all eigeninformation in condensed form. Thus the eigensolutions (i.e. the eigenvalues and the eigenvectors) in analytical forms for such graphs are obtained by solving 2 × 2 or 4 × 4 determinants that in turn result in the charge densities and bond orders of the corresponding molecules in analytical forms. Some mathematical properties of the eigenvalues of such graphs have also been explored.     

Polymers and random graphs

We establish a precise connection between gelation of polymers in Lushnikov's model and the emergence of the giant component in random graph theory. This is achieved by defining a modified version of the Erdös-Rényi process; when contracting to a polymer state space, this process becomes a discrete-time Markov chain embedded in Lushnikov's process. The asymptotic distribution of the number of transitions in Lushnikov's model is studied. A criterion for a general Markov chain to retain the Markov property under the grouping of states is derived. We obtain a noncombinatorial proof of a theorem of Erdös-Rényi type.     

Localization in general one-dimensional random systems

We discuss two ways of extending the recent ideas of localization from discrete Schrödinger operators (Jacobi matrices) to the continuum case. One case allows us to prove localization in the Goldshade, Molchanov, Pastur model for a larger class of functions than previously. The other method studies the model –+V, whereV is a random constant in each (hyper-) cube. We extend Wegner's result on the Lipschitz nature of the ids to this model.Dedicated to Walter Thirring on his 60^th birthdayResearch partially supported by USNSF under Grant DMS-8416049     

The statistics of random directed graphs

The analysis of random graphs developed by the author, principally as a model for polymerization processes, is extended to the case of directed random graphs, with models of neural nets in mind. The principal novelty of the directed case is the representation of the partition function by a complex rather than a real integral, and the replacement of simple maxima in asymptotic evaluations by an interesting form of saddle point.     

Localization transition of biased random walks on random networks

We study random walks on large random graphs that are biased towards a randomly chosen but fixed target node. We show that a critical bias strength bc exists such that most walks find the target within a finite time when b > bc. For b < bc, a finite fraction of walks drift off to infinity before hitting the target. The phase transition at b=bc is a critical point in the sense that quantities such as the return probability P(t) show power laws, but finite-size behavior is complex and does not obey the usual finite-size scaling ansatz. By extending rigorous results for biased walks on Galton-Watson trees, we give the exact analytical value for bc and verify it by large scale simulations.     

Scale-free random graphs and Potts model

We introduce a simple algorithm that constructs scale-free random graphs efficiently: each vertexi has a prescribed weight P_i ∝ i^-μ (0 < μ< 1) and an edge can connect verticesi andj with rateP _i P _j . Corresponding equilibrium ensemble is identified and the problem is solved by theq → 1 limit of the q-state Potts model with inhomogeneous interactions for all pairs of spins. The number of loops as well as the giant cluster size and the mean cluster size are obtained in the thermodynamic limit as a function of the edge density. Various critical exponents associated with the percolation transition are also obtained together with finite-size scaling forms. The process of forming the giant cluster is qualitatively different between the cases of λ > 3 and 2 < λ < 3, whereλ = 1 +μ ^-1 is the degree distribution exponent. While for the former, the giant cluster forms abruptly at the percolation transition, for the latter, however, the formation of the giant cluster is gradual and the mean cluster size for finiteN shows double peaks.     

Localization in one dimensional correlated random potentials

The localization length of one-dimensional disordered systems with statistically correlated random potentials is studied both numerically and analytically. The results indicate that the localization length generally increases when the correlation function is positive. In the presence of anticorrelation effects the localization length may be shorter than in the uncorrelated case.     

Dynamics of excitable nodes on random graphs

We study the interplay of topology and dynamics of excitable nodes on random networks. Comparison is made between systems grown by purely random (Erdős–Rényi) rules and those grown by the Achlioptas process. For a given size, the growth mechanism affects both the thresholds for the emergence of different structural features as well as the level of dynamical activity supported on the network.     

Localization of particles in a two-dimensional random potential

A recently proposed theory of the density response of particles moving in a random potential is applied to two-dimensional systems. The particles are found to be localized for arbitrary small disorder. By decreasing the potential fluctuations we find an abrupt transition from an insulating state to a quasi-conducting state exhibiting exceedingly small values for the inverse susceptibility, the inverse localization length and the excitation gap of the dynamical conductivity.     

Generating random graphs with tunable clustering coefficients

Most real-world networks exhibit a high clustering coefficient—the probability that two neighbors of a node are also neighbors of each other. We propose two algorithms, Conf and Throw, that take triangle and single edge degree sequences as input and generate a random graph with a target clustering coefficient. We analyze them theoretically for the case of a regular graph. Conf generates a random graph with the input degree sequence and the clustering coefficient anticipated from the input. Experimental results match quite well with the anticipated clustering coefficient except for highly dense graphs, in which case the experimental clustering coefficient is higher than the anticipated value. For Throw, the degree sequence and the clustering coefficient of the generated graph varies from the input. However, it maintains the expected degree distribution, and the clustering coefficient of the generated graph can also be predicted using analytical results. Experiments show that, for Throw, the results match quite well with the analytical results. Typically, only information about degree distribution is available. We also propose an algorithm Deg that takes degree sequence and clustering coefficient as input and generates a graph with the same properties. Experiments show results for Deg that are quite similar to those for Conf.     

Continuous random networks from graphs to glasses

The direct connection between the structure of amorphous materials, modelled geometrically by graphs, and their physical properties is demonstrated. The structural and physical differences between glasses and crystals are emphasized.     

Localization for random and quasiperiodic potentials

A survey is made of some recent mathematical results and techniques for Schrödinger operators with random and quasiperiodic potentials. A new proof of localization for random potentials, established in collaboration with H. von Dreifus, is sketched.     

Symmetric vertex models on planar random graphs

We solve a 4-(bond)-vertex model on an ensemble of 3-regular (Φ³) planar random graphs, which has the effect of coupling the vertex model to 2D quantum gravity. The method of solution, by mapping onto an Ising model in field, is inspired by the solution by Wu et.al. of the regular lattice equivalent – a symmetric 8-vertex model on the honeycomb lattice, and also applies to higher valency bond vertex models on random graphs when the vertex weights depend only on bond numbers and not cyclic ordering (the so-called symmetric vertex models).The relations between the vertex weights and Ising model parameters in the 4-vertex model on Φ³ graphs turn out to be identical to those of the honeycomb lattice model, as is the form of the equation of the Ising critical locus for the vertex weights. A symmetry of the partition function under transformations of the vertex weights, which is fundamental to the solution in both cases, can be understood in the random graph case as a change of integration variable in the matrix integral used to define the model.Finally, we note that vertex models, such as that discussed in this paper, may have a role to play in the discretisation of Lorentzian metric quantum gravity in two dimensions.     

Dynamics of heuristic optimization algorithms on random graphs

In this paper, the dynamics of heuristic algorithms for constructing small vertex covers (or independent sets) of finite-connectivity random graphs is analysed. In every algorithmic step, a vertex is chosen with respect to its vertex degree. This vertex, and some environment of it, is covered and removed from the graph. This graph reduction process can be described as a Markovian dynamics in the space of random graphs of arbitrary degree distribution. We discuss some solvable cases, including algorithms already analysed using different techniques, and develop approximation schemes for more complicated cases. The approximations are corroborated by numerical simulations. Received 14 March 2002 Published online 31 July 2002