The influence maximization problem seeks to identify a set of influential users in a social network to maximize the spread of information. While prior research has focused extensively on improving computational efficiency, it has largely overlooked fairness in information dissemination across different social groups. A widely adopted fairness criterion is the maximin objective, which aims to maximize the minimum influence received by any group. However, under this objective, the fairness-aware influence maximization problem is NP-hard even to approximate well. In this work, we consider randomized seed selection strategies for fairness-aware influence maximization to address this challenge. We introduce a noise-based smoothing technique to tackle the non-smoothness of the objective function and develop an approximate solution based on the stochastic Frank–Wolfe algorithm. For efficient and theoretically grounded gradient estimation, we leverage the reverse influence sampling method, which enables provable gradient approximation. To obtain a discrete solution, we apply swap rounding to the fractional output, resulting in a randomized seed set that achieves a \((1-1/e,2\epsilon)\) -approximation for monotone functions and a \((1/e,2\epsilon)\) -approximation for non-monotone functions, with probability at least \(1-\delta\) , where \(\epsilon\) and \(\delta\) are user-defined accuracy parameters. Although accurate gradient estimation typically requires a large number of samples and may incur a high computational cost, we further derive upper and lower bounds on the gradient estimates and demonstrate that under certain conditions, using fewer samples still preserves the theoretical approximation guarantee. We validate our approach on six real-world social network datasets, and the results demonstrate that our algorithm effectively balances fairness and influence spread while maintaining strong performance.

Due to important applications in viral marketing, influence maximization (IM) has become a well-studied problem. It aims at finding a small subset of initial users so that they can deliver information to the largest amount of users through the word-of-mouth effect. The original IM only considers a singleton item. And the majority of extensions ignore the relationships among different items or only consider their competitive interactions. In reality, the diffusion probability of one item will increase when users adopted supplementary products in advance. Motivated by this scenario, we propose a supplementary independent cascade (IC) and discuss the supplementary IM problem. Our problem is NP-hard, and the computation of the objective function is #P-hard. We notice that the diffusion probability will change when considering the impact of its supplementary product. Therefore, the efficient reverse influence sampling (RIS) techniques cannot be applied to our problem directly even though the objective function is submodular. To address this issue, we utilize the sandwich approximation (SA) strategy to obtain a data-dependent approximate solution. Furthermore, we define the supplementary-based reverse reachable (SRR) sets and then propose a heuristic algorithm. Finally, the experimental results on three real datasets support the efficiency and superiority of our methods.

Influence maximization (IM) is a representative and classic problem that has been studied extensively before. The most important application derived from the IM problem is viral marketing. Take us as a promoter, we want to get benefits from the influence diffusion in a given social network, where each influenced (activated) user is associated with a benefit. However, there is often competing information initiated by our rivals diffusing in the same social network at the same time. Consider such a scenario, a user is influenced by both my information and my rivals' information. Here, the benefit from this user should be weakened to certain degree. How to quantify the degree of weakening? Based on that, we propose an overall evaluations on benefits of influence (OEBI) problem. We prove the objective function of the OEBI problem is not monotone, not submodular, and not supermodular. Fortunately, we can decompose this objective function into the difference of two submodular functions and adopt a modular-modular procedure to approximate it with a data-dependent approximation guarantee. Because of the difficulty to compute the exact objective value, we design a group of unbiased estimators by exploiting the idea of reverse influence sampling, which can improve time efficiency significantly without losing its approximation ratio. Finally, numerical experiments on real datasets verified the effectiveness of our approaches regardless of performance and efficiency.

In the last few decades, profit maximization (PM), which is mainly considered for maximizing net profits, i.e., the difference between gain and cost, has been a prominent issue for online social networks (OSNs). However, the output-to-input ratio, which is an important metric in economics, is also worth studying for OSNs. In this article, we present a novel problem that considers the PM problem from the ratio of gain and cost, known as output-to-input ratio maximization (OIRM). Unfortunately, it is neither submodular nor supermodular. The hill-climbing greedy algorithm for solving this problem is a$1-e^{-(1-c_{g})}$approximation algorithm, where$c_{g}$is the curvature of the monotone submodular set function$g$. To speed up the hill-climbing greedy algorithm, we propose the threshold decrease algorithm and prove that its approximation ratio is$1-e^{-(1-c_{g})^{2}}-\epsilon $. In addition, based on the relationship between classical net PM and OIRM, the algorithms for solving PM can also solve OIRM. Finally, we evaluate the performance of our algorithms using massive experiments on real datasets. To the best of our knowledge, this is the first time to study the OIRM in viral marketing.

Nowadays, different innovations spread rapidly in online social networks. An activation state can indicate whether each user adopts the target information. The effector detection problem aims to find a way to generate an activation state as close to an observed one as possible. In this article, based on the influence spread, the unconstrained and constrained effector detection problems are proposed. To tackle them, we design two approximation algorithms since the problem is NP-hard, and the objective function is nonsubmodular. For the unconstrained case, our objective function can be best provided with the difference of two submodular functions. Thus, we address this problem through the modular-modular algorithm. For the constrained case, we devise the solutions for the original function, submodular upper bound, and lower bound according to an idea of reverse influence sampling. Then, there is a data-dependent approximate solution using the sandwich approximation algorithm. Finally, we show the correctness and superiority of our methods through massive experiments in three real-world networks.