Here is a long list of sources I consulted at various points while doing research for this project. As it might have become clear through reading the previous installments of this series, this was more a talk about the densest subgraph problem than it was about theory being useful in computer science. There are a few reasons for that, which I might explain in more detail at some point in the future1.

In Part 3, we discussed the densest subgraph problem (DSP) and some algorithms for solving it. In this section, we’ll be looking at how we can generalize this problem and those algorithms to solve some other problems. This is the part of the talk where I will introduce some fancy new math I had to learn in order to understand how one might generalize iterative peeling to solve adjacent problems.

In Part 2 of this talk, we gave a crash course to graph theory and showed how we can use it to view some real-world problems as instances of the densest subgraph problem (DSP). But what exactly is the DSP? If you’ve studied graph theory, you may have heard of something called the Maximum Clique Problem. The goal of the max clique problem is to find the largest complete subgraph in a graph. If we consider our vertices to be people, and edges to represent a friendship relationship between two people, in the max clique problem we are trying to find the largest friend group in a community.

Simplicity and necessity: designs should be as simple and small as possible. Minimize functionality, favour minimal installs, and disable unused functionality. Aka: minimize the attack surface. Safe defaults: deny-by-default. Design systems to fail closed (denying access) and favour allowlists over denylists.

When we study computer and internet security (aka cybersecurity, in most circles), we are primarily interested in how people interact with software, computer systems, and networks, and in how they can be misused by various agents. We are typically not concerned with unintentional mistakes or other types of damages (such as a network failure cause by an outage or a natural disaster).