- 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

Generating random networks that consist of a single connected component with a given degree distribution

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, United Kingdom

PDF

Phys. Rev. E 99, 042308 – Published 17 April, 2019

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

Abstract

We present a method for the construction of ensembles of random networks that consist of a single connected component with a given degree distribution. This approach extends the construction toolbox of random networks beyond the configuration model framework, in which one controls the degree distribution but not the number of components and their sizes. Unlike configuration model networks, which are completely uncorrelated, the resulting single-component networks exhibit degree-degree correlations. Moreover, they are found to be disassortative, namely, high-degree nodes tend to connect to low-degree nodes and vice versa. We demonstrate the method for single-component networks with ternary, exponential, and power-law degree distributions.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (49)

  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 Press, 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 (Eindhoven, 2013), available at https://www.win.tue.nl/∼rhofstad/NotesRGCN2013.pdf.
  5. M. E. J. Newman, Networks: An Introduction (Oxford University Press, Oxford, 2010).
  6. S. Havlin and R. Cohen, Complex Networks: Structure, Robustness and Function (Cambridge University Press, New York, 2010).
  7. E. Estrada, The Structure of Complex Networks: Theory and Applications (Oxford University Press, Oxford, 2011).
  8. A. Barrat, M. Barthélemy, and A. Vespignani, Dynamical Processes on Complex Networks (Cambridge University Press, Cambridge, 2012).
  9. V. Latora, V. Nicosia, and G. Russo, Complex Networks: Principles, Methods and Applications (Cambridge University Press, Cambridge, 2012).
  10. P. Erdős and A. Rényi, On random graphs I, Publ. Math. Debrecen 6, 290 (1959).
  11. P. Erdős and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960).
  12. P. Erdős and A. Rényi, On the evolution of random graphs II, Bull. Int. Stat. Inst. 38, 343 (1961).
  13. B. Bollobás, The evolution of random graphs, Trans. Amer. Math. Soc. 286, 257 (1984).
  14. M. Molloy and B. Reed, A critical point for random graphs with a given degree sequence, Random Struct. Algorithms 6, 161 (1995).
  15. M. Molloy and A. Reed, The size of the giant component of a random graph with a given degree sequence, Comb., Probab. Comput. 7, 295 (1998).
  16. B. Bollobás, Random Graphs (Cambridge University Press, Cambridge, 2001).
  17. I. Tishby, O. Biham, E. Katzav, and R. Kühn, Revealing the microstructure of the giant component in random graph ensembles, Phys. Rev. E 97, 042318 (2018).
  18. 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).
  19. R. Cohen and S. Havlin, Scale-Free Networks are Ultrasmall, Phys. Rev. Lett. 90, 058701 (2003).
  20. P. Erdős and T. Gallai, Graphs with given degrees of vertices, Matematikai Lapok 11, 264 (1960).
  21. S. A. Choudum, A simple proof of the Erdős-Gallai theorem on graph sequences, Bull. Australian Math. Soc. 33, 67 (1986).
  22. 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).
  23. I. Tishby, O. Biham, R. Kühn, and E. Katzav, Statistical analysis of articulation points in configuration model networks, Phys. Rev. E 98, 062301 (2018).
  24. E. Katzav, O. Biham, and A. K. Hartmann, Distribution of shortest path lengths in subcritical Erdős-Rényi networks, Phys. Rev. E 98, 012301 (2018).
  25. M. Kang, Giant components in random graphs, The IMA Volumes in Mathematics and its Applications, edited by A. Beveridge, J. R. Griggs, L. Hogben, G. Musiker, and P. Tetali (Springer International Publishing, Switzerland, 2016), Vol. 159, p. 235.
  26. B. Bollobás and O. Riordan, The phase transition in the Erdős-Rényi random graph process, Bolyai Soc. Math. Studies 25, 59 (2013).
  27. O. Riordan, The phase transition in the configuration model, Combin. Probab. Comput. 21, 265 (2012).
  28. S. Mizutaka and T. Hasegawa, Disassortativity of percolating clusters in random networks, Phys. Rev. E 98, 062314 (2018).
  29. M. E. J. Newman, Assortative Mixing in Networks, Phys. Rev. Lett. 89, 208701 (2002).
  30. F. W. J. Olver, D. M. Lozier, R. F. Boisvert, and C. W. Clark, NIST Handbook of Mathematical Functions (Cambridge University Press, Cambridge, 2010).
  31. G. Bianconi, The entropy of randomized network ensembles, Europhys. Lett. 81, 28005 (2008).
  32. G. Bianconi, Entropy of network ensembles, Phys. Rev. E 79, 036114 (2009).
  33. A. J. E. M. Janssen and J. S. H. van Leeuwaarden, Giant component sizes in scale-free networks with power-law degrees and cutoffs, Europhys. Lett. 112, 68001 (2015).
  34. S. Johnson, J. J. Torres, J. Marro, and M. A. Munoz, Entropic Origin of Disassortativity in Complex Networks, Phys. Rev. Lett. 104, 108702 (2010).
  35. O. Williams and C. I. Del Genio, Degree correlations in directed scale-free networks, PLoS One 9, e110121 (2014).
  36. T. Coolen, A. Annibale, and E. Roberts, Generating Random Networks and Graphs (Oxford University Press, Oxford, 2017).
  37. A. C. C. Coolen, A. De Martino, and A. Annibale, Constrained Markovian dynamics of random graphs, J. Stat. Phys. 136, 1035 (2009).
  38. A. Annibale, A. C. C. Coolen, L. P. Fernandes, F. Fraternali, and J. Kleinjung, Tailored graph ensembles as proxies or null models for real networks I: Tools for quantifying structure, J. Phys. A 42, 485001 (2009).
  39. E. S. Roberts, T. Schlitt, and A. C. C. Coolen, Tailored graph ensembles as proxies or null models for real networks II: Results on directed graphs, J. Phys. A 44, 275002 (2011).
  40. E. S. Roberts, A. Annibale, and A. C. C. Coolen, Tailored random graph ensembles, J. Phys.: Conf. Ser. 410, 012097 (2013).
  41. S. S. Shen-Orr, R. Milo, S. Mangan, and U. Alon, Network motifs in the transcriptional regulation network of Escherichia coli, Nat. Genet. 31, 64 (2002).
  42. N. Kashtan, S. Itzkovitz, R. Milo, and U. Alon, Topological generalizations of network motifs, Phys. Rev. E 70, 031909 (2004).
  43. S. Maslov, K. Sneppen, and A. Zaliznyak, Detection of topological patterns in complex networks: Correlation profile of the internet, Physica A 333, 529 (2004).
  44. J. Park and M. E. J. Newman, Origin of degree correlations in the Internet and other networks, Phys. Rev. E 68, 026112 (2003).
  45. P. Holme and J. Zhao, Exploring the assortativity-clustering space of a network's degree sequence, Phys. Rev. E 75, 046111 (2007).
  46. L. Giot et al., A protein interaction map of Drosophila melanogaster, Science 302, 1727 (2003).
  47. S. Wandelt, X. Sun, E. Menasalvas, A. Rodriguez-González, and M. Zanin, On the use of random graphs as null model of large connected networks, Chaos, Solitons Fractals 119, 318 (2019).
  48. M. Karsai, G. Iniguez, R. Kikas, K. Kaski, and J. Kertész, Local cascades induced global contagion: How heterogeneous thresholds, exogenous effects, and unconcerned behaviour govern online adoption spreading, Sci. Rep. 6, 27178 (2016).
  49. M.-X. Li, Z.-Q. Jiang, W.-J. Xie, S. Micciche, M. Tumminello, W.-X. Zhou, and R. N. Mantegna, A comparative analysis of the statistical properties of large mobile phone calling networks, Sci. Rep. 4, 5132 (2014).

Outline

Information

Phys. Rev. E 99, 042308– Published 17 April, 2019
  • Received 22 September 2018
Crossmark - Check for updates button

©2019 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation