Browsing by Author "Yuan, Jing"
Now showing 1 - 4 of 4
- Results Per Page
- Sort Options
Item A Random Algorithm for Profit Maximization in Online Social Networks(Elsevier B.V.) Chen, T.; Liu, B.; Liu, W.; Fang, Q.; Yuan, Jing; Wu, Weili; 56851698 (Wu, W); Yuan, Jing; Wu, WeiliGiven a social network G and a positive integer 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. For 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. The Profit Maximization with Multiple Adoptions (PM²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²A problem, which could achieve a (1-1/e-ε)-approximate solution with high probability and is also the best performance ratio of the PM²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. ©2019 Elsevier B.V.Item Breach-Free Sleep-Wakeup Scheduling for Barrier Coverage with Heterogeneous Wireless Sensors(Institute of Electrical and Electronics Engineers Inc.) Zhang, Z.; Wu, Weili; Yuan, Jing; Du, Dingzhu; 288884264 (Du, D); Wu, Weili; Yuan, Jing; Du, DingzhuBarrier Coverage plays a vital role in wireless sensor networks. Research on barrier coverage has mainly focused on the lifetime maximization and the critical conditions to achieve k-Barrier Coverage under various sensing models. When sensors are randomly deployed along the boundary of an area of interest, they may form several disjoint barrier covers. To maximize the lifetime of barrier coverage, those barrier covers need to be scheduled to avoid a security problem, call breach. In a heterogeneous wireless sensor network, given a set of barrier-covers each with a lifetime, we study the problem of finding a lifetime-maximizing subset with a breach-free sleep-wakeup scheduling. We first prove that it can be judged in polynomial time whether a given sleep-wakeup schedule is breach-free or not, but given a set of barrier-covers, it is NP-Complete to determine whether there exists a breach-free schedule. Then, we show that the problem of finding a lifetime-maximizing breach-free schedule is equivalent to the maximum node weighted path problem in a directed graph, and design a parameterized algorithm. Experimental results show that our algorithm significantly outperforms the heuristics proposed in the literature.Item Marginal Gains to Maximize Content Spread in Social Networks(Institute of Electrical and Electronics Engineers Inc., 2019-05-06) Yang, W.; Ma, J.; Li, Y.; Yan, R.; Yuan, Jing; Wu, Weili; Li, D.; 56851698 (Wu, W); Yuan, Jing; Wu, WeiliThe growing importance of social network for sharing and spreading various contents is leading to the changes in the way of information diffusion. To what extent can social content be diffused highly depends on the size of seed nodes and connectivity of the network. If the seed set is predetermined, then the best way to maximize the content spread is to add connectivities among the users. The existing work shows the content spread maximization problem to be NP-hard. One of the difficulties of designing an effective and efficient algorithm for the content spread maximization problem lies in that the objective function we aim to maximize lacks submodularity. In our work, we formulate the maximize content spread problem from an incremental marginal gain perspective. Although the objective function we derive is not submodular, both submodular lower and upper bounds are constructed and proved. Therefore, we apply the sandwich framework and devise a marginal increment-based algorithm (MIS) that guarantees a data-dependent factor. Furthermore, a novel scalable content spread maximization algorithm influence ranking and fast adjustment (IRFA), which is based on the influence ranking of a single node and fast adjustment with each boosting step in the network, is proposed. Through extensive experiments, we demonstrate that both MIS and IRFA algorithms are effective and outperform other edge selection strategies.Item Near Optimal Social Promotion in Online Social Networks(2018-12) Yuan, Jing; 0000-0001-6407-834X (YUAN, J); Wu, WeiliDue to dramatic growth of user population in the past decade, online social networks have become attractive channels for companies to launch marketing campaigns. We study a couple of closely related problems in online social networks. We first study the problem of active friending, which can be considered as a service provided by the social platforms to stimulate user engagement. The idea is that a source user can name a target user and the social platform offers a friending strategy to maximize the probability of the target accepting the invitation from the source. We prove that the problem is NP-hard and propose a discrete semi-differential based algorithm with guaranteed approximation ratio. As for the profit maximization problem, we consider the scenario when a profit is generated from group activities, captured by a hypergraph where hyperedges are introduced to represent the interactions among multiple users. We prove that the problem is NP-hard and develop an approximation algorithm along with an exchange-based technique to maximize the profit generated from group activities. In social advertising, the goal of online social platforms is to optimize the ad allocation with multiple advertisers. We access the tradeoff between maximizing the revenue earned from each advertiser and reducing free-riding to ensure the truthfulness of advertisers. We prove that both budgeted and unconstrained ad allocation problems are NP-hard and then develop constant factor approximation algorithms for both problems. We also study the adaptive version of the seed selection problem and the discount allocation problem. The goal is to find a limited set of highly influential seed users to assign proper discounts, such that the number of users who finally adopt the product is maximized. We propose a series of adaptive policies with bounded approximation ratio for both problems.