- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Revealing the microstructure of the giant component in random graph ensembles

Ido Tishby, Ofer Biham, and Eytan Katzav

Reimer Kühn

  • Racah Institute of Physics, The Hebrew University, Jerusalem 91904, Israel

  • Mathematics Department, King's College London, Strand, London WC2R 2LS, England, United Kingdom

PDF

Phys. Rev. E 97, 042318 – Published 25 April, 2018

DOI: https://doi.org/10.1103/PhysRevE.97.042318

Abstract

The microstructure of the giant component of the Erdős-Rényi network and other configuration model networks is analyzed using generating function methods. While configuration model networks are uncorrelated, the giant component exhibits a degree distribution which is different from the overall degree distribution of the network and includes degree-degree correlations of all orders. We present exact analytical results for the degree distributions as well as higher-order degree-degree correlations on the giant components of configuration model networks. We show that the degree-degree correlations are essential for the integrity of the giant component, in the sense that the degree distribution alone cannot guarantee that it will consist of a single connected component. To demonstrate the importance and broad applicability of these results, we apply them to the study of the distribution of shortest path lengths on the giant component, percolation on the giant component, and spectra of sparse matrices defined on the giant component. We show that by using the degree distribution on the giant component one obtains high quality results for these properties, which can be further improved by taking the degree-degree correlations into account. This suggests that many existing methods, currently used for the analysis of the whole network, can be adapted in a straightforward fashion to yield results conditioned on the giant component.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (48)

  1. R. Albert and A.-L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74, 47 (2002).
  2. S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks: From Biological Networks to the Internet and WWW (Oxford University, Oxford, 2003).
  3. S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Critical phenomena in complex networks, Rev. Mod. Phys. 80, 1275 (2008).
  4. R. van der Hofstad, Random Graphs and Complex Networks, Vol. 1 (Cambridge University Press, 2016).
  5. M. E. J. Newman, Networks: An Introduction (Oxford University, Oxford, 2010).
  6. A. Barrat, M. Barthélemy, and A. Vespignani, Dynamical Processes on Complex Networks (Cambridge University, Cambridge, England, 2012).
  7. P. Erdős and Rényi, On random graphs I, Publicationes Mathematicae Debrecen 6, 290 (1959).
  8. P. Erdős and Rényi, On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960).
  9. P. Erdős and Rényi, On the evolution of random graphs II, Bull. Int. Stat. Inst. 38, 343 (1961).
  10. B. Bollobás, The evolution of random graphs, Trans. Amer. Math. Soc. 286, 257 (1984).
  11. M. Molloy and A. Reed, A critical point for random graphs with a given degree sequence, Random Struct. Alg. 6, 161 (1995).
  12. M. Molloy and A. Reed, The size of the giant component of a random graph with a given degree sequence, Combin. Prob. and Comp. 7, 295 (1998).
  13. B. Bollobás, Random Graphs (Cambridge University, Cambridge, England, 2001).
  14. B. Bollobás, S. Janson, and O. Riordan, The phase transition in inhomogeneous random graphs, Random Struct. Alg. 31, 3 (2007).
  15. S. Janson and O. Riordan, Duality in inhomogeneous random graphs, and the cut metric, Random Struct. Alg. 39, 399 (2011).
  16. A. Engel, R. Monasson, and A. K. Hartmann, On large-deviation properties of Erdős-Rényi random graphs, J. Stat. Phys. 117, 387 (2004).
  17. G. Biroli and R. Monasson, A single defect approximation for localized states on random lattices, J. Phys. A 32, L255 (1999).
  18. R. Kühn, Spectra of sparse random matrices, J. Phys. A 41, 295002 (2008).
  19. V. Sood, S. Redner, and D. ben-Avraham, First-passage properties of the Erdős-Rényi random graph, J. Phys. A 38, 109 (2005).
  20. C. De Bacco, S. N. Majumdar, and P. Sollich, The average number of distinct sites visited by a random walker on random graphs, J. Phys. A 48, 205004 (2015).
  21. I. Tishby, O. Biham, and E. Katzav, The distribution of path lengths of self avoiding walks on Erdős-Rényi networks, J. Phys. A 49, 285002 (2016).
  22. I. Tishby, O. Biham, and E. Katzav, The distribution of first hitting times of random walks on Erdős-Rényi networks, J. Phys. A 50, 115001 (2017).
  23. D. J. Watts, A simple model of global cascades on random networks, Proc. Natl. Acad. Sci. USA 99, 5766 (2002).
  24. M. E. J. Newman, Spread of epidemic disease on networks, Phys. Rev. E 66, 016128 (2002).
  25. M. E. J. Newman, Assortative mixing in networks, Phys. Rev. Lett. 89, 208701 (2002).
  26. B. Karrer and M. E. J. Newman, Message passing approach for general epidemic models, Phys. Rev. E 82, 016101 (2010).
  27. T. Rogers, Assessing node risk and vulnerability in epidemics on networks, Europhys. Lett. 109, 28005 (2015).
  28. R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani, Epidemic processes in complex networks, Rev. Mod. Phys. 87, 925 (2015).
  29. D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Network Robustness and Fragility: Percolation on Random Graphs, Phys. Rev. Lett. 85, 5468 (2000).
  30. V. D. Blondel, J.-L. Guillaume, J. M. Hendrickx, and R. M. Jungers, Distance distribution in random graphs and application to network exploration, Phys. Rev. E 76, 066101 (2007).
  31. E. Katzav, M. Nitzan, D. ben Avraham, P. L. Krapivsky, R. Kühn, N. Ross, and O. Biham, Analytical results for the distribution of shortest path lengths in random networks, Europhys. Lett. 111, 26006 (2015).
  32. M. Nitzan, E. Katzav, R. Kühn, and O. Biham, Distance distribution in configuration-model networks, Phys. Rev. E 93, 062309 (2016).
  33. S. Melnik and J. P. Gleeson, Simple and accurate analytical calculation of shortest path lengths, arXiv:1604.05521.
  34. M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E 64, 026118 (2001).
  35. P. Erdős and T. Gallai, Graphs with given degrees of vertices, Matematikai Lapok 11, 264 (1960).
  36. S. A. Choudum, A simple proof of the Erdős-Gallai theorem on graph sequences, Bulletin Australian Mathematical Society 33, 67 (1986).
  37. F. W. J. Olver, D. M. Lozier, R. F. Boisvert, and C. W. Clark, NIST Handbook of Mathematical Functions (Cambridge University, Cambridge, England, 2010).
  38. H. Bonneau, A. Hassid, O. Biham, R. Kühn, and E. Katzav, Distribution of shortest cycle lengths in random networks, Phys. Rev. E 96, 062307 (2017).
  39. L. A. Shepp and S. P. Lloyd, Ordered cycle lengths in a random permutation, Trans. Am. Math. Soc. 121, 340 (1966).
  40. S. Johnson, J. J. Torres, J. Marro, and M. A. Muñoz, Entropic Origin of Disassortativity in Complex Networks, Phys. Rev. Lett. 104, 108702 (2010).
  41. O. Williams and C. I. Del Genio, Degree correlations in directed scale-free networks, PLoS ONE 9, e110121 (2014).
  42. M. L. Mehta, Random Matrices (Academic, Amsterdam, 2004).
  43. G. Livan, M. Novaes, and P. Vivo, Introduction to Random Matrices: Theory and Practice (Springer, New York, 2018).
  44. T. Rogers, I. Pérez Castillo, R. Kühn, and K. Takeda, Cavity approach to the spectral density of sparse symmetric random matrices, Phys. Rev. E 78, 031116 (2008).
  45. N. I. Akhiezer, The Classical Moment Problem and Some Related Questions in Analysis (Oliver & Boyd, Edinburgh, 1965).
  46. S. F. Edwards and R. C. Jones, The eigenvalue spectrum of a large symmetric random matrix, J. Phys. A 9, 1595 (1976).
  47. R. Kühn, Disentangling giant component and finite cluster contributions in sparse matrix spectra, Phys. Rev. E 93, 042110 (2016).
  48. R. Kühn and T. Rogers, Heterogeneous micro-structure of percolation in sparse networks, Europhys. Lett. 118, 68003 (2017).

Outline

Information

Phys. Rev. E 97, 042318– Published 25 April, 2018
  • Received 6 December 2017
Crossmark - Check for updates button

©2018 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation