Directed Random Graphs with given Degree Distributions

References

• R. Arratia and T.M. Liggett. How likely is an i.i.d. degree sequence to be graphical? Ann. Appl. Probab., 15(1B):652–670, 2005. MR2114985Google Scholar
• E.A. Bender and E.R. Canfield. The asymptotic number of labeled graphs with given degree sequences. J. Comb. Theory A, 24(3):296–307, 1978. MR0505796Google Scholar
• C. Berge. Graphs and hypergraphs, volume 6. Elsevier, 1976. MR0384579Google Scholar
• N.H. Bingham, C.M. Goldie, and J.L. Teugels. Regular variation. Encyclopedia of mathematics and its applications. Cambridge University Press, 1987. MR0898871Google Scholar
• J. Blitzstein and P. Diaconis. A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Internet Mathematics, 6(4):489–522, 2011. MR2809836Google Scholar
• B. Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. Eur. J. Combin., 1:311–316, 1980. MR0595929Google Scholar
• B. Bollobás. Random graphs, volume 73 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2 edition, 2001. MR1864966Google Scholar
• T. Britton, M. Deijfen, and A. Martin-Löf. Generating simple random graphs with prescribed degree distribution. J. Stat. Phys., 124(6):1377–1397, 2006. MR2266448Google Scholar
• A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web. Comput. Netw., 33:309–320, 2000.Google Scholar
• F. Chung and L. Lu. The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci., 99:15879–15882, 2002. MR1944974Google Scholar
• F. Chung and L. Lu. Connected components in random graphs with given degree sequences. Ann. Comb., 6:125–145, 2002. MR1955514Google Scholar
• P. Erdős and T. Gallai. Graphs with given degree of vertices. Mat. Lapok., 11:264–274, 1960.Google Scholar
• P. L. Erdős, I. Miklós, and Z. Toroczkai. A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs. Electron J. Comb., 17:1–10, 2010. MR2644852Google Scholar
• P.P. Fiziev. Uniform generation of random directed graphs with prescribed degree sequence. Master’s thesis, Max Planck Institute, Germany, March 2006.Google Scholar
• J. Kleinberg, R. Kumar, R. Raghavan, S. Rajagopalan, and A. Tomkins. Proceedings of the International Conference on Combinatorics and Computing, volume 1627 of Lecture Notes in Computer Science, chapter The Web as a Graph: Measurements, Models, and Methods, pages 1–17. Springer-Verlag, 1999. MR1730317Google Scholar
• P.L. Krapivsky and S. Redner. A statistical physics perspective on web growth. Comput. Netw., 39:261–276, 2002.Google Scholar
• P.L. Krapivsky, G.J. Rodgers, and S. Redner. Degree distributions of growing networks. Phys. Rev. Lett., 86(23):5401–5404, 2001.Google Scholar
• M.D. LaMar. Algorithms for realizing degree sequences of directed graphs. arXiv:0906.0343, pages 1–35, 2010.Google Scholar
• B.D. McKay and N.C. Wormald. Asymptotic enumeration by degree sequence of graphs of high degree. Eur. J. Combin., 11:565–580, 1990. MR1078713Google Scholar
• B.D. McKay and N.C. Wormald. Uniform generation of random regular graphs of moderate degree. J. Algorithms, 11(1):52–67, 1990. MR1041166Google Scholar
• B.D. McKay and N.C. Wormald. Asymptotic enumeration by degree sequence of graphs with degrees o(n1/2). Combinatorica, 11:369–382, 1991. MR1137769Google Scholar
• M. Molloy and B. Reed. A critical point for random graphs with a given degree sequence. Random Struct. Alg., 6(2–3):161–180, 1995. MR1370952Google Scholar
• M.E.J. Newman, S.H. Strogatz, and D.J. Watts. Random graphs with arbitrary degree distributions and their applications. Phys. Rev., 64(2):1–17, 2001.Google Scholar
• R.C. Read. The enumeration of locally restricted graphs (II). J. Lond. Math. Soc., 35:344–351, 1960. MR0140443Google Scholar
• R. van der Hofstad. Random graphs and complex networks. http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf, 2012.Google Scholar
• R. van der Hofstad, G. Hooghiemstra, and P. Van Mieghem. Distances in random graphs with finite variance degrees. Random Struct. Alg., 27:76–123, 2005. MR2150017Google Scholar
• N.C. Wormald. Some problems in the enumeration of labelled graphs. PhD thesis, Newcastle University 1978.Google Scholar
• N.C. Wormald. Models of random regular graphs. London Mathematical Society Lecture Notes Series, pages 239–298, 1999. MR1725006Google Scholar