This page has the course materials from the Introduction to Networks class I taught at Middlebury College for the 2023 Winter Term.

The schedule for Winter Term, which requires meeting 8 hours per week, is much more intensive than a regular, semester- or quarter-length course would be. To account for the demanding in-person requirements of the term, I wanted to make sure that the out-of-class material was much lighter. Thus, the weekly homework assignments were designed to take at most one hour. In future iterations of this course I would instead devote at least an hour of in-class time to work on problem sets, giving the students the opportunity to practice the lecture material without the added burden of extensive homework assignments.

I split up the class to have two, 3-hour lecture days (with a break in the middle), and one 2-hour Computer Lab day. On lecture days we covered material from Easley and Kleinberg’s Networks, Crowds, and Markets (E&K hereafter). For certain subjects, the material from E&K was complemented by other readings, and lecture material was complemented by the activities below.

The PageRank and Information Cascades activities were done at the recommendation of Johan Ugander, who also let me reference all of his course materials from the version of Introduction to Networks that he teaches at Stanford. Thank you for all the support and ideas, Johan!

Course Website and Resources

A sample course website is available at https://github.com/izabelaguiar/intro_networks. The repository contains a sample syllabus, sample homework assignments, sample computer lab assignments, sample final project rubrics and datasets, supplementary notes, and corresponding .tex files. The syllabus contains a sample agenda broken down by day, where each day covers 3 hours of lecture material. Lecture notes were handwritten and directly adapted from E&K, and thus are not included. The Additional Notes folder contains supplemental notes, papers, and slides with supplemental figures.

Course Activities

Introductions: Making a network
Materials: long pieces of yarn, a generated network, name tags, pieces of paper
Learning Goals: introductory definitions of graph theory, ice-breaker activity, common reference point for future examples of networks.

For this activity, I used the course roster to generate a random network. Each student in the class was randomly assigned 0-3 “best friends” in the class. I wrote each student’s name, along with their list of best friends, on individual pieces of paper.

The fist activity in the class was to ask each student to come write their name and pronouns on the board, along with their favourite breakfast food, after which I would give them a name tag and the slip of paper with their best friends on it.

Later in the class, I asked the students to all walk outside. On their way out the door, I gave each student a piece of string for each name they had on their slip of paper. Once we were all outside, we stood in a circle and I told everybody that their pieces of paper had a list of their best friends on it. Each student’s job was to find their best friends and give them one end of one of the strings they were holding.

Once everybody had finished finding their best friends, I said that we had formed a “best friend network” and explained some basic graph theory. All the nodes in this network are people, all the edges are strings, and there is an edge between two nodes if they are best friends. Anybody who had themselves as a best friend had a self loop, and anybody who had no best friends was disconnected. We talked about how some best friendships were unreciprocated, and thus that the network was directed.

In addition to using this network for introducing the terms above, I referenced this network multiple times throughout the term: as we were introducing new topics, learning to visualize networks, or if I needed a common reference as an example, I would use the “best friend network” from our first day.

This activity also allowed for a get-to-know you activity that was relevant for the course material. It was so fun to be introduced to networks and your classmates by feeling yourself a part of a network as well.

Edge Betweenness: Flows on a network
Materials: large pieces of paper with a network pre-drawn on each
Learning Goals: experience flows on a graph and learn how to calculate edge betweenness and betweenness centrality

To prep the class for learning about edge betweenness, I started the class with a quiz asking students to find the edge in a network with the highest embeddedness. The sample graph is uploaded in the Additional Notes folder as betweenness_graph.pdf. In this graph, all of the edges have the same embeddedness. I used the opportunity to talk about how even though they have the same embeddedness, we can see that the edge in the middle plays a different role in the network, and how it was disappointing that embeddedness failed to capture this. This was a great chance to talk about how some metrics are better than others for describing certain attributes of networks.

I created four large pieces of paper with the same simple network on them. After learning about edge betweenness, I split the class into four groups of size 8 and gave each group a copy of the network. Each person in the group had to write their initials on one of the nodes. Then, each student had to “visit” each other node in the network, and had to mark a tally on each edge they used to visit their friends. After everybody visited each other, I explained that each person had visited each other twice, so we had to divide the tallies for each edge in half.

We had extra time during this class, so the students then did the activity again, but this time putting a tally on each node in their path on the network. This introduced and explained betweenness centrality of nodes.

This activity gave students the opportunity to understand different ways to measure the role of edges in a network, and gave them intuition for what a flow on a network is. It also gave them a rigorous way to determine edge betweenness, so that they could understand how it is computed and how the Girvan Newman algorithm works.

PageRank: Random Walks
Materials: marbles, see-through cups or jars, random number generator, hacky sack, arrows for the ground
Learning Goals: experience the process of PageRank, understand a random walk over a graph

In addition to the advice and experience of Johan Ugander, I relied on the description at this webpage. My only edits were that I purchased marbles (instead of making pom-poms) for the “counters”, and I used adhesive arrows to mark the edges and nodes on the ground. I also used the network drawn in Figure 14.6 of E&K and relabeled the nodes 1-8.

I used the notebook PageRank_RandomWalk.ipynb as my random choice generator which also plots limiting distributions of “marbles in jars” if we continued the exercise for much longer.

At the end of class, we re-did the activity with the inclusion of teleportation to represent how Scaled PageRank works. I set the “wait time” on the random generator to be shorter for this exercise to try and make it faster/more exciting.

Information Cascades: Generating a Cascade
Materials: at least twice as many playing cards as there are students, half of a black suit and half of a red suit, prizes like candy or snacks
Learning Goals: experience an information cascade.
The idea for this activity is credited to Aaron Roth. Thank you Prof. Roth!

Prior to the start of class, organize two separate decks of cards. Each deck should have the same amount of cards and that number should be greater than or equal to the number of students in the class. In one deck, about 1/3 of the cards should be black and in the other deck about 1/3 of the cards should be red.

In the deck of cards that has majority red cards, place two black cards on the top, one black card as the fourth card, and the remaining black cards randomly distributed throughout the remainder of the deck. In the deck of cards that has majority black cards, place two red cards on the top, one red as the fourth card, and the remaining red cards randomly distributed throughout the remainder of the deck.

When introducing Information Cascades and Herding (Chapter 16.2 of E&K), describe the simple herding experiment as it’s presented in the textbook: with two urns and three balls in each urn. Describe the logical rules that each of the first four students might follow in the experiment as they are presented in the section.

Then, announce that the class is going to get to experience an information cascade, that is mathematically different from the one you just discussed, but has the benefit of being scalable to the classroom. The instructions for the experiment are follows:

– Place both decks on a table at the front of the classroom.
– Ask a student to flip a coin to determine which deck of cards you use.
– Announce that each student who guesses the correct majority of cards in the selected deck will get a prize.
– Each student then has to come to the front of the class, draw a card from the top of the deck, and write their name on the board along with their guess of what the majority color in the deck is. The student should then discard their card face down on the table.
– Say that you want them to write their guess so you can remember who gets a prize and who doesn’t.
– It’s important that you stress each student should write their guess, not what they actually saw: this mirrors the information cascade because each person just gets their own private information, they can only infer others’ private information through publicly accessible decisions.

If the students follow the logical rules you just discussed, then an incorrect cascade will take place. At the end of the activity, ask everybody who guessed something opposite from what they saw to raise their hands– this will be the majority of the class. Discuss how this represents how cascades can be wrong and admit that you rigged the deck. If you hadn’t rigged the deck, though, there would still be a nonzero probability of this incorrect cascade taking place! (e.g., in a deck of 26 cards with 8 red cards and 18 black cards, assuming that the cards are all uniformly distributed throughout the deck, there is a (8/26)*(7/25) = 8.6% chance of this exact same cascade happening, and a greater probability of a cascade happening at some early point!)