Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Random Algorithm for Profit Maximization with Multiple Adoptions in Online Social Networks
98
0
0.0
(
0
)
Added by
Tiantian Chen
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Online social networks have been one of the most effective platforms for marketing and advertising. Through word of mouth effects, information or product adoption could spread from some influential individuals to millions of users in social networks. Given a social network $G$ and a constant $k$, the influence maximization problem seeks for $k$ nodes in $G$ that can influence the largest number of nodes. This problem has found important applications, and a large amount of works have been devoted to identifying the few most influential users. But most of existing works only focus on the diffusion of a single idea or product in social networks. However, in reality, one company may produce multiple kinds of products and one user may also have multiple adoptions. Given multiple kinds of different products with different activation costs and profits, it is crucial for the company to distribute the limited budget among multiple products in order to achieve profit maximization. Profit Maximization with Multiple Adoptions (PM$^{2}$A) problem aims to seek for a seed set within the budget to maximize the overall profit. In this paper, a Randomized Modified Greedy (RMG) algorithm based on the Reverse Influence Sampling (RIS) technique is presented for the PM$^{2}$A problem, which could achieve a $(1-1/e-varepsilon)$-approximate solution with high probability. Compared with the algorithm proposed in [16] that achieves a $frac{1}{2}(1-1/e^{2})$-approximate solution, our algorithm provides a better performance ratio which is also the best performance ratio of the PM$^{2}$A problem. Comprehensive experiments on three real-world social networks are conducted, and the results demonstrate that our RMG algorithm outperforms the algorithm proposed in [16] and other heuristics in terms of profit maximization, and could better allocate the budget.
rate research
Read More
Online social network has been one of the most important platforms for viral marketing. Most of existing researches about diffusion of adoptions of new products on networks are about one diffusion. That is, only one piece of information about the product is spread on the network. However, in fact, one product may have multiple features and the information about different features may spread independently in social network. When a user would like to purchase the product, he would consider all of the features of the product comprehensively not just consider one. Based on this, we propose a novel problem, multi-feature budgeted profit maximization (MBPM) problem, which first considers budgeted profit maximization under multiple features propagation of one product. Given a social network with each node having an activation cost and a profit, MBPM problem seeks for a seed set with expected cost no more than the budget to make the total expected profit as large as possible. We consider MBPM problem under the adaptive setting, where seeds are chosen iteratively and next seed is selected according to current diffusion results. We study adaptive MBPM problem under two models, oracle model and noise model. The oracle model assumes conditional expected marginal profit of any node could be obtained in O(1) time and a (1-1/e) expected approximation policy is proposed. Under the noise model, we estimate conditional expected marginal profit of a node by modifying the EPIC algorithm and propose an efficient policy, which could return a (1-exp({epsilon}-1)) expected approximation ratio. Several experiments are conducted on six realistic datasets to compare our proposed policies with their corresponding non-adaptive algorithms and some heuristic adaptive policies. Experimental results show efficiencies and superiorities of our policies.
Activity maximization is a task of seeking a small subset of users in a given social network that makes the expected total activity benefit maximized. This is a generalization of many real applications. In this paper, we extend activity maximization problem to that under the general marketing strategy $vec{x}$, which is a $d$-dimensional vector from a lattice space and has probability $h_u(vec{x})$ to activate a node $u$ as a seed. Based on that, we propose the continuous activity maximization (CAM) problem, where the domain is continuous and the seed set we select conforms to a certain probability distribution. It is a new topic to study the problem about information diffusion under the lattice constraint, thus, we address the problem systematically here. First, we analyze the hardness of CAM and how to compute the objective function of CAM accurately and effectively. We prove this objective function is monotone, but not DR-submodular and not DR-supermodular. Then, we develop a monotone and DR-submodular lower bound and upper bound of CAM, and apply sampling techniques to design three unbiased estimators for CAM, its lower bound and upper bound. Next, adapted from IMM algorithm and sandwich approximation framework, we obtain a data-dependent approximation ratio. This process can be considered as a general method to solve those maximization problem on lattice but not DR-submodular. Last, we conduct experiments on three real-world datasets to evaluate the correctness and effectiveness of our proposed algorithms.
Social networks have been popular platforms for information propagation. An important use case is viral marketing: given a promotion budget, an advertiser can choose some influential users as the seed set and provide them free or discounted sample products; in this way, the advertiser hopes to increase the popularity of the product in the users friend circles by the world-of-mouth effect, and thus maximizes the number of users that information of the production can reach. There has been a body of literature studying the influence maximization problem. Nevertheless, the existing studies mostly investigate the problem on a one-off basis, assuming fixed known influence probabilities among users, or the knowledge of the exact social network topology. In practice, the social network topology and the influence probabilities are typically unknown to the advertiser, which can be varying over time, i.e., in cases of newly established, strengthened or weakened social ties. In this paper, we focus on a dynamic non-stationary social network and design a randomized algorithm, RSB, based on multi-armed bandit optimization, to maximize influence propagation over time. The algorithm produces a sequence of online decisions and calibrates its explore-exploit strategy utilizing outcomes of previous decisions. It is rigorously proven to achieve an upper-bounded regret in reward and applicable to large-scale social networks. Practical effectiveness of the algorithm is evaluated using both synthetic and real-world datasets, which demonstrates that our algorithm outperforms previous stationary methods under non-stationary conditions.
Random walk-based sampling methods are gaining popularity and importance in characterizing large networks. While powerful, they suffer from the slow mixing problem when the graph is loosely connected, which results in poor estimation accuracy. Random walk with jumps (RWwJ) can address the slow mixing problem but it is inapplicable if the graph does not support uniform vertex sampling (UNI). In this work, we develop methods that can efficiently sample a graph without the necessity of UNI but still enjoy the similar benefits as RWwJ. We observe that many graphs under study, called target graphs, do not exist in isolation. In many situations, a target graph is related to an auxiliary graph and a bipartite graph, and they together form a better connected {em two-layered network structure}. This new viewpoint brings extra benefits to graph sampling: if directly sampling a target graph is difficult, we can sample it indirectly with the assistance of the other two graphs. We propose a series of new graph sampling techniques by exploiting such a two-layered network structure to estimate target graph characteristics. Experiments conducted on both synthetic and real-world networks demonstrate the effectiveness and usefulness of these new techniques.
Profit maximization (PM) is to select a subset of users as seeds for viral marketing in online social networks, which balances between the cost and the profit from influence spread. We extend PM to that under the general marketing strategy, and form continuous profit maximization (CPM-MS) problem, whose domain is on integer lattices. The objective function of our CPM-MS is dr-submodular, but non-monotone. It is a typical case of unconstrained dr-submodular maximization (UDSM) problem, and take it as a starting point, we study UDSM systematically in this paper, which is very different from those existing researcher. First, we introduce the lattice-based double greedy algorithm, which can obtain a constant approximation guarantee. However, there is a strict and unrealistic condition that requiring the objective value is non-negative on the whole domain, or else no theoretical bounds. Thus, we propose a technique, called lattice-based iterative pruning. It can shrink the search space effectively, thereby greatly increasing the possibility of satisfying the non-negative objective function on this smaller domain without losing approximation ratio. Then, to overcome the difficulty to estimate the objective value of CPM-MS, we adopt reverse sampling strategies, and combine it with lattice-based double greedy, including pruning, without losing its performance but reducing its running time. The entire process can be considered as a general framework to solve the UDSM problem, especially for applying to social networks. Finally, we conduct experiments on several real datasets to evaluate the effectiveness and efficiency of our proposed algorithms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
