Small-world and scale-free networks

Degrees of separation, small-world networks and model. Power-law degree distributions, scale-free networks and models.

Lecture handouts:

• (3) Small-world networks and model
  
• (3-4) Scale-free distributions and networks
• (4) Preferential attachment models

Lab notebooks:

• (iv) Small-world and scale-free models (I, II, III)
• (vi) Errors and attacks on the Internet (III)

Book chapters:

• → Ch. 3.8-9: Small worlds etc. & Ch. 4-5: Scale-free property etc. in  Barabási, A.-L., Network Science (Cambridge University Press, 2016).
  
• Ch. 8.4: Power laws etc. &  Ch. 14-15: Models of network formation etc. in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
• Ch. 18: Power laws etc. and Ch. 20: Small-world phenomenon in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).

Course readings:

• Milgram, S., The small world problem , Psychol. Today 1(1), 60-67 (1967). 
  
• Granovetter, M.S., The strength of weak ties, Am. J. Sociol. 78(6), 1360-1380 (1973).
  
• → 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).
• → Zamora-López, G. & Brasselet, R., Sizing the length of complex networks, e-print arXiv:1810.12825v1, pp. 25 (2018).
  
• → Kleinberg, J.M., Navigation in a small world, Nature 406(6798), 845 (2000).

• 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).
  
• Faloutsos, M., Faloutsos, P. & Faloutsos, C., On power-law relationships of the Internet topology, Comput. Commun. Rev. 29(4), 251-262 (1999).
• Clauset, A., Shalizi, C.R. & Newman, M.E.J., Power-law distributions in empirical data, SIAM Rev. 51, 661-703 (2009).
• → 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).
• Dorogovtsev, S.N. & Mendes, J.F.F., Evolution of networks, Adv. Phys. 51(4), 1079-1187 (2002).
• De Domenico, M. & Arenas, A., Modeling structure and resilience of the dark network, Phys. Rev. E 95(2), 022313 (2017).
• Golosovsky, M., Preferential attachment mechanism of complex network growth, e-print arXiv:1802.09786v1, pp. 12 (2018).
  
• Voitalov, I., van der Hoorn, P. et al., Scale-free networks well done, e-print arXiv:1811.02071v1, pp. 31 (2018).
  
• Broido, A.D. & Clauset, A., Scale-free networks are rare, Nat. Commun. 10(1), 1017 (2019).
• Barabási, A.-L., Love is all you need, reply to e-print arXiv:1801.03400v1, pp. 6 (2018).
• → Holme, P., Rare and everywhere, Nat. Commun. 10(1), 1016 (2019).
• → Mannion, S. & MacCarron, P., Fitting degree distributions of complex networks, e-print arXiv:2212.06649v1, pp. 21 (2022).