CS167: Reading in Algorithms Triangle-Dense Graphs∗

Triangle-Dense Graphs ” [1]. The motivation of the paper is to develop a theory of algorithms for social networks, like the graphs derived from Facebook or Twitter data mentioned in the first lecture. That is, the goal is to develop graph algorithms that work well on social networks, if not on worst-case graphs. What’s special about social networks? In the first lecture we mentioned three common properties: they are generally big, sparse, and have a skewed degree distribution. This paper discusses a different property: large triangle density. Intuitively, this is similar to having a large average clustering coefficient. Formally, the triangle density of a graph is the fraction of “filled in ” 2-hop paths (aka “wedges”), which can also be written as 3 · number of triangles number of wedges Note the factor of “3 ” comes in because each triangle of a graph spawns three distinct wedges. Every graph has a triangle density between 0 and 1. An acyclic graph has triangle density 0; so does a cycle of length at least 4. A triangle has a triangle density of 1, as does a clique, as does a disjoint union of cliques. A little thought shows the converse is also true: a graph has triangle density 1 only if it is the disjoint union of cliques. The paper studies graphs with “large ” triangle density, with the motivation that large social networks tend to have this property (among others). For example, let’s compare the Facebook graph with a random graph. By a “random graph, ” we mean the following (called an “Erdős-Rényi graph”): for parameters n and p ∈ [0, 1], form a graph with n vertices by including each of th