Loading...
Random graphs with specific degree distribution and giant component size
Hébert-Dufresne, Laurent Pósfai, Márton Allard, Antoine
Hébert-Dufresne, Laurent
Pósfai, Márton
Allard, Antoine
Title / Series / Name
Physical Review Research
Publication Volume
7
Publication Issue
2
Pages
Editors
Keywords
General Physics and Astronomy
Files
Loading...
Po_sfai-Ma_rton_2025.pdf
Adobe PDF, 1.15 MB
URI
https://hdl.handle.net/20.500.14018/27804
Abstract
Random networks are a powerful tool in the analytical modeling of complex networks as they allow us to write approximate mathematical models for diverse properties and behaviors of complex systems. These models are often used to study stochastic processes like percolation, where the giant connected component breaks down as edges are removed, yet they fail to properly account for the size of that component, even in a deterministic setting where all edges exist. Here, we introduce a simple conceptual step to account for such connectivity constraints in existing models. We distinguish between network neighbors based on two types of connections that can lead, or not, to the giant component, which we refer to as critical and subcritical degrees. The giant component is the largest unique component of a network that scales with the network's size under our model. It is analogous to many properties of interest, such as the largest epidemic possible on a contact network or the connectivity of an infrastructure network. Accounting explicitly for this component also allows us to capture important structural features of the network in a system of only one or two equations. When applied to sparse connected networks, we show that our approach compares favorably with the predictions of state-of-the-art models, like message passing, which require a number of equations that are linear in system size. We discuss potential applications of this simple framework for studying infrastructure networks where connectivity constraints are critical to the function of the system.
Topic
Publisher
Place of Publication
Type
Journal article
Date
2025-06-03
Language
ISBN
Identifiers
10.1103/PhysRevResearch.7.L022050