Network formation and evolution

Generative models of network evolution and link copying models. Network optimization models and random geometric graphs.

Lectures materials:

• Models of network evolution (see below)
  
• Network optimization models (slides)

Book chapters:

• Ch. 5: Barabási-Albert model in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
  
• Ch. 14: Models of network formation in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).

Course readings:

• Kleinberg, J.M., Kumar, R. et al., The web as a graph, In: Proceedings of COCOON ’99 (Tokyo, Japan, 1999), pp. 1–17.
  
• Dorogovtsev, S.N., Mendes, J.F.F. & Samukhin, A.N., Structure of growing networks with preferential linking, Phys. Rev. Lett. 85(21), 4633 (2000).
• Bianconi, G. & Barabási, A.-L., Competition and multiscaling in evolving networks, Europhys. Lett. 54(4), 436-442 (2001).
• Krapivsky, P.L. & Redner, S., Organization of growing random networks, Phys. Rev. E 63(6), 066123 (2001).
• Dorogovtsev, S.N. & Mendes, J.F.F., Evolution of networks, Adv. Phys. 51(4), 1079–1187 (2002).
• Vázquez, A., Growing network with local rules, Phys. Rev. E 67(5), 056104 (2003).
• Krapivsky, P.L. & Redner, S., Network growth by copying, Phys. Rev. E 71(3), 036118 (2005).
• Leskovec, J., Kleinberg, J. & Faloutsos, C., Graph evolution, ACM Trans. Knowl. Discov. Data 1(1), 1–41 (2007).
• Hébert-Dufresne, L., Allard, A. et al., Structural preferential attachment, Phys. Rev. Lett. 107(15), 158702 (2011).
• Hébert-Dufresne, L., Allard, A. et al., Structural preferential attachment, Phys. Rev. E 85(2), 026108 (2012).

• D'Souza, R.M., Borgs, C. et al., Emergence of tempered preferential attachment from optimization, P. Natl. Acad. Sci. USA 104(15), 6112-6117 (2007).
  
• Fabrikant, A., Koutsoupias, E. & Papadimitriou, C., Heuristically optimized trade-offs, In: Proceedings of ICALP ’02 (Malaga, Spain, 2002), pp. 110-122.
• Pržulj, N., Corneil, D.G. & Jurisica, I., Modeling interactome: Scale-free or geometric?, Bioinformatics 20(18), 3508–3515 (2004).
• Ferrer i Cancho, R. & Solé, R.V., Optimization in complex networks, e-print arXiv:cond-mat/0111222v1, pp. 4 (2006).
• Gastner, M.T. & Newman, M.E.J., Optimal design of spatial distribution networks, Phys. Rev. E 74(1), 016117 (2006).
• Papadopoulos, F., Kitsak, M. et al., Popularity versus similarity in growing networks, Nature 489(7417), 537-540 (2012).