Kinetic Theory of Random Graphs: from Paths to Cycles

We introduce a simple one-parameter network growth algorithm which is able to reproduce a wide variety of realistic network structures but without having to invoke any global information about node degrees such as preferential-attachment probabilities. Scale-free networks arise at the transition point between quasi-random and quasi-ordered networks. We provide a detailed formalism which accurately describes the entire network range, including this critical point. Our formalis...

In this work we make an attempt to understand social networks from a mathematical viewpoint. In the first instance we consider a network where each node representing an individual can connect with a neighbouring node with a certain probability along with connecting with individuals who are friends of friends. We find that above a particular value of a chosen combination of parameters, the probability of connection between two widely separated nodes is a scale free. We next co...

We consider the self organizing process of merging and regeneration of vertices in complex networks and demonstrate that a scale-free degree distribution emerges in a steady state of such a dynamics. The merging of neighbor vertices in a network may be viewed as an optimization of efficiency by minimizing redundancy. It is also a mechanism to shorten the distance and thus decrease signaling times between vertices in a complex network. Thus the merging process will in particul...

The extremal characteristics of random structures, including trees, graphs, and networks, are discussed. A statistical physics approach is employed in which extremal properties are obtained through suitably defined rate equations. A variety of unusual time dependences and system-size dependences for basic extremal properties are obtained.

We propose a possible relation between complex networks and gravity. Our guide in our proposal is the power-law distribution of the node degree in network theory and the information approach to gravity. The established bridge may allow us to carry geometric mathematical structures, which are considered in gravitational theories, to probabilistic aspects studied in the framework of complex networks and vice versa.

Approaches from statistical physics are applied to investigate the structure of network models whose growth rules mimic aspects of the evolution of the world-wide web. We first determine the degree distribution of a growing network in which nodes are introduced one at a time and attach to an earlier node of degree k with rate A_ksim k^gamma. Very different behaviors arise for gamma<1, gamma=1, and gamma>1. We also analyze the degree distribution of a heterogeneous network, th...

We study a simple model in which the growth of a network is determined by the location of one or more random walkers. Depending on walker speed, the model generates a spectrum of structures situated between well-known limiting cases. We demonstrate that the average degree observed by a walker is related to the global variance. Modulating the extent to which the location of node attachment is determined by the walker as opposed to random selection is akin to scaling the speed ...

Systems as diverse as genetic networks or the world wide web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature is found to be a consequence of the two generic mechanisms that networks expand continuously by the addition of new vertices, and new vertices attach preferentially to already well connected sites. A model based on these two ingredie...

The theory of random graphs goes back to the late 1950s when Paul Erd\H{o}s and Alfr\'ed R\'enyi introduced the Erd\H{o}s-R\'enyi random graph. Since then many models have been developed, and the study of random graph models has become popular for real-life network modelling such as social networks and financial networks. The aim of this overview is to review relevant random graph models for real-life network modelling. Therefore, we analyse their properties in terms of styli...

We propose generalizations of a number of standard network models, including the classic random graph, the configuration model, and the stochastic block model, to the case of time-varying networks. We assume that the presence and absence of edges are governed by continuous-time Markov processes with rate parameters that can depend on properties of the nodes. In addition to computing equilibrium properties of these models, we demonstrate their use in data analysis and statisti...