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.

In recent years, the pursuit of higher expressive power in graph neural networks (GNNs) has often led to more complex aggregation mechanisms and deeper architectures. To address these issues, we have identified redundant structures in GNNs, and by pruning them, we propose Pruned MP-GNNs, K-Path GNNs, and K-Hop GNNs based on their original architectures. We show that 1) Although some structures are pruned in Pruned MP-GNNs and Pruned K-Path GNNs, their expressive power has not been compromised. 2) K-Hop MP-GNNs and their pruned architecture exhibit equivalent expressiveness on regular and strongly regular graphs. 3) The complexity of pruned K-Path GNNs and pruned K-Hop GNNs is lower than that of MP-GNNs, yet their expressive power is higher. Experimental results validate our refinements, demonstrating competitive performance across benchmark datasets with improved efficiency.

Influence maximization (IM) is a classical and heated issue in online social networks. Although some works have studied multifeature IM, they do not consider this problem from the perspective of users’ preferences. In this article, we construct a novel multifeature spreading model that considers users’ different preferences, namely, the MFP-independent cascade (IC) model, which uses the IC model as the basic propagation model. Some features are positive or negative depending on users’ preferences. According to this spreading model, we consider a novel problem that focuses on the influence gap between positive features and negative features, namely, positive evaluation maximization (PEM). This problem is NP-hard and nonsubmodular. Fortunately, PEM can be expressed as DS decomposition because the positive influence and the negative influence are both monotone submodular. Based on DS decomposition, we design some special greedy strategies, namely, the parametric conditioned greedy (PCG). To reduce the computational cost of our method, we design fast PCG (FPCG) algorithm using the sampling technique. In addition, the approximation ratio of the PCG and FPCG approaches is only the gap between their$O(\epsilon)$values. Finally, we evaluate our algorithms by performing massive experiments on real datasets.

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.