Kinetic Theory of Random Graphs: from Paths to Cycles

A simple and accurate relationship is demonstrated that links the average shortest path, nodes, and edges in a complex network. This relationship takes advantage of the concept of link density and shows a large improvement in fitting networks of all scales over the typical random graph model. The relationships herein can allow researchers to better predict the shortest path of networks of almost any size.

Many research fields, reaching from social networks and epidemiology to biology and physics, have experienced great advance from recent developments in random graphs and network theory. In this paper we propose to view percolation on a directed random graph as a generic model for step-growth polymerisation. This polymerisation process is used to manufacture a broad range of polymeric materials, including: polyesters, polyurethanes, polyamides, and many others. We link feature...

Subgraphs and cycles are often used to characterize the local properties of complex networks. Here we show that the subgraph structure of real networks is highly time dependent: as the network grows, the density of some subgraphs remains unchanged, while the density of others increase at a rate that is determined by the network's degree distribution and clustering properties. This inhomogeneous evolution process, supported by direct measurements on several real networks, lead...

Inspired by empirical studies of networked systems such as the Internet, social networks, and biological networks, researchers have in recent years developed a variety of techniques and models to help us understand or predict the behavior of these systems. Here we review developments in this field, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment...

We present a novel way to characterize the structure of complex networks by studying the statistical properties of the trajectories of random walks over them. We consider time series corresponding to different properties of the nodes visited by the walkers. We show that the analysis of the fluctuations of these time series allows to define a set of characteristic exponents which capture the local and global organization of a network. This approach provides a way of solving tw...

We investigate a simple generative model for network formation. The model is designed to describe the growth of networks of kinship, trading, corporate alliances, or autocatalytic chemical reactions, where feedback is an essential element of network growth. The underlying graphs in these situations grow via a competition between cycle formation and node addition. After choosing a given node, a search is made for another node at a suitable distance. If such a node is found, a ...

We study the evolution of a random graph under the constraint that the diameter remain constant as the graph grows. We show that if the graph maintains the form of its link distribution it must be scale-free with exponent between 2 and 3. These uniqueness results may help explain the scale-free nature of graphs, of varying sizes, representing the evolved metabolic pathways in 43 organisms.

We present a general model for the growth of weighted networks in which the structural growth is coupled with the edges' weight dynamical evolution. The model is based on a simple weight-driven dynamics and a weights' reinforcement mechanism coupled to the local network growth. That coupling can be generalized in order to include the effect of additional randomness and non-linearities which can be present in real-world networks. The model generates weighted graphs exhibiting ...

Small-world architectures may be implicated in a range of phenomena from disease propagation to networks of neurons in the cerebral cortex. While most of the recent attention on small-world networks has focussed on the effect of introducing disorder/randomness into a regular network, we show that that the fundamental mechanism behind the small-world phenomenon is not disorder/randomness, but the presence of connections of many different length scales. Consequently, in order t...

Connections in complex networks are inherently fluctuating over time and exhibit more dimensionality than analysis based on standard static graph measures can capture. Here, we introduce the concepts of temporal paths and distance in time-varying graphs. We define as temporal small world a time-varying graph in which the links are highly clustered in time, yet the nodes are at small average temporal distances. We explore the small-world behavior in synthetic time-varying netw...