| Summary: | Online social networks (OSNs) have witnessed their prosperous developments in recent
years. Based on the established relations among individuals in OSNs, ideas and opinions
can be spread via a word-of-mouth effect. To exploit this effect, many companies have
taken OSNs as the major advertising channels to promote their products, which has
motivated substantial research on viral marketing. Among them, influence maximization,
seed minimization, and profit maximization have been extensively studied in the past
decades. These three problems are mainly studied in the non-adaptive setting in the
literature, i.e., seed user selection phase does not involve any observations on influence
propagation in reality. In this thesis, we extend profit maximization into a generalized
version as target profit maximization and investigate these three problems in the adaptive
setting, formulated as adaptive influence maximization, adaptive seed minimization, and
adaptive target profit maximization respectively.
Firstly, we study the adaptive influence maximization (IM) problem. Given a social
network G and an integer k, the influence maximization problem asks for a seed set S
of k nodes from G to maximize the expected number of nodes activated via an influence
propagation. In the adaptive setting, the k seed nodes are selected in batches of equal
size b, such that the i-th batch is identified after the actual influence results of the former
i-1 batches are observed. We propose the first practical algorithm for the adaptive IM
problem that could provide the worst-case approximation guarantee of 1-e^α(ε-1) with
high probability, where ε∊(0, 1) is a user-specified parameter and α= 1-(1-1/b)^b is set
by the batch size b. Our approach is based on a novel general framework AdaptGreedy
which could be instantiated by any existing non-adaptive IM algorithms with expected
approximation guarantee. In this regard, we design a novel non-adaptive IM algorithm
called EPIC which not only provides strong expected approximation guarantee, but also
presents superior performance compared with the existing IM algorithms. Meanwhile, we
clarify some existing misunderstandings in recent work and shed light on further study
of the adaptive IM problem.
Subsequently, we consider the adaptive seed minimization (SM) problem. As a dual
problem of influence maximization, the seed minimization problem asks for the minimum
number of seed nodes to influence a required number η of users in a given social network
G. In the adaptive setting, the seed nodes are selected in several batches, such that
the choice of current batch may exploit information about the actual influence of the
previous batches. We devise a novel algorithm, ASTI, which addresses the adaptive
seed minimization problem in O (η(m+n)/ε^2 ln n) expected time and offers an approximation
guarantee of (ln η+1)^2/((1-(1-1/b)^b)(1-1/e)(1-ε)) in expectation, where η is the targeted number of influenced nodes, b is size of each seed node batch, and ε∊(0, 1) is a user-specified
parameter. To the best of our knowledge, ASTI is the first algorithm that provides such
an approximation guarantee without incurring prohibitive computation overhead.
Eventually, we explore the adaptive target profit maximization (TPM) problem.
Given a social network G, the profit maximization (PM) problem asks for a set of seed
nodes to maximize the profit, i.e., revenue of influence spread less the cost of seed selection.
The TPM problem, which generalizes the PM problem, aims to select a subset
of seed nodes from a given target user set T to maximize the profit. In the adaptive
setting, the seed users are selected through multiple batches, such that the selection of
current batch exploits the knowledge of actual influence in the previous batches. To
acquire an overall understanding, we study adaptive TPM under the oracle model and
the noise model, to which we propose ADG and AddATP algorithms with strong theoretical
guarantees respectively. In addition, we propose the idea of hybrid error to better
handle the sampling errors under the noise model and design a novel algorithm HATP
that boosts the efficiency of AddATP significantly.
|
|---|