Statistical and Machine Learning Approaches for Network Analysis

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 ...