Hostname: page-component-74656f9884-rngvg Total loading time: 0 Render date: 2026-11-05T22:35:42.419Z Has data issue: false hasContentIssue false
  • English
  • Français

The k-Core and Branching Processes

Published online by Cambridge University Press:  01 January 2008

OLIVER RIORDAN
OLIVER RIORDAN*
Affiliation:
Royal Society Research Fellow, Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Cambridge CB3 0WB, UK (e-mail: O.M.Riordan@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The k-core of a graph G is the maximal subgraph of G having minimum degree at least k. In 1996, Pittel, Spencer and Wormald found the threshold λc for the emergence of a non-trivial k-core in the random graph G(n, λ/n), and the asymptotic size of the k-core above the threshold. We give a new proof of this result using a local coupling of the graph to a suitable branching process. This proof extends to a general model of inhomogeneous random graphs with independence between the edges. As an example, we study the k-core in a certain power-law or ‘scale-free’ graph with a parameter c controlling the overall density of edges. For each k ≥ 3, we find the threshold value of c at which the k-core emerges, and the fraction of vertices in the k-core when c is ϵ above the threshold. In contrast to G(n, λ/n), this fraction tends to 0 as ϵ→0.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 1 , January 2008 , pp. 111 - 136
Copyright
Copyright © Cambridge University Press 2007

References

[1]Aiello, W., Chung, F. and Lu, L. (2001) A random graph model for power law graphs. Experiment. Math. 10 53–66.CrossRefGoogle Scholar
[2]Barabási, A.-L. and Albert, R. (1999) Emergence of scaling in random networks. Science 286 509–512.CrossRefGoogle ScholarPubMed
[3]Bollobás, B. (1984) The evolution of sparse graphs. In Graph Theory and Combinatorics: Cambridge 1983, Academic Press, London, pp. 35–57.Google Scholar
[4]Bollobás, B., Janson, S. and Riordan, O. (2005) The phase transition in a uniformly grown random graph has infinite order. Random Struct. Alg. 26 1–36.CrossRefGoogle Scholar
[5]Bollobás, B., Janson, S. and Riordan, O. (2007) The phase transition in inhomogeneous random graphs. Random Struct. Alg. 31 3–122.CrossRefGoogle Scholar
[6]Cain, J. and Wormald, N. (2006) Encores on cores. Electron. J. Combin. 13 R81.CrossRefGoogle Scholar
[7]Callaway, D. S., Hopcroft, J. E., Kleinberg, J. M., Newman, M. E. J. and Strogatz, S. H. (2001) Are randomly grown graphs really random? Phys. Rev. E 64 041902.CrossRefGoogle ScholarPubMed
[8]Chvátal, V. (1991) Almost all graphs with 1.44n edges are 3-colorable. Random Struct. Alg. 2 11–28.CrossRefGoogle Scholar
[9]Cooper, C. (2004) The cores of random hypergraphs with a given degree sequence. Random Struct. Alg. 25 353–375.CrossRefGoogle Scholar
[10]Darling, R. W. R. and Norris, J. R. (2005) Differential equation approximations for Markov chains. Manuscript.Google Scholar
[11]Dorogovtsev, S. N., Mendes, J. F. F. and Samukhin, A. N. (2001) Anomalous percolation properties of growing networks. Phys. Rev. E 64 066110.CrossRefGoogle ScholarPubMed
[12]Durrett, R. (2003) Rigorous result for the CHKNS random graph model. In Proc. Discrete Random Walks 2003 (Banderier, C. and Krattenthaler, C., eds), Discrete Mathematics and Theoretical Computer Science AC 95–104. http://dmtcs.loria.fr/proceedings/CrossRefGoogle Scholar
[13]Fernholz, D. and Ramachandran, V. (2003) The giant k-core of a random graph with a specified degree sequence. Manuscript.Google Scholar
[14]Harris, T. E. (1960) A lower bound for the critical probability in a certain percolation process. Proc. Cam. Philos. Soc. 56 13–20.CrossRefGoogle Scholar
[15]Janson, S. and Luczak, M. J. (2007) A simple solution to the k-core problem. Random Struct. Alg. 30 50–62.CrossRefGoogle Scholar
[16]Kalikow, S. and Weiss, B. (1988) When are random graphs connected? Israel J. Math. 62 257–268.CrossRefGoogle Scholar
[17]Kallenberg, O. (2002) Foundations of Modern Probability, 2nd edn, Springer, New York.CrossRefGoogle Scholar
[18]Kleitman, D. J. (1966) Families of non-disjoint subsets, J. Combin. Theory 1 153–155.CrossRefGoogle Scholar
[19]Molloy, M. (2005) Cores in random hypergraphs and Boolean formulas. Random Struct. Alg. 27 124–135.CrossRefGoogle Scholar
[20]Molloy, M. and Reed, B. (1995) A critical point for random graphs with a given degree sequence. Random Struct. Alg. 6 161–179.CrossRefGoogle Scholar
[21]Pittel, B., Spencer, J. and Wormald, N. (1996) Sudden emergence of a giant k-core in a random graph. J. Combin. Theory Ser. B 67 111–151.CrossRefGoogle Scholar
[22]Riordan, O. (2005) The small giant component in scale-free random graphs. Combin. Probab. Comput. 14 897–938.CrossRefGoogle Scholar
[23]Söderberg, B. (2002) General formalism for inhomogeneous random graphs. Phys. Rev. E 66 066121.CrossRefGoogle ScholarPubMed