Course title: Random Graphs and Complex Networks

Instructor: Nelly Litvak, UT

Course schedule: the course schedule can be found here.

IMPORTANT: Here you will find a general information only!
For this course we will use Wikispaces Classroom.
All students that have subscribed for the course before August 27 should have received an invitation to join the wiki. If you want to join the course, please contact the instructor for an invitation or a join code.


The course is aiming at students in theoretical and applied mathematics with interest in probability, graphs and networks, and emerging Network Science. The purpose of the course is to introduce the students to network phenomenon and its applications and to provide a solid background in its mathematical foundations within the theory of random graphs.

Course description: Network science is an exciting multidisciplinary research area that studies the network phenomenon and its applications ranging from web search and transportation networks to understanding the structure of social connections, and processes on networks such as infection and information spreading. We will learn why the networks driven by random mechanism end up almost entirely connected, what was behind the success of Google, and why your friends usually have more friends than you do.

After a short introduction in most essential properties of real-life networks, we will devote the major part of the course to the theory of random graphs. Mathematically, it is natural to model a network as a graph of nodes connected by edges. The connections in these networks, such a friendships in social networks, are often a result of random events, therefore, the theory of random graphs is most suitable for their analysis. The methodology leverages on two important classes of stochastic processes: branching processes and martingales. We will cover three essential random graph models: Erdös-Rényi random graph, Configuration model, and Preferential Attachment model.

In the last part of the course we will cover important problems in Network Science that are directly related to the network structures: What are the most important nodes in the network? Do similar nodes usually connect to each other? Which nodes should receive the information first, if we want this information to reach as many people as possible?

The course will finish with hands-on research project and presentations.

Examination. Homework assignments , presentation of own research, and oral exam .

Organization: Most weeks: 3X45 minutes lecture. Some weeks: 2X45 minutes lecture + 45 min to discuss or work on homework exercises. Last week: presentations. The students are encouraged to work on homework and research project in pairs.

Literature: Remco van der Hofstad. Random Graphs and Cmplex Networks. Vol. I.
Available at http://www.win.tue.nl/~rhofstad/NotesRGCN.html and http://www.win.tue.nl/~rhofstad/NotesRGCN.pdf

Prerequisites: The course is aimed at master students in theoretical and applied mathematics and possibly physics and computer science. Solid knowledge of probability theory is necessary. Programming skills are optional. Students who like programming and applied problems can put it to use in a research assignment.