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?

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 ${a}$ and ${b}$ and ${c}$ form a line:

$\displaystyle a \leftrightarrow b \leftrightarrow c,$

then there also is an edge from ${a}$ to ${c}$. The intuition, I believe, is that if ${b}$ has two “friends” ${a}$ and ${c}$ 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.

## Un-Social Applications

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 ${G}$ is an ${n}$-vertex graph with ${o(n^3)}$ triangles, then there is a set of ${o(n^2)}$ 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.

## Open Problems

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?

1. January 22, 2014 10:32 am

I have been interested for a long time now in using graphs to do logic. For that you need more than positive links — negative relations are more generative than positive relations. This is analogous to social networks where people can “unlike” other people, or website networks where the information at one node can contradict the information at another node. In my pursuits it turns out that particular species of graph-theoretic “cacti” are much more useful than the usual trees and unsigned graphs.

• January 22, 2014 3:00 pm

For what it’s worth, here is my somewhat dry exposition of “painted cacti” and their application to propositional calculus.

Painted cacti are rooted cacti with any number of symbols (“paints”) from a finite alphabet attached to each node. In the intended interpretation these symbols are boolean variables.

Triangles are interesting because they arise in logical case expressions. In one of the more usual interpretations of the cactus graphs, a rooted triangular lobe says that the values of the two non-root nodes are logically inequivalent.

2. January 22, 2014 6:35 pm

It might also be interesting to ask for the triangle removal theorem from a computational standpoint how quickly one can identify an efficient set to remove. This seems like it could be a tough problem.

3. January 23, 2014 6:33 pm

immediately wonder if there is some generalization of that interesting “triangle removal” thm by Imre Ruzsa and Endre Szemerédi to cliques. a triangle of course is a 3-clique.
re social network analysis, it also has great connections to datamining. and lets not forget that google pagerank, called by some as one of the most important algorithms of all, is basically a sophisticated graph analysis algorithm.

4. February 10, 2014 5:29 am

On a related note, I wrote a quick post defending Rutger’s on its decision to offer a class on Beyonce. It is precisely because such research used to informed effort to analyze networks through the use of directed acyclic graphs (DAGs) will ultimately make the world a better place in my mind.

http://thefurloff.com/2014/02/10/why-a-class-on-beyonce-is-a-good-idea/