Modelling and Searching Networks

Winter 2018

Time and location: AIMS Cameroon, February 26 - March 16 (inclusive)

Course outline Lecture, quiz, and assignment schedule

Lecture notes: Lecture 1, Lecture 2, Lecture 3, Lecture 4; Lecture 5; Lecture 6; Lecture 7; Lecture 8;
Lecture 9; Lecture 10; Lecture 11; Lecture 12

Course description:

This is a course on modelling and searching networks. In the first six weeks we will focus on modelling networks, with an emphasis on the emerging theory of complex networks. The study of complex networks analyzes graph-theoretical properties arising in real-world networks arising in technological, social, and biological contexts. Web pages and their links, protein-protein interaction networks, and on-line social networks such as Facebook and LinkedIn are some of the commonly studied examples of such networks. After an introduction to complex networks and their properties, we will focus on the analysis of several models simulating their evolution such as the preferential attachment model, copying model, geometric models, and the iterated local transitivity model.

The second half of the course focuses on graph searching. Graph searching is a hot topic in mathematics and computer science now, as it leads to a wealth of beautiful mathematics, and since it provides mathematical models for many real-world problems such as eliminating a computer virus in a network, computer games, or even counterterrorism. In all searching problems, there is a notion of searchers (or cops) trying to capture some robber (or intruder, or fugitive). A basic optimization question here is: What is the fewest number of searchers required to capture the robber? We focus on the game of Cops and Robbers, and delve into discussion of properties of the cop number of a graph, retracts, and Meyniel's conjecture.

While material will be presented mostly in a traditional lecture format, some lectures will include experiential components: students will work in small groups and present to the class solutions.

Audience: All students interested in Mathematics and its applications.

Prerequisites: An undergraduate degree in Mathematics. Some background in discrete mathematics and probability would helpful, but not required.

Text: None. Three recommended texts are the following:

A. Bonato, A Course on the Web Graph, American Mathematical Society Graduate Studies Series in Mathematics, Providence, Rhode Island, 2008.

A. Bonato, R.J. Nowakowski, The Game of Cops and Robbers on Graphs, American Mathematical Society, Providence, Rhode Island, 2011.

A. Bonato, P. Pralat, Graph Searching Games and the Probabilistic Method, CRC Press, 2017.

Anthony Bonato's web page.