It has become customary to use “graph” to refer to the underlying data structures at social networks like Facebook. (Computer scientists call the study of graphs “network theory,” but on the web the word “network” is used to refer to the websites themselves).

A graph consists of a set of nodes connected by edges. The original internet graph is the web itself, where webpages are nodes and links are edges. In social graphs, the nodes are people and the edges friendship. Edges are what mathematicians call relations. Two important properties that relations can either have or not have are symmetry (if A ~ B then B ~ A) and transitivity (if A ~ B and B ~ C then A ~ C).

Facebook’s social graph is symmetric (if I am friends with you then you are friends with me) but not transitive (I can be friends with you without being friends with your friend). You could say friendship is probabilistically transitive in the sense that I am more likely to like someone who is a friend’s friend then I am a user chosen at random. This is basis of Facebook’s friend recommendations.

Twitter’s graph is probably best thought of as an interest graph. One of Twitter’s central innovations was to discard symmetry: you can follow someone without them following you. This allowed Twitter to evolve into an extremely useful publishing platform, replacing RSS for many people. The Twitter graph isn’t transitive but one of its most powerful uses is retweeting, which gives the Twitter graph what might be called curated transitivity.

Graphs can be implicitly or explicitly created by users. Facebook and Twitter’s graphs were explicitly created by users (although Twitter’s Suggested User List made much of the graph de facto implicit). Google Buzz attempted to create a social graph implicitly from users’ emailing patterns, which didn’t seem to work very well.

Over the next few years we’ll see the rising importance of other types of graphs. Some examples:

**Taste:** At Hunch we’ve created what we call the taste graph. We created this implicitly from questions answered by users and other data sources. Our thesis is that for many activities – for example deciding what movie to see or blouse to buy – it’s more useful to have the neighbors on your graph be people with similar tastes versus people who are your friends.

**Financial Trust:** Social payment startups like Square and Venmo are creating financial graphs – the nodes are people and institutions and the relations are financial trust. These graphs are useful for preventing fraud, streamlining transactions, and lowering the barrier to accepting non-cash payments.

**Endorsement:** An endorsement graph is one in which people endorse institutions, products, services or other people for a particular skill or activity. LinkedIn created a successful professional graph and a less successful endorsement graph. Facebook seems to be trying to layer an endorsement graph on its social graph with its Like feature. A general endorsement graph could be useful for purchasing decisions and hence highly monetizable.

**Local**: Location-based startups like Foursquare let users create social graphs (which might evolve into better social graphs than what Facebook has since users seem to be more selective friending people in local apps). But probably more interesting are the people and venue graphs created by the check-in patterns. These local graphs could be useful for, among other things, recommendations, coupons, and advertising.

Besides creating graphs, Facebook and Twitter (via Facebook Connect and OAuth) created identity systems that are extremely useful for the creation of 3rd party graphs. I expect we’ll look back on the next few years as the golden age of graph innovation.