Random graph ensembles with many short loops

1. Basic constructions. 2. Equilibrium and nonequilibrium networks. 3. Equilibrium uncorrelated networks. 4. Nonequilibrium nongrowing scale-free nets. 5. Types of correlations. 6. When pair correlations are important. 7. When loops are important. 8. Pair degree-degree correlations in growing networks. 9. How to construct an equilibrium net with given degree-degree correlations. 10. How to construct a growing scale-free net with a given clustering (towards a real-space renorm...

The spectrum of the adjacency matrix plays several important roles in the mathematical theory of networks and in network data analysis, for example in percolation theory, community detection, centrality measures, and the theory of dynamical systems on networks. A number of methods have been developed for the analytic computation of network spectra, but they typically assume that networks are locally tree-like, meaning that the local neighborhood of any node takes the form of ...

The aim of this work is to try to bridge over theoretical immunology and disordered statistical mechanics. Our long term hope is to contribute to the development of a quantitative theoretical immunology from which practical applications may stem. In order to make theoretical immunology appealing to the statistical physicist audience we are going to work out a research article which, from one side, may hopefully act as a benchmark for future improvements and developments, from...

In this paper we offer a solution to a long-standing problem in the study of networks. Message passing is a fundamental technique for calculations on networks and graphs. The first versions of the method appeared in the 1930s and over the decades it has been applied to a wide range of foundational problems in mathematics, physics, computer science, statistics, and machine learning, including Bayesian inference, spin models, coloring, satisfiability, graph partitioning, networ...

This dissertation contributes to mathematical and algorithmic problems that arise in the analysis of network and biological data.

In statistical mechanical investigations on complex networks, it is useful to employ random graphs ensembles as null models, to compare with experimental realizations. Motivated by transcription networks, we present here a simple way to generate an ensemble of random directed graphs with, asymptotically, scale-free outdegree and compact indegree. Entries in each row of the adjacency matrix are set to be zero or one according to the toss of a biased coin, with a chosen probabi...

Although the ``scale-free'' literature is large and growing, it gives neither a precise definition of scale-free graphs nor rigorous proofs of many of their claimed properties. In fact, it is easily shown that the existing theory has many inherent contradictions and verifiably false claims. In this paper, we propose a new, mathematically precise, and structural definition of the extent to which a graph is scale-free, and prove a series of results that recover many of the clai...

Statistical properties of evolving random graphs are analyzed using kinetic theory. Treating the linking process dynamically, structural characteristics such as links, paths, cycles, and components are obtained analytically using the rate equation approach. Scaling laws for finite systems are derived using extreme statistics and scaling arguments.

Random graph models have played a dominant role in the theoretical study of networked systems. The Poisson random graph of Erdos and Renyi, in particular, as well as the so-called configuration model, have served as the starting point for numerous calculations. In this paper we describe another large class of random graph models, which we call equitable random graphs and which are flexible enough to represent networks with diverse degree distributions and many nontrivial type...

Erd\H{o}s and R\'{e}nyi showed the paradoxical result that there is a unique (and highly symmetric) countably infinite random graph. This graph, and its automorphism group, form the subject of the present survey.