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.

Fair resource allocation has found widespread application across various fields, such as economics and computer science, and has garnered significant attention. In this paper, we address the problem of allocating a set of indivisible chores among a group of agents. Our objective is to achieve an allocation that satisfies the fairness criterion of weighted equitable up to one item and the efficiency criterion of fractional Pareto-Optimal. Inspired by Fisher Market equilibrium [9] , we construct a WEQ1 allocation among Market equilibrium through item transferring and price raising. Our algorithm provides a WEQ1+fPO allocation for additive valuations in pseudo-polynomial time. Moreover, we consider a special k -ary instance, i.e., each agent has at most k different disutility values for chores when k is a constant. We show that a WEQ1+fPO allocation can be computed in polynomial time in such case.

In modern wireless communication systems, a profound grasp of the channel impulse response (CIR) is pivotal for optimizing the design and functionality of algorithms and systems, especially for multiple-input-multiple-output (MIMO) technology. Conventional methods for gauging and modeling the channels rely on evaluating spatial points sampled discretely, resulting in limitations in acquiring pertinent channel information across a broad region. To overcome these limitations, this study embeds the physical principles of electromagnetic wave propagation into data-driven deep learning models, achieving second-level regional CIR computing efficiency that is hundreds of times faster. The proposed physics-informed deep ray tracing network (PIDRTN) integrates multiple U-shaped network (U-Net) encoder-decoder blocks, capturing radio wave propagation characteristics within a specific region surrounded by buildings, including two equivalent signal propagation directions in a two-dimensional space and a signal intensity correction term. Then, the network employs a parameter-free nonlinear signal transmission module to emulate the physical principles of signal propagation and obtain accurate CIRs from limited anchor locations, which will iteratively generate CIRs for various times within a specified region subjected to enhancement and denoising operations. Furthermore, the PIDRTN-A model, which utilizes anchor data to improve model accuracy, is proposed. A dataset encompassing diverse fading scenarios is constructed using the ray tracing (RT) method. Extensive experiments demonstrate that the proposed models effectively capture directional and reflective properties of signals; using the RT model as a benchmark, normalized root mean squared errors (NRMSEs) of 0.1226 and 0.0969 are obtained for the PIDRTN and PIDRTN-A models, respectively.

Social-media platforms provide citizens a new way to stay informed and offer marketers a shot at promoting their brand. In social advertising, information diversity can create a level playing field for competitive information dissemination. Team diversity is important because teams with a diverse composition tend to perform better over time. The former demands that all the social networks’ users should receive diverse information. The later requires teams to be diverse with respect to team members’ attributes. However, to our knowledge, not only the diversity of the information spreading in the social network but also the influential users’ attributes are never simultaneously considered in research. Therefore, we propose a novel information- and team-based dual-diversity maximization (ITDM) problem in this article. The dual-diversity focused by the ITDM problem can be cast as a combination of information diversity and team diversity. The goal of ITDM problem is to obtain a good strategy for building marketing teams composed of influential social networks’ users. To some extent, this problem is an extension of classical IM problem that aims at selecting some influential users to trigger large information spread in social networks. The main difference between them is that team composition is taken into consideration by ITDM problem. Given that the ITDM problem is challenging, an algorithm on the foundation of Shapley value and negative-cycle-detection is designed to address it. We experimentally demonstrate the effectiveness of our algorithm on several real-world datasets.

To provide a new perspective for understanding the dynamics of advertising campaigns in online influencer marketing (OIM), this article proposes the modified agent-based (MAB) model. As an extension of the existing agent-based model, it takes into account some important factors such as influencer avoidance and product competition and modifies some existing parameters to provide a more realistic approach for simulating marketing campaigns. Based on it, we define a novel set function named as dual-profit function. It is proven to be nonsubmodular and nonsupermodular. The dual-profit maximization (DPM) problem which regards dual-profit function as its objective function and the DPM algorithm used to address DPM problem is proposed. The influence of several parameters is evaluated through experiments conducted on real-world datasets.

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.

With the application and development of the fifth-generation (5G) communications, it is essential to gain insight understanding of the multi-antenna wireless channel characterizations. In particular, their relevant Channel Impulse Response (CIR) so to ensure the effective design of algorithms and systems. However, both the traditional channel measurement and modelling are essentially based on assessment at discretely sampled spatial points without the capability to obtain the relevant channel information over a given surrounding area. To overcome this limitation, this paper proposes to re-assemble the discretely sampled CIRs into equalized video streams. With this basis, a deep learning based video super-resolution method, namely, the Time Decomposition Video Super-Resolution (TDVSR), has been proposed to restore the area channel information for the first time. Moreover, a time decomposition module based on Bidirectional Long Short-Term Memory (BiLSTM) has been designed to decompose the re-assembled CIRs into video form in the time dimension. A retrained video super-resolution model will then process the composited data and output high-resolution frames, which will be reversed to the CIRs at the dense density target area. A data set with various typical fading scenarios has been constructed by Ray Tracing (RT) method. Extensive experiments demonstrate that the proposed TDVSR model successfully learned the nonlinear propagation laws through the data-driven method, which shows satisfied restoration accuracy with significantly increased computation 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.

Restriction site-associated DNA sequencing (RADseq) is a powerful technology that has been extensively applied in population genetics, phylogenetics and genetic mapping. Although many software packages are available for ecological and evolutionary studies, a few effective tools are available for extracting genotype data with RADseq for genetic mapping, a prerequisite for quantitative trait locus mapping, comparative genomics and genome scaffold assembly. Here, we present an integrated pipeline called gmRAD for generating single nucleotide polymorphism (SNP) genotypes from RADseq data, de novo, across a genetic mapping population derived by crossing two parents. As an analytical strategy, the software takes five steps to implement the whole algorithms, including clustering the first (forward) reads of each parent, building two parental references, generating parental SNP catalogs, calling SNP genotypes across all individuals and filtering the genotype data for genetic linkage mapping. All the steps can be completed with a simple command line, but they can be also performed optionally if prerequisite files are available. To validate its application, we also performed a real data analysis with RADseq data from an F1 hybrid population derived by crossing Populus deltoides and Populus simonii. The software gmRAD is freely available at https://github.com/tongchf/gmRAD.

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.

The 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.

In the past decade, tremendous research effort has been devoted to viral marketing. Most existing works on seed selection in social networks do not take into account the scenario when a profit can be generated from group activities. Each activity has a profit that can be measured by the excitement of the participants. The excitement about one piece of information can vary significantly among different groups of people. Given a social network and a profit function, how can we select the seed users to maximize the expected total amount of profit? This problem is essentially different from the classic influence maximization problem, and existing approaches cannot be directly applied to solve the problem. In this paper, we study the problem of activity profit maximization in social networks. We first prove that the maximizing activity profit problem is nondeterministic polynomial time-hard and cannot be approximated within a constant factor by the simple greedy algorithm. Supermodular degree of a function measures the extent to which it violates submodularity. We design an algorithm that achieves an approximation ratio of (1/(Δ+ 2)) provided that the supermodular degree of the social graph is bounded with A. We then develop an exchange-based technique to further improve the quality of the solution. We also devise a randomized variation approach to overcome the computational burden of the proposed algorithms. Extensive experimental results on three real benchmark data sets demonstrate the efficacy and efficiency of our algorithms over several baseline heuristics.

Accurately predicting for network traffic is significant for network operation and maintenance in software-defined networks (SDN). In this paper, Multi-frequency characteristic of complex network traffic is considered, and a new algorithm named EMD-based multi-model Prediction (EMD-MMP) for network prediction is proposed. The main idea in this algorithm is to decompose the network traffic series into different modes with different frequency by Empirical Mode Decomposition (EMD). According to the characteristics and the cross correlation coefficient of the modes, we reconstruct new components for de-noising by summing up parts of the high frequency modes. Then the new components and the remaining old modes are predicted by ARMA and SVR methods. Finally, the historical traffic data of Internet2 is employed for our experiments to demonstrate the precision of our new prediction algorithm compared with the Auto-Regressive and Moving Average (ARMA) and Support Vector Regression (SVR) models. On average, the EMD-MMP method improves ARMA and SVR by 0.62% and 10.6% at the Mean Absolute Percentage Error (MAPE) statistic indicator, and the Mean Square Error (MSE) of EMD-MMP is 12060.92 while the ARMA and SVR are 13968.8 and 47588.3. Besides, the EMD-MMP algorithm gives a better understanding of the nature of the network traffic.

The feature of centralized network control logic in Software-Defined Networks (SDNs) paves a way for green energy saving. Router power consumption attracts a wide spread attention in terms of energy saving. Most research on it is at component level or link level, i.e. each router is independent of energy saving. In this paper, we study global power management at network level by rerouting traffic through different paths to adjust the workload of links when the network is relatively idle. We construct the expand network topology according to routers' connection. A 0-1 integer linear programming model is formulated to minimize the power of integrated chassis and linecards that are used while putting idle ones to sleep under constraints of link utilization and packet delay. We proposed two algorithms to solve this problem: alternative greedy algorithm and global greedy algorithm. For comparison, we also use Cplex method just as GreenTe does since GreenTe is state of the art global traffic engineering mechanism. Simulation results on synthetic topologies and real topology of CERNET show the effectiveness of our algorithms.

Routing in wireless sensor networks (WSNs) is very challenging due to their inherent characteristics of large scale, no global identification, dynamic topology, and very limited power, memory, and computational capacities for each sensor. Recent research on WSNs routing protocol has proved that data-centric technologies are needed for performing in-network aggregation of data to yield energy-efficient dissemination. As an effective distributed approach, ant colony optimization (ACO) algorithms have been introduced to the design of data-centric routing protocol and have got many achievements, but still have some shortcomings blocking their further application in the large scale WSNs. To overcome the flaws of conventional ant-based data-centric routing algorithms, we proposed an improved protocol by adding a new type of ant, search ant, to supply prior information to the following ants. Besides, we introduced the strategy of simulating global pheromone update to accelerate the convergence of our algorithm and defined a "retry" rule to avoid dead-lock of the protocol. All of these modifications made the routing protocol scalable, practicable and energy-conservative. Simulation results showed the great advantages of the new protocol