Kinetic Theory of Random Graphs: from Paths to Cycles

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.

A model for growing networks is introduced, having as a main ingredient that new nodes are attached to the network through one existing node and then explore the network through the links of the visited nodes. From exact calculations of two limiting cases and numerical simulations the phase diagram of the model is obtained. In the stationary limit, large network sizes, a phase transition from a network with finite average connectivity to a network with a power law distributio...

We discuss various aspects of the statistical formulation of the theory of random graphs, with emphasis on results obtained in a series of our recent publications.

In the context of growing networks, we introduce a simple dynamical model that unifies the generic features of real networks: scale-free distribution of degree and the small world effect. While the average shortest path length increases logartihmically as in random networks, the clustering coefficient assumes a large value independent of system size. We derive expressions for the clustering coefficient in two limiting cases: random (C ~ (ln N)^2 / N) and highly clustered (C =...

We study directed random graphs (random graphs whose edges are directed), and present new results on the so-called strong components of those graphs. We provide analytic and simulation results on two special classes of strong component, called cycle components and knots, which are important in random networks that represent certain computational systems.

We review the recent fast progress in statistical physics of evolving networks. Interest has focused mainly on the structural properties of random complex networks in communications, biology, social sciences and economics. A number of giant artificial networks of such a kind came into existence recently. This opens a wide field for the study of their topology, evolution, and complex processes occurring in them. Such networks possess a rich set of scaling properties. A number ...

Complex networks describe a wide range of systems in nature and society, much quoted examples including the cell, a network of chemicals linked by chemical reactions, or the Internet, a network of routers and computers connected by physical links. While traditionally these systems were modeled as random graphs, it is increasingly recognized that the topology and evolution of real networks is governed by robust organizing principles. Here we review the recent advances in the f...

The poster presents an analytic formalism describing metric properties of undirected random graphs with arbitrary degree distributions and statistically uncorrelated (i.e. randomly connected) vertices. The formalism allows to calculate the main network characteristics like: the position of the phase transition at which a giant component first forms, the mean component size below the phase transition, the size of the giant component and the average path length above the phase ...

We study the distribution of cycles of length h in large networks (of size N>>1) and find it to be an excellent ergodic estimator, even in the extreme inhomogeneous case of scale-free networks. The distribution is sharply peaked around a characteristic cycle length, h* ~ N^a. Our results suggest that h* and the exponent a might usefully characterize broad families of networks. In addition to an exact counting of cycles in hierarchical nets, we present a Monte-Carlo sampling a...

We show how scale-free degree distributions can emerge naturally from growing networks by using random walks for selecting vertices for attachment. This result holds for several variants of the walk algorithm and for a wide range of parameters. The growth mechanism is based on using local graph information only, so this is a process of self-organisation. The standard mean-field equations are an excellent approximation for network growth using these rules. We discuss the effec...