In this work, we present Stochastic Graph Neural Diffusion, which approaches deep learning on graphs as a continuous stochastic heat diffusion process. We generalize the Stochastic Heat Equation on the Riemannian manifold to graphs and treat GNNs as a discretization of the Stochastic Heat Conduction Equation on graphs. In our model, the choice of discretization operators for different temporal and spatial operators corresponds to different layer structures and topologies. Our model is generalized to the GRAND model, where the presence of noise through heat conduction significantly increases robustness and alleviates the over-smoothing of GNNs to some extent. We propose several methods for stochastic heat equations on discrete graphs, treating information diffusion on graphs as a heat transfer process. We develop several versions of SGAND and achieve competitive results on many standard graph benchmarks.

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.

Heterogeneous graph neural networks (HGNNs) possess powerful representational capabilities, successfully capturing the rich semantic and structural information inherent in heterogeneous graphs. The core of HGNNs is the aggregation of neighbor features. However, existing HGNNs often lack comprehensiveness in their selection of neighbors. They either overlook the intermediate nodes within metapaths as well as the direct neighbors in the original graph, or they neglect the semantic neighbors connected by metapaths. Furthermore, the potential relationship between semantics and structure is rarely considered. To address the limitations, we propose a novel framework named Parallel Neighbor Aggregation for Heterogeneous Graph Neural Network (PNAHN). PNAHN utilizes a full range of neighbor features by dividing neighbor aggregation into three levels: homogeneous subgraph level, heterogeneous subgraph level, and original graph level. Targeted aggregation is then employed in parallel to derive semantic embedding from subgraphs and structural embedding from the original graph. Finally, to comprehend interactions between each pair of semantics and structure, a transformer-based fusion is applied to derive the final node representations. Empirical experiments on three real-world heterogeneous graph datasets demonstrate that PNAHN outperforms the existing state-of-the-art methods.

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.

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.

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.

A critical problem in wireless sensor networks is to maximize their lifetimes. Data aggregation is an effective method to reduce redundant data and minimize the overall energy consumption. This method requires data to be delayed and processed in their paths to the sink node, so it causes extra time delay to the networks. This paper studies the aggregation node selection problem in sensor networks with time delay constraint, and the objective is to minimize the overall energy consumption of networks. A dynamic programming algorithm is proposed to solve the problem. This algorithm can turn out the optimal solution in polynomial time. Extensive simulations have been conducted to evaluate the performance of the proposed algorithm; the results show the efficiency of the algorithm in energy consumption reduction.