Continuity of the Integrated Density of States on Random Length Metric Graphs

We establish several properties of the integrated density of states for random quantum graphs: Under appropriate ergodicity and amenability assumptions, the integrated density of states can be defined using an exhaustion procedure by compact subgraphs. A trace per unit volume formula holds, similarly as in the Euclidean case. Our setting includes periodic graphs. For a model where the edge lengths are random and vary independently in a smooth way we prove a Wegner estimate and related regularity results for the integrated density of states. These results are illustrated for an example based on the Kagome lattice. In the periodic case we characterise all compactly supported eigenfunctions and calculate the position and size of discontinuities of the integrated density of states.      

A novel configuration model for random graphs with given degree sequence

Recently, random graphs in which vertices are characterized by hidden variables controlling the establishment of edges between pairs of vertices have attracted much attention. This paper presents a specific realization of a class of random network models in which the connection probability between two vertices (i,j) is a specific function of degrees ki and kj. In the framework of the configuration model of random graphs, we find the analytical expressions for the degree correlation and clustering as a function of the variance of the desired degree distribution. The obtained expressions are checked by means of numerical simulations. Possible applications of our model are discussed.     

Bootstrap Percolation in Living Neural Networks

Recent experimental studies of living neural networks reveal that their global activation induced by electrical stimulation can be explained using the concept of bootstrap percolation on a directed random network. The experiment consists in activating externally an initial random fraction of the neurons and observe the process of firing until its equilibrium. The final portion of neurons that are active depends in a non linear way on the initial fraction. The main result of this paper is a theorem which enables us to find the final proportion of the fired neurons, in the asymptotic case, in the case of random directed graphs with given node degrees as the model for interacting network. This gives a rigorous mathematical proof of a phenomena observed by physicists in neural networks.     

Factorizations of Polynomials over Noncommutative Algebras and Sufficient Sets of Edges in Directed Graphs

To directed graphs with unique sink and source we associate a noncommutative associative algebra and a polynomial over this algebra. Edges of the graph correspond to pseudo-roots of the polynomial. We give a sufficient condition when coefficients of the polynomial can be rationally expressed via elements of a given set of pseudo-roots (edges). Our results are based on a new theorem for directed graphs also proved in this paper. To the memory of Felix Alexandrovich Berezin. Vladimir Retakh was partially supported by NSA     

Families of Line-Graphs and Their Quantization

Any directed graph G with N vertices and J edges has an associated line-graph L(G) where the J edges form the vertices of L(G). We show that the non-zero eigenvalues of the adjacency matrices are the same for all graphs of such a family L ⁿ (G). We give necessary and sufficient conditions for a line-graph to be quantisable and demonstrate that the spectra of associated quantum propagators follow the predictions of random matrices under very general conditions. Line-graphs may therefore serve as models to study the semiclassical limit (of large matrix size) of a quantum dynamics on graphs with fixed classical behaviour.     

Hierarchy Depth in Directed Networks

In this study, we explore the depth measures for flow hierarchy in directed networks. Two simple measures are defined—rooted depth and relative depth—and their properties are discussed. The method of loop collapse is introduced, allowing investigation of networks containing directed cycles. The behavior of the two depth measures is investigated in Erdös-Rényi random graphs, directed Barabási-Albert networks, and in Gnutella p2p share network. A clear distinction in the behavior between non-hierarchical and hierarchical networks is found, with random graphs featuring unimodal distribution of depths dependent on arc density, while for hierarchical systems the distributions are similar for different network densities. Relative depth shows the same behavior as existing trophic level measure for tree-like networks, but is only statistically correlated for more complex topologies, including acyclic directed graphs.     

On Large Deviation Properties of Erdös–Rényi Random Graphs

We show that large deviation properties of Erdös-Rényi random graphs can be derived from the free energy of the q-state Potts model of statistical mechanics. More precisely the Legendre transform of the Potts free energy with respect to ln q is related to the component generating function of the graph ensemble. This generalizes the well-known mapping between typical properties of random graphs and the q 1 limit of the Potts free energy. For exponentially rare graphs we explicitly calculate the number of components, the size of the giant component, the degree distributions inside and outside the giant component, and the distribution of small component sizes. We also perform numerical simulations which are in very good agreement with our analytical work. Finally we demonstrate how the same results can be derived by studying the evolution of random graphs under the insertion of new vertices and edges, without recourse to the thermodynamics of the Potts model.     

Granger Causality among Graphs and Application to Functional Brain Connectivity in Autism Spectrum Disorder

Graphs/networks have become a powerful analytical approach for data modeling. Besides, with the advances in sensor technology, dynamic time-evolving data have become more common. In this context, one point of interest is a better understanding of the information flow within and between networks. Thus, we aim to infer Granger causality (G-causality) between networks’ time series. In this case, the straightforward application of the well-established vector autoregressive model is not feasible. Consequently, we require a theoretical framework for modeling time-varying graphs. One possibility would be to consider a mathematical graph model with time-varying parameters (assumed to be random variables) that generates the network. Suppose we identify G-causality between the graph models’ parameters. In that case, we could use it to define a G-causality between graphs. Here, we show that even if the model is unknown, the spectral radius is a reasonable estimate of some random graph model parameters. We illustrate our proposal’s application to study the relationship between brain hemispheres of controls and children diagnosed with Autism Spectrum Disorder (ASD). We show that the G-causality intensity from the brain’s right to the left hemisphere is different between ASD and controls.     

Modeling complex networks with self-similar outerplanar unclustered graphs

This paper introduces a family of modular, self-similar, small-world graphs with clustering zero. Relevant properties of this family are comparable to those of some networks associated with technological systems with a low clustering, like the power grid or some electronic circuits. Moreover, the graphs are outerplanar and it is know that many algorithms that are NP-complete for general graphs perform polynomial in outerplanar graphs. Therefore the graphs constitute a good mathematical model for these systems.     

Continuous-Time Classical and Quantum Random Walk on Direct Product of Cayley Graphs

In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability of observing particle on direct product of graph is obtained by multiplication of probability on the corresponding to sub-graphs, where this method is useful to determining probability of walk on compficated graphs. Using this method, we calculate the probability of Continuous-time classical and quantum random walks on many of finite direct product Cayley graphs （complete cycle, complete Kn, charter and n-cube）. Also, we inquire that the classical state the stationary uniform distribution is reached as t→∞ but for quantum state is not always satisfied.     

Long Paths and Cycles in Dynamical Graphs

We study the large-time dynamics of a Markov process whose states are finite directed graphs. The number of the vertices is described by a supercritical branching process, and the edges follow a certain mean-field dynamics determined by the rates of appending and deleting. We find sufficient conditions under which asymptotically a.s. the order of the largest component is proportional to the order of the graph. A lower bound for the length of the longest directed path in the graph is provided as well. We derive an explicit formula for the limit as time goes to infinity, of the expected number of cycles of a given finite length. Finally, we study the phase diagram.     

Market Choices Driven by Reference Groups: A Comparison of Analytical and Simulation Results on Random Networks

The present paper reports simulation results for a simple model of reference group influence on market choices, e.g., brand selection. The model was simulated on three types of random graphs, Erdos–Renyi, Barabasi–Albert, and Watts–Strogatz. The estimates of equilibria based on the simulation results were compared to the equilibria of the theoretical model. It was verified that the simulations exhibited the same qualitative behavior as the theoretical model, and for graphs with high connectivity and low clustering, the quantitative predictions offered a viable approximation. These results allowed extending the results from the simple theoretical model to networks. Thus, by increasing the positive response towards the reference group, the third party may create a bistable situation with two equilibria at which respective brands dominate the market. This task is easier for large reference groups.     

The Number of Large Graphs with a Positive Density of Triangles

We give upper and lower bounds on the number of graphs of fixed degree which have a positive density of triangles. In particular, we show that there are very few such graphs, when compared to the number of graphs without this restriction. We also show that in this case the triangles seem to cluster even at low density.     

Markov Chain Methods for Analyzing Urban Networks

Complex transport networks abstracted as graphs (undirected, directed, or multi-component) can be effectively analyzed by random walks (or diffusions). We have unified many concepts into one framework and studied in details the structural and spectral properties of spatial graphs for five compact urban patterns.     

Universality for the Distance in Finite Variance Random Graphs

We generalize the asymptotic behavior of the graph distance between two uniformly chosen nodes in the configuration model to a wide class of random graphs. Among others, this class contains the Poissonian random graph, the expected degree random graph and the generalized random graph (including the classical Erdős-Rényi graph). In the paper we assign to each node a deterministic capacity and the probability that there exists an edge between a pair of nodes is equal to a function of the product of the capacities of the pair divided by the total capacity of all the nodes. We consider capacities which are such that the degrees of a node have uniformly bounded moments of order strictly larger than two, so that, in particular, the degrees have finite variance. We prove that the graph distance grows like log  _ν N, where the ν depends on the capacities and N denotes the size of the graph. In addition, the random fluctuations around this asymptotic mean log  _ν N are shown to be tight. We also consider the case where the capacities are independent copies of a positive random Λ with , for some constant c and τ>3, again resulting in graphs where the degrees have finite variance. The method of proof of these results is to couple each member of the class to the Poissonian random graph, for which we then give the complete proof by adapting the arguments of van der Hofstad et al. (Random Struct. Algorithms 27(2):76–123, 2005).     

Vertex models on Feynman diagrams

We discuss the statistical mechanics of vertex models on both generic (“thin”) and planar (“fat”) random graphs. Such models can be formulated as the N → 1 and N → ∞ limits of N × N complex matrix models, respectively. From the graph theoretic perspective one is using matrix model and field theory inspired methods to count various classes of directed graphs. For the thin random graphs we use saddle point methods to solve the models in the thermodynamic, large number of vertices limit and note that, as in the case of the eight-vertex model on the square lattice, various other models such as the Ising model appear as particular limits. The generic solution of the fat graph model is rather more elusive, but we show that for several choices of the couplings the models can be reduced to eigenvalue integrals and their critical behaviour deduced.     

Penrose tiling fractality in coordination Cayley’s tree graphs representation

We offer the mathematical apparatus for mapping lattice and cellular systems into the generalized coordination Cayley’s tree graphs. These Cayley’s trees have a random branchiness property and an intralayer interbush local intersection. Classical Bethe-Cayley tree graphs don’t have these properties. Bush type simplicial decomposition on Cayley’s tree graphs is introduced, on which the enumerating polynomials or enumerating distributions are built. Within the entropy methodology three types of fractal characteristics are introduced, which characterize quasi-crystalline pentagonal Penrose tiling. The quantitative estimate for the frontal-radial fractal percolation on a Cayley’s tree graph of a Penrose tiling leading to the overdimensioned effect is calculated.     

Formulas for the characteristic polynomial coefficients of the pendant graphs of linear chains,cycles and stars

Formulas for the characteristic polynomial (CP) coefficients of three classes of (n + p)-vertex graphs, i.e. linear chains, cycles and stars where p pendant vertices are attached to n base vertices in one-to-one correspondence (p = 0, 1, 2, …, n), have been developed. Such pendant graphs become reciprocal graphs for linear chains and cycles if p = n. The n-vertex star graphs follow the same rule as paths and cycles, they become reciprocal on adding a pendant vertex to each of n vertices. The formulas so developed have been expressed in matrix product and in analytical forms for the three classes of graphs that require only the values of n and p for calculation of the respective CP coefficients. Such formulas have the general applicability for a large variety of molecular graphs with varying n and p and have been shown to be reduced to the corresponding formulas for reciprocal graphs that are the special cases of the graphs discussed here.     

Planar unclustered scale-free graphs as models for technological and biological networks

Many real life networks present an average path length logarithmic with the number of nodes and a degree distribution which follows a power law. Often these networks have also a modular and self-similar structure and, in some cases — usually associated with topological restrictions — their clustering is low and they are almost planar. In this paper we introduce a family of graphs which share all these properties and are defined by two parameters. As their construction is deterministic, we obtain exact analytic expressions for relevant properties of the graphs including the degree distribution, degree correlation, diameter, and average distance, as a function of the two defining parameters. Thus, the graphs are useful to model some complex networks, in particular several families of technological and biological networks, and in the design of new practical communication algorithms in relation to their dynamical processes. They can also help understanding the underlying mechanisms that have produced their particular structure.     

Phase Transitions in Dynamical Random Graphs

We study a large-time limit of a Markov process whose states are finite graphs. The number of the vertices is described by a supercritical branching process, and the dynamics of edges is determined by the rates of appending and deleting. We find a phase transition in our model similar to the one in the random graph model G _n,p . We derive a formula for the line of critical parameters which separates two different phases: one is where the size of the largest component is proportional to the size of the entire graph, and another one, where the size of the largest component is at most logarithmic with respect to the size of the entire graph. In the supercritical phase we find the asymptotics for the size of the largest component.