CS167: Reading in Algorithms Counting Triangles∗

In these notes we discuss the earlier sections of a paper of Suri and Vassilvitskii, with the great title “Counting Triangles and the Curse of the Last Reducer ” [2]. It is a good example of an applied paper with interesting algorithmic content. Consider an unweighted, undirected graph G = (V,E). G could be anything, but the authors are motivated by graphs derived from social networks. For example, G could be the Facebook graph, where vertices represent people, and the edges represent (bilateral) friendship links. Or G could be derived from a naturally directed social network, such at the Twitter graph (with an arc (u, v) if u follows v), by ignoring the directions of the links. Having an application domain in mind, like social network analysis, can suggest extra properties of the data which guide the decision of what algorithm to use for a computational problem. This point often differentiates “pure ” algorithms papers and “applied ” algorithms papers. In the former, there is usually a premium on “general purpose ” algorithms that work pretty well on all inputs (your undergrad algorithms class likely had this flavor). In the latter, one often wants to tailor the algorithm somewhat to the application domain of interest, to obtain results superior to that of the general-purpose algorithm. We’ll see many more examples of this later in the course. The relevant properties of social networks for today’s discussion are: 1. They are big. Big enough that one needs an algorithm that run in close to linear time. Possibly so big that it doesn’t even fit into the main memory of a single commodity computer, in which case parallel algorithms are also important. 2. They are sparse. Meaning the number of edges m is linear in the number of vertices n. Equivalently, the average degree of a vertex is constant. For example, in the Facebook graph, the average degree is in the low hundreds, while n is over 1 billion. ∗ c©2014, Tim Roughgarden