KDD'2012 Tutorial: Information and Influence Spread in Social Networks

Carlos Castillo (Qatar Computing Research Institute)

Wei Chen (Microsoft Research Asia)

Laks V. S. Lakshmanan (University of British Columbia)

August 12, 2012

Abstract

There is tremendous interest in information propagation in social networks, fueled by applications such as viral marketing, epidemiology, analysis of the spread of innovations, among many others. At the core of these applications there is a phenomenon called influence propagation, where actions performed by people propagate through a social network. In the general setting we have (i) a network representing social ties; (ii) weights representing strengths or probabilities of influence among people; and (iii) a database of traces of past propagations of actions, sometimes described as information cascades.

In this tutorial, we will overview complementary currents that have led to excitement around this area: advances in mathematical sociology, technology and availability of large real data sets, advances in tools (both mathematical and software) for purposes of analysis, and advances in algorithms for analyzing information propagation. After surveying these developments, the bulk of the tutorial will focus on algorithms. No special prerequisite knowledge is needed to attend this tutorial, designed for any data mining researcher or practitioner interested on these topics.

Tutorial Slides:

Part I: —Motivation, Applications and Key Concepts [slides] [slides with notes]

Part II: Data and Tools [slides] [slides with notes]

Part III: —Influence Maximization [slides] [slides with notes]

Part IV: —Other Issues [slides] [slides with notes]

Part V: —Challenges [slides] [slides with notes]