Random graphs as models of networks

We study random graph models for directed acyclic graphs, an important class of networks that includes citation networks, food webs, and feed-forward neural networks among others. We propose two specific models, roughly analogous to the fixed edge number and fixed edge probability variants of traditional undirected random graphs. We calculate a number of properties of these models, including particularly the probability of connection between a given pair of vertices, and comp...

A key challenge within the social network literature is the problem of network generation - that is, how can we create synthetic networks that match characteristics traditionally found in most real world networks? Important characteristics that are present in social networks include a power law degree distribution, small diameter and large amounts of clustering; however, most current network generators, such as the Chung Lu and Kronecker models, largely ignore the clustering ...

This article serves as an introduction to the study of networks of social systems. First, we introduce the reader to key mathematical tools to study social networks, including mathematical representations of networks and essential terminology. We describe several network properties of interest and techniques for measuring these properties. We also discuss some popular generative models of networks and see how the study of these models provides insight into the mechanisms for ...

In the last decades, the study of models for large real-world networks has been a very popular and active area of research. A reasonable model should not only replicate all the structural properties that are observed in real world networks (for example, heavy tailed degree distributions, high clustering and small diameter), but it should also be amenable to mathematical analysis. There are plenty of models that succeed in the first task but are hard to analyze rigorously. On ...

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...

Random graph (RG) models play a central role in the complex networks analysis. They help to understand, control, and predict phenomena occurring, for instance, in social networks, biological networks, the Internet, etc. Despite a large number of RG models presented in the literature, there are few concepts underlying them. Instead of trying to classify a wide variety of very dispersed models, we capture and describe concepts they exploit considering preferential attachment,...

A model of correlated random networks is examined, i.e. networks with correlations between the degrees of neighboring nodes. These nodes do not necessarily have to be direct neighbors, the maximum range of the correlations can be arbitrarily chosen. Two different methods for the creation of such networks are presented: one of them is a generalization of a well-known algorithm by Maslov and Sneppen. The percolation threshold for the model is calculated and the result is tested...

Random networks are widely used to model complex networks and research their properties. In order to get a good approximation of complex networks encountered in various disciplines of science, the ability to tune various statistical properties of random networks is very important. In this manuscript we present an algorithm which is able to construct arbitrarily degree-degree correlated networks with adjustable degree-dependent clustering. We verify the algorithm by using empi...

It appeared recently that the underlying degree distribution of networks may play a crucial role concerning their robustness. Empiric and analytic results have been obtained, based on asymptotic and mean-field approximations. Previous work insisted on the fact that power-law degree distributions induce high resilience to random failure but high sensitivity to attack strategies, while Poisson degree distributions are quite sensitive in both cases. Then, much work has been done...

Online social networks are a dominant medium in everyday life to stay in contact with friends and to share information. In Twitter, users can connect with other users by following them, who in turn can follow back. In recent years, researchers studied several properties of social networks and designed random graph models to describe them. Many of these approaches either focus on the generation of undirected graphs or on the creation of directed graphs without modeling the dep...