Edge typing to make transitivity useful

There have been several studies over the past year that have shown that we are influenced by properties of people to whom we are not directly connected. There seems to be a pattern: if I have property X, then my immediate friends tend to be more Xy than would otherwise be expected (not surprising), but their friends whom I don’t know are also affected by my Xiness, and sometimes even their friends (which does seem surprising).

All of which is to say that transitivity in social networks is more interesting and important than it might seem intuitively. Social network sites have tried, in various ways, to exploit transitivity, usually in some form of speading: recommending things that I like or am doing to my immediate neighbours, and suggesting that people at distance 2 might usefully become friends at distance 1.

These attempts have, I think it is fair to say, been less than successful. A big part of the reason is the failure to model links (edges) as being of different kinds, as well as different intensities. Such sites do have access to intensity data, so they can estimate a weight for edges linking people (although probably this also is a bit shaky since many forms of contact are automated, so it’s not clear how much bonding each actually represents). In particular, connections that derive from work and those that derive from leisure seem like they should be treated differently, and some of the embarrasing faux pas have resulted from e.g. trying to get people to friend their boss’s boss. But, in general, people live in many different communities, and transitivity doesn’t work well across communities. It seems hard to be able to tell when transitivity is and is not a good thing without distinguishing different kinds of connections, and so different kinds of edges. For example, a personal relationship could be represented by a red edge, a work relationship by a blue edge, and a family relationship by a green edge. Now transitivity along paths of the same colour becomes a much more powerful, and less treacherous, idea.

From the perspective of data analysis, there are two challenges: how to acquire the information about what kind of edge a relationship is, and how to modify analysis techniques to take edges of different kinds into account.

The colour of an edge is not easy to induce from observing the activity on that edge. For example, suppose that you have access to someone’s email and you want to work out who are their friends, and who are professional contacts. The structure of email addresses doesn’t help much because a friend’s work email might be used, and because email addresses tend to be surrogates anyway. Time of day doesn’t help much because many people send personal email at work, and many send work emails out of working hours. The content of emails might help, but many organisations have extensive in-house non-work emails (for example, Enron had many emails about fantasy football that circulated only within the company). Social network sites have an advantage because they can ask users to explain which category of “friending” a particular contact is (this could be a big win — a category of “annoying person I don’t want to offend by removing the contact” could easily become the most popular edge type). In an intelligence or law enforcement setting, where the existence of the contact is acquired by observation or interception, the problem of categorising the contact is just as difficult.

Even if the edges can be labelled to indicate their type, using this information to improve the analysis of the resulting graph is difficult, and largely unstudied (AFAIK). Most approaches use some kind of iterative approach (see here for a recent example and some references). Integrating edge types into spectral approaches would be particularly useful — volunteers anyone?

Advertisements

0 Responses to “Edge typing to make transitivity useful”



  1. Leave a Comment

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: