7.2 The Structure of a Sparse Bipartite Graph

We start defining the parameters of the graphs considered in this section. The basic case of a bipartite graph is the symmetric one, that is, both sets of vertices have equal cardinality, say m = m₁ = m₂. Further, the number of edges is denoted by n. Note that all results provided here are asymptotic approximations. Thus, we somehow fix the ratio of n/m and consider what happens as m turns to infinity. Of course, n has to be an integer number, hence we set it equal to the largest integer that is less than or equal to our aspired target. For instance, if we want to achieve a “constant” ratio of 1 − ε, we define n = (1 − ε)m .

Furthermore, we are also interested in the asymmetric situation, that is, m₁ ≠ m₂. We may assume without loss of generality, that m₁ > m₂ holds. In order to obtain comparable results, we are using the same parameter m as above. Note that a symmetric graph contains in total 2m nodes, hence we assure that m₁ + m₂ = 2m is satisfied. This is done by choosing a constant c (0, 1) and defining m₁ = m(1 + c) , respectively m₂ = 2m − m₁. Thus, we yield and can obtain any desired constant ratio in the limit. Note that we do not consider further settings, for instance, assuming constant m₂ or sublinear growth of this parameter. This is based on the fact that we see no practical interest in these settings. Moreover our methods could not be easily applied, because of the completely different component structure.

Additionally, we provide results concerning nonbipartite graphs. Again, we assume that the graph contains 2m nodes and n edges, where the latter value is defined as above. Thus, we can point out similarities and differences.

To simplify the notation, we assign the following numbers to the cases discussed above:

1. Symmetric bipartite graphs.

2. Asymmetric bipartite graphs, c (0, 1) holds.

3. Ordinary, nonbipartite graphs.

For each result, the parameters may depend on the considered case. Thus, we use an index to provide the corresponding number. Furthermore, note that the asymmetry factor c is defined in the asymmetric bipartite case only, hence it does not influence cases 1 and 3 and can thus be omitted in these situations. Furthermore, we consider two different setups:

A. Sparse graph, ε (0, 1) respectively is fixed and n, m₁, and m₂ defined as above.

B. “Critical case,” n equals m.

First, we consider the probability that all components are either trees or unicyclic, that is, no complex component occurs. Further, we consider the likelihood that a graph possesses a complex part having even more cycles. For symmetric bipartite and usual graphs, it is shown that these probabilities tend to zero, under the conditions of Setup A. However, there is a phase transition if this limit is exceeded, compare with Setup B. We infer a similar behavior considering the asymmetric case, but the critical ratio decreases as the asymmetry increases. In particular, the following results hold:

Theorem 7.1 (Setup A; Cases 1, 2, and 3) [7, 10] The probability that no complex component occurs is given by

(Setup A; Cases 1 and 3) [8, 11] The probability that the complex part of the graph contains at most r more edges than nodes is given by

(Setup B; Cases 1 and 3) [3, 7] The probability, that no complex component occurs is given by

We want to emphasize that our approach allows us to compute the given coefficients (and even more detailed expansions) explicitly. For instance, we get

and,

Note that these results provide practical suitable estimates for sufficiently large m, see Section 7.6 for empirical data. Further, we may compare the individual coefficients. Thus, we yield p₁(ε) ≤ p₃(ε) and p₁(ε) ≤ p₂(ε, c) if ε and c satisfy the required properties. We conclude that symmetric bipartite graphs are less likely to contain complex components under the considered properties.

Several related results are given in the literature. For example, Lemma 2.1 of Ref. [14] treats Case 1 under Setup A, but it does not provide an asymptotic approximation. The nonbipartite case is considered in Ref. [3]. We proceed considering tree components:

Theorem 7.2 (Setup A; Cases 1 and 3) [7] The number of tree components T(k, ε) with k vertices satisfies a central limit theorem of the form

where N(0, 1) is a normal random variable,

and

Further, mean and variance are asymptotically given by and as m tends to infinity, respectively.

(Setup A; Case 2) [10] Let (x₀, y₀) be defined by

Then, the number of tree components with k vertices possesses asymptotically the mean

Moreover, a similar formula for the variance can be found, see Ref. [10].

It is surprising that we obtain exactly the same result, both in Case 1 as well as in Case 3. However, asymmetric bipartite graphs behave differently. Note that the number of isolated vertices (i.e., trees of size one) increases, as the asymmetry increases. As a further consequence, we obtain a decreased number of trees of size two, but this trend is not unique. For instance, the number of trees possessing five nodes increases with rising asymmetry. Finally, we present two theorems concerning cycles and cyclic components.

Theorem 7.3 (Setup A; Cases 1, 2, and 3) [7, 10] The number of cyclic components with cycle length 2k (respectively k in Case 3) has in limit a Poisson distribution Po(λ_i(k, ε, c)). Further, the number of cycles has in limit a Poisson distribution , too. All parameters are given in Table 7.1.

Table 7.1 Parameters of Theorems 7.3 and 7.4.

Note that these parameters are somehow related, that is,

holds.

Theorem 7.4 (Setup A; Cases 1, 2, and 3) [7, 10] The number of vertices contained in cycles V(ε, c) has a limiting distribution with characteristic function ϕ_i(s), as given in Table 7.1. Further, denote the number of vertices contained in unicyclic components by U(ε, c). Then, mean and variance of U(ε, c) have in limit the values provided in Table 7.1.

We notice that asymmetry leads to an increased number of cycles and nodes in cyclic components. Furthermore, both parameters increase if we consider an ordinary graph instead of the symmetric bipartite version.

To prove the results claimed above, we first introduce notations and techniques that are required to deduce the results. This is done in the following sections. The formal proofs are finally given in Section 7.5. However, for the sake of shortness, we consider the symmetric bipartite version only. Note that the further results can be deduced in a similar way, but are either much easier to prove (ordinary graphs) or else very long without providing any further insights. Details omitted here can be found in Refs. [7, 10–12].