An ensemble of random graphs with identical degree distribution

Area of Science:

• Network Science
• Graph Theory
• Statistical Physics

Background:

• Degree distribution is crucial for analyzing complex networks, often exhibiting power-law properties.
• Understanding network topology is essential for characterizing their behavior and function.

Purpose of the Study:

• To investigate topological properties of a novel graph space N(p,q,t) with a specific power-law degree distribution.
• To determine how parameters p and q influence network characteristics such as diameter, spanning tree number, and assortativity.
• To establish complementary measures for distinguishing between different network models.

Main Methods:

• Generation of an ensemble of random graphs N(p,q,t) with P(k)∼k^-γ (γ=3).
• Analytical calculations and numerical simulations to study topological structures.
• Analysis of diameter, spanning tree number, and Pearson correlation coefficient for assortativity.

Main Results:

• The graph model N(1,0,t) exhibits small-world properties, while others may not, based on diameter.
• Exact solutions for spanning tree numbers provide bounds for the graph space.
• Phase transitions in assortativity (nonassortative to disassortative) were observed over time for p≠1.

Conclusions:

• Topological parameters (diameter, spanning tree number, assortativity) effectively distinguish network models within the N(p,q,t) space.
• These parameters serve as valuable complements to degree distribution analysis.
• A null graph model was developed for comparative analysis.