Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-26T01:50:11.025Z Has data issue: false hasContentIssue false

References

Published online by Cambridge University Press:  12 January 2017

Remco van der Hofstad
Remco van der Hofstad
Affiliation:
Technische Universiteit Eindhoven, The Netherlands
Get access

Summary

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
Image of the first page of this content. For PDF version, please use the ‘Save PDF’ preceeding this image.'
Type
Chapter
Information
Random Graphs and Complex Networks , pp. 306 - 316
Publisher: Cambridge University Press
Print publication year: 2016

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Achlioptas, D., Clauset, A., Kempe, D., and Moore, C. 2005. On the bias of traceroute sampling or, power-law degree distributions in regular graphs. In: STOC-05: Proceedings of the 37th Annual ACMSymposium on Theory of Computing.
Adamic, L. A. 1999. The small world web. Pages 443–454 of: Lecture Notes in Computer Science, vol. 1696. Springer.Google Scholar
Addario-Berry, L., Broutin, N., and Goldschmidt, C. 2010. Critical random graphs: limiting constructions and distributional properties. Electron. J. Probab., 15(25), 741–775.Google Scholar
Aiello, w., chung, f., and lu, l. 2002. random evolution in massive graphs. pages 97–122 of: handbookof massive data sets. Massive Comput., vol. 4. Dordrecht: Kluwer Acad. Publ.
Aigner, M., and Ziegler, G. 2014. Proofs from The Book. Fifth edn. Springer-Verlag, Berlin. Including illustrations by Karl H., Hofmann.
Albert, R., and Barabási, A. -L. 2002. Statistical mechanics of complex networks. Rev. Modern Phys., 74(1), 47–97.Google Scholar
Albert, R., Jeong, H., and Barabási, A. -L. 1999. Internet: diameter of the World-Wide Web. Nature, 401, 130–131.Google Scholar
Albert, R., Jeong, H., and Barabási, A. -L. 2001. Error and attack tolerance of complex networks. Nature, 406, 378–382.Google Scholar
Aldous, D. Random graphs and complex networks. Transparencies available from http://www.stat.berkeley.edu/∼aldous/Talks/net.ps.
Aldous, D. 1991. Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab., 1(2), 228–266.Google Scholar
Aldous, D. 1993. Tree-based models for random distribution of mass. J. Stat. Phys., 73, 625–641.Google Scholar
Aldous, D. 1997. Brownian excursions, critical random graphs and the multiplicative coalescent. Ann.Probab., 25(2), 812–854.Google Scholar
Alili, L., Chaumont, L., and Doney, R. A. 2005. On a fluctuation identity for random walks and Lévy processes. Bull. London Math. Soc., 37(1), 141–148.Google Scholar
Alon, N., and Spencer, J. 2000. The probabilistic method. Second edn.Wiley-Interscience Series in Discrete Mathematics and Optimization. New York: John Wiley & Sons.
Amaral, L. A. N., Scala, A., Barthélémy, M., and Stanley, H. E. 2000. Classes of small-world networks. Proc. Natl. Acad. Sci. USA, 97, 11149–11152.Google Scholar
Angel, O., Hofstad, R. van der, and Holmgren, C. Preprint (2016). Limit laws for self-loops and multipleedges in the configuration model. Available from http://arxiv.org/abs/1603.07172.
Anthonisse, J. 1971. The rush in a graph. Technical Report University of Amsterdam Mathematical Center.
Arratia, R., and Liggett, T. 2005. How likely is an i.i.d. degree sequence to be graphical. Ann. Appl. Probab., 15(1B), 652–670.Google Scholar
Athreya, K., and Ney, P. 1972. Branching processes. New York: Springer-Verlag. Die Grundlehren der mathematischen Wissenschaften, Band 196.
Austin, T. L., Fagen, R. E., Penney, W. F., and Riordan, J. 1959. The number of components in random linear graphs. Ann. Math. Statist, 30, 747–754.Google Scholar
Azuma, K. 1967. Weighted sums of certain dependent random variables. Tohoku Math. J., 3, 357–367.Google Scholar
Backstrom, L., Boldi, P., Rosa, M., Ugander, J., and Vigna, S. 2012. Four degrees of separation. Pages 33–42 of: Proceedings of the 3rd Annual ACM Web Science Conference. ACM.
Bak, P. 1996. How Nature Works: The Science of Self-Organized Criticality. New York: Copernicus.
Ball, F., Sirl, D., and Trapman, P. 2009. Threshold behaviour and final outcome of an epidemic on a random network with household structure. Adv. in Appl. Probab., 41(3), 765–796.Google Scholar
Ball, F., Sirl, D., and Trapman, P. 2010. Analysis of a stochastic SIR epidemic on a random network incorporating household structure. Math. Biosci., 224(2), 53–73.Google Scholar
Barabási, A. -L. 2002. Linked: the new science of networks. Cambridge, Massachusetts: Perseus Publishing.
Barabási, A. -L., and Albert, R. 1999. Emergence of scaling in random networks. Science, 286(5439), 509–512.Google Scholar
Barabási, A. -L., Albert, R., and Jeong, H. 2000. Scale-free characteristics of random networks: the topology of the world-wide web. Phys. A, 311, 69–77.Google Scholar
Barabási, A. -L., Jeong, H., Néda, Z., Ravasz, E., Schubert, A., and Vicsek, T. 2002. Evolution of the social network of scientific collaborations. Phys. A, 311(3-4), 590–614.Google Scholar
Barraez, D., Boucheron, S., and Fernandez de la Vega, W. 2000. On the fluctuations of the giant component. Combin. Probab. Comput., 9(4), 287–304.Google Scholar
Bavelas, A. 1950. Communication patterns in task-oriented groups. Journ. Acoust. Soc. Amer., 22(64), 725–730.Google Scholar
Behrisch, M., Coja-Oghlan, A., and Kang, M. 2014. Local limit theorems for the giant component of random hypergraphs. Combin. Probab. Comput., 23(3), 331–366.Google Scholar
Bender, E. A., and Canfield, E. R. 1978. The asymptotic number of labelled graphs with given degree sequences. Journal of Combinatorial Theory (A), 24, 296–307.Google Scholar
Bender, E. A., Canfield, E. R., and McKay, B. D. 1990. The asymptotic number of labeled connected graphs with a given number of vertices and edges. Random Structures Algorithms, 1(2), 127–169.Google Scholar
Bennet, G. 1962. Probability inequaltities for the sum of independent random variables. J. Amer. Statist.Assoc., 57, 33–45.Google Scholar
Berger, N., Borgs, C., Chayes, J. T., D'Souza, R. M., and Kleinberg, R. D. 2004. Competition-induced preferential attachment. Pages 208–221 of: Automata, languages and programming. Lecture Notes in Comput. Sci., vol. 3142. Berlin: Springer.
Berger, N., Borgs, C., Chayes, J. T., D'Souza, R. M., and Kleinberg, R. D. 2005a. Degree distribution of competition-induced preferential attachment graphs. Combin. Probab. Comput., 14(5-6), 697–721.Google Scholar
Berger, N., Borgs, C., Chayes, J. T., and Saberi, A. 2005b. On the spread of viruses on the Internet. Pages 301–310 of: SODA–05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discretealgorithms. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics.
Berger, N., Borgs, C., Chayes, J., and Saberi, A. 2014. Asymptotic behavior and distributional limits of preferential attachment graphs. Ann. Probab., 42(1), 1–40.Google Scholar
Bertoin, J. 2006. Random fragmentation and coagulation processes. Cambridge Studies in Advanced Mathematics, vol. 102. Cambridge: Cambridge University Press.
Bhamidi, S. In preparation (2007). Universal techniques to analyze preferential attachment trees: globaland local analysis. Available from http://www.unc.edu/∼bhamidi/preferent.pdf.
Bhamidi, S., Hofstad, R. van der, and Hooghiemstra, G. 2010. First passage percolation on random graphs with finite mean degrees. Ann. Appl. Probab., 20(5), 1907–1965.Google Scholar
Bhamidi, S., Hofstad, der R. van, and Hooghiemstra, G. Universality for first passage percolation on sparserandom graphs. Preprint (2012). To appear in Ann. Probab.
Bianconi, G., and Barabási, A. -L. 2001a. Bose–Einstein condensation in complex networks. Phys. Rev.Lett., 86(24), 5632–5635.Google Scholar
Bianconi, G., and Barabási, A. -L. 2001b. Competition and multiscaling in evolving networks. Europhys.Lett., 54, 436–442.Google Scholar
Billingsley, P. 1968. Convergence of probability measures. New York: John Wiley and Sons.
Billingsley, P. 1995. Probability and measure. Third edn. Wiley Series in Probability and Mathematical Statistics. New York: John Wiley & Sons Inc. A Wiley-Interscience Publication.
Boldi, P., and Vigna, S. 2014. Axioms for centrality. Internet Math., 10(3-4), 222–262.Google Scholar
Bollobás, B. 1980. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin., 1(4), 311–316.Google Scholar
Bollobás, B. 1981. Degree sequences of random graphs. Discrete Math., 33(1), 1–19.Google Scholar
Bollobás, B. 1984a. The evolution of random graphs. Trans. Amer. Math. Soc., 286(1), 257–274.Google Scholar
Bollobás, B. 1984b. The evolution of sparse graphs. Pages 35–57 of: Graph theory and combinatorics(Cambridge, 1983). London: Academic Press.
Bollobás, B. 1998. Modern graph theory. Graduate Texts in Mathematics, vol. 184. Springer-Verlag, New York.
Bollobás, B. 2001. Random graphs. Second edn. Cambridge Studies in Advanced Mathematics, vol. 73. Cambridge: Cambridge University Press.
Bollobás, B., and Riordan, O. 2003a. Mathematical results on scale-free random graphs. Pages 1–34 of: Handbook of graphs and networks. Wiley-VCH, Weinheim.
Bollobás, B., and Riordan, O. 2003b. Robustness and vulnerability of scale-free random graphs. InternetMath., 1(1), 1–35.Google Scholar
Bollobás, B., and Riordan, O. 2004. The diameter of a scale-free random graph. Combinatorica, 24(1), 5–34.Google Scholar
Bollobás, B., Riordan, O., Spencer, J., and Tusnády, G. 2001. The degree sequence of a scale-free random graph process. Random Structures Algorithms, 18(3), 279–290.Google Scholar
Bollobás, B., Borgs, C., Chayes, J., and Riordan, O. 2003. Directed scale-free graphs. Pages 132–139 of: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD,2003). New York: ACM.
Bollobás, B., Janson, S., and Riordan, O. 2007. The phase transition in inhomogeneous random graphs. Random Structures Algorithms, 31(1), 3–122.Google Scholar
Bonato, A. 2008. A course on the web graph. Graduate Studies in Mathematics, vol. 89. Providence, RI: American Mathematical Society.
Borgs, C., Chayes, J. T., Kesten, H., and Spencer, J. 1999. Uniform boundedness of critical crossing probabilities implies hyperscaling. Random Structures Algorithms, 15(3-4), 368–413.Google Scholar
Borgs, C., Chayes, J. T., Kesten, H., and Spencer, J. 2001. The birth of the infinite cluster: finite-size scaling in percolation. Comm. Math. Phys., 224(1), 153–204. Dedicated to Joel L. Lebowitz.Google Scholar
Borgs, C., Chayes, J., Hofstad, R. van der, Slade, G., and Spencer, J. 2005a. Random subgraphs of finite graphs. I. The scaling window under the triangle condition. Random Structures Algorithms, 27(2), 137–184.Google Scholar
Borgs, C., Chayes, J., Hofstad, R. van der, Slade, G., and Spencer, J. 2005b. Random subgraphs of finite graphs. II. The lace expansion and the triangle condition. Ann. Probab., 33(5), 1886–1944.Google Scholar
Borgs, C., Chayes, J., Hofstad, R. van der, Slade, G., and Spencer, J. 2006. Random subgraphs of finite graphs. III. The phase transition for th. n-cube. Combinatorica, 26(4), 395–410.Google Scholar
Borgs, C., Chayes, J. T., Daskalis, C., and Roch, S. 2007. First to market is not everything: an analysis of preferential attachment with fitness. Pages 135–144 of: STOC–07: Proceedings of the thirty-ninthannual ACM symposium on Theory of computing. New York, NY, USA: ACM Press.
Breiman, L. 1992. Probability. Classics in Applied Mathematics, vol. 7. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA. Corrected reprint of the 1968 original.
Bressloff, P. 2014. Waves in neural media. Lecture Notes on Mathematical Modelling in the Life Sciences. Springer, New York. From single neurons to neural fields.
Brin, S., and Page, L. 1998. The anatomy of a large-scale hypertextual Web search engine. Pages 107–117 of: Computer Networks and ISDN Systems, vol. 33.Google Scholar
Britton, T., Deijfen, M., andMartin-Löf, A. 2006. Generating simple random graphs with prescribed degree distribution. J. Stat. Phys., 124(6), 1377–1397.Google Scholar
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., and Wiener, J. 2000. Graph structure in the Web. Computer Networks, 33, 309–320.Google Scholar
Buckley, P. G., and Osthus, D. 2004. Popularity based random graph models leading to a scale-free degree sequence. Discrete Math., 282(1-3), 53–68.Google Scholar
Cayley, A. 1889. A theorem on trees. Q. J. Pure Appl. Math., 23, 376–378.Google Scholar
Champernowne, D. G. 1953. A model of income distribution. Econ. J., 63, 318.Google Scholar
Chen, N., and Olvera-Cravioto, M. 2013. Directed random graphs with given degree distributions. Stoch.Syst., 3(1), 147–186.Google Scholar
Chernoff, H. 1952. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Statistics, 23, 493–507.Google Scholar
Choudum, S. A. 1986. A simple proof of the Erdős-Gallai theorem on graph sequences. Bull. Austral. Math.Soc., 33(1), 67–70.Google Scholar
Chung, F., and Lu, L. 2002a. The average distances in random graphs with given expected degrees. Proc.Natl. Acad. Sci. USA, 99(25), 15879–15882 (electronic).Google Scholar
Chung, F., and Lu, L. 2002b. Connected components in random graphs with given expected degree sequences. Ann. Comb., 6(2), 125–145.Google Scholar
Chung, F., and Lu, L. 2003. The average distance in a random graph with given expected degrees. InternetMath., 1(1), 91–113.Google Scholar
Chung, F., and Lu, L. 2006a. Complex graphs and networks. CBMS Regional Conference Series in Mathematics, vol. 107. Published for the Conference Board of the Mathematical Sciences, Washington, DC.
Chung, F., and Lu, L. 2006b. Concentration inequalities and martingale inequalities: a survey. InternetMath., 3(1), 79–127.Google Scholar
Chung, F., and Lu, L. 2006c. The volume of the giant component of a random graph with given expected degrees. SIAM J. Discrete Math., 20, 395–411.Google Scholar
Clauset, A., and Moore, C. Preprint (2003). Traceroute sampling makes random graphs appear to havepower law degree distributions. Available from https://arxiv.org/abs/cond-mat/0312674.
Clauset, A., and Moore, C. 2005. Accuracy and scaling phenomena in Internet mapping. Phys. Rev. Lett., 94, 018701: 1–4.Google Scholar
Clauset, A., Shalizi, C., and Newman, M. E. J. 2009. Power-law distributions in empirical data. SIAM. review, 51(4), 661–703.Google Scholar
Cohen, R., Erez, K., ben Avraham, D., and Havlin, S. 2000. Resilience of the Internet to random breakdowns. Phys. Rev. Letters, 85, 4626.Google Scholar
Cohen, R., Erez, K., ben Avraham, D., and Havlin, S. 2001. Breakdown of the Internet under intentional attack. Phys. Rev. Letters, 86, 3682.Google Scholar
Cooper, C., and Frieze, A. 2003. A general model of web graphs. Random Structures Algorithms, 22(3), 311–335.Google Scholar
Cooper, C., and Frieze, A. 2004. The size of the largest strongly connected component of a random digraph with a given degree sequence. Combin. Probab. Comput., 13(3), 319–337.Google Scholar
Corless, R. M., Gonnet, G. H., Hare, D. E. G., Jeffrey, D. J., and Knuth, D. E. 1996. On the Lambert W function. Adv. Comput. Math., 5, 329–359.Google Scholar
Coupechoux, E., and Lelarge, M. 2014. How clustering affects epidemics in random networks. Adv. in Appl.Probab., 46(4), 985–1008.Google Scholar
De Castro, R., and Grossman, J. W. 1999a. Famous trails to Paul Erdős. Rev. Acad. Colombiana Cienc.Exact. Fí s. Natur., 23(89), 563–582. Translated and revised from the English.Google Scholar
De Castro, R., and Grossman, J. W. 1999b. Famous trails to Paul Erdős. Math. Intelligencer, 21(3), 51–63. With a sidebar by Paul M. B., Vitanyi.Google Scholar
Deijfen, M., Esker, H. van den, Hofstad, R. van der, and Hooghiemstra, G. 2009. A preferential attachment model with random initial degrees. Ark. Mat., 47(1), 41–72.Google Scholar
Dembo, A., and Zeitouni, O. 1998. Large deviations techniques and applications. 2nd Applications of Mathematics (New York), vol. 38. New York: Springer-Verlag.
Dereich, S., and Mörters, P. 2009. Random networks with sublinear preferential attachment: Degree evolutions. Electronic Journal of Probability, 14, 122–1267.Google Scholar
Dereich, S., and Mörters, P. 2011. Random networks with concave preferential attachment rule. Jahresber.Dtsch. Math.-Ver., 113(1), 21–40.Google Scholar
Dereich, S., and Mörters, P. 2013. Random networks with sublinear preferential attachment: the giant component. Ann. Probab., 41(1), 329–384.Google Scholar
Dodds, P., Muhamad, R., and Watts, D. 2003. An experimental study of search in global social networks. Science, 301(5634), 827–829.Google Scholar
Dommers, S., Hofstad, R. van der, and Hooghiemstra, G. 2010. Diameters in preferential attachment graphs. Journ. Stat. Phys., 139, 72–107.Google Scholar
Dorogovtsev, S. N. 2010. Lectures on complex networks. Oxford Master Series in Physics, vol. 20. Oxford University Press, Oxford. Oxford Master Series in Statistical Computational, and Theoretical Physics.
Dorogovtsev, S. N., Ferreira, A. L., Goltsev, A. V., and Mendes, J. F. F. 2010. Zero Pearson coefficient for strongly correlated growing trees. Phys. Rev. E, 81(3), 031135.Google Scholar
Dudley, R. M. 2002. Real analysis and probability. Cambridge Studies in Advanced Mathematics, vol. 74. Cambridge: Cambridge University Press. Revised reprint of the 1989 original.
Durrett, R. 2007. Random graph dynamics. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge: Cambridge University Press.
Durrett, R. 2010. Probability: theory and examples. Fourth edn. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge.
Dwass, M. 1962. A fluctuation theorem for cyclic random variables. Ann. Math. Statist., 33, 1450–1454.Google Scholar
Dwass, M. 1968. A theorem about infinitely divisible distributions. Z. Wahrscheinleikheitsth., 9, 206–224.Google Scholar
Dwass, M. 1969. The total progeny in a branching process and a related random walk. J. Appl. Prob., 6, 682–686.Google Scholar
Easley, D., and Kleinberg, J. 2010. Networks, crowds, and markets: Reasoning about a highly connectedworld. Cambridge University Press.
Ebel, H., Mielsch, L. -I., and Bornholdt, S. 2002. Scale-free topology of e-mail networks. Phys. Rev. E, 66, 035103.Google Scholar
Eckhoff, M., and Mörters, P. 2014. Vulnerability of robust preferential attachment networks. Electron. J.Probab., 19, no. 57, 47.Google Scholar
Embrechts, P., Klüppelberg, C., and Mikosch, T. 1997. Modelling extremal events. Applications of mathematics (New York), vol. 33. Berlin: Springer-Verlag. For insurance and finance.
Erdős, P. 1947. Some remarks on the theory of graphs. Bull. Amer. Math. Soc., 53, 292–294.Google Scholar
Erdős, P., and Gallai, T. 1960. Graphs with points of prescribed degrees. (Hungarian). Mat. Lapok, 11, 264–274.Google Scholar
Erdős, P., and Rényi, A. 1959. On random graphs. I. Publ. Math. Debrecen, 6, 290–297.Google Scholar
Erdős, P., and Rényi, A. 1960. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int.Közl., 5, 17–61.Google Scholar
Erdős, P., and Rényi, A. 1961a. On the evolution of random graphs. Bull. Inst. Internat. Statist., 38, 343–347.Google Scholar
Erdős, P., and Rényi, A. 1961b. On the strength of connectedness of a random graph. Acta Math. Acad. Sci.Hungar., 12, 261–267.Google Scholar
Erdős, P., and Wilson, R. J. 1977. On the chromatic index of almost all graphs. J. Combinatorial TheorySer. B, 23(2–3), 255–257.Google Scholar
Ergün, G., and Rodgers, G. J. 2002. Growing random networks with fitness. Phys. A, 303, 261–272.Google Scholar
Esker, H. van den, Hofstad, R. van der, and Hooghiemstra, G. 2008. Universality for the distance in finite variance random graphs. J. Stat. Phys., 133(1), 169–202.Google Scholar
Faloutsos, C., Faloutsos, P., and Faloutsos, M. 1999. On power-law relationships of the internet topology. Computer Communications Rev., 29, 251–262.Google Scholar
Feld, S. L. 1991. Why your friends have more friends than you do. American Journal of Sociology, 96(6), 1464–1477.Google Scholar
Feller, W. 1968. An introduction to probability theory and its applications. Volume I. 3rd edn. New York: Wiley.
Feller, W. 1971. An introduction to probability theory and its applications. Volume II. 2nd edn. New York: Wiley.
Fortunato, S. 2010. Community detection in graphs. Physics Reports, 486(3), 75–174.Google Scholar
Freeman, L. 1977. A set of measures in centrality based on betweenness. Sociometry, 40(1), 35–41.Google Scholar
Gao, P., and Wormald, N. 2016. Enumeration of graphs with a heavy-tailed degree sequence. Adv. Math., 287, 412–450.Google Scholar
Gilbert, E. N. 1959. Random graphs. Ann. Math. Statist., 30, 1141–1144.Google Scholar
Gladwell, M. 2006. The tipping point: How little things can make a big difference. Hachette Digital, Inc.
Gnedin, A., Hansen, B., and Pitman, J. 2007. Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws. Probab. Surv., 4, 146–171.Google Scholar
Gradshteyn, I. S., and Ryzhik, I. M. 1965. Table of integrals, series, and products. Fourth edition prepared by Ju. V., Geronimus and M. Ju., Ceitlin. Translated from the Russian by Scripta Technica, Inc. Translation edited by Alan Jeffrey. New York: Academic Press.
Granovetter, M. S. 1973. The strength of weak ties. American Journal of Sociology, 1360–1380.
Granovetter, M. S. 1995. Getting a job: A study of contacts and careers. University of Chicago Press.
Grimmett, G. 1999. Percolation. 2nd edn. Berlin: Springer.
Grimmett, G. R., and Stirzaker, D. R. 2001. Probability and random processes. Third edn. New York: Oxford University Press.
Grossman, J. W. 2002. The evolution of the mathematical research collaboration graph. Pages 201–212 of: Proceedings of the Thirty-third Southeastern International Conference on Combinatorics, Graph Theoryand Computing (Boca Raton, FL, 2002), vol. 158.Google Scholar
Hagberg, O., andWiuf, C. 2006. Convergence properties of the degree distribution of some growing network models. Bull. Math. Biol., 68, 1275–1291.Google Scholar
Halmos, P. 1950. Measure theory. D. Van Nostrand Company, Inc., New York N. Y.
Harary, F. 1969. Graph theory. Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.- London.
Harris, T. 1963. The theory of branching processes. Die Grundlehren der Mathematischen Wissenschaften, Bd. 119. Berlin: Springer-Verlag.
Heuvel, M. van den, and Sporns, O. 2011. Rich-club organization of the human connectome. The Journalof Neuroscience, 31(44), 15775–15786.Google Scholar
Hirate, Y., Kato, S., and Yamana, H. 2008. Web structure in 2005. Pages 36–46 of: Algorithms and modelsfor the web-graph. Springer.
Hoeffding, W. 1963. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58, 13–30.Google Scholar
Hofstad, R. van der. 2010. Percolation and random graphs. Pages 173–247 of: New perspectives instochastic geometry. Oxford Univ. Press, Oxford.
Hofstad, R. van der. 2015. Random graphs and complex networks. Vol. II. In preparation, see http://www.win.tue.nl/∼rhofstad/NotesRGCNII.pdf.
Hofstad, R. van der, Kager, W., and Müller, T. 2009. A local limit theorem for the critical random graph. Electron. Commun. Probab., 14, 122–131.Google Scholar
Hofstad, R. van der, and Keane, M. 2008. An elementary proof of the hitting time theorem. Amer. Math.Monthly, 115(8), 753–756.Google Scholar
Hofstad, R. van der, Leeuwaarden, J. H. S. van, and Stegehuis, C. Preprint (2015). Hierarchical configurationmodel.
Hofstad, R. van der, and Litvak, N. 2014. Degree-degree dependencies in random graphs with heavy-tailed degrees. Internet Math., 10(3-4), 287–334.Google Scholar
Hofstad, R. van der, and Spencer, J. 2006. Counting connected graphs asymptotically. European J. Combin., 27(8), 1294–1320.Google Scholar
Hollander, F. den. 2000. Large deviations. Fields Institute Monographs, vol. 14. Providence, RI: American Mathematical Society.
Hoorn, P. van der, and Litvak, N. 2015. Upper bounds for number of removed edges in the Erased Configuration Model. Proceedings of the 12th International Workshop on Algorithms and Models for the Web-Graph, WAW 2015, 10–11 Dec 2015, Eindhoven, pp. 54–65. Lecture Notes in Computer Science 9479. Springer International Publishing. ISSN 0302-9743 ISBN 978-3-319-26783-8.
Huffaker, B., Fomenkov, M., and Claffy, K. 2012 (May). Internet topology data comparison. Tech. rept. Cooperative Association for Internet Data Analysis (CAIDA).
Jagers, P. 1975. Branching processes with biological applications. London: Wiley-Interscience [John Wiley & Sons]. Wiley Series in Probability and Mathematical Statistics—Applied Probability and Statistics.
Jagers, P., and Nerman, O. 1984. The growth and composition of branching populations. Adv. in Appl.Probab., 16(2), 221–259.Google Scholar
Jagers, P., and Nerman, O. 1996. The asymptotic composition of supercritical multi-type branching populations. Pages 40–54 of: Séminaire de Probabilités, XXX. Lecture Notes in Math., vol. 1626. Berlin: Springer.
Janson, S. 2005. Asymptotic degree distribution in random recursive trees. Random Structures Algorithms, 26(1-2), 69–83.Google Scholar
Janson, S. 2007. Monotonicity, asymptotic normality and vertex degrees in random graphs. Bernoulli, 13(4), 952–965.Google Scholar
Janson, S. 2009. The probability that a random multigraph is simple. Combin. Probab. Comput., 18(1-2), 205–225.Google Scholar
Janson, S. 2010. Asymptotic equivalence and contiguity of some random graphs. Random StructuresAlgorithms, 36(1), 26–45.Google Scholar
Janson, S. 2011. Probability asymptotics: notes on notation. Available at http://arxiv.org/pdf/1108.3924.pdf.
Janson, S. 2014. The probability that a random multigraph is simple. II. J. Appl. Probab., 51A (Celebrating 50 Years of The Applied Probability Trust), 123–137.Google Scholar
Janson, S., Knuth, D. E., Łuczak, T., and Pittel, B. 1993. The birth of the giant component. RandomStructures Algorithms, 4(3), 231–358. With an introduction by the editors.Google Scholar
Janson, S., Łuczak, T., and Rucinski, A. 2000. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York.
Janson, S., and Spencer, J. 2007. A point process describing the component sizes in the critical window of the random graph evolution. Combin. Probab. Comput., 16(4), 631–658.Google Scholar
Járai, A., and Kesten, H. 2004. A bound for the distribution of the hitting time of arbitrary sets by random walk. Electron. Comm. Probab., 9, 152–161 (electronic).Google Scholar
Jin, S., and Bestavros, A. 2006. Small-world characteristics of Internet topologies and implications on multicast scaling. Computer Networks, 50, 648–666.Google Scholar
Jordan, J. 2006. The degree sequences and spectra of scale-free random graphs. Random StructuresAlgorithms, 29(2), 226–242.Google Scholar
Karinthy, F. 1929. Chains. In: Everything is different. Publisher unknown.
Karlin, S. 1967. Central limit theorems for certain infinite urn schemes. J. Math. Mech., 17, 373–401.Google Scholar
Karp, R. M. 1990. The transitive closure of a random digraph. Random Structures Algorithms, 1(1), 73–93.Google Scholar
Kemperman, J. H. B. 1961. The passage problem for a stationary Markov chain. Statistical Research Monographs, Vol. I. The University of Chicago Press, Chicago, Ill.
Kesten, H., and Stigum, B. P. 1966a. Additional limit theorems for indecomposable multidimensional Galton–Watson processes. Ann. Math. Statist., 37, 1463–1481.Google Scholar
Kesten, H., and Stigum, B. P. 1966b. A limit theorem for multidimensional Galton–Watson processes. Ann.Math. Statist., 37, 1211–1223.Google Scholar
Kesten, H., and Stigum, B. P. 1967. Limit theorems for decomposable multi-dimensional Galton–Watson processes. J. Math. Anal. Appl., 17, 309–338.Google Scholar
Kleinberg, J. M. 1999. Authoritative sources in a hyperlinked environment. J. ACM, 46(5), 604–632.Google Scholar
Kleinberg, J. M. 2000a. Navigation in a small world. Nature, 406, 845.Google Scholar
Kleinberg, J. M. 2000b (May). The small-world phenomenon: an algorithm perspective. Pages 163–170 of: Proc. of the twenty-third annual ACM symposium on Principles of distributed computing.
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S, and Tomkins, A. 1999. The Web as a graph: measurements, models, and methods. Pages 1–17 of: Computing and Combinatorics: 5th Annual InternationalConference, COCOON-99, Tokyo, Japan, July 1999. Proceedings. Lecture Notes in Computer Science.
Konstantopoulos, T. 1995. Ballot theorems revisited. Statist. Probab. Lett., 24(4), 331–338.Google Scholar
Krapivsky, P. L., and Redner, S. 2001. Organization of growing random networks. Phys. Rev. E, 63, 066123.Google Scholar
Krapivsky, P. L., and Redner, S. 2005. Network growth by copying. Phys. Rev. E, 71(3), 036118.Google Scholar
Krapivsky, P. L., Redner, S., and Leyvraz, F. 2000. Connectivity of growing random networks. Phys. Rev.Lett., 85, 4629.Google Scholar
Krioukov, D., Kitsak, M., Sinkovits, R., Rideout, D., Meyer, D., and Boguñá, M. 2012. Network cosmology. Scientific reports, 2.Google Scholar
Kumar, R., Raghavan, P., Rajagopalan, S, and Tomkins, A. 1999. Trawling the Web for emerging cyber communities. Computer Networks, 31, 1481–1493.Google Scholar
Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., and Upfal, E. 2000. Stochastic models for the web graph. Pages 57–65 of: 42st Annual IEEE Symposium on Foundations of ComputerScience.
Lakhina, A., Byers, J. W., Crovella, M., and Xie, P. 2003. Sampling biases in IP topology measurements. Pages 332–341 of: Proceedings of IEEE INFOCOM 1.
Lengler, J., Jug, F., and Steger, A. 2013. Reliable neuronal systems: the importance of heterogeneity. PLoS ONE, 8(12), 1–10.Google Scholar
Leskovec, J., Kleinberg, J., and Faloutsos, C. 2005. Graphs over time: densification laws, shrinking diameters and possible explanations. Pages 177–187 of: Proceedings of the eleventh ACM SIGKDDinternational conference on Knowledge discovery in data mining. ACM.
Leskovec, J., Kleinberg, J., and Faloutsos, C. 2007. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD), 1(1), 2.Google Scholar
Leskovec, J., Lang, K., Dasgupta, A., and Mahoney, M. 2009. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Math., 6(1), 29–123.Google Scholar
Leskovec, J., Lang, K., and Mahoney, M. 2010. Empirical comparison of algorithms for network community detection. Pages 631–640 of: Proceedings of the 19th International Conference on World Wide Web. WWW–10. New York, NY, USA: ACM.
Liljeros, F., Edling, C. R., Amaral, L. A. N., and Stanley, H. E. 2001. The web of human sexual contacts. Nature, 411, 907.Google Scholar
Lindvall, T. 2002. Lectures on the coupling method. Dover Publications, Inc., Mineola, NY. Corrected reprint of the 1992 original.
Lint, J. H. van, and Wilson, R. M. 2001. A course in combinatorics. 2nd Cambridge: Cambridge University Press.
Litvak, N., and Hofstad, R. van der. 2013. Uncovering disassortativity in large scale-free networks. Phys.Rev. E, 87(2), 022801.Google Scholar
Lotka, A. J. 1926. The frequency distribution of scientific productivity. Journal of the Washington Academyof Sciences, 16(12), 317–323.Google Scholar
Lovász, L. 2012. Large networks and graph limits. American Mathematical Society Colloquium Publications, vol. 60. American Mathematical Society, Providence, RI.
Lu, L. 2002. Probabilistic methods in massive graphs and Internet computing. Ph.D. thesis, University of California, San Diego. Available at http://math.ucsd.edu/∼llu/thesis.pdf.
Łuczak, T. 1990a. Component behavior near the critical point of the random graph process. RandomStructures Algorithms, 1(3), 287–310.Google Scholar
Łuczak, T. 1990b. On the number of sparse connected graphs. Random Structures Algorithms, 1(2), 171–173.Google Scholar
Łuczak, T., Pittel, B., and Wierman, J. 1994. The structure of a random graph at the point of the phase transition. Trans. Amer. Math. Soc., 341(2), 721–748.Google Scholar
Lyons, R., Pemantle, R., and Peres, Y. 1995. Conceptual proofs of L log L criteria for mean behavior of branching processes. Ann. Probab., 23(3), 1125–1138.Google Scholar
Martin-Löf, A. 1986. Symmetric sampling procedures, general epidemic processes and their threshold limit theorems. J. Appl. Probab., 23(2), 265–282.Google Scholar
Martin-Löf, A. 1998. The final size of a nearly critical epidemic, and the first passage time of a Wiener process to a parabolic barrier. J. Appl. Probab., 35(3), 671–682.Google Scholar
Milgram, S. 1967. The small world problem. Psychology Today, May, 60–67.Google Scholar
Miller, J. C. 2009. Percolation and epidemics in random clustered networks. Phys. Rev. E, 80(Aug), 020901.Google Scholar
Mitzenmacher, M. 2004. A brief history of generative models for power law and lognormal distributions. Internet Math., 1(2), 226–251.Google Scholar
Molloy, M., and Reed, B. 1995. A critical point for random graphs with a given degree sequence. RandomStructures Algorithms, 6(2-3), 161–179.Google Scholar
Molloy, M., and Reed, B. 1998. The size of the giant component of a random graph with a given degree sequence. Combin. Probab. Comput., 7(3), 295–305.Google Scholar
Móri, T. F. 2002. On random trees. Studia Sci. Math. Hungar., 39(1-2), 143–155.Google Scholar
Móri, T. F. 2005. The maximum degree of the Barabási–Albert random tree. Combin. Probab. Comput., 14(3), 339–348.Google Scholar
Nachmias, A., and Peres, Y. 2010. The critical random graph, with martingales. Israel J. Math., 176, 29–41.Google Scholar
Nerman, O., and Jagers, P. 1984. The stable double infinite pedigree process of supercritical branching populations. Z. Wahrsch. Verw. Gebiete, 65(3), 445–460.Google Scholar
Newman, M. E. J. 2000. Models of the small world. J. Stat. Phys., 101, 819–841.Google Scholar
Newman, M. E. J. 2001. The structure of scientific collaboration networks. Proc. Natl. Acad. Sci. USA, 98, 404.Google Scholar
Newman, M. E. J. 2002. Assortative mixing in networks. Phys. Rev. Lett., 89(20), 208701.Google Scholar
Newman, M. E. J. 2003. The structure and function of complex networks. SIAM Rev., 45(2), 167–256 (electronic).Google Scholar
Newman, M. E. J. 2005. Power laws, Pareto distributions and Zipf's law. Contemporary Physics, 46(5), 323–351.Google Scholar
Newman, M. E. J. 2009. Random graphs with clustering. Phys. Rev. Lett., 103(Jul), 058701.Google Scholar
Newman, M. E. J. 2010. Networks: an introduction. Oxford University Press.
Newman, M. E. J., Strogatz, S., and Watts, D. 2002. Random graph models of social networks. Proc. Nat.Acad. Sci., 99, 2566–2572.Google Scholar
Newman, M. E. J., Watts, D. J., and Barabási, A. -L. 2006. The structure and dynamics of networks. Princeton Studies in Complexity. Princeton University Press.
Norros, I., and Reittu, H. 2006. On a conditionally Poissonian graph process. Adv. in Appl. Probab., 38(1), 59–75.Google Scholar
O'Connell, N. 1998. Some large deviation results for sparse random graphs. Probab. Theory Related Fields, 110(3), 277–285.Google Scholar
Okamoto, M. 1958. Some inequalities relating to the partial sum of binomial probabilities. Ann. Inst. Statist.Math., 10, 29–35.Google Scholar
Oliveira, R., and Spencer, J. 2005. Connectivity transitions in networks with super-linear preferential attachment. Internet Math., 2(2), 121–163.Google Scholar
Olivieri, E., and Vares, M. E. 2005. Large deviations and metastability. Encyclopedia of Mathematics and its Applications. Cambridge: Cambridge University Press.
Ostroumova, L., and Grechnikov, E. 2012. The distribution of second degrees in the Bollobás–Riordan random graph model. Mosc. J. Comb. Number Theory, 2(2), 85–110.Google Scholar
Otter, R. 1949. The multiplicative process. Ann. Math. Statist., 20, 206–224.Google Scholar
Pansiot, J.-J., and Grad, D. 1998. On routes and multicast trees in the Internet. ACM SIGCOMM ComputerCommunication Review, 28(1), 41–50.Google Scholar
Pareto, V. 1896. Cours d'economie politique. Geneva, Switserland: Droz.
Pastor-Satorras, R., and Vespignani, A. 2007. Evolution and structure of the Internet: A statistical physicsapproach. Cambridge University Press.
Peköz, E., Röllin, A., and Ross, N. 2013. Degree asymptotics with rates for preferential attachment random graphs. Ann. Appl. Probab., 23(3), 1188–1218.Google Scholar
Peköz, E., Röllin, A., and Ross, N. Preprint (2014). Joint degree distributions of preferential attachmentrandom graphs. Available from http://arxiv.org/pdf/1402.4686.pdf.
Pitman, J., and Yor, M. 1997. The two-parameter Poisson–Dirichlet distribution derived from a stable subordinator. Ann. Probab., 25(2), 855–900.Google Scholar
Pittel, B. 1990. On tree census and the giant component in sparse random graphs. Random StructuresAlgorithms, 1(3), 311–342.Google Scholar
Pittel, B. 2001. On the largest component of the random graph at a nearcritical stage. J. Combin. TheorySer. B, 82(2), 237–269.Google Scholar
Pool, I., and Kochen, M. 1978. Contacts and influence. Social Networks, 1, 5–51.Google Scholar
Rényi, A. 1959. On connected graphs. I. Magyar Tud. Akad. Mat. Kutató Int. Közl., 4, 385–388.Google Scholar
Resnick, S. 2007. Heavy-tail phenomena. Springer Series in Operations Research and Financial Engineering. Springer, New York. Probabilistic and statistical modeling.
Ross, N. 2013. Power laws in preferential attachment graphs and Stein's method for the negative binomial distribution. Adv. in Appl. Probab., 45(3), 876–893.Google Scholar
Rudas, A., Tóth, B., and Valkó, B. 2007. Random trees and general branching processes. Random StructuresAlgorithms, 31(2), 186–202.Google Scholar
Seneta, E. 1969. Functional equations and the Galton-Watson process. Advances in Appl. Probability, 1, 1–42.Google Scholar
Sierksma, G., and Hoogeveen, H. 1991. Seven criteria for integer sequences being graphic. J. Graph Theory, 15(2), 223–231.Google Scholar
Siganos, G., Faloutsos, M., Faloutsos, P., and Faloutsos, C. 2003. Power laws and the AS-level Internet topology. IEEE/ACM Trans. Netw., 11(4), 514–524.Google Scholar
Simon, H. A. 1955. On a class of skew distribution functions. Biometrika, 42, 425–440.Google Scholar
Solomonoff, R., and Rapoport, A. 1951. Connectivity of random nets. Bull. Math. Biophys., 13, 107–117.Google Scholar
Spencer, J. 1997. Enumerating graphs and Brownian motion. Comm. Pure Appl. Math., 50(3), 291–294.Google Scholar
Spitzer, F. 1956. A combinatorial lemma and its application to probability theory. Trans. Amer. Math. Soc., 82, 323–339.Google Scholar
Spitzer, F. 1976. Principles of random walk. 2nd edn. New York: Springer.
Sporns, O. 2011. Networks of the Brain. MIT Press.
Strassen, V. 1965. The existence of probability measures with given marginals. Ann. Math. Statist., 36, 423–439.Google Scholar
Strogatz, S. 2001. Exploring complex networks. Nature, 410(8), 268–276.Google Scholar
Szemerédi, E. 1978. Regular partitions of graphs. Pages 399–401 of: Problèmes combinatoires et théoriedes graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Colloq. Internat. CNRS, vol. 260. CNRS, Paris.
Szymanski, J. 2005. Concentration of vertex degrees in a scale-free random graph process. RandomStructures Algorithms, 26(1-2), 224–236.Google Scholar
Thorisson, H. 2000. Coupling, stationarity, and regeneration. Probability and its applications (New York). New York: Springer-Verlag.
Trapman, P. 2007. On analytical approaches to epidemics on networks. Theoretical Population Biology, 71(2), 160–173.Google Scholar
Travers, J., and Milgram, S. 1969. An experimental study of the small world problem. Sociometry, 32, 425–443.Google Scholar
Ugander, J., Karrer, B., Backstrom, L., and Marlow, C. Preprint (2011). The anatomy of the Facebook social graph. Available from http://arxiv.org/pdf/1111.4503.pdf.
Vega-Redondo, F. 2007. Complex social networks. Econometric Society Monographs, vol. 44. Cambridge University Press, Cambridge.
Viswanath, B., Mislove, A., Cha, M., and Gummadi, K. 2009. On the evolution of user inter-action in Facebook. Pages 37–42 of: Proceedings of the 2Nd ACM Workshop on Online Social Networks. WOSN-09. New York, NY, USA: ACM.
Watts, D. J. 1999. Small worlds. The dynamics of networks between order and randomness. Princeton Studies in Complexity. Princeton, NJ: Princeton University Press.
Watts, D. J. 2003. Six degrees. The science of a connected age. New York: W. W. Norton & Co. Inc.
Watts, D. J., and Strogatz, S. H. 1998. Collective dynamics of ‘small-world’ networks. Nature, 393, 440–442.Google Scholar
Wendel, J. G. 1975. Left-continuous random walk and the Lagrange expansion. Amer. Math. Monthly, 82, 494–499.Google Scholar
Williams, D. 1991. Probability with martingales. Cambridge Mathematical Textbooks. Cambridge: Cambridge University Press.
Willinger, W., Alderson, D., and Doyle, J. C. 2009. Mathematics and the Internet: A source of enormous confusion and great potential. Notices of the American Mathematical Society, 56(5), 586–599.Google Scholar
Willinger, W., Govindan, R., Jamin, S., Paxson, V., and Shenker, S. 2002. Scaling phenomena in the Internet: Critically examining criticality. Proc. Natl. Acad. Sci., 99, 2573–2580.Google Scholar
Wilson, R., Gosling, S., and Graham, L. 2012. A review of Facebook research in the social sciences. Perspectives on Psychological Science, 7(3), 203–220.Google Scholar
Wright, E. M. 1977. The number of connected sparsely edged graphs. J. Graph Theory, 1(4), 317–330.Google Scholar
Wright, E. M. 1980. The number of connected sparsely edged graphs. III. Asymptotic results. J. GraphTheory, 4(4), 393–407.Google Scholar
Yook, S.-H., Jeong, H., and Barabási, A. -L. 2002. Modeling the Internet's large-scale topology. Proc. Natl.Acad. Sci., 99(22), 13382–13386.Google Scholar
Yule, G. U. 1925. A mathematical theory of evolution, based on the conclusions of Dr. J. C., Willis F. R. S. Phil. Trans. Roy. Soc. London, B, 213, 21–87.Google Scholar
Zipf, G. K. 1929. Relative frequency as a determinant of phonetic change. Harvard Studies in ClassicalPhilology, 15, 1–95.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

  • References
  • Remco van der Hofstad, Technische Universiteit Eindhoven, The Netherlands
  • Book: Random Graphs and Complex Networks
  • Online publication: 12 January 2017
  • Chapter DOI: https://doi.org/10.1017/9781316779422.014
Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

  • References
  • Remco van der Hofstad, Technische Universiteit Eindhoven, The Netherlands
  • Book: Random Graphs and Complex Networks
  • Online publication: 12 January 2017
  • Chapter DOI: https://doi.org/10.1017/9781316779422.014
Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

  • References
  • Remco van der Hofstad, Technische Universiteit Eindhoven, The Netherlands
  • Book: Random Graphs and Complex Networks
  • Online publication: 12 January 2017
  • Chapter DOI: https://doi.org/10.1017/9781316779422.014
Available formats
×