Incremental mining of top-k maximal influential paths in network data

Abstract

Information diffusion refers to the spread of abstract ideas and concepts, technical information, and actual practices within a social system, where the spread denotes flow or movement from a source to an adopter, typically via communication and influence. Discovering influence relations among users has important applications in viral marketing, personalized recommendations and feed ranking in social networks. Existing works on information diffusion analysis have focused on discovering "influential users" and "who influences whom" relationships using data obtained from social networks. However, they do not consider the continuity of influence among users. In this paper, we develop a method for inferring top-k maximal influential paths which can capture the continuity of influence. We define a generative influence propagation model based on the Independent Cascade Model and Linear Threshold Model, which mathematically models the spread of certain information through a network. We formalize the top-k maximal influential path inference problem and develop an efficient algorithm, called TIP, to infer the top-k maximal influential paths. TIP makes use of the properties of top-k maximal influential paths to dynamically increase the support and prune the projected databases. As databases evolve over time, we also develop an incremental mining algorithm IncTIP to maintain top-k maximal influential paths. We evaluate the proposed algorithms on both synthetic and real-world datasets. The experimental results demonstrate the effectiveness and efficiency of both TIP and IncTIP. © 2013 Springer-Verlag Berlin Heidelberg.