Large-scale structure and models

Random graphs and real networks. Degrees of separation in small-world networks, power-law distributions of scale-free networks and mixing in networks.

Lectures materials:

• Random graph models (slides)
  
• Configuration graph model (slides)
• Exponential random graph model (slides)
  
• Small-world networks and models (slides)
  
• Scale-free networks and models (slides)
• Node mixing in networks (slides)
  

Book chapters:

• Ch. 3: Random networks, Ch. 4-5: Scale-free model etc. & Ch. 7: Correlation etc. in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
  
• Ch. 8: Large-scale structure etc. & Ch. 12-15: Network models in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
• Ch. 11: Random Models etc. & Ch. 17: Global properties etc. in Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).
  
• Ch. 18: Power laws etc. & Ch. 20: Small-world etc. in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).
  

Course readings:

• Erdős, P. & Rényi, A., On random graphs I, Publ. Math. Debrecen 6, 290-297 (1959).
• Newman, M.E.J., Watts, D.J. & Strogatz, S.H., Random graph models of social networks, P. Natl. Acad. Sci. USA 99, 2566-2572 (2002).
  
• Newman, M.E.J., Strogatz, S.H. & Watts, D.J., Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E 64(2), 026118 (2001).
  
• Milo, R., Kashtan, N. et al., On the uniform generation of random graphs with prescribed degree sequences, e-print arXiv:0312028v2, pp. 4 (2004).
• Carstens, C.J. & Horadam, K.J., Switching edges to randomize networks, J. Complex Netw. 5(3), 337-351 (2017).
• Dorogovtsev, S.N. & Mendes, J.F.F., Evolution of networks, Adv. Phys. 51(4), 1079-1187 (2002).

• Milgram, S., The small world problem, Psychol. Today 1(1), 60-67 (1967). 
  
• Watts, D.J. & Strogatz, S.H., Collective dynamics of 'small-world' networks, Nature 393(6684), 440-442 (1998).
• Dodds, P.S., Muhamad, R. & Watts, D.J., An experimental study of search in global social networks, Science 301(5634), 827-829 (2003).
• Liben-Nowell, D., Novak, J. et al., Geographic routing in social networks, P. Natl. Acad. Sci. USA 102(33), 11623-11628 (2005).
• Backstrom, L., Boldi, P. et al., Four degrees of separation, In: Proceedings of WebSci '12 (Evanston, IL, USA, 2012), pp. 45-54.
• Ugander, J., Karrer, B. et al., The anatomy of the Facebook social graph, e-print arXiv:1111.4503v1, pp. 17 (2011).

• de Solla Price, D.J., Networks of scientific papers, Science 149, 510-515 (1965).
  
• Barabási, A.-L. & Albert, R., Emergence of scaling in random networks, Science 286(5439), 509-512 (1999).
  
• Clauset, A., Shalizi, C.R. & Newman, M.E.J., Power-law distributions in empirical data, SIAM Rev. 51, 661-703 (2009).
  
• Faloutsos, M., Faloutsos, P. & Faloutsos, C., On power-law relationships of the Internet topology, Comput. Commun. Rev. 29(4), 251-262 (1999).
  
• Golosovsky, M., Preferential attachment mechanism of complex network growth, e-print arXiv:1802.09786v1, pp. 12 (2018).
  
• Albert, R., Jeong, H. & Barabási, A.-L., Error and attack tolerance of complex networks, Nature 406(6794), 378-382 (2000).
  
• Albert, R., Jeong, H. & Barabási, A.-L., Diameter of the World Wide Web, Nature 401, 130-131 (1999).
• Broido, A.D. & Clauset, A., Scale-free networks are rare, e-print arXiv:1801.03400v1, pp. 14 (2018).
  
• Barabási, A.-L., Love is all you need, reply to e-print arXiv:1801.03400v1, pp. 6 (2018).

• Newman, M.E.J., Mixing patterns in networks, Phys. Rev. E 67(2), 026126 (2003).
  
• Newman, M.E.J., Assortative mixing in networks, Phys. Rev. Lett. 89(20), 208701 (2002).
  
• Newman, M.E.J. & Park, J., Why social networks are different from other types of networks, Phys. Rev. E 68(3), 036122 (2003).
  
• Pastor-Satorras, R., Vázquez, A. & Vespignani, A., Dynamical and correlation properties of the Internet, Phys. Rev. Lett. 87(25), 258701 (2001).
  
• Vázquez, A., Pastor-Satorras, R. & Vespignani, A., Large-scale topological and dynamical properties of the Internet, Phys. Rev. E 65(6), 066130 (2002).
  
• Xulvi-Brunet, R. & Sokolov, I.M., Changing correlations in networks: Assortativity and dissortativity, Acta Phys. Pol. B 36, 1431-1455 (2005).
  
• Park, J. & Barabási, A.-L., Distribution of node characteristics in complex networks, P. Natl. Acad. Sci. USA 104(46), 17916-17920 (2007).
  
• Foster, J.G., Foster, D.V. et al., Edge direction and the structure of networks, P. Natl. Acad. Sci. USA 107(24), 10815-10820 (2010).
  
• Estrada, E., Combinatorial study of degree assortativity in networks, Phys. Rev. E 84(4), 047101 (2011).