Statistical and Machine Learning Approaches for Network Analysis

7.7 Conclusion and Summary

We considered the growth process of sparse random bipartite graphs. Our analysis was based on a generating function approach by applying a double saddle point method. Thus, we obtained asymptotic results concerning the component structure of the graph. In particular, we considered the distribution of the number of tree components of given size, the number of cycles, and the number of nodes contained in cycles, and the probability that components of certain complexity occur. Hence, we showed that it is very likely that the graph consists of trees and unicyclic components only, if the number of edges is less than a critical value. Using further calculations, we obtained a Gaussian limit law for the number of trees, and limiting Poisson distribution for the number of cycles. Finally, we provided some results concerning the critical value, where a phase transition occurs.

We considered both symmetric bipartite graphs possessing an equal number of nodes of both kinds as well as an asymmetric model. Furthermore, we provided corresponding results concerning nonbipartite graphs and found substantial similarities. Finally, we provided numerical results, which positively supported our theoretical hypothesis.

As future work, we suggest a detailed analysis of the partial differential recursion of the generating functions of complex bipartite graphs with positive excess. Using these results, it will be possible to study the phase transition in full detail, similar ...