Please use this identifier to cite or link to this item: http://idr.nitk.ac.in/jspui/handle/123456789/7739
Title: Discount heuristics and heterogeneous probabilities for optimal influence in social networks
Authors: Sivasailam, K.
Sebastian, V.K.
Jacob, D.M.
Bhattacharya, S.
Issue Date: 2014
Citation: 2014 6th International Conference on Computational Aspects of Social Networks, CASoN 2014, 2014, Vol., , pp.13-18
Abstract: Given a graph 'G', Influence Maximization is the problem of finding a subset of nodes of size 'k' that would maximize the spread of influence in G. This problem has applications in viral marketing studies and spread of information through 'word of mouth'. The problem, as defined by Domingos and Richardson, can be stated as follows: If we can give a product to a small subset of the population such that these people will convince the most number of people to adopt the product in the future, which subset would we choose? Discount heuristics provide great computational speed up in comparison to the traditional greedy algorithm, which runs for hours for networks with tens of thousands of nodes. In this work, we cite a perceived limitation in the degree discount heuristic for Influence maximization, and develop three new discount heuristics, namely Closeness discount, Betweenness discount and PageRank discount for comparison against the degree discount. We show that using degree discount heuristic still leads to the best seed set selection and hence show that the perceived limitation in the degree discount heuristic does not exist. In addition, we also show that PageRank discount beats Degree Discount in terms of Influence Spread when heterogeneous probabilities are used, thus showing that merely considering graph characteristics without taking into account other nodal properties is insufficient. � 2014 IEEE.
URI: http://idr.nitk.ac.in/jspui/handle/123456789/7739
Appears in Collections:2. Conference Papers

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.