Structure of social network graphs

Many researchers study social network graphs to try and understand how we as humans interact, especially in information systems and online. However, it has always been difficult to validate results because privacy concerns usually limit access to real datasets. Many results have been validated using artificial graphs, generated in a way that mimics the large-scale properties of real graphs. For example, the artificial graphs look like real graphs in the sense that they obey power laws, have the right kind of degree sequences and so on.

Often, preferential attachment is used as the construction technique. In this algorithm, an edge is attached to a vertex with a probability in proportion to the number of edges already attached to it.  This seems intuitively plausible in many human settings: a person with many friends tends to meet more people and so has a greater chance of making more friends.

There have been hints for a while that these artificial graphs were not quite like real graphs, even though they match according to many large-scale measures. For example, Newman showed that, in human graphs, high-degree nodes tended to be connected to high-degree nodes, while in technical networks this was not the case — even though both looked the same from a power-law perspective.

But now Faloutsos’s group at CMU have shown convincingly that there are substantial differences between artificial and real graphs. They looked at what happens to the diameter of a graph as edges are uniformly randomly deleted. As edges are deleted, the diameter grows slowly but, at some point, there’s a sharp increase. They call this the shatter point.

The important thing is that the shatter point of artificial graphs is substantially higher (i.e. the fraction of edges remaining when this happens) than for real graphs. In other words, graphs generated by humans rather than simply by preferential attachment are somehow tougher. Although humans must be choosing edges to connect based on local criteria, they must somehow do this in a way that makes the global srtucture of the graph more robust. It’s not at all clear (to me at least) how this happens, but it seems plausible.

One of the implications of this difference is that it calls into question much of the conventional wisdom about social networks, whenever this has been derived from, or validated by, artificially generated datasets. Which is quite a lot of the time.


0 Responses to “Structure of social network graphs”

  1. Leave a Comment

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: