An ensemble of random graphs with identical degree distribution

Abstract

Degree distribution, or equivalently called degree sequence, has been commonly used to be one of most significant measures for studying a large number of complex networks with which some well-known results have been obtained. By contrast, in this paper, we report a fact that two arbitrarily chosen networks with identical degree distribution can have completely different other topological structure, such as diameter, spanning trees number, pearson correlation coefficient, and so forth. Besides that, for a given degree distribution (as power-law distribution with exponent $\gamma =3$ discussed here), it is reasonable to ask how many network models with such a constraint we can have. To this end, we generate an ensemble of this kind of random graphs with $P(k)\sim k^{-\gamma }$ ($\gamma =3$), denoted as graph space $\mathcal{N}(p,q,t)$ where probability parameters $p$ and $q$ hold on $p+q=1$, and indirectly show the cardinality of $\mathcal{N}(p,q,t)$ seems to be large enough in the thermodynamics limit, i.e., $N\to \infty$, by varying values of $p$ and $q$. From the theoretical point of view, given an ultrasmall constant $p_c$, perhaps only graph model $N(1,0,t)$ is small-world and other are not in terms of diameter. And then, we study spanning trees number on two deterministic graph models and obtain both upper bound and lower bound for other members. Meanwhile, for arbitrary $p(\ne 1)$, we prove that graph model $N(p,q,t)$ does go through two phase transitions over time, i.e., starting by non-assortative pattern and then suddenly going into disassortative region, and gradually converging to initial place (non-assortative point). Among of them, one "null" graph model is built.

References in corpus (15)

• Emergence of scaling in random networks
• Power laws, Pareto distributions and Zipf's law
• Assortative mixing in networks
• Mixing patterns in networks
• Stochastic blockmodels and community structure in networks
• Why social networks are different from other types of networks
• Synchronization is optimal in non-diagonalizable networks
• Competing epidemics on complex networks
• Fractal and Transfractal Recursive Scale-Free Nets
• Random walks on weighted networks
• Scaling laws for diffusion on (trans)fractal scale-free networks
• Different thresholds of bond percolation in scale-free networks with identical degree sequence
• Predicting disease-related genes by path-based similarity and community structure in protein-protein interaction network
• Universal features of mountain ridge networks on Earth
• Random Walks on Complex Networks

Cited by in corpus (3)

• Dense networks with scale-free feature
• A general model of hierarchical fractal scale-free networks
• Constructions and properties of a class of random scale-free networks