The Erlang weighted tree, a new branching process

Mehrdad Moharrami, V. Subramanian, M. Liu, R. SundaresanRandom Struct. Algorithms 2020 · OpenReview

TL;DR

This paper introduces the Erlang Weighted Tree (EWT), a novel branching process that captures the complex, interdependent structure of certain random graphs. The authors analyze its extinction probability and growth rate, revealing a connection to the Krein-Rutman eigenvalue, which offers a powerful tool for understanding the behavior of these intricate networks.

What Problem Does This Paper Address?

The paper tackles the challenge of understanding the structure and behavior of complex random graphs, particularly those exhibiting an "interdependent structure." Traditional random graph models often assume independence between components, which doesn't always reflect real-world networks. The authors focus on a specific random graph model that arises as a local weak limit, and they introduce the Erlang Weighted Tree (EWT) as a way to formally study this limit. The EWT, unlike simpler models, encodes a multi-type branching process with an uncountable number of types, making its analysis more complex. The core problem is to characterize the fundamental properties of this EWT, such as its probability of extinction and its growth rate, and to understand how these properties relate to the underlying random graph structure.

Methods

The paper employs a combination of probabilistic and spectral theory techniques. Key methods include:

  • Local Weak Convergence: The EWT is established as the local weak limit of a sequence of random graphs, a standard technique for analyzing the local structure of large random graphs.
  • Branching Process Theory: The EWT is modeled as a multi-type branching process, allowing the application of established results and techniques from this field.
  • Operator Theory and Spectral Analysis: The authors heavily utilize the concept of growth operators and their spectral properties, particularly the Krein-Rutman eigenvalue and its associated eigenfunctions. This is a central tool for determining growth rates and extinction probabilities.
  • Point Process Perspective: A point process framework is used to analyze the growth rate operator, providing a different lens through which to understand the branching process.
  • Fixed Point Theory: The probability of extinction is characterized as the smallest fixed point of a specific operator, a common approach in branching process analysis.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • EWT's Interdependent Structure: The EWT is not just a simple branching process; its vertices encode a multi-type branching process with an uncountable number of types, reflecting a more complex, interdependent structure than typical random graph limits.
  • Krein-Rutman Eigenvalue as Growth/Extinction Indicator: The Krein-Rutman eigenvalue of the growth operator plays a crucial role. Its value directly determines the probability of extinction (≤ 1 implies extinction, > 1 implies survival) and dictates the growth rate of the process.
  • Smallest Fixed Point for Extinction: The probability of extinction is precisely identified as the smallest fixed point of a specific operator, providing a concrete mathematical target for calculation.
  • Eigenfunctions Reveal Population Dynamics: The left and right eigenfunctions of the growth operator offer insights into the population's behavior: the left eigenfunction captures the asymptotic distribution of vertex types, while the right eigenfunction reflects the root's influence on generation sizes.

Key Results

  • The Erlang Weighted Tree (EWT) is formally defined and shown to be the local weak limit of a specific random graph model.
  • The probability of extinction of the EWT is characterized as the smallest fixed point of an operator.
  • The Krein-Rutman eigenvalue of the growth operator is identified, and its relationship to extinction (β₀ ≤ 1 implies extinction) is established.
  • Explicit formulas for the growth rate and the probability of extinction are derived.
  • The paper provides explicit formulas for the Krein-Rutman eigenvalue and its corresponding left and right eigenfunctions for the case where the potential degree distribution is geometric.

Limitations and Future Work

  • Condition C Failure: The EWT does not satisfy "Condition C" (uniform positivity of the density of the growth operator), meaning direct application of some standard branching process results is not possible, necessitating a different analytical approach.
  • Open Problems: The paper explicitly lists several open problems:
  • Asymptotic distribution of $Z_l$ conditioned on $Z_l > 0$ for $\beta_0 \le 1$.
  • The connection between the reversibility of a continuous-state Markov process and the unimodularity of the branching process.
  • The precise relationship between the probability of extinction and the proportion of vertices in the giant component of the finite graph model.
  • Relaxing the assumption of a finite moment generating function for the potential degree distribution.
  • Exploring the local weak limit when vertices iterate to use their full budget.
  • Extending the methodology to more general multi-type branching processes with uncountable types.

Summary updated

Abstract

In this paper, we study a new discrete tree and the resulting branching process, which we call the \textbf{E}rlang \textbf{W}eighted \textbf{T}ree(\textbf{EWT}). The EWT appears as the local weak limit of a random graph model proposed in~\cite{La2015}. In contrast to the local weak limit of well-known random graph models, the EWT has an interdependent structure. In particular, its vertices encode a multi-type branching process with uncountably many types. We derive the main properties of the EWT, such as the probability of extinction, growth rate, etc. We show that the probability of extinction is the smallest fixed point of an operator. We then take a point process perspective and analyze the growth rate operator. We derive the Krein--Rutman eigenvalue $β_0$ and the corresponding eigenfunctions of the growth operator, and show that the probability of extinction equals one if and only if $β_0 \leq 1$.
BibTeX
@article{moharrami2020erlang,
  author = {Mehrdad Moharrami and V. Subramanian and M. Liu and R. Sundaresan},
  title = {{The Erlang weighted tree, a new branching process}},
  journal = {Random Struct. Algorithms},
  year = {2020},
  url = {https://openreview.net/forum?id=UUAq4PBMHA},
}
Figure