Graduate Course at the Mathematics Department
2003-4 Spring Semester
Instructor: assoc. prof. Μ.A. Boudourides
The aim of this course is to offer a detailed overview of the theory of complex networks, a relatively new field, the study of which has started during the last years. Undoubtedly, the interest in complex networks has followed the growth - mainly during the last decade - of computer networking on a global scale, as it is manifested by the Internet and the World-Wide Web (or Web). Furthermore, a large number of other applications of complex networks has appeared in many fields, as in sociology, economics, biology, physics etc. Therefore, it is urgently important for theorists to comprehend the distinctive characteristics of complex networks through a variety of perspectives, as in structural-static analysis, in dynamic (time-dependent) behavior and in studies of networked (non-linear) dynamical systems.
In particular, we are going to cover six areas around complex networks. First, we are going to study the 'small world' properties, which in a sense place complex networks somewhere in between regular lattices and random graphs. Although small world networks have been known to social scientists since the 1960s, during the last years they have been found in a growing number of different cases, as in the Web and networks of scientific collaboration. Moreover, two important characteristics found in complex networks are that these networks are scale-free and that various attributes are distributed on these networks according to non-linear power laws. In this way, studying the graph structure of the Internet, one is able to discern that these types of non-linear behavior abound in a broad range, from the Internet topology to the World-Wide Web and e-mail networks. By understanding the structure and the dynamics of complex networks, one is able to implement more efficient methods and algorithms of search on such networks. Finally, we are interested in analyzing a group of diffusion phenomena occurring on complex networks, as in epidemics, viruses, spamming etc.; thus, we intend to study those mechanisms generating heterogeneous patterns over the network and implying their propagation or effacement or emergence of diverse equilibrium patterns.
Note: Readings followed by (*) are compulsory - others are recommended but optional.
- Small World Networks
- Slides (in greek) (*)
- Duncan J. Watts, "Small Worlds," Chapter 3 of D.J. Watts, Six Degrees: The Science of a Connected Age (New York & London: W.W. Norton & Company, 2002). (*)
- Watts, D.J., & Strogatz, S.H. (1998). Collective dynamics of 'small-world' networks, Nature, vol. 393, pp. 440-442. (*)
- Newman, M.E.J. (2000). Models of the small-world, Journal of Statistical Physics, vol. 101, pp. 819-841.
- Small Worlds in WWW, Society and Scientific Collaboration
- Slides (in greek) (*)
- Adamic, L.A. (1999). The small world web. In Lecture Notes in Computer Science, Proceedings of the European Conference in Digital Libraries (ECDL) '99 Conference, pp. 443-454 (Berlin: Springer, 1999). (*)
- Barabasi, A. (2001). The physics of the Web, Physics World, vol. 14, no. 7, art. 9. (*)
- Boudourides, M., & Antypas, G. (2002). A simulation of the structure of the World-Wide Web. Sociological Research Online, vol. 7, no. 1.
- Watts, D.J. (1999). Networks, dynamics and the small-world phenomenon. American Journal of Sociology, vol. 105, no. 2, pp. 493-527.
- Newman, M.E.J. (2001). The structure of scientific collaboration networks, Proceedings of the National Academy of Sciences, vol. 98, no. 2, pp. 404-409.
- Scale-Free Networks and Power Laws
- Slides (in greek) (*)
- Duncan J. Watts, "Beyond the Small World," Chapter 4 of D.J. Watts, Six Degrees: The Science of a Connected Age (New York & London: W.W. Norton & Company, 2002). (*)
- Barabasi, A., & Albert, R. (1999). Emergence of scaling in random networks. Science, vol. 286, pp. 509-512. (*)
- Albert, R., & Barabasi, A.L. (2002). Statistical mechanics of complex networks. Review of Modern Physics, vol. 74, pp. 47-97. (*)
- Amaral, L.A.N., Scala, A., Barthelemy, M., & Stanley, H.E. (2000). Classes of behavior of small-world networks. Proceedings of the National Academy of Sciences, vol. 97, pp. 11149-11152.
- Power Laws in WWW and the Internet
- Slides (in greek) (*)
- Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., & Wiener, J. (2000). Graph structure in the web. In the Proceedings of the 9th World Wide Web Conference.
- Adamic, L.A., & Huberman, B.A. (2000). Power-law distribution of the World Wide Web. Science, vol. 287, p. 2115a. (*)
- Barabasi, A.L., Albert, R., Jeong, H., & Bianconi, G. (2000). Power-law distribution of the World Wide Web. Science, vol. 287, p. 2115b. (*)
- Faloutsos, M., Faloutsos, P., & Faloutsos, C. (1999). On power-law relationships of the Internet topology. Computer Communication Review, vol. 29, pp. 251-262.
- Ebel, H., Mielsch, L.I., & Bornholdt, S. (2002). Scale-free topology of e-mail networks. Physical Review E, vol. 66, 035103.
- Search in Networks
- Slides (in greek) (*)
- Duncan J. Watts, "Search in Networks," Chapter 5 of D.J. Watts, Six Degrees: The Science of a Connected Age (New York & London: W.W. Norton & Company, 2002). (*)
- Kleinberg, J. (2000). The small-world phenomenon: An algorithmic perspective. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 163-170 (New York: ACM, 2000).
- Kleinberg, J. (2000). Navigation in a small world. Nature, vol. 406, p. 845. (*)
- Watts, D.J., Dodds, P.S., & Newman, M.E.J. (2002). Identity and search in social networks. Science, vol. 296, pp. 1302-1305.
- Adamic, L.A., Lukose, R.M., Puniyani, A.R., & Huberman, B.A. (2001). Search in power-law networks. Physical Review E, vol. 64, no. 046135. (*)
- Kim, B.J., Yoon, C.N., Han, S.K., & Jeong, H. (2002). Path finding strategies in scale-free networks. Physical Review E, vol. 65, no. 027103.
- Menczer, F. (2002). Growing and navigating the small world Web by local content, Proceedings of the National Academy of Sciences, vol. 99, no. 22, pp. 14014-14019.
- Lawrence, S., & Giles, C.L. (1999). Accessibility of information on the web. Nature, vol. 400, pp. 107-109.
- Diffusion in Networks
- Slides (in greek) (*)
- Duncan J. Watts, "Epidemics and Failures," Chapter 6 of D.J. Watts, Six Degrees: The Science of a Connected Age (New York & London: W.W. Norton & Company, 2002). (*)
- Watts, D.J. (2002). A simple model of global cascades on random networks. Proceedings of the National Academy of Sciences, vol. 99, pp. 5766-5771. (*)
- Newman, M.E.J., Forrest, S., & Balthrop, J. (2002). Email networks and the spread of computer viruses. Physical Review E, vol. 66, 035101.
- Boykin, P.O., & Roychowdhury, V. (2004). Personal email networks: An effective anti-spam tool (cond-mat/0402143).
- Tyler, J.R., Wilkinson, D.M. & Huberman, B.A. (2003). Email as spectroscopy: Automated discovery of community structure within organizations (cond-mat/0303264).
- metadiktya mailing list metadiktya at nicomedia dot math dot upatras dot gr: accessible only to students attending the course.
- PAJEK: software for the analysis and visualization of large networks.
- UCINET: Social network analysis software.
- GRAPHVIZ: Open source (Linux/Unix) graph drawing software.
- D.J. Watts, Networks and Complexity in Social Systems, Columbia University.
- M.E.J. Newman, Complex Systems Network Theory, University of Michigan.
- D.R. White, Networks and Complexity, University of California at Irvine.
- S. Borgatti, Methods and concepts of social network analysis, Boston College.
- B. Wellman, Social Network Analysis, University of Toronto.
- M. Kearns, Networked Life, University of Pennsylvania.
- J. Kleinberg, The Structure of Information Networks, Cornell University.
- C. Papadimitriou, Game theory and the Internet, University of California at Berkeley.