Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems open journal systems 

Generating maximally disassortative graphs with given degree distribution

Pim van der Hoorn, University of Twente, Northeastern University
Liudmila Ostroumova, Moscow Institute of Physics and Technology and Yandex
Egor Samosvat, Moscow Institute of Physics and Technology and Yandex

We present an algorithm that solves the problem of generating graphs, with a given degree distribution, that are maximally disassortative (with respect to Spearman's rank correlation). As a result, we obtain a general lower bound for Spearman's rho on graphs, which depends on the distribution of the probability mass between the head and tail of the size-biased degree distribution.

AMS 2000 subject classifications: Primary 05C80, 62H20.

Keywords: Random graphs, degree distribution, degree-degree correlation, disassortativity.

Creative Common LOGO

Full Text: PDF

Hoorn, Pim Van Der, Ostroumova, Liudmila, Samosvat, Egor, Generating maximally disassortative graphs with given degree distribution, Stochastic Systems, 8, (2018), 1-44 (electronic). DOI: 10.1214/16-SSY231.


[1]    Alderson, D. L. and Li, L. (2007). Diversity of graphs with highly variable connectivity. Physical Review E 75, 4, 046102. MR2358589

[2]    Bassler, K. E., Del Genio, C. I., Erdʺo    s, P. L., Miklós, I., and Toroczkai, Z. (2015). Exact sampling of graphs with prescribed degree correlations. New Journal of Physics 17, 8, 083052. MR3404225

[3]    Bollobás, B. (1980). A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics 1, 4, 311–316. http://www.sciencedirect.com/science/article/pii/S0195669880800308. MR0595929

[4]    Chen, N. and Olvera-Cravioto, M. (2015). Efficient simulation for branching linear recursions. In Winter Simulation Conference (WSC), 2015. IEEE, 2716–2727.

[5]    Deprez, P. and Wüthrich, M. V. (2015). Construction of directed assortative configuration graphs. arXiv preprint arXiv:1510.00575. MR3683431

[6]    Hurd, T. (2015). The construction and properties of assortative configuration graphs. arXiv preprint arXiv:1512.03084.

[7]    Kannan, R., Tetali, P., and Vempala, S. (1999). Simple markov-chain algorithms for generating bipartite graphs and tournaments. Random Structures and Algorithms 14, 4, 293–308. MR1691976

[8]    Maslov, S. and Sneppen, K. (2002). Specificity and stability in topology of protein networks. Science 296, 5569, 910–913.

[9]    Menche, J., Valleriani, A., and Lipowsky, R. (2010). Asymptotic properties of degree-correlated scale-free networks. Physical Review E 81, 4, 046103.

[10]    Mesfioui, M. and Tajar, A. (2005). On the properties of some nonparametric concordance measures in the discrete case. Nonparametric Statistics 17, 5, 541–554. http://www.tandfonline.com/doi/abs/10.1080/10485250500038967. MR2141361

[11]    Molloy, M. and Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random structures & algorithms 6, 2–3, 161–180. http:// onlinelibrary.wiley.com/doi/10.1002/rsa.3240060204/full. MR1370952

[12]    Newman, M. E. (2002). Assortative mixing in networks. Physical review letters 89, 20, 208701. http://prl.aps.org/abstract/PRL/v89/i20/e208701. MR1975193

[13]    Newman, M. E., Strogatz, S. H., and Watts, D. J. (2001). Random graphs with arbitrary degree distributions and their applications. Physical Review E 64, 2, 026118. http://journals.aps.org/pre/abstract/10.1103/PhysRevE.64.026118.

[14]    Schweizer, B. and Wolff, E. F. (1981). On nonparametric measures of dependence for random variables. The annals of statistics, 879–885. MR0619291

[15]    Spearman, C. (1904). The proof and measurement of association between two things. The American journal of psychology 15, 1, 72–101.

[16]    Stanton, I. and Pinar, A. (2012). Constructing and sampling graphs with a prescribed joint degree distribution. Journal of Experimental Algorithmics (JEA) 17, 3–5. MR2981864

[17]    Van Der Hofstad, R. (2016). Random graphs and complex networks. Vol. 1. Cambridge University Press. MR3617364

[18]    van der Hofstad, R. and Litvak, N. (2014). Degree-degree dependencies in random graphs with heavy-tailed degrees. Internet mathematics 10, 3–4, 287–334. MR3259269

[19]    van der Hoorn, P. (2016). Asymptotic analysis of network structures: degree-degree correlations and directed paths. Ph.D. thesis, University of Twente.

[20]    van der Hoorn, P. and Litvak, N. (2014). Convergence of rank based degree-degree correlations in random directed networks. Moscow Journal of Combinatorics and Number Theory 4, 4, 45–83. http://mjcnt.phystech. edu/en/article.php?id=92. MR3375960

[21]    van der Hoorn, P. and Litvak, N. (2015). Degree-degree dependencies in directed networks with heavy-tailed degrees. Internet Mathematics 11, 2, 155–179. http://dx.doi.org/10.1080/15427951.2014.927038. MR3316861

[22]    Villani, C. (2008). Optimal transport: old and new. Vol. 338. Springer Science & Business Media. MR2459454

[23]    Xulvi-Brunet, R. and Sokolov, I. (2004). Reshuffling scale-free networks: From random to assortative. Physical Review E 70, 6, 066102.

[24]    Yang, D., Pan, L., and Zhou, T. (2017). Lower bound of assortativity coefficient in scale-free networks. Chaos: An Interdisciplinary Journal of Nonlinear Science 27, 3, 033113. MR3627943

Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238