Random Networks with Tunable Degree Distribution and Clustering

Recent work on the structure of social networks and the internet has focussed attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results...

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

We propose a Markov chain simulation method to generate simple connected random graphs with a specified degree sequence and level of clustering. The networks generated by our algorithm are random in all other respects and can thus serve as generic models for studying the impacts of degree distributions and clustering on dynamical processes as well as null models for detecting other structural properties in empirical networks.

We present a generator of random networks where both the degree-dependent clustering coefficient and the degree distribution are tunable. Following the same philosophy as in the configuration model, the degree distribution and the clustering coefficient for each class of nodes of degree $k$ are fixed ad hoc and a priori. The algorithm generates corresponding topologies by applying first a closure of triangles and secondly the classical closure of remaining free stubs. The pro...

This paper presents an algorithm for generating scale-free networks with adjustable clustering coefficient. The algorithm is based on a random walk procedure combined with a triangle generation scheme which takes into account genetic factors; this way, preferential attachment and clustering control are implemented using only local information. Simulations are presented which support the validity of the scheme, characterizing its tuning capabilities.

We offer a solution to a long-standing problem in the physics of networks, the creation of a plausible, solvable model of a network that displays clustering or transitivity -- the propensity for two neighbors of a network node also to be neighbors of one another. We show how standard random graph models can be generalized to incorporate clustering and give exact solutions for various properties of the resulting networks, including sizes of network components, size of the gian...

Recent years have seen a growing interest in the modeling and simulation of social networks to understand several social phenomena. Two important classes of networks, small world and scale free networks have gained a lot of research interest. Another important characteristic of social networks is the presence of community structures. Many social processes such as information diffusion and disease epidemics depend on the presence of community structures making it an important ...

Probabilistic networks display a wide range of high average clustering coefficients independent of the number of nodes in the network. In particular, the local clustering coefficient decreases with the degree of the subtending node in a complicated manner not explained by any current models. While a number of hypotheses have been proposed to explain some of these observed properties, there are no solvable models that explain them all. We propose a novel growth model for both ...

The random graph of Erdos and Renyi is one of the oldest and best studied models of a network, and possesses the considerable advantage of being exactly solvable for many of its average properties. However, as a model of real-world networks such as the Internet, social networks or biological networks it leaves a lot to be desired. In particular, it differs from real networks in two crucial ways: it lacks network clustering or transitivity, and it has an unrealistic Poissonian...

We extend the standard scale-free network model to include a ``triad formation step''. We analyze the geometric properties of networks generated by this algorithm both analytically and by numerical calculations, and find that our model possesses the same characteristics as the standard scale-free networks like the power-law degree distribution and the small average geodesic length, but with the high-clustering at the same time. In our model, the clustering coefficient is also...