Applications of social networks to arbitrary graphs
Tim Roughgarden is a faculty member at Stanford, with interests in modern algorithms—my term. So his research is all about auctions, game theory, microeconomics, and social networks. You can see his visible hand here, from time to time.
Today I want to talk about a beautiful result on social networks due to Tim and his co-authors.
I just spent some time talking with Tim and Jon Kleinberg about social networks. We are all on the advisory board for The Simons Theory Institute, which just met last Friday in Berkeley. Well not exactly. I had the honor of being on the board from the beginning and I am now an ex-member, removed as part of the good practice of all boards: removed to allow new members to join. It was fun to be on the board, to see the Institute start from scratch, and now to see terrific programs in progress.
Social Talk On Social Networks
A side benefit of being on advisory boards is that sometimes during a meeting there is time to chat with other members. This meeting Tim and Jon and I had a chance to talk during a “break” about some of their recent work on social networks.
Let me be anti-social about social networks—just to make a point—I will take a position that some may have about this area. We can think of a social network as a class of undirected graphs—a prime example is the “friend” graph from Facebook. So what is new? We have been using graphs in computer theory forever, certainly there are plenty of graph results in theory. We have studied algorithms for various types of graphs: graphs in general, planar graphs, regular graphs, dense graphs, sparse graphs, graphs without certain minors, and random graphs. We have studied other properties of graphs beside algorithms: one important class of results is the ability to locally-test certain graph properties.
So—to repeat—what is new? Plenty. The rise of social networks has created a whole new genre of important problems. Some problems have to do with generative models. That is random models that can generate the type of graphs that actually arise as social networks.
Tim and Jon explained some of their new work, which is not generative at all. And I find their work quite compelling. It studies graphs that can be generated any way at all, random or not. Their idea is to try to isolate a property that social networks have, and then show that this property implies some useful structural theorems.
A toy example is: if a graph has degree less than some constant, then it has no large clique. Of course. The important thing is that their results are not probabilistic in nature; they work for any graphs, no matter how they have been generated, and say that property X always implies structure Y. And they are non-trivial.
This worst-case flavor is why I find these results to be so exciting. One can imagine using them to solve problems in computing that have nothing to do with social networks. Since graphs are so fundamental to our understanding of computation, any new structural theorems are welcome.
I think this type of result shows the importance of the studying new types of graphs that appear to arise from social networks. In the hands of imaginative researchers like Tim and Jon, they suggest new structural questions that “pure” graph theorists might never have looked at. This is really exciting to me.
Let’s look in more detail in what Tim did, and we will discuss Jon’s theorems another time.
New Graph Theorems
Tim with Rishi Gupta and Seshadhri Comandur have a paper titled Decompositions of Triangle-Dense Graphs. Quoting them, they ask the following natural question:
Is there a combinatorial assumption weak enough to hold in every “reasonable” model of social networks, yet strong enough to permit useful structural and algorithmic results?
The short answer is: Yes.
In order to understand their theorem we need two insights: one is the property X that social graphs often have, and the other is Y a structural property.
The property X is really simple. In social networks it very often happens that if and and form a line:
then there also is an edge from to . The intuition, I believe, is that if has two “friends” and we expect that often they also will be friends too. This means that social networks will often have lots of triangles. Again quoting them:
Social networks are generally sparse and yet have remarkably large triangle density; the Facebook graph, for instance, has triangle density 0.16. High triangle density is perhaps the least controversial signature of social networks.
The structural property Y is a bit more technical and is called a tightly-knit family—see their paper for a precise definition. Roughly Y means that the graph is a disjoint union of relatively large subgraphs of radius 2. Such graphs are approximations to cliques.
This yields their main theorem:
Theorem: (Main Decomposition Theorem). For every triangle-dense graph G, there exists a tightly-knit family that contains a constant fraction of the triangles of G.
The above theorem shows that social networks that follow the triangle property have a structural theorem. I wondered to Tim and Jon whether they had thought about trying to use this theorem to prove theorems about graphs in general. In particular, the fact that the theorem is all about triangles made me ask whether Tim had considered using his technology to try an prove the famous triangle-removal theorem. This theorem states:
Theorem: If is an -vertex graph with triangles, then there is a set of edges such that the removal of those edges eliminates all the triangles.
This is due to Imre Ruzsa and Endre Szemerédi.
Tim and Jon said they liked the idea, had not thought about it, and perhaps it was possible.
Do you like the idea of studying graph properties that arise from social networks. Can they be used to solve other problems? What about the triangle-removal theorem?