查看文章

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 …