Title: Targeted Influence Maximization in Labeled Social Network with Non Target Constraints
Date/Time: March 28th, 2017 @ 3:30 PM
Place: 223 Atanasoff
Major Professor: Pavankumar Aduri, Samik Basu
Committee Members: Jin Tian
Abstract:
The objective of influence maximization problem is to find a set of highly influential nodes that maximizes the spread of influence in a social network. Such a set of nodes is called seed set. Targeted labeled influence maximization problem is an extension that attempts to find a seed set that maximizes influence among certain labeled nodes. However, in certain application areas such as market and political sciences, it is desirable to limit the spread of influence on certain set of nodes while maximizing the influence spread among different set of nodes. Motivated by this, in this work we formulate and study Constrained Targeted Influence Maximization problem where where anetwork has two types of nodes - targets and non-targets. For a given k and theta, the objective is to find a k size seed set which maximizes the influence over the targets and keeps the influence over the non-targets within the threshold theta. We propose two algorithms based on the greedy approach and establish certain approximation guarantees. We extend this greedy algorithm to a Multi-Greedy algorithm. However, the pure greedy methods are not practically viable due to prohibitively high time overhead. To address that, we develop two-phase framework that will enable us to use multiple heuristic choices as subroutines. We experimentally show that several of these heuristic algorithms produce solutions whose quality is close to the quality of solutions produced by the greedy algorithm. We have developed a prototype framework and evaluated all the algorithms using social networks with different types and sizes.