Analysis of Complex Networks

5.3 Connectivity

As already mentioned, the connectivity property of neutral networks of RNA structures has a profound impact on our picture of evolutionary optimization. It is closely related to the connectivity of the two subcubes induced by the unpaired and paired nucleotides. We present the combinatorial, constructive proof that localizes the threshold value for generalized n-cubes due to [18]. The particular construction has led to several computational studies on the connectivity of neutral networks [11, 12].

Lemma 5.1 Let Qⁿ_α be a generalized n-cube, , and Γ _n an induced Qⁿ_α-subgraph obtained by selecting each Qⁿ_α-vertex with independent probability λ. Then we have

Proof. Claim1. Suppose . Then for arbitrary l∈,Γ_n contains a.s. exclusively vertices of degree ≥ l.

To prove the claim we first observe that is equivalent to (1–λ)^α–1)α<1. We fix l ∈ . Using the linearity of expectation, ...