An ensemble of random graphs with identical degree distribution

DOI10.1063/1.5105354MaRDI QIDQ5218167zbMATH OpenOpenAlexWikidataFDO

Authors Fei Ma, Ping Wang, Xiaomin Wang

Publication date 28 February 2020

Published in Chaos: An Interdisciplinary Journal of Nonlinear Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.11208

zbMATH Keywords

complex networksnumerical simulations

Mathematics Subject Classification ID

Vertex degrees (05C07) Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

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 $mathcalN(p,q,t)$ where probability parameters $p$ and $q$ hold on $p+q=1$, and indirectly show the cardinality of $mathcalN(p,q,t)$ seems to be large enough in the thermodynamics limit, i.e., $Nightarrowinfty$, 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(eq1)$, 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.

Recommendations

• Random growth networks with exponential degree distribution
• On the degree properties of generalized random graphs
• Tailored graph ensembles as proxies or null models for real networks. I: Tools for quantifying structure
• Degree correlations in scale-free random graph models
• Degree distribution of a scale-free random graph model

Cites work

• A critical point for random graphs with a given degree sequence
• A network hierarchy-based method for functional module detection in protein-protein interaction networks
• An iteration method for computing the total number of spanning trees and its applications in graph theory
• Collective dynamics of `small-world' networks
• Emergence of Scaling in Random Networks
• Geometry of minimum spanning trees on scale-free networks
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• Inhomogeneous percolation on multilayer networks
• Loop-erased random walks, spanning trees and Hamiltonian cycles
• On topological properties of Sierpinski networks
• Predicting disease-related genes by path structure and community structure in protein-protein networks
• Scaling laws for diffusion on (trans)fractal scale-free networks
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence

Cited in

(10)

• Entropy and enumeration of spanning connected unicyclic subgraphs in self-similar network
• A method to calculate the number of spanning connected unicyclic(bicyclic) subgraphs in 2-separable networks
• Ensemble nonequivalence in random graphs with modular structure
• Constructions and properties of a class of random scale-free networks
• Tailored graph ensembles as proxies or null models for real networks. I: Tools for quantifying structure
• Random growth networks with exponential degree distribution
• Random growth scale-free networked models with an identical degree distribution and a tunable assortativity index
• Stochastic growth tree networks with an identical fractal dimension: construction and mean hitting time for random walks
• Random walks and consensus problem on tree network with an identical degree distribution
• Scale-free networks with positive integer exponent

This page was built for publication: An ensemble of random graphs with identical degree distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5218167)