Cluster Tails for Critical Power-Law Inhomogeneous Random Graphs

Area of Science:

• Graph Theory
• Probability Theory
• Statistical Physics

Background:

• Previous work established the scaling limit of cluster sizes for rank-1 inhomogeneous random graphs with finite variance and infinite third moment degrees.
• The established limit shows that rescaled cluster sizes converge to a sequence of decreasing random variables when degrees follow a power law.

Purpose of the Study:

• To investigate the tail probabilities of the rescaled largest cluster in rank-1 inhomogeneous random graphs.
• To extend existing results on largest cluster size distributions to graphs with infinite third moment degrees.

Main Methods:

• Utilizing large deviation theory to analyze the tail behavior of the largest cluster.
• Employing weak convergence arguments to establish the probabilistic limits.
• Extending techniques from Erdős-Rényi random graph analysis to inhomogeneous models.

Main Results:

• The study provides explicit characterization of the probability that the largest cluster size exceeds a given threshold.
• Results are derived for rank-1 inhomogeneous random graphs where node degrees exhibit infinite third moments.

Conclusions:

• This research offers a deeper understanding of the extreme cluster sizes in complex random graph structures.
• The findings contribute to the theory of random graphs with heavy-tailed degree distributions.