Structure of Information Pathways in Social Networks

One of the papers I am looking forward to at KDD 2008 is "The Structure of Information Pathways in a Social Communication Network"  by Kossinets, Kleinberg and Watts (PDF). This paper analyzes the communication graph of an email network. The authors present two important and novel concepts to social networks research: Temporal distance and Network backbone. They beautifully incorporate a rather Operating Systems textbook technique of vector clocks into the analysis of social networks. Following is an excerpt from the abstract:

....We formulate a temporal notion of “distance” in the underlying social network by measuring the minimum time required for information to spread from one node to another — a concept that draws on the notion of vector-clocks from the study of distributed computing systems. We find that such temporal measures provide structural insights that are not apparent from analyses of the pure social network topology. In particular, we define the network backbone to be the subgraph consisting of edges on which information has the potential to flow the quickest. We find that the backbone is a sparse graph with a concentration of both highly embedded edges and long-range bridges—a finding that sheds new light on the relationship between tie strength and connectivity in social networks.

The authors use vector clocks to determine the nodes that are up-to date with respect to each other and describe a network backbone as

the subset of edges in the social network that are not bypassed by a faster alternate path.

Thus a network backbone is the set of edges that are critical in ensuring the flow of information within the network and thereby responsible for keeping the nodes 'in sync' with respect to each other. The idea of a backbone is not new and many real world networks like the internet are known to have some such equivalent. Traditionally, in social networks most of the attention so far has been on the "strength of weak links".  In this paper, the authors not only validate this phenomena, but also show that these links are critical in the network backbone structure. This is a paper that offers some deep insights and fundamentally advances our knowledge of how information flows in social networks.

Comments

[eq2 gold]

I found the approach to be novel and useful. As with nearly any analysis technique, caution should be used in selecting the time-period and group size to be studied.