Random graphs with arbitrary degree distributions and their applications
- PMID:11497662
- DOI: 10.1103/PhysRevE.64.026118
Random graphs with arbitrary degree distributions and their applications
Abstract
Recent work on the structure of social networks and the internet has focused attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean component size, the size of the giant component if there is one, the mean number of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the world-wide web and collaboration graphs of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.
Similar articles
- Network robustness and fragility: percolation on random graphs.Callaway DS, Newman ME, Strogatz SH, Watts DJ.Callaway DS, et al.Phys Rev Lett. 2000 Dec 18;85(25):5468-71. doi: 10.1103/PhysRevLett.85.5468.Phys Rev Lett. 2000.PMID:11136023
- Are randomly grown graphs really random?Callaway DS, Hopcroft JE, Kleinberg JM, Newman ME, Strogatz SH.Callaway DS, et al.Phys Rev E Stat Nonlin Soft Matter Phys. 2001 Oct;64(4 Pt 1):041902. doi: 10.1103/PhysRevE.64.041902. Epub 2001 Sep 20.Phys Rev E Stat Nonlin Soft Matter Phys. 2001.PMID:11690047
- Emergence of the giant weak component in directed random graphs with arbitrary degree distributions.Kryven I.Kryven I.Phys Rev E. 2016 Jul;94(1-1):012315. doi: 10.1103/PhysRevE.94.012315. Epub 2016 Jul 27.Phys Rev E. 2016.PMID:27575156
- On the centrality of vertices of molecular graphs.Randić M, Novič M, Vračko M, Plavšić D.Randić M, et al.J Comput Chem. 2013 Nov 5;34(29):2514-23. doi: 10.1002/jcc.23413. Epub 2013 Aug 19.J Comput Chem. 2013.PMID:23955387
- Combinatorial properties of graphs and groups of physico-chemical interest.El-Basil S.El-Basil S.Comb Chem High Throughput Screen. 2008 Nov;11(9):707-22. doi: 10.2174/138620708786306014.Comb Chem High Throughput Screen. 2008.PMID:18991574Review.
Cited by
- EEG functional connectivity is partially predicted by underlying white matter connectivity.Chu CJ, Tanaka N, Diaz J, Edlow BL, Wu O, Hämäläinen M, Stufflebeam S, Cash SS, Kramer MA.Chu CJ, et al.Neuroimage. 2015 Mar;108:23-33. doi: 10.1016/j.neuroimage.2014.12.033. Epub 2014 Dec 19.Neuroimage. 2015.PMID:25534110Free PMC article.
- The effects of connectivity on metapopulation persistence: network symmetry and degree correlations.Shtilerman E, Stone L.Shtilerman E, et al.Proc Biol Sci. 2015 May 7;282(1806):20150203. doi: 10.1098/rspb.2015.0203.Proc Biol Sci. 2015.PMID:25833858Free PMC article.
- Comparison of large networks with sub-sampling strategies.Ali W, Wegner AE, Gaunt RE, Deane CM, Reinert G.Ali W, et al.Sci Rep. 2016 Jul 6;6:28955. doi: 10.1038/srep28955.Sci Rep. 2016.PMID:27380992Free PMC article.
- New perspectives on the "silo effect": initial comparisons of network structures across public health collaboratives.Bevc CA, Retrum JH, Varda DM.Bevc CA, et al.Am J Public Health. 2015 Apr;105 Suppl 2(Suppl 2):S230-5. doi: 10.2105/AJPH.2014.302256. Epub 2015 Feb 17.Am J Public Health. 2015.PMID:25689195Free PMC article.
- Trust transitivity in social networks.Richters O, Peixoto TP.Richters O, et al.PLoS One. 2011 Apr 5;6(4):e18384. doi: 10.1371/journal.pone.0018384.PLoS One. 2011.PMID:21483683Free PMC article.
Related information
LinkOut - more resources
Other Literature Sources
Miscellaneous