Degree Type

Thesis

Date of Award

2017

Degree Name

Master of Science

Department

Computer Science

Major

Computer Science

First Advisor

Samik Basu

Second Advisor

Pavan Aduri

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 a network 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.

DOI

https://doi.org/10.31274/etd-180810-5280

Copyright Owner

Naresh Somisetty

Language

en

File Format

application/pdf

File Size

55 pages

Share

COinS