Largest connected component in duplication-divergence growing graphs with symmetric coupled divergence

This paper investigates the phase transition of the largest connected component in duplication-divergence growing graphs with symmetric coupled divergence, identifying a critical divergence rate and demonstrating how the inclusion or exclusion of non-interacting vertices in duplication events influences the transition's characteristics and its relationship to bond percolation.

The Gist

Imagine a bustling city that grows every day. In this city, new people (vertices) are born by copying existing residents. When a copy is made, the new person inherits all the friendships (edges) of the original. However, life is messy: sometimes these new friendships break or fade away. This process of copying and losing connections is what scientists call a "duplication-divergence" model.

This paper studies how this city evolves, specifically focusing on when the city transforms from having many small, isolated neighborhoods into having one giant, connected metropolis where everyone is linked, directly or indirectly. This giant neighborhood is called the "largest connected component."

Here is the breakdown of the paper's findings using simple analogies:

1. The Two Ways to Copy

The author explores two different rules for who gets copied to create a new resident:

• The "Social Butterfly" Rule ($d=1$): You can only copy someone who already has at least one friend. If you have no friends, you can't be copied.
• The "Total Population" Rule ($d=0$): You can copy anyone, even people who are completely alone and have no friends at all.

The paper finds that this small difference in who gets copied changes the entire structure of the city's growth.

2. The Tipping Point (The Phase Transition)

The study looks for a specific "tipping point" (called $\delta_c$). Think of this as a dial that controls how often friendships break (the "divergence rate").

• If the dial is set low (friendships rarely break), the city stays connected.
• If the dial is set high (friendships break constantly), the city shatters into tiny, isolated islands.

The paper calculates exactly where this dial needs to be set for the city to snap from "connected" to "broken."

3. The "Euler Entropy" Compass

To find this tipping point, the author uses a mathematical tool called the Euler characteristic.

• The Analogy: Imagine the city as a piece of fabric. The Euler characteristic is like a count of the holes in the fabric versus the patches.
• The Singularity: When the city is on the verge of breaking apart, this mathematical count hits zero. The author calls the natural logarithm of this count "Euler entropy." When this entropy hits a "singularity" (a mathematical explosion or zero), it signals that the giant connected neighborhood is about to disappear.

4. The Magic Transformation

Here is the most interesting part of the discovery:
The author found that the "Social Butterfly" city ($d=1$) and the "Total Population" city ($d=0$) behave very differently. However, by applying a clever mathematical "time warp" (a transformation of the time variable), the author could make the data from the "Total Population" city look almost exactly like the "Social Butterfly" city.

• The Metaphor: It's like watching a movie of the "Total Population" city played at a variable speed. If you speed up or slow down the playback just right, the moment the city breaks apart aligns perfectly with the moment the "Social Butterfly" city breaks apart. This suggests that the underlying physics of the collapse is the same, even though the rules for who gets copied are different.

5. The Result: A Continuous Break

The paper concludes that this transition isn't a sudden, explosive crash (like a glass shattering). Instead, it is a continuous transition.

• The Analogy: Imagine a bridge slowly losing planks one by one. It doesn't snap instantly; it gradually becomes unstable until it finally can't hold traffic.
• The math shows that the "giant neighborhood" shrinks smoothly as the friendship-breaking rate increases, rather than vanishing in a single instant.

Summary

In short, this paper uses math to map out exactly when a growing network of connections falls apart. It discovers that even if you change the rules about who gets to be copied (including lonely people or only social people), you can mathematically "re-time" the process to see that the moment of collapse happens in a very similar, smooth, and predictable way. The study also highlights that "lonely" vertices (people with no friends) play a surprisingly important role in shaping how and when the network breaks.

Technical Summary

Technical Summary: Largest Connected Component in Duplication-Divergence Growing Graphs with Symmetric Coupled Divergence

Problem Statement
This study investigates the structural evolution of sequentially growing networks generated by duplication-divergence models, specifically focusing on the emergence and transition of the largest connected component (LCC). The research addresses the specific case of symmetric coupled divergence (where the divergence asymmetry rate $\sigma = 1/2$). A central challenge addressed is the role of non-interacting vertices (isolated nodes with degree $k=0$) in shaping topological transitions. The paper distinguishes between two selection mechanisms for vertex duplication:

1. $d=1$: Duplication occurs only among interacting vertices (those with at least one edge).
2. $d=0$: Duplication occurs uniformly among all vertices, including non-interacting ones.

The goal is to characterize the phase transition associated with the LCC, identify the critical divergence rate $\delta_c$, and analyze the relationship between this transition and the singularity locus of the Euler entropy ($\delta_{c,\xi}$).

Methodology
The authors employ a combination of analytical derivations and finite-size scaling analysis on simulated growing graphs.

• Model Dynamics: Starting from an initial graph of two connected vertices, the network grows by iteratively duplicating a vertex and probabilistically diverging its edges. The divergence probability is $\delta$, and the symmetric coupling implies equal probability for edge loss from either the original or copy vertex.
• Analytical Approximations: The expected number of interacting vertices $N(\delta, t)$ and edges $E(\delta, t)$ are derived. For large $t$, $N(\delta, t)$ is approximated as $2(1-\delta)t$. The edge count follows a Gamma function distribution derived in prior work [19].
• Topological Indicators: The study utilizes the Euler characteristic ($\chi = t - E(\delta, t)$ for graphs without $n$-cliques $n \ge 3$) and its natural logarithm, the Euler entropy ($\ln|t - E(\delta, t)|$), to detect topological singularities.
• Finite-Size Scaling (FSS): To determine critical exponents and the critical point $\delta_c$, the authors apply FSS ansatzes to:
  • The probability $P(\delta, t)$ of a vertex belonging to the LCC.
  • The susceptibility $\chi(\delta, t)$ of this probability.
  • The weighted average component size $\langle s \rangle$.
  • A modified susceptibility $\chi'(\delta, t)$ excluding non-interacting vertices ($s=1$).
• Time Transformation: For the $d=0$ model, a time transformation $t'(\delta, t)$ is introduced to map the growth dynamics of the $d=0$ case onto the $d=1$ framework, allowing for a unified analysis of the Euler entropy singularity.

Key Results

1. Critical Divergence Rates:

   • For the $d=0$ model, a singularity in the Euler entropy is found at $\delta_{c,\xi} \approx 0.442$.
   • For the $d=1$ model, the Euler entropy singularity occurs at $\delta_{c,\xi} \approx 1 - e^{-1} \approx 0.632$.
   • The critical point for the LCC transition, $\delta_c$, is found to slightly precede the Euler entropy singularity. For the $d=1$ model, $\delta_c = 0.6 \pm 0.002$. For the $d=0$ model, a modified critical point $\delta_c' = 0.425 \pm 0.001$ is identified when analyzing component sizes excluding isolated vertices.

2. Scaling and Critical Exponents:

   • The transition is characterized by scaling collapse of $P(\delta, t)$ and $\chi(\delta, t)$.
   • For the $d=1$ model, the estimated exponents are $\zeta = -0.033 \pm 0.059$ and $\nu = 9.634 \pm 0.069$. The relation $\psi/\nu = 1 + 2\zeta/\nu$ holds, yielding $\psi/\nu \approx 1$.
   • The estimated $\zeta$ is extremely small (order of $10^{-2}$), suggesting the transition may be continuous rather than explosive (which would imply $\zeta=0$).
   • For the $d=0$ model (excluding $s=1$), the scaling collapse yields $\nu' = 6.185 \pm 0.002$ and $\varsigma = 6.827 \pm 0.002$.

3. Role of Non-Interacting Vertices:

   • The presence of non-interacting vertices ($d=0$) significantly alters the growth pattern and the location of the critical divergence rate compared to the $d=1$ case.
   • The time transformation $t'(\delta, t)$ successfully maps the $d=0$ Euler entropy curve to exhibit a singularity locus near $1 - e^{-1}$, similar to the $d=1$ case, despite the underlying differences in vertex selection.

Significance and Claims
The paper claims to provide a deeper understanding of structural changes in duplication-divergence networks under symmetric coupled divergence. The primary contributions are:

• Identification of Phase Transitions: The study locates the phase transition for the largest connected component in symmetric coupled divergence models, distinguishing between cases where isolated vertices are included or excluded from the duplication process.
• Correlation with Topological Singularities: It demonstrates that the LCC transition occurs near the locus where the Euler characteristic is zero (singularity in Euler entropy), reinforcing the utility of topological invariants in detecting connectivity transitions in growing graphs.
• Impact of Vertex Selection: The work highlights that the inclusion of non-interacting vertices ($d=0$) is a crucial factor in determining the critical divergence rate, shifting the transition point significantly compared to models restricted to interacting vertices ($d=1$).
• Nature of the Transition: The estimated exponents suggest the transition is continuous, with $\zeta \approx 0$ and $\psi/\nu \approx 1$, drawing a plausible analogy to jamming transitions and bond percolation, though the authors remain modest about definitive classification.

The findings suggest implications for bond percolation in these specific growing graph models, particularly regarding how the mechanism of vertex selection influences the global connectivity of the network.