Features

This is a continuation of the interview from KDnuggets News 07:n11 issue.

Gregory Piatetsky-Shapiro, Q5: Can you summarize the key insights of your 2 KDD Best Papers:

• David Kempe, Jon Kleinberg, and Eva Tardos, Maximizing the Spread of Influence through a Social Network, KDD-2003 Best Paper.

• Jure Leskovec, Jon Kleinberg, and Christos Faloutsos, Graphs Over Time: Densification Laws, Shrinking Diameters, and Possible Explanations, KDD-2005 Best Paper

Jon Kleinberg

By way of background, the mechanisms through which information and influence spread across a social network is a topic that has a rich history in the social sciences. For example, a large sub-field of sociology is concerned with empirical studies of the diffusion of innovations, in which one analyzes how new technological and social practices cascade from a set of early adopters, through personal and professional networks, and ultimately to success or failure. (Word-of-mouth effects and "viral marketing" are two other reflections of this phenomenon.) Formal models for these kinds of processes have also been studied by mathematical economists and sociologists.

This topic has increasingly been attracting the interest of computer scientists over the past few years -- in part this is because we are collecting on-line data on the spread of ideas and technologies, and in part it's because the kinds of probabilistic models for studying networks that our community has been developing turn out to fit very well with these types of questions.

In our KDD 2003 paper, David Kempe, Eva Tardos, and I were motivated in particular by the confluence of these social science models with a paper that Pedro Domingos and Matt Richardson had just published at KDD 2001. Pedro and Matt raised the following style of question in their paper: if we have the ability to market a new product to a small number of initial adopters in a social network, whom should we target if the goal is to create as a large a cascade of further adoptions as possible? What David, Eva, and I were able to show in our 2003 paper is that, while the general problem is computationally intractable, one can find strong approximation algorithms for selecting an influential set of initial adopters in some of the most fundamental models. The basic idea was to exploit a subtle kind of "diminishing returns" property (known in discrete optimization as "submodularity") that enables hill-climbing heuristics to produce close-to-optimal solutions. This analysis tool then became a guide for developing richer models that were still computationally manageable; some of these subsequently proved useful to researchers modeling the spread of other kinds of information, including the spread of news stories through the links among weblogs.

Over longer time scales, the network structure itself is subject to dynamic processes and change, and this was the subject of the KDD 2005 paper with Jure Leskovec and Christos Faloutsos. We looked at a number of different kinds of networks (including citation and co-authorship networks from the scientific literature, for which extremely detailed temporal data is available), and we found that they exhibit some recurring but unexpected phenomena as they grow. First of all, they densify -- with the average number of links per node increasing according to a fairly simple pattern -- and second, the average distance between nodes tends to shrink slowly over time. Subsequent work by a number of other groups has identified these two phenomena in a range of further networks over time, suggesting their generality. We also considered a class of models that -- through simulation at least -- exhibit densification and shrinking distances; the models operate by positing that nodes form new links through a sequence of rapid, cascading processes on the network structure. This hints at an interesting potential connection between the 2003 and 2005 papers, suggesting some of the ways in which dynamic network behavior over short time scales might have structural effects over much longer time scales.

What's this?