ItemQuality of Barrier Cover with Wireless Sensors(Inderscience Enterprises Ltd, 2019-04-01) Wu, Weili; Zhang, Zhao; Gao, Chuangen; Du, Hai; Wang, Hua; Du, Dingzhu; Wu, Weili; Du, DingzhuA set of wireless sensors is called a barrier cover if they can monitor the boundary of an area so that an intruder cannot enter the area without being found by any sensor. The quality of a barrier cover is the shortest length of path along which an intruder can enter the area from outside. We study four problems, in this paper, related to the quality of the barrier cover and give their computational complexity and algorithmic solutions. ItemMarginal 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. ItemSet Function Optimization(Operations Research Society of China, 2018-12-17) Wu, Weili; Zhang, Z.; Du, Dingzhu; Wu, Weili; Du, DingzhuThis article is an introduction to recent development of optimization theory on set functions, the nonsubmodular optimization, which contains two interesting results, DS (difference of submodular) functions decomposition and sandwich theorem, together with iterated sandwich method and data-dependent approximation. Some potential research problems will be mentioned. © 2018, The Author(s). ItemMaximisation of the Number of β-View Covered Targets in Visual Sensor Networks(Inderscience Enterprises Ltd., 2019-03-24) Guo, L.; Li, D.; Wang, Y.; Zhang, Z.; Tong, Guangmo; Wu, Weili; Du, Dingzhu; 56851698 (Wu, W); 288884264 (Du, D); Tong, Guangmo; Wu, Weili; Du, DingzhuIn some applications using visual sensor networks (VSNs), the facing directions of targets are bounded. Therefore existing full-view coverage (all the facing directions of a target constitutes a disk) is not necessary. We propose a novel model called β-view coverage model through which only necessary facing directions of a target are effectively viewed. This model uses much fewer cameras than those used by full-view coverage model. Based on β-view coverage model, a new problem called β-view covered target maximisation (BVCTM) problem is proposed to maximise the number of β-view covered targets given some fixed and freely rotatable camera sensors. We prove its NP-hardness and transform it into an Integer Linear Programming problem equivalently. Besides, a (1 - e - 1 )-factor approximate algorithm and a camera-utility based greedy algorithm are given for this problem. Finally, we conduct many experiments and investigate the influence of many parameters on these two algorithms. © 2019 Inderscience Enterprises Ltd. ItemViral Marketing of Online Game by DS Decomposition In Social Networks(Elsevier B.V.) Gao, C.; Du, H.; Wu, Weili; Wang, H.; 56851698 (Wu, W); Wu, WeiliIn social networks, the spread of influence has been studied extensively, but most efforts in existing literature are made on the product used by a single person. This paper attempts to address the product which is used by many persons such as the online game. When multiple people participate in one game, interaction between users is accompanied by browsing and clicking on advertisements, and operators can also earn certain advertising revenues. All these revenues are related to information interaction between people involved in one game. We use game profit to represent all of the revenues gained from players involved in one game and model the game profit maximization problem in social networks, which finds a seed set to maximize the game profit between players who are influenced to buy the game. We prove that the problem is NP-hard and the objective function is neither submodular nor supermodular. To solve it, we decompose it into the Difference between two Submodular functions (DS decomposition) and propose four heuristic algorithms. To address the complexity of computing objective function, we design a new sampling method based on reverse reachable set technology. Experiment results on real datasets show that our approaches perform well. ©2019 Elsevier B.V. ItemA 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  and other heuristics in terms of profit maximization, and could better allocate the budget. ©2019 Elsevier B.V.