A Novel and Model Independent Approach for Efficient Influence Maximization in Social Networks

摘要

Most of the recent online social media collects a huge volume of data not just about who is linked with whom (aka link data) but also, about who is interacting with whom (aka interaction data). The presence of both variety and volume in these datasets pose new challenges while conducting social network analysis. In particular, we present a general framework to deal with both variety and volume in the data for a key social network analysis task - Influence Maximization. The well known influence maximization problem [15] (or viral marketing through social networks) deals with selecting a few influential initial seeds to maximize the awareness of product(s) over the social network. As it is computationally hard [15], a greedy approximation algorithm is designed to address the influence maximization problem. However, the major drawback of this greedy algorithm is that it runs extremely slow even on network datasets consisting of a few thousand nodes and edges [20,6]. Several efficient heuristics have been proposed in the literature [6] to alleviate this computational difficulty; however these heuristics are designed for specific influence propagation models such as linear threshold model and independent cascade model. This motivates the strong need to design an approach that not only works with any influence propagation model, but also efficiently solves the influence maximization problem. In this paper, we precisely address this problem by proposing a new framework which fuses both link and interaction data to come up with a backbone for a given social network, which can further be used for efficient influence maximization. We then conduct thorough experimentation with several real life social network datasets such as DBLP, Epinions, Digg, and Slashdot and show that the proposed approach is efficient as well as scalable.