Random growth networks with exponential degree distribution

Area of Science:

• Complex networks
• Statistical physics
• Graph theory

Background:

• Complex networks are often modeled as random graphs with specific constraints like degree distribution.
• Degree distribution is a key characteristic attracting significant research interest in network science.
• Exponential degree distributions (P(k)∼ exp(αk)) are a focus for modeling certain complex networks.

Purpose of the Study:

• To develop a method for constructing exactly solvable random graphs with exponential degree distributions.
• To explore the topological properties of a novel graph space S(p,p^c,t).
• To investigate whether models within this space exhibit properties like small-worldness and assortative mixing.

Main Methods:

• Introduction of type-A and type-B operations for graph construction.
• Development of algorithm A for generating exactly solvable random graphs.
• Extension of the model to a graph space S(p,p^c,t) parameterized by p and p^c (where p+p^c=1).
• Analysis of topological structure properties within the N(p,p^c,t) model.

Main Results:

• The proposed algorithm successfully constructs random graphs with exponential degree distributions.
• The graph space S(p,p^c,t) and its members N(p,p^c,t) exhibit the small-world property.
• Assortative mixing was observed in the studied network models.
• Demonstration that distinct network members can possess different topological properties (e.g., spanning trees) despite sharing the same degree distribution.

Conclusions:

• The developed algorithm provides a framework for creating and analyzing random graphs with exponential degree distributions.
• The N(p,p^c,t) models effectively capture small-world and assortative mixing phenomena.
• Highlighting the importance of considering diverse topological properties beyond degree distribution when comparing networks.