Search

In crowdsourcing systems, a challenge arises in efficiently recruiting workers with unknown execution speed to complete tasks with precedence constraints within the shortest possible time. Recent research either only studies recruiting unknown workers or focuses on assigning tasks with precedence constraints, but few works consider both these factors. This paper aims to address this challenge considering all these factors by proposing a digital twin-assisted Combinatorial Multi-arm bandit based multi-round work Recruitment and task Scheduling (CMRS) scheme. Firstly, with the help of digital twin technology, we build digital twin models for crowdsourcing tasks and workers in digital twin layer of platform. And we formulate a Multi-round Workers recruitment and Task scheduling with Precedence constraints (MWTP) problem with the object of minimizing task completion time (makespan) to model the above challenging issue in crowdsourcing computing. The MWTP problem can be divided into two sub-problems, the task scheduling sub-problem and the worker recruitment sub-problem. Secondly, in the CMRS scheme, the differential evolution based task scheduling (DETS) algorithm and CUCB-based worker recruitment (CWR) method are proposed to solve them, respectively. Specifically, for the task scheduling sub-problem, we first propose a priority-driven based task scheduling (PDTS) approximation algorithm to produce a primary solution with an explicit approximation ratio. Then a DETS algorithm is proposed to use the solution of PDTS for initialization and generate a better solution that further improves the performance. For the unknown workers recruitment sub-problem, we use the Combinatorial Multi-Arm Bandit framework to model this, and propose CWR method to learn the computational capabilities of workers while maintaining good performance during multiple rounds of worker recruitment by adding a tuning term to balanced exploration and exploitation. Finally, verified by extensive comparison experiments, the CMRS scheme can achieve the best performance of makespan compared with the baselines in most cases. [ABSTRACT FROM AUTHOR]

The influence maximization problem asks to find a small number of early adopters of a product in a social network, such that the expected number of total adoptions is maximized over the network. The problem has been well-studied, but most of the studies focus on the case of a single product or purely competitive products. This paper proposes a new influence diffusion model for multiple complementary products, namely, the comparative linear threshold (Com-LT) model. Under the Com-LT model, we model the complementary relation by reducing the thresholds of nodes. With this model, we study two problems: SelfInfMax and CompInfMax. We prove that these two problems are both NP-Hard under the Com-LT model. For both the SelfInfMax and the CompInfMax problem, we theoretically analyze the monotonicity and submodularity, and accordingly leverage lower bound optimization to devise non-trivial effective approximation algorithms. We conduct experiments over 4 real-world datasets. The experimental results demonstrate the correctness and efficiency of the proposed algorithms. • We study the complementary version of the influence maximization problem. • We propose Com-LT model to describe the influence spread of non- competitive products. • We studied the SelfInfMax and the CompInfMax problem and show their hardness. • We propose approximation algorithms with high quality feasible solutions. • We conduct experiments on real networks and show the effectiveness of our algorithms. [ABSTRACT FROM AUTHOR]

Highlights • An approaximation algorithm for the case with bounded number of divisible resources. • A 6 + 2 10 + ε -approximation algorithm for the case where u ij ∈ {0, u j }. • A polynomial-time approximation algorithm for the general case. Abstract Resource allocation is a classic problem in economics and computer science. The application scenarios of resource allocation include inheritance settlements, computation resource sharing and so on. This paper focuses on the max-min fair allocation of resources in which m resources need to be allocated to n agents while maximizing the minimum utility of any agent. When money transfer is not allowed, the existing work on max-min fair allocation only focuses on the fair allocation of indivisible resources. However, in real applications, the allocated resource set may simultaneously include indivisible resources and divisible resources, e.g., the allocated resources in distributed systems include the indivisible CPU resources, the divisible storage resource and the divisible bandwidth resource. The combination of indivisible resources and divisible resources creates a new challenge and requires us to consider how to coordinate the allocations of indivisible resources and divisible resources in the allocation process. Therefore, we investigate the combined max-min fair allocation problem in which the allocated resource set consists of both indivisible resources and divisible resources. We present a 6+2 10 + ε (ε > 0)-factor approximation algorithm for the restricted case where u ij ∈ {0, u j } (i.e., the utility of a resource j is either 0 or u j for each agent i) and the agent valuations for the divisible resources are in proximity to each other. Moreover, we propose an approximation algorithm for the general case based on the augmented flow idea. Experiments conducted on real data show that the average performance of the proposed approximation algorithm is better than 80% of the performance of the optimal algorithm, which requires exponential time in the worst case unless P = NP. To the best of our knowledge, the proposed algorithm is the first approximation algorithm for the general case of the combined max-min fair allocation problem when money transfer is not allowed. The proposed algorithm can be adopted to design more efficient expert systems that apply to resource allocation in distributed systems, inheritance settlements and so on. The adoption of the proposed algorithm contributes to promoting the broader application of expert systems in the fair allocation of computation resources and social resources. The experimental results show that the proposed algorithm can perform well in real applications. [ABSTRACT FROM AUTHOR]

Highlights • Most prediction problems of data networks are non-linear. • Shallow neural networks are fast. • Kernel approximation is a non-linear data transformation. • Shallow neural networks with kernel approximation are non-linear and fast models. • Proposed model is faster with prediction results comparable to deep models. Abstract Intrusion detection and network traffic classification are two of the main research applications of machine learning to highly demanding data networks e.g. IoT/sensors networks. These applications present new prediction challenges and strict requirements to the models applied for prediction. The models must be fast, accurate, flexible and capable of managing large datasets. They must be fast at the training, but mainly at the prediction phase, since inevitable environment changes require constant periodic training, and real-time prediction is mandatory. The models need to be accurate due to the consequences of prediction errors. They need also to be flexible and able to detect complex behaviors, usually encountered in non-linear models and, finally, training and prediction datasets are usually large due to traffic volumes. These requirements present conflicting solutions, between fast and simple shallow linear models and the slower and richer non-linear and deep learning models. Therefore, the perfect solution would be a mixture of both worlds. In this paper, we present such a solution made of a shallow neural network with linear activations plus a feature transformation based on kernel approximation algorithms which provide the necessary richness and non-linear behavior to the whole model. We have studied several kernel approximation algorithms: Nystrom, Random Fourier Features and Fastfood transformation and have applied them to three datasets related to intrusion detection and network traffic classification. This work presents the first application of a shallow linear model plus a kernel approximation to prediction problems with highly demanding network requirements. We show that the prediction performance obtained by these algorithms is positioned in the same range as the best non-linear classifiers, with a significant reduction in computational times, making them appropriate for new highly demanding networks. [ABSTRACT FROM AUTHOR]

Highlights • The algorithm is on average 20% more efficient (faster). • The algorithm has 511% (158%) (mean, median) faster convergence. • Probability bound is calculated. • The algorithm can potentially have many applications. Abstract It is well known that Minimum Feedback Arc Set is in a general case NP-complete. There are different kinds of exact, heuristic and approximation algorithms for solving this problem, but currently there is only one published Monte Carlo algorithm which solves Minimum Feedback Arc Set in polynomial time with arbitrary probability. To further advance the state of the art we have devised new and improved ant inspired Monte Carlo algorithm which on average has 20% faster empirical running time. Due to a learning mechanism the new algorithm also achieved 511% faster convergence in terms of median and 158% improvement in terms of arithmetic mean. This has been done while at the same time maintaining the ability of the algorithm to find optimal solution with arbitrary probability. In addition, the new and improved ant inspired algorithm has substantially improved convergence consistency. A tighter probability bound has also been calculated for the Monte Carlo algorithm. The aforementioned contributions have their significance in a design and implementation of expert and intelligent system. Considering a wide presence of MFAS in a variety of areas the obtained results are significant in other applications as well. [ABSTRACT FROM AUTHOR]

Highlights • The skyline query is very useful in data analysis, but is has the largesize problem. • Approximate skylining finds an informative and concise set of skylinefor usability. • A linear-time algorithm is presented for approximate skylining in intwo dimensions. • Greedy solutions with indexing techniques are presented for higher dimensions. Abstract Querying databases to search for "best" objects matching users' preferences is a fundamental problem of intelligent systems and applications. The skyline query is an important tool for solving such a best-matching problem from the concept of multi-criteria optimization. However, it has the size problem as the size of the results of a skyline query grows superlinearly with the number of criteria. Here, we propose to find both the informative and concise set of skyline, a refined skyline set without similar objects. The informativeness requires the reduced set to cover the skyline, i.e., for every skyline point in the original dataset, there exists a close point in the reduced set, which help users to understand the skyline in more detail and make a better decision. The conciseness requires the size of the reduced set that can cover the skyline is as smaller as possible, which help users to make a quick decision. Finding both the informative and concise set of skyline will boost the usability of intelligent systems. More specifically, we propose two new skyline queries to find the informative and concise set of skyline: minimum skyline query, and extended minimum skyline query. The main idea is to return the minimum number of approximation objects, in which there is an object within a predefined distance threshold for each skyline object. The difference of the two query types is that the former one selects approximation objects only from skyline set, while the latter one selects from the whole dataset. We present an exact solution which computes minimum skyline in linear time for a 2 d -space. As both minimum skyline and extended minimum skyline problems are NP-hard for dimensionality at least three, we present greedy solutions that obtain a 1 + ln R approximation of the optimums. A comprehensive performance evaluation demonstrates that the size of skyline set can be effectively reduced by using the proposed (extended) minimum skyline queries and our proposed algorithms have promising results. [ABSTRACT FROM AUTHOR]

Highlights • A differential-relation-based rough set model on relational databases is proposed. • Using this model, the measures for differential dependencies (DDs) are expressed. • An efficient method to compute the approximate error measure of g 3 for DDs is developed. • The rough sets on the differential decision systems (DDSs) are introduced. • A bridge between DDs in databases and attribute dependencies in DDSs is formed. Abstract Data dependencies in databases and attribute dependencies in decision systems are important when addressing problems concerning data quality and attribute reduction, in which measures play a significant role in approximating these dependencies to achieve better adaptation to uncertain data. This paper proposes a differential-relation-based rough set model from the perspective of relational databases to express the dependency degree, error measures, confidence, information granulation and differential class distance for differential dependencies (DDs) and the relationships among them in a unified framework. Moreover, the error measure g 3 has been widely studied and applied for data dependencies. However, the computation of g 3 for DDs is NP-complete. Therefore, based on the proposed rough set, we introduce a new method that can compute the approximate error measure g 3 ˜ of g 3 in polynomial time. This study demonstrates that our approach can provide a substantially better approximation, that is, an approximation closer to the optimal solution g 3 , compared to the existing greedy method. We also introduce the differential-relation-based rough set from the perspective of information systems and make a connection to the rough sets induced by non-equivalence relations. The two views of the differential-relation-based rough sets form an essential bridge between the DDs in databases and attribute dependencies in differential decision systems (DDSs) that allows sharing measures for approximating the dependencies. These results are meaningful for approximate computations, the development of algorithms for attribute reduction in decision systems and the discovery of approximate differential dependencies (ADDs) in databases. [ABSTRACT FROM AUTHOR]

Created by Zadeh in 1965, Fuzzy Set Theory (FST) has been continuously developed in the past five decades and has established itself one of the preeminent approximate reasoning methodologies. In the literature, there exists multitudes of differing approaches for specifying FST's foundational building blocks (such as the various versions of fuzzy set and arithmetic operators) that it has become challenging for an FST user (e.g. an otherwise proficient engineer who is not an expert in fuzzy set theory) to select or tailor-make fuzzy operators truly appropriate for solving his/her problems. In a recent work (Ngan, 2017a), within the type-1 fuzzy setting, a framework termed probabilistic linguistic computing (PLC) has been proposed to empower such type of FST users to understand and dissect fuzzy operators available in the literature, and to tailor-make their own fuzzy operators to solve their own application problems. In this article, we will revisit this work and extend it to the general type-2 fuzzy setting, as well as to other type-2-like fuzzy settings. Among the contributions are: (i) we demonstrate that the generalized PLC framework can indeed provide a concrete, accessible pathway for the FST users to understand and tailor-make their own set operators in the type-2 and type-2-like fuzzy settings – this is distinct from many other theoretical studies within the type-2 fuzzy set (T2FS) literature which primarily focus on deep technical developments while offering virtually no accessible guidelines for the FST users to use T2FS in their applications; (ii) the set operators constructed from the proposed approach are computationally simple and efficient; and (iii) the proposed approach offers a straightforward way to understand the logical relations between set operators for the general type-2 fuzzy sets and those for type-2-like fuzzy sets. [ABSTRACT FROM AUTHOR]

Large graphs are scale-free, ubiquitous having irregular relationships and non-trivial topology. Frequent subgraph mining is a popular method for knowledge extraction from graphs. Most of the existing frequent subgraph mining algorithms are centralized algorithms that cannot handle a single large graph efficiently and incur high communication cost. However, to make the task of subgraph mining less expensive computationally, approximate subgraph mining can be applied which will capture similar structure subgraphs as of exact subgraph mining. In this paper, we propose an approximate subgraph mining algorithm named Ap-FSM implemented on distributed graph environment Pregel. The working of Ap-FSM is divided into three phases. The first phase selects the representative graph from the original graph while preserving the original graph properties. The second phase efficiently performs subgraph extension. Phase 3 introduces a novel two-step optimization for performing subgraph pruning. Analyzing such large graph data will be beneficial from the perspective of expert and intelligent systems, as discovered patterns can be used for knowledge discovery and decision making. To evaluate the performance of Ap-FSM, experiments are performed over three real life datasets having up to billion edges. The results show that the proposed Ap-FSM significantly outperforms the state-of-art frequent subgraph mining algorithms and overcome the challenges of performing frequent subgraph mining on a massive large graph. It is also shown that Ap-FSM achieves high scalability and speedup in distributed graph environment and is highly accurate in finding frequent subgraphs from a single large graph. [ABSTRACT FROM AUTHOR]

Feature selection is an effective pre-processing step to remove possible redundant and irrelevant features for various machine learning paradigms, which can help build a more understandable machine learning based component in hybrid expert systems. Single-label quadratic programming feature selection (QPFS) model is formulated as a QP problem with a unit simplex constraint to both minimize feature-feature redundancy and maximize feature-label relevance simultaneously. Since its redundancy matrix is desired not to be positive semi-definite and then estimated by Nystrom low-rank approximation method, its performance depends greatly on under-sampling rate and random permutation. In this paper, without any approximation, we extend this model to construct a regularized version (rQPFS), resulting in a strictly convex QP problem, to achieve a globally optimal subset of features. To reduce the increment of computational time for entire redundancy matrix, Frank–Wolfe method with a sub-linear convergence rate and its special cases for strictly convex function and unit simplex constraint are applied to solve our rQPFS efficiently. Furthermore, to tackle multi-label FS paradigm, pruned problem transformation trick is used to evaluate feature-label relevance to describe label correlations sufficiently. The detailed experimental study on eight data sets shows that our proposed method performs the best, compared with six state-of-the-art multi-label FS methods, according to six instance-based performance evaluation measures. [ABSTRACT FROM AUTHOR]

Learning from imbalanced datasets is a frequent but challenging task for standard classification algorithms. Although there are different strategies to address this problem, methods that generate artificial data for the minority class constitute a more general approach compared to algorithmic modifications. Standard oversampling methods are variations of the SMOTE algorithm, which generates synthetic samples along the line segment that joins minority class samples. Therefore, these approaches are based on local information, rather on the overall minority class distribution. Contrary to these algorithms, in this paper the conditional version of Generative Adversarial Networks (cGAN) is used to approximate the true data distribution and generate data for the minority class of various imbalanced datasets. The performance of cGAN is compared against multiple standard oversampling algorithms. We present empirical results that show a significant improvement in the quality of the generated data when cGAN is used as an oversampling algorithm. [ABSTRACT FROM AUTHOR]

Low-rank approximation algorithms aim to utilize convex nuclear norm constraint of linear matrices to recover ill-conditioned entries caused by multi-sampling rates, sensor drop-out. However, these existing algorithms are often limited in solving high-dimensionality and rank minimization relaxation. In this paper, a robust kernel factorization embedding graph regularization method is developed to statically impute missing measurements. Specifically, the implicit high-dimensional feature space of ill-conditioned data is factorized by kernel sparse dictionary. Then, a robust sparse-norm and graph regularization constraints are performed in the objective function to ensure the consistency of the spatial information. For the optimization of the parameters involved in the model, a distributed adaptive proximal Newton gradient descent learning strategy is proposed to accelerate the convergence. Furthermore, considering the dynamic time-series and potentially non-stationary structure of industrial data, we propose extended incremental versions to alleviate the complexity of the overall model computation. Extensive data recovery experiments are conducted on two real industrial processes to evaluate the proposed method in comparison with existing state-of-the-art restorers. The results show that the proposed methods can impute better with different missing rates and have strong competitiveness in practical application. • Static and incremental data recovery methods are proposed. • Kernel factorization, sparse norm and graph regularization are integrated. • Distributed updating strategy of parameters is proposed. • The maximum missing rate of the proposed methods is given. • Real industrial processes show that our algorithms have higher recoverability. [ABSTRACT FROM AUTHOR]

Within visual range air combat involves execution of highly complex and dynamic activities, requiring rapid, sequential decision-making to achieve success. Fighter pilots spend years perfecting tactics and maneuvers for these types of combat engagements, yet the ongoing emergence of unmanned, autonomous vehicle technologies elicits a natural question — can an autonomous unmanned combat aerial vehicle (AUCAV) be imbued with the necessary artificial intelligence to perform challenging air combat maneuvering tasks independently? We formulate and solve the air combat maneuvering problem (ACMP) to examine this important question, developing a Markov decision process (MDP) model to control a defending AUCAV seeking to destroy an attacking adversarial vehicle. The MDP model includes a 5-degree-of-freedom, point-mass aircraft state transition model to accurately represent both kinematics and energy while maneuvering. An approximate dynamic programming (ADP) approach is proposed wherein we develop and test an approximate policy iteration algorithm that implements value function approximation via neural network regression to attain high-quality maneuver policies for the AUCAV. A representative intercept scenario is specified for testing purposes wherein the AUCAV must engage and destroy an adversary aircraft attempting to penetrate the defended airspace. Several designed experiments are conducted to determine how aircraft velocity and adversary maneuvering tactics impact the efficacy of the proposed ADP solution approach and to enable efficient algorithm parameter tuning. ADP-generated policies are compared to two benchmark maneuver policies constructed from two reward shaping functions found in the ACMP literature, attaining improved mean probabilities of kill for 24 of 36 air combat situations considered. • Within visual range air combat requires execution of complex & dynamic maneuvers. • An air combat maneuvering problem is formulated & solved via reinforcement learning. • Preliminary results indicate high-quality maneuver polices are attainable. • Our modeling & solution procedures improve behavior of computer generated forces. • Intelligent behavior within air combat simulations increases quality of insights. [ABSTRACT FROM AUTHOR]

This paper considers a three-stage flexible flow shop scheduling problem, where the jobs have the group constraint at the second stage and the three stages consist of unrelated parallel machines. Because of the complexity of this problem, approximation algorithms are more appropriate to solve it. Firstly, we propose ten heuristic algorithms based on the idea of combined algorithms proposed by Soewandi and Elmaghraby (2001) and give their time complexities. Secondly, since there is no reference on the worst-case performance ratios of RDM, SP.H1 and SP.H2 algorithms for the unrelated parallel machines, we provide the worst-case performance ratios of these three algorithms and then give the worst-case performance ratios of the nine algorithms proposed in this paper. Finally, to evaluate the performance of the ten algorithms, four lower bounds of this problem are proposed in Appendix A and a computational experiment is designed, where lots of instances are generated and each algorithm is run with every instance. Experimental results indicate that the performances of ten heuristic algorithms are contingent on different configurations and SP.JH-MJ algorithm generally outperforms the others with respect to the three-stage flexible flow shop scheduling problem addressed in this paper. [ABSTRACT FROM AUTHOR]

Abstract: The main disadvantage of self-organizing polynomial neural networks (SOPNN) automatically structured and trained by the group method of data handling (GMDH) algorithm is a partial optimization of model weights as the GMDH algorithm optimizes only the weights of the topmost (output) node. In order to estimate to what extent the approximation accuracy of the obtained model can be improved the particle swarm optimization (PSO) has been used for the optimization of weights of all node-polynomials. Since the PSO is generally computationally expensive and time consuming a more efficient Levenberg–Marquardt (LM) algorithm is adapted for the optimization of the SOPNN. After it has been optimized by the LM algorithm the SOPNN outperformed the corresponding models based on artificial neural networks (ANN) and support vector method (SVM). The research is based on the meta-modeling of the thermodynamic effects in fluid flow measurements with time-constraints. The outstanding characteristics of the optimized SOPNN models are also demonstrated in learning the recurrence relations of multiple superimposed oscillations (MSO). [Copyright &y& Elsevier]

Abstract: In manufacturing systems, many maintenance tasks require equipment to be stopped in order to safely perform them. However, such stoppage cannot last for too long since it might directly result in short-term production losses. In this paper, we investigate how long we can strategically shut down equipment for maintenance during scheduled operations without affecting system throughput. Using the concept of maintenance opportunity windows (MOWs), we estimate such time intervals for various system configurations. Simulations are used to deal with uncertainties in production lines, such as random machine failures, starvations, blockages, etc. Moreover, the proposed MOW algorithms are demonstrated through simulations and real case studies in an automotive assembly plant. [Copyright &y& Elsevier]

The paper proposes a novel supervised algorithm for data classification based on fuzzy vector quantization. The novelty here lies in including an optimization procedure to determine the step size of the quantization process. Adoption of fuzzy space for data exploration eliminates the problem of class-overlapping, while dealing with high dimensional non-linear data. In the proposed approach, the input data are first been transformed from the Euclidean space to the fuzzy space with three membership grades. Next, we have used uniform manifold approximation algorithm ( UMAP ), for projecting the data in visual space by selection of the most contrasting features from the fuzzy vectors. Then these features are passed through a quantization step with a novel step-optimization technique. Optimizing the quantization step and making it independent of data sets significantly speeds up the process. As the class information of all the feature vectors obtained by UMAP is known, majority voting principle has been used to locate the class-centroids in the subsequent step which in turn represent the class labels of the test samples. In test phase, after obtaining the test vectors, the Hyperspherical Direction Cosines (HDC) between the test vectors and the previously obtained class-centroids are evaluated. The test sample is finally assigned that class label where the sum of absolute differences (SAD) of these direction cosines is minimum. We have validated our classifier on various benchmark data sets and achieved higher accuracy with significantly low computation time than the existing state-of-the-art algorithms. • A novel pattern classifier algorithm using Fuzzy Vector Quantization is proposed. • Fuzzy-space representation of data eliminates the problem of class-overlapping. • Introducing optimization to determine the step size of the quantization process. • Validation of the classifier algorithm on various high dimensional benchmark datasets. • Achieved higher accuracy with significantly low computation cost. [ABSTRACT FROM AUTHOR]

Abstract: Methods of fuzzy rule extraction based on rough set theory are rarely reported in incomplete interval-valued fuzzy information systems. This paper deals with such systems. Instead of obtaining rules by attribute reduction, which may have a negative effect on inducting good rules, the objective of this paper is to extract rules without computing attribute reducts. The data completeness of missing attribute values is first presented. Two different approximation methods are then defined. Two algorithms based on the two approximation methods, called MRBFA and MRBBA are proposed for rule extraction. The two algorithms are evaluated by a housing database from UCI. The experimental results show that MRBFA and MRBBA achieve better classification performances than the method based on attribute reduction. [Copyright &y& Elsevier]

• We are the first to address the NP-hard Budgeted Maximum Coverage Problem. • We propose an algorithm that combines reinforcement learning with local search. • We introduce the first set of benchmark instances for the problem. • The proposed algorithm outperforms the comparison algorithms and the CPLEX solver. The Budgeted Maximum Coverage Problem (BMCP) is a general model with a number of real-world applications. Given n elements with nonnegative profits, m subsets of elements with nonnegative weights and a total budget, the BMCP aims to select some subsets such that the total weight of the selected subsets does not exceed the budget, while the total profit of the associated elements is maximized. BMCP is NP-hard and thus computationally challenging. We investigate for the first time an effective practical algorithm for solving this problem, which combines reinforcement learning and local search. The algorithm iterates through two distinct phases, namely a tabu search phase and a probability learning based perturbation phase. To assess the effectiveness of the proposed algorithm, we show computational results on a set of 30 benchmark instances introduced in this paper and present comparative studies with respect to the approximation algorithm, the genetic algorithm and the CPLEX solver. [ABSTRACT FROM AUTHOR]

• We propose a unified community-based seed triggering model. • Two new variants of influence maximization and prevention problems are defined. • Efficient algorithms with provable approximation guarantees are designed. • Extensive experiments demonstrate the effectiveness of our methods. Given a social network, the classical influence maximization (IM) and misinformation prevention (MP) problems both adopt similar seed triggering models, i.e., convincing k specific users to become seed nodes by material incentive (e.g. free products). However, in real life, those chosen seeds may not be willing to spread information as expected, which will affect the final diffusion. Instead of convincing one single user, we can target a user community, in the hope that some of them may turn into propagation seeds voluntarily. This community-based seed (Com-seed) triggering model can be used in real-world applications such as distributing flyers or offering discounts in local communities, where the objective is to maximize the promotion effect with the given budget constraints. In this paper, we aim to maximize the influence or minimize the misinformation spread by finding an optimal community-based budget allocation under the Com-seed triggering models. We present new formulations of the influence maximization and misinformation prevention problems from the community perspective and design effective and scalable algorithms to solve these new problems. With intricately designed community-based sampling schemes and approximation guarantee of the greedy approach over integer lattice, our algorithms can achieve (1 - 1 / e - ∊) -approximation results. Experiments show our methods outperform all baselines and run faster than the state-of-the-art methods in both influence maximization and misinformation prevention problems, which demonstrate the effectiveness and scalability of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Given a social network where the users are associated with non-uniform selection cost, the problem of Budgeted Influence Maximization (BIM in short) asks for selecting a subset of the nodes within an allocated budget for initial activation, such that due to the cascading effect, influence in the network is maximized. In this paper, we study this problem with a variation, where a subset of the users are marked as target users, each of them is assigned with a benefit and this can be earned by influencing them. The goal here is to maximize the earned benefit by initially activating a set of nodes within the budget. This problem is referred to as the Earned Benefit Maximization Problem. First, we show that this problem is NP-Hard and the benefit function follows the monotonicity , sub-modularity property under the Independent Cascade Model of diffusion. We propose an incremental greedy strategy for this problem and show, with minor modification it gives (1 − 1 e ) -factor approximation guarantee on the earned benefit. Next, by exploiting the sub-modularity property of the benefit function, we improve the efficiency of the proposed greedy algorithm. Then, we propose a hop-based heuristic method, which works based on the computation of the 'expected earned benefit'. Finally, we perform a series of extensive experiments with four publicly available, real-life social network datasets. From the experiments, we observe that the seed sets selected by the proposed algorithms can achieve more benefit compared to many existing methods. Particularly, the hop-based approach is found to be more efficient than the other ones for solving this problem. • Earned Benefit Maximization Problem has been studied. • An approximation algorithm has been Proposed for this problem. • The algorithm has been improved by exploiting the submodularity property of the benefit function. • For larger datasets, an efficient heuristic solution has been proposed. • Extensive set of experiments have been conducted. [ABSTRACT FROM AUTHOR]