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:
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.